Welcher Algorithmus für eine Snake-KI?

[Gremlin]

Meine erste Antwort war falsch.

Ich meinte das die Schlange in einem Bereich um sich angibt, wieviele Züge
minimal notwendig sind, bis diese passiert werden könnte, also in der Art:

Delphi-Quellcode:

-

   4 4 4 4 S 4..
     3 3 3 S 3..
       2 2 S 2.. 
         1 S 1..

Welche Information stehen für dich im Labyrint bereit, ausser den Wänden (W)
der gegnerische Schlangen (S) und des Apfels (A)?

(a) Theoretisch ist die (S) eine Wand die sich aber bewegen kann. Deshalb könnte
man (S) ignorieren und zuerst den kürzesten Weg zum Apfel ermitteln.

(b) Dir ist bekannt, wo sich (S) befindet.
Jetzt musst du nur noch herausfinden, ob sich eine Position von (S) auf dem
kürzesten Weg befindet.
Wenn ja, dann könntest du die Werte von (S) von den Werten des Wegs abziehen.
Sind dort Werte von 0 oder kleiner vorhanden, so ergibt sich eine Kollision,
die auf dem direkten und kürzesten Weg nicht aufgelöst werden kann.

(c) Diese Kollisionspunkte (K) werden dann bei einer erneuten Berechnung wie
eine echte Wand (W) interpretiert. Dann geht die Berechnung weiter wie unter (a)

Sollte bei dieser Berechnung kein kürzester Weg mehr möglich sein, so geht es
in die Berechnung von Zügen zur Zeitgewinnung um (S) doch noch auszuweichen.


Ich hoffe ich habs so geschrieben das man es verstehen kann.

[Matze]

Hi,

Zitat von Gremlin:

Sollte bei dieser Berechnung kein kürzester Weg mehr möglich sein, so geht es
in die Berechnung von Zügen zur Zeitgewinnung um (S) doch noch auszuweichen.

Eigentlich geht's mir genau darum.

Der kürzeste Weg wird bei mir generell berechnet, wenn nicht gerade eine Schlange den kompletten Weg zum Apfel abschneidet. Ist dies nicht der Fall, kriecht die andere Schlange einfach außen herum (wie bei dir der Punkt a). Und mein aktuelles Problem ist nun genau diese Berechnung für den Fall, dass der Apfel zu dem Zeitpunkt auf keiner Weise erreicht werden kann.
Dein Vorgehen b kann ich nicht ganz nachvollziehen bzw. sehe keinen Sinn dahinter.

[Matze]

Hat mir evtl. noch irgend jemand Tipps?

Die genannten Vorschläge sind ja wirklich nicht schlecht, nur verstehe ich immer noch nicht, wie ich ermitteln kann, wo sich eine Lücke zum Futter ergibt. Es ist auch nicht so sehr wichtig, aber mich würde es interessieren, wie man so etwas genau umsetzen kann.

Grüße