Welcher Algorithmus für eine Snake-KI?

[Sidorion]

Zunächst sollte man noch eine weitere Abbruchbedingung einführen: konnte kein Nachbar mit n+1 besetzt werden, dann muss die Schlefe abbrechen. Einfach bei jedem Schleifendurchgang einen Boolean auf false setzen. Beim Setzen eines Nachbarn wird der dann auf true gesetzt.

Zudem hast Du in dieser Situatin zwei Möglichkeiten: 1. die blaue Schlange verfällt in einen Sicherheitsmodus, in dem sie einfach verhindert, dass sie irgendwo gegenstößt oder 2. Du machst eine zweiten A* Durchlauf, in dem die andere Schlange eins weiter gerückt ist. Falls dann immernoch kein Weg existiert, rückst Du die andere Schlange noch eins weiter (nur gedanklich, die blaue schaut also 'in die Zukunft'). Dies führt aber gaaaanz schnell zu sehr vielen Möglichkeiten, da in jedem Schritt für die grüne drei Möglichkeiten zum Weiterkriechen existieren

[Matze]

Hm das klingt ja reichlich kompliziert, aber ich versuche mich mal. Herzlichen Dank!

[Sidorion]

Ich hab da nochmal drüber nachgedacht.. Du musst den A* 'rückwärts' anwenden.
Du gehst quasi vom Schlangenkopf zum Futter und löschst in jedem Schleifendurchlauf das letzte Glied jeder Schlange aus der A* map. Dadurch wird das Weiterkriechen der Schlangen simuliert und bei der Pfadsuche wird das dann berücksichtigt.
Einziges Problem ist nun, dass Du in Deiner A*-Map den Weg vom Futter zur Schlange hast. Dies lässt sich aber dadurch lösen, indem Du nun den Weg vom Futter zur Schlange 'zurücklegst' und das Feld, von dem aus Du den Schlangenkopf 'betrittst' ist die Richtung, in nie die Schlange weiterkriechen muss.

[Matze]

Hi,

das verstehe ich nun nicht ganz. Ich berechnet pro Schlangenzug das ganze Spielfeld mit A* neu. Daher dürfte es egal sein, in welcher Richtung ich den Algorithmus anwende, denke ich. Der von mir angesprochene Fall ist bisher noch nie aufgetreten, da sich irgendwo noch ein Bug befinden muss, den ich nicht entdecken kann. Aber das soll euch nicht weiter stören. Diesen Spezialfall setze ich daher ganz ans Ende meiner Liste.

[Sidorion]

Folgendes: Je Schritt in der A* berechnung vergeht doch ein Spielzug (wenn schlange vom futter 4 weg ist, braucht sie 4 Züge um hinzukommen). Jetzt kannst Du also in jedem Schritt die Karte dahingehend anpassen, dass Du das jeweils letzte Feld jeder Schlange als begehbar markierst (Die Schlange ist ja ein Feld weitergekrochen). Damit ergibt sich dann plötzlich doch ein Weg bei Deinem Fehlerbild.
Jetzt zum umgekehrten A*: Wenn jetzt die andere Schlange näher am Futter als an der KI-Schlange ist würdest Du wenn Du vom Futter ausgehst einen Umweg machen, der nicht nötig wäre. Im Anderen Fall würde die Schlange zu direkt laufen wollen. Daher musst Du in diesem Fall tatsächlich vom Schlangenkopf aus das Futter suchen. Dadurch bekommst Du aber den kürzesten Weg vom Futter sur Schlange und musst also diesen kürzesten Weg entlangehen um den letzten 'Zwischenschritt' zu finden. Dieser ist dann der erste für die Schlange.
Ich hoffe, das war jetzt bissi verständlicher.

p.s.: das Sperren von Feldern wo sich die Köpfe hinbewegen in jedem Schritt würde ich erstmal vernachlässigen, denn das würde un Längen komplizierter werden, da Du in jedem Schritt die dreifache Anzahl von Möglichkeiten durchgehen müsstest (je Schritt drei neue A* je altem A*). Hier könnte man zwar einige Fälle ausschließen, aber das würde noch kompliziertere Berechnungen mit Wertungen und so bedeuten.

[Matze]

Hi,

ok danke, das klingt ganz gut, doch ist es nun so, dass die Situation, die im Anhang zu finden ist, häufig auftritt. Im umschlossenen leeren Feld sind nun keinerlei Infos zur Entfernung zum Apfel enthalten. Ich weiß auch nicht einmal, wie ich überprüfen kann, ob sich die Schlange in solch einer Situation befindet, außer ich setze ein Limit für die Schleife des A*-Algorithmusses fest und nach Ablauf dieses, muss sich die Schlange in so einem Zustand befinden. Doch das scheint mit keine schöne Lösung zu sein.

Hinzu kommt noch etwas viel komplizierteres, was mir am meisten Schwierigkeiten bereitet:
Die Schlange darf sich aktuell nicht beliebig bewegen, denn sonst kann es schnell sein, dass sie den Apfel nie erreichen wird. Sie müsste nun beispielsweise nach oben und in der Spalte daneben nach unten kriechen, denn dann hat sich der Schwanz von ihr so weit fortbewegt, dass die Schlange zum Apfel kann. Würde die Schlange hingegen zuerst nach rechts und dann nach oben kriechen, ist das Spiel zu Ende.
Ist das in vertretbarem Aufwand irgendwie lösbar?

Grüße

Edit: Anhang vergessen

[Sidorion]

Ich gehe mal davon aus, wir reden vom Fehler jpeg und die KI steuert die blaue schlange.
Dann sieht der A* so aus:
in Schritt 0 (aktuelle Situation) kann die blaue Schlange nicht zum Apfel. Trotzdem fangen wir an.
Wir schreiben also in alle Nachbarn des Schlangenkopfes eine 1. Jetzt bewegt sich die grüne ein Feld vorwärts und damit wird das Feld 0,7 frei (und Blue kann zum Apfel). Dieses tragen wir in die A* map ein und machen den 1. Schritt.
In Schritt 1 schreiben wir in alle Nachbarn der einser eine zwei (in dem Fall nicht nach oben, weil da ja noch Reste von Grüni sind).Jetzt läuft Grüni ja wieder eins vor und damit wird Feld 1,7 frei und damit der Weg zum Apfel kürzer (aber das interessiert uns erstmal nicht)! auch dieses neue Freifeld wird in der A* map eingetragen. Und weiter mit Schritt 2. usw bis der Apfel erreicht ist.
Jetzt hast Du in Deiner A* map die Wegkosten vom Apfel zu Blue stehen und weisst erstmal immernoch nicht wohin sie soll, aber das kommt jetzt. Du hangelst Dich vom Apfel zu Blue immer über den niederwertigsten Nachbarn. bei zwei gleichen isses egal, wohin Du gehst, weil beide Wege gleich lang sind. Irgendwann stößt Du dann auf den Schlangenkopf von Blue und das Feld, von dem aus Du den Kopf betreten hast ist die Richtung, in die Blue kriechen muss.

[Matze]

Hi

Ich hatte den Anhang vergessen und ihn oben hinzugefügt.

Dennoch danke für deine Erklärung, doch damit lässt sich das aktuelle Problem wohl nicht lösen.

[Sidorion]

Na SnakeBloed schon, denn da wird ja irgendwann ein Weg frei (wenn Dus so machst wie ich gesagt habe mit dem entfernen des letzen Gliedes vom Kopf aus).
SnakeDumm löst man, indem man A* vom Kopf aus anfängt und den Nachbarn überschreibt, wenn der neue Wert größer dem alten ist. Ist man fertig mit A* (keine Änderung mehr) geht man wieder Richtung kleinster Nachbar vom Kopf aus. Dadurch schlängelt sich die Schlange von links nach rechts und hofft, irgendwann aus dem Gefängnis zu kommen.

[Matze]

Hi,

also irgendwie ist mir das zu hoch. Ich kann doch keine Fallunterscheidung durchführen. Der Algorithmus muss für beide (bzw. für alle) Beispiele funktionieren.