Welcher Algorithmus für eine Snake-KI?

[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