Welcher Algorithmus für eine Snake-KI?

[Matze]

Hi zusammen,

ich bin dabei in C++ einen Snake-Clon zu programmieren - bzw. dieser ist fertig - nur habe ich nun eine 2. Schlange, die computergesteuert ist, hinzugefügt. Da ich mich in C++ noch nicht sonderlich gut auskenne, prüfe ich zur Zeit, in welcher Richtung das Futter ist und laufe in diese, wenn keine Schlange im Weg ist (Das sind mit den ganzen Fallunterscheidungen rund 200 Zeilen Code und entsprechend unübersichtlich). Das geht zwar soweit auch wunderbar, doch kommt es öfters vor, das eine Schlange in eine Sackgasse läuft (beispielsweise in eine selbst "gekrochene").

Nun komme ich wohl um eine Tiefensuche nicht herum, befürchte ich. Ideal wäre vermutlich AStar (A*) und habe mir auch ein Tutorial von Luckie und Daniel angesehen, doch das in C++ umzusetzen bzw. mich im Code zurechtzufinden, fällt mir nicht ganz so leicht.

Gibt es da vielleicht eine andere effiziente Möglichkeit, solche Fehlzüge der Schlange zu vermeiden?


Grüße

[SirThornberry]

spontan hab ich an einen Routenplaner gedacht als ich das gelesen hab. Die einfachste Variante ist vom aktuellen Punkt aus rekursiv alle möglichen Wege zu berechnen und den kürzesten zu nehmen. Bei der Wegverfolgung muss natürlich beachtet werden wo man lang kann, wo also noch keine schlange ist.

[Matze]

Hi,

was ich als Ergebnis brauche ich eigentlich nur die Richtung (hoch, runter, rechts, links), danach muss das wieder neu berechnet werden.
Aber ich kann mal schauen, ob ich eine rekursive Wegsuche hinbekomme, danke.

[Sidorion]

Also für diese Anwendung ist wohl A* die effektivste Methode.
Das Prinzip ist einfach:
Du nimmst ein 2D-Array von der Größe Deiner Karte.
Dieses füllst Du erstmal mit Nullen.
Danach schreibst Du in jede Zelle wo Wand oder Schlange ist eine -1 rein.
Jetzt wird in die Nachbarn der Nahrung je eine 1 reingeschrieben (ausser Wert=-1).
Dann wird eine Schleife gestartet (ab n=1):
Für jede Zelle der Karte, die n als Wert enthält schreibst Du in die Nachbarn n+1 als Wert, falls dort kein Wert >0 und <n+1 steht.
Danach wird mit n+1 gesucht.
Das machst Du solange, bis das Feld mit dem Schlangenkopf einen Wert>0 enthält.(Schleifenabbruch).
Neue Richtung für die Schlange ist nun der Nachbar, der den kleinsten Wert>0 enthält.

[Matze]

Hui das klingt gut und muss ich gleich mal testen, vielen Dank! :)
Die Algorithmen, die ich mir alle angesehen habe, kamen mir irgendwie komplizierter vor.

[Corpsman]

In meinem Sample Pathfinder ist der A* einmal für Gewichtetete und ungewichtete Kanten gezeigt. Da kannst vielleicht was "Klaun".

[Matze]

Hi,

danke, doch das möchte ich erstmal selbst probieren. :)
Nur scheitere ich daran und ich finde absolut keinen Fehler. Wer Lust hat, kann mal schauen, ob er einen Fehler findet.

Noch ein paar Bemerkungen, die für das Verständnis beitragen:
map->map ist das Spielfeld-Array, das für die Ausgabe ausgewertet wird (Futter: -1, leere Felder: 0, Schlangen >= 1)
map->map_a_star ist das Spielfeld nur eben am Ende aufbereitet mit dem A*-Algorithmus
Die Variablen- und Funktionsbezeichnungen sind selbsterklärend, denke ich.


Ich rufe den Algorithmus so auf:

Code:

a_star(game_map, food1, pc1_snake, pc1_snake->head_x, pc1_snake->head_y)

Das Problem momentan ist, dass

Code:

while (is_empty_field_around(map, food, snake->head_x, snake->head_y))

zu einer Endlosschleife führt und ich finde keinen Fehler. :( Optimiert habe ich noch nichts, ich weiß selbst, dass das sicher nicht sehr performant ist. ^^

Code:

bool is_food_field(cl_map* map, int x, int y)
{
   return map->map[x][y] == -1;
}

// check if there is a zero-filled field around the snake's head
bool is_empty_field_around(cl_map* map, cl_food* food, int x, int y)
{
   // left
   if ((x > 0) && (map->map_a_star[x - 1][y] == 0) && (! is_food_field(map, x - 1, y)))
      return true;
   // right
   if ((x < map->field_width) && (map->map_a_star[x + 1][y] == 0) && (! is_food_field(map, x + 1, y)))
      return true;
   // top
   if ((y > 0) && (map->map_a_star[x][y - 1] == 0) && (! is_food_field(map, x, y - 1)))
      return true;
   // bottom
   if ((y < map->field_height) && (map->map_a_star[x][y + 1] == 0) && (! is_food_field(map, x, y + 1)))
      return true;

   return false;
}

// filles the fields around with a defined number if the number is smaller than the existing one
void fill_fields_around(cl_map* map, int x, int y)
{
   printf("map_a_star[x][y]: %d\n", map->map_a_star[x][y]);
   // left
   if ((x > 0) && ((map->map_a_star[x - 1][y] == 0) || (map->map_a_star[x - 1][y] > map->map_a_star[x][y])) && (! is_food_field(map, x - 1, y)))
   {
      printf("foooooo\n");
      map->map_a_star[x - 1][y] = map->map_a_star[x][y] + 1;
   }
   // right
   else if ((x < map->field_width) && ((map->map_a_star[x + 1][y] == 0) || (map->map_a_star[x + 1][y] > map->map_a_star[x][y])) && (! is_food_field(map, x + 1, y)))
      map->map_a_star[x + 1][y] = map->map_a_star[x][y] + 1;
   // top
   else if ((y > 0) && ((map->map_a_star[x][y - 1] == 0) || (map->map_a_star[x][y - 1] > map->map_a_star[x][y])) && (! is_food_field(map, x, y - 1)))
      map->map_a_star[x][y - 1] = map->map_a_star[x][y] + 1;
   // bottom
   else if ((y < map->field_height) && ((map->map_a_star[x][y + 1] == 0) || (map->map_a_star[x][y + 1] > map->map_a_star[x][y])) && (! is_food_field(map, x, y + 1)))
      map->map_a_star[x][y + 1] = map->map_a_star[x][y] + 1;
}

// I'm sure, that's not the performantest astar-algorithm, but so I think it's more understandable
char a_star(cl_map* map, cl_food* food, cl_snake* snake, int x, int y)
{
   int step_number;

   // fill all forbidden array fields with a -1 ans all other fields with zero
   for (int i = 0; i < map->field_width; i++)
   {
      for (int j = 0; j < map->field_height; j++)
      {
         map->map_a_star[i][j] = (map->map[i][j] > 0) ? -1 : 0;
      }
   }

   // fill all needed fields with the distance to the food

   // fill the fields around the food with a 1 if there is no snake
   // left field of the food
   if ((food->food_x > 0) && (map->map_a_star[food->food_x - 1][food->food_y] == 0))
      map->map_a_star[food->food_x - 1][food->food_y] = 1;
   // right field of the food
   if ((food->food_x < map->field_width) && (map->map_a_star[food->food_x + 1][food->food_y] == 0))
      map->map_a_star[food->food_x + 1][food->food_y] = 1;
   // top field of the food
   if ((food->food_y > 0) && (map->map_a_star[food->food_x][food->food_y - 1] == 0))
      map->map_a_star[food->food_x][food->food_y - 1] = 1;
   // bottom field of the food
   if ((food->food_y < map->field_height) && (map->map_a_star[food->food_x][food->food_y + 1] == 0))
      map->map_a_star[food->food_x][food->food_y + 1] = 1;
   
   // fill the rest of the field (exit the loop if all fields around the snake's head are not zero filled)
   step_number = 1;
   while (is_empty_field_around(map, food, snake->head_x, snake->head_y))
   {
      // increase all fields around the current one step-by-step
      for (int i = 0; i < map->field_width; i++)
      {
         for (int j = 0; j < map->field_height; j++)
         {
            if (map->map_a_star[i][j] == step_number)
            {
               fill_fields_around(map, i, j);
            }
         }
      }
      step_number++;
   }

   ...
}

Hoffnungsvoll grüßt
Matze


Edit [22:25]: 1 Bug korrigiert, geht aber immer noch nicht
Edit [22:30]: 1 Bug korrigiert, geht aber immer noch nicht
Edit [22:42]: 1 Bug korrigiert, geht aber immer noch nicht

[Sidorion]

Aufgefallen ist mir nur, dass Du bei allen Prüfungen der umliegenden Felder auf >0 und <Feldbreite/Höhe prüfst. Dies erscheint mir unlogisch, da das Array entweder von 0 bis Felbreite-1 oder von 1 bis Feldbreite geht. D.h. Du hast eigentlich Feldbreite+1.

Wenn Du beim A* Map initialisieren das Futterfeld auch mit -1 belegst kannst Du Dir die ganzen (!IsFoodFoield..) sparen.

Du füllst in fill_fields_around immer nur ein Feld. Mach hier mal die ganzen elses weg.

[Matze]

Hi,

ah, da hast du natürlich in allen Punkten vollkommen recht! Danke. :thumb:

Der Algorithmus an sich scheint nun zu funktionieren (Anhang 1), doch vermute ich, dass dieser unter bestimmten Umständen nicht brauchbar ist (Skizze im Anhang 2). Denn wenn ich mir diese Situation vorstelle, müssten alle Felder unterhalb der grünen Schlange 0 bleiben und somit kann die blaue Schlange nichts machen.
Muss ich dann manuell abfragen, in welche x-/y-Richtung die blaue Schlange muss, um möglichst schnell beim Apfel zu sein und den Schlangen-Crash gesondert abfangen?

Grüße

[sirius]

Diesen Fall kannst du ja abfangen, wenn du durch deine Map gehts und nix mehr geändert hast und trotzdem eine 0 unter deinem Schlangenkopf liegt. Dann würde ich als neues Ziel das Schlangenende der grünen Schlange ansetzen.

[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 :oops:

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

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. :gruebel:

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

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:

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. :gruebel:

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

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

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

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. :stupid:

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. :gruebel:

[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. :duck: Es ist auch nicht so sehr wichtig, aber mich würde es interessieren, wie man so etwas genau umsetzen kann.

Grüße