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.