Welcher Algorithmus für eine Snake-KI?

[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.