AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren
Zurück Delphi-PRAXiS Programmierung allgemein Programmieren allgemein Welcher Algorithmus für eine Snake-KI?
Thema durchsuchen
Ansicht
Themen-Optionen

Welcher Algorithmus für eine Snake-KI?

Ein Thema von Matze · begonnen am 7. Mai 2007 · letzter Beitrag vom 15. Mai 2007
Antwort Antwort
Seite 1 von 4  1 23     Letzte »    
Benutzerbild von Matze
Matze
(Co-Admin)

Registriert seit: 7. Jul 2003
Ort: Schwabenländle
14.929 Beiträge
 
Turbo Delphi für Win32
 
#1

Welcher Algorithmus für eine Snake-KI?

  Alt 7. Mai 2007, 11:01
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
  Mit Zitat antworten Zitat
Benutzerbild von SirThornberry
SirThornberry
(Moderator)

Registriert seit: 23. Sep 2003
Ort: Bockwen
12.235 Beiträge
 
Delphi 2006 Professional
 
#2

Re: Welcher Algorithmus für eine Snake-KI?

  Alt 7. Mai 2007, 11:18
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.
Jens
Mit Source ist es wie mit Kunst - Hauptsache der Künstler versteht's
  Mit Zitat antworten Zitat
Benutzerbild von Matze
Matze
(Co-Admin)

Registriert seit: 7. Jul 2003
Ort: Schwabenländle
14.929 Beiträge
 
Turbo Delphi für Win32
 
#3

Re: Welcher Algorithmus für eine Snake-KI?

  Alt 7. Mai 2007, 11:24
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.
  Mit Zitat antworten Zitat
Sidorion

Registriert seit: 23. Jun 2005
403 Beiträge
 
#4

Re: Welcher Algorithmus für eine Snake-KI?

  Alt 7. Mai 2007, 12:33
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.
Manchmal sehen Dinge, die wie Dinge aussehen wollen mehr wie Dinge aus, als Dinge
<Esmerelda Wetterwachs>
  Mit Zitat antworten Zitat
Benutzerbild von Matze
Matze
(Co-Admin)

Registriert seit: 7. Jul 2003
Ort: Schwabenländle
14.929 Beiträge
 
Turbo Delphi für Win32
 
#5

Re: Welcher Algorithmus für eine Snake-KI?

  Alt 7. Mai 2007, 16:52
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.
  Mit Zitat antworten Zitat
Benutzerbild von Corpsman
Corpsman

Registriert seit: 8. Nov 2005
Ort: nähe Stuttgart
981 Beiträge
 
Delphi XE2 Professional
 
#6

Re: Welcher Algorithmus für eine Snake-KI?

  Alt 7. Mai 2007, 16:59
In meinem Sample Pathfinder ist der A* einmal für Gewichtetete und ungewichtete Kanten gezeigt. Da kannst vielleicht was "Klaun".
Uwe
My Sitewww.Corpsman.de

My marble madness clone Balanced ( ca. 70,0 mb ) aktuell ver 2.01
  Mit Zitat antworten Zitat
Benutzerbild von Matze
Matze
(Co-Admin)

Registriert seit: 7. Jul 2003
Ort: Schwabenländle
14.929 Beiträge
 
Turbo Delphi für Win32
 
#7

Re: Welcher Algorithmus für eine Snake-KI?

  Alt 7. Mai 2007, 21:44
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
  Mit Zitat antworten Zitat
Sidorion

Registriert seit: 23. Jun 2005
403 Beiträge
 
#8

Re: Welcher Algorithmus für eine Snake-KI?

  Alt 8. Mai 2007, 11:01
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.
Manchmal sehen Dinge, die wie Dinge aussehen wollen mehr wie Dinge aus, als Dinge
<Esmerelda Wetterwachs>
  Mit Zitat antworten Zitat
Benutzerbild von Matze
Matze
(Co-Admin)

Registriert seit: 7. Jul 2003
Ort: Schwabenländle
14.929 Beiträge
 
Turbo Delphi für Win32
 
#9

Re: Welcher Algorithmus für eine Snake-KI?

  Alt 8. Mai 2007, 14:33
Hi,

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

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
Miniaturansicht angehängter Grafiken
astar_error_845.gif   snake_astar_166.png  
  Mit Zitat antworten Zitat
Benutzerbild von sirius
sirius

Registriert seit: 3. Jan 2007
Ort: Dresden
3.443 Beiträge
 
Delphi 7 Enterprise
 
#10

Re: Welcher Algorithmus für eine Snake-KI?

  Alt 8. Mai 2007, 16:46
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.
Dieser Beitrag ist für Jugendliche unter 18 Jahren nicht geeignet.
  Mit Zitat antworten Zitat
Antwort Antwort
Seite 1 von 4  1 23     Letzte »    


Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 17:42 Uhr.
Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz