Welcher Algorithmus für eine Snake-KI?

[Sidorion]

Nein Du versuchst erst den ersten. Wenn der klappt, dann kann die Schlange zum Apfel und verfolgt dieses Ziel. Wenn nicht kann die Schlange auch nicht zum Apfel und verfolgt die Überlebensstrategie. Hierzu muss ich aber nochmal nachdenken, weil das klappt so nicht, da die Werte ja immer wieder überschrieben werden.

[Sidorion]

Hab gestern nochmal drüber nachgedacht. Du musst die Stelle finden, an der der Ring aufbrechen wird (weil der nachgezogene Schwanz irgendwann so weit vorrückt, dass eine Lücke entsteht). An dieser Stelle muss die Schlange dann rauskriechen. Wenn Du den Punkt hast, machst Du einen A* zu diesem Punkt und gehst dann aber mit dem Kopf in die Richtung weiter, die den größten Wert (also den längeren Weg) hat.

[Whookie]

Also - auch ganz spontan - hätte ich gesagt, wenn Du das Ziel nicht erreichen kannst, dann könntest du A* nochmal Aufrufen aber die gegnerische Schlange bis auf Ihr letztes Element komplett entfernen und das Schlangenende als Ziel verwenden (Nahrung auch weg). Kann dieser Schritt ausgeführt werden (extra überprüfung nötig, weil ja die grüne Schlange weg ist!!), dann bist du fertig (dadurch bewegt sie die blaue Schlange auf das Ende der grünen zu - Achtung die grüne Schlange könnte ja noch um einiges länger sein und links auch noch einige Felder "nach oben" gehen).
Ist ein Schritt aufs Schlangenende hin nicht mehr möglich, würde ich A* mit dem eigenen Schlangenende als Ziel aufrufen .. dann sollte die Schlange in einen "loop-modus" gehen bis wieder Nahrung erreicht werden kann.

[Matze]

Hi, danke für die Antworten.

Zitat von Sidorion:

Hab gestern nochmal drüber nachgedacht. Du musst die Stelle finden, an der der Ring aufbrechen wird [...] An dieser Stelle muss die Schlange dann rauskriechen.

Völlig richtig, das wäre die schönste Methode. Nur ist das Problem, wie ich die Stelle ermitteln kann, an der der Ring aufbrechen wird. Ich müsste irgendwie ermitteln, an welcher Stelle sich der Ring schließt und die Wertigkeit des berührenden Schlangenstücks müsste die Anzahl an Schritten sein, bis es wieder einen Weg gibt.
Nur darf sich die Schlange nicht selbst das Öffnen des Rings durch ungeschicktes Kriechen verhindern. Hinzu kommt, dass der Schlangenkopf beim Aufbrechen in unmittelbarer Nähe sein sollte, um keine Zeit zu verlieren.

Zitat von Whookie:

[...] dann sollte die Schlange in einen "loop-modus" gehen bis wieder Nahrung erreicht werden kann.

So eine "Standby"-Lösung habe ich gestern Abend noch schnell implementiert, doch das gefällt mir eigentlich nicht und hat mit Intelligenz auch nicht mehr viel gemeinsam. Falls sich Sidorions Vorschlag nicht ohne weiteres umsetzen lässt, werde ich es allerdings so machen müssen.

[Sidorion]

Nein Du ermittelst einfach für jedes Feld am Rand, wie lange es dauern wird, bis es nichtmehr besetzt ist. Also für feste Wände unendlich(-1), für Schlangenteile Abstand zum hinteren Ende (der jeweiligen Schlange). Das Feld mit dem niedrigsten positiven Wert ist die (zukünftige) Lücke. Jetzt füllst Du die A* Map, als wäre das Futter an diesem Feld. Wenn Du damit fertig bist, lässt Du die Schlange den teuersten Nachbern vom Kopf ansteuern. Damit hält sie sich möglichst weit vom Loch entfernt, um es sich a) nicht zuzubauen und b) nach Möglichkeit lange genug zu überleben, da sie dadurch den Platz im Ring optimal ausnutzt (zumindest in der Theorie )
Irgendwann ist dann das Spiel so weit fortgeschritten, dass der Apfel plötzlich wieder erreichbar wird (obwohl der Ring noch geschlossen ist, aber dazu siehe oben). Dann verfolgt die Schlange wieder die Fressstrategie und bewegt sich auf das Loch zu, obwohl es im Moment noch geschlossen ist. (Danit sollte der Kopf dann beim Aufbrechen in unmittelbarer Nähe sein)

[Matze]

Hi

Das klingt ja ganz schön komplex alles.
Ich müsste davor aber ermitteln, welche Schlangenteile überhaupt im Weg sind. Für mich langsam ein unlösbares Problem, diese KI.

[Sidorion]

Nö. Du kannst ja beim A* initialisieren, da wo Du die Schlangen einzeichnest für jedes Teil den Abstand zum Ende eintragen (negativ mit offset, da ja 'Wand'=-1 und Entfernungen positiv). Damit ist der größte Wert <-1 die potentielle Lücke. Ausserdem erleichterst Du Dir dadurch das 'Entfernen' des letzten Schlangenstücks bei jedem A* Durchlauf, indem Du einfach alle Zahlen <-2 um eins erhöhst und -2:=0 setzt.

[Matze]

Das A*-Array besitzt doch bereits den Abstand zum Ende, da der Schlangenkopf die Länge der Schlange enthält und zum Ende hin immer um eines abnimmt. Das dann negativ und 1 abgezogen müsste das sein, was du meinst. Aber wieso sollte sich dadurch die potentielle Lücke ergeben?
Der größte Wert < -1 wäre dann eben immer kurz vorm Schwanzende. Irgendwas scheine ich noch nicht zu verstehen.

[Gremlin]

Hi,

nur mal als Idee.

Was spricht gegen ein 2. Array in das nur die anderen Schlangen als
Felder eingetragen werden. Dieses enthält vom Kopf ausgehend die
voraussichtlichen Züge die notwendig sind, bis die Schlange an der
Stelle S vorbeigehuscht ist.

Delphi-Quellcode:

-
    5 4 3 2 1 S 1 2 3 4 5
    X 4 3 2 1 S 1 2 3 4
        3 2 1 S 1 2 3
          2 1 S 1 2
            1 S 1

Befindest du dich beispielsweise an Position X, dann weisst du das
mindestens 4 Züge notwendig sind, die Stelle der Schlange zu passieren,
angenommen die möchtest dich von links nach rechts bewegen und die
Schlange S bewegt sich von unten nach oben. Somit könntest du auch
entscheiden, ob es überhaupt möglich ist den Weg ohne Kollision zu
kreuzen.

[Matze]

Hi,

danke. Ich kann momentan jedoch bereits genau ermitteln, ob es möglich ist ohne Kollision, zum Futter zu kommen (Das erledigt der A*-Algorithmus). Dein Vorschlag ist im Endeffekt nur dieser Algorithmus, wenn ich es richtig verstanden habe. Das Array sieht so aus, dass die Schlangen den Wert -1 haben und die restlichen Felder sind mit dem Wert gefüllt, der den Abstand zum Futter angibt.

Das Problem ist jedoch, dass es Situationen gibt, in denen ich diese Angaben nicht ermitteln kann, weil es keinen "freien" Weg zum Futter gibt. Und da muss ich nun irgendwie berechnen, wie sich die Schlange in der Zeit, bis es wieder einen Weg gibt, bewegen muss und das möglichst so, dass sie zum Zeitpunkt, an dem sich ein Weg ergibt, bereits in der Nähe der neuen Lücke ist.