KI für Dummies

[Lebostein]

Für meine alte QBasic-Adventure-Engine habe ich das Pathfinding nach folgendem Matrixalgorithmus implementiert:
http://shatteredrealmproductions.com/Tw ... inding.htm
Man muss zwar zu Beginn einmalig einige Matrixoperationen durchführen, braucht aber dann für die Berechnung beliebiger Wege keinerlei Berechnungen mehr anzustellen, da alle kürzesten Verbindungen beliebiger Punkte in einer Matrix zusammengefasst sind.

[DieFüchsin]

Für die Suche nach dem schnellsten und direktesten Weg, brauchst du ja nur die interne AGS-Pathfinding Mechanik zu bemühen,
genauso wie in jedem normalen Adventure.

Du zeichnest einfach überall walkable areas ein und wenn der spieler auf einem punkt steht,
schickst du einfach den computerspieler zu den koordinaten wo der spieler steht.
CPU.Walk( player.x, player.y, eBlock, eWalkableAreas);
damit geht der Cpu player einmal automatisch auf den kürzesten Weg Richtung Computer Spieler.

Der CPU-player soll aber nicht direkt zur Spielfigur laufen, sondern nur die Feldanzahl, die er gewürfelt hat.
Ich denke, so einfach ist es also nicht, wenn ich nur die Walk-Funktion benutze.
Ich stelle es mir so vor, dass der CPU-Player die Felder Punkt für Punkt nacheinander ansteuert, wobei jeder Punkt einem Koordinatenpaar entspricht.

Regions oder Hotspots oder ähnliches kann ich nicht benutzen, weil ich über 100 Felder, aber nur etwa 30 Hotspots und Regions zur Verfügung habe.

Zum Spielablauf:

Der Spieler würfelt und klickt dann nacheinander Felder an, um voranzukommen. Sind alle Würfelaugen "verbraucht" würfelt der Computer und zieht den Verfolger in Richtung Spieler.

Schafft es der Spieler bis zur Tür bevor der Verfolger ihn einholt, hat man gewonnen, ansonsten gewinnt der Verfolger.



Mein Hauptproblem ist momentan, wie ich dem Programm das Spielfeld beibringe und wie ich dort dann den Algorithmus anwende.
Zwar habe ich schon mit Arrays gearbeitet, weiß aber mit 1-dimensionalen und 2-dimensionalen nichts anzufangen. Wie simuliere ich damit ein Spielfeld?

[papapischu]

Ich kann leider kein AGS, aber in einer anderen Programmiersprache würde ich es so machen:
-Gib jedem Feld eine Nummer (von 1 bis n).
-Definiere ein 2D Array das genau dann einen Eintrag hat, wenn zwei Felder benachbart sind.
Bsp.: Drei nebeneinander liegende Felder |6|7|8|, das Array hätte dann folgende Einträge pfad[0][0] = 6 , pfad[0][1] = 7 (es gibt einen Pfad von 6 nach 7), pfad[1][0] = 7 , pfad[1][1] = 8 (es gibt einen Pfad von 7 nach 8)
-Jetzt kannst du deinen path_finding Algorithmus programmieren, und immer wenn geprüft wird ob es zwischen zwei Punkten (Feldern) eine Verbindung gibt, musst du das etwa so machen:

-- existiert verbindung zwischen feld_x udn feld_y?
for(int i =0; i<path.length; i++) {
if((path[0]=feld_x and path[1]=feld_y) or(path[0]=feld_y and path[1]=feld_x)) return true;
}
return false;

-Du kannst jetzt auch noch ein zweites Array anlegen, dass die x und y Koordinate deiner Felder speichert (z.B. die linke obere ecke).
Also z.B. Feld 6 an x=100, y=120 feld_pos[6][0]=100, feld_pos[6][1]=120
So könntest du bei einem Mausklick überprüfen, ob es ein Feld an dieser Stelle gibt.

Ich hoffe das bringt dich irgendwie weiter.

[Rocco]

Mein Hauptproblem ist momentan, wie ich dem Programm das Spielfeld beibringe und wie ich dort dann den Algorithmus anwende.
Zwar habe ich schon mit Arrays gearbeitet, weiß aber mit 1-dimensionalen und 2-dimensionalen nichts anzufangen. Wie simuliere ich damit ein Spielfeld?

die arrays sind eindimensional weil AGS soweit mir bekannt ist, keine mehrdimensionalen Arrays unterstüzt.
das modul das ich weiter oben angesprochen habe ist nicht mehr verfügbar, vielleicht wirds wieder geuppt.

Code: Alles auswählen

char spielfeld[200] = { 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
                               0,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,
                               0,x,x,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,x,0,
                               0,P,0,x,0,0,0,0,0,0,0,0,0,0,0,0,0,C,x,
                               usw..... }

das wäre das spielfeld in ganz vereinfachter form, wobei die x dann die begehbaren felder darstellen würden.
P der Spieler ist und C der Computer.

arrays mit den koordinaten:

Code: Alles auswählen

int spielfeld_koord_x[200] = { 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
                               0,10,15,20,26,32,40,48,55,69,78,90,112,125,134,145,160,180,190,0,
                               0,12,18,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0.....}

int spielfeld_koord_y[200] = { 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
                               0,30,30,30,30,30,30,.....}

andere variablen:

Code: Alles auswählen

int player_feld = 62;
int cpu_feld = 78;

int würfelanzahl = 0;

mit diesen arrays könntest du das spiel simulieren,
natürlich musst du dir noch was einfallen lassen, für die höhenstufen usw..

prinzipiell könntest du aber nach dem gewürfelt wurde, schauen welche felder rund um den spieler begehbar sind (x)
und nur auf solche felder dürfte der spieler oder CPU Gegner dann ziehen.

[DieFüchsin]

Das Spielfeld lässt sich nicht in ein regelmäßiges Raster einteilen. Kann ich das Spielfeld trotzdem so simulieren?

[DasJan]

Ja, indem du es als Graph speicherst. Schau mal in dem Beispiel, was ich oben gepostet habe, in der fw_example.php nach.

Das Jan

[DieFüchsin]

Ich weiß leider nicht, wie ich das Ganze in eine Graphen-kompatible Form bringen kann.

Der Escher-Effekt bewirkt, dass sich die Kästchen nicht in ein regelmäßiges Raster bringen lassen.
Felder, die auf dem Bild weit auseinander zu stehen scheinen, überschneiden sich.

[perfektopheles]

Also Rocco hat es schon geschrieben.
Du hast einen Graphen (auf Papier), dessen N+1 Knoten nummeriert sind, also k_0, k_1, ..., k_N. Diese Knoten haben auf dem Bild gewisse Bildschirmkoordinaten, z.B. k_0 = (640, 480).

Die Bildschirmkoordinaten aller Knoten schreibst du in ein Array, aber weil es in AGS scheinbar keine 2-dimensionalen Arrays gibt (wie billig ), nehmen wir zwei 1-dimensionale Arrays für die X- und Y-Komponente der Knotenkoordinaten:

Code: Alles auswählen

int knoten_koord_x[N+1] = { 0, ... }
int knoten_koord_y[N+1] = { 0, ... }

Dann machst du diese All-Pairs-Shortest-Path-Matrix, wie DasJan es beschrieb, in der Vorgängerknoten (oder Nachfolgerknoten) stehen, so dass man sich den kürzesten Weg zwischen zwei beliebigen Knoten sukzessive rekonstruieren kann.
Den Graphen hast du dann implizit in dieser Matrix, wo alles über Knotenindizes zusammenhängt. D.h. in AGS brauchst du nur die Matrix und keinen Graphen mehr. Verwirrt es dich, dass die Matrix ein Raster darstellt, dein Feld aber keins ist?
Die Matrix kann man auch als ein 1-dimensionales Array speichern (einfach jede Zeile nacheinander im Array ablegen und dann ist wert[zeile, spalte] = wert[zeile*(N+1) + spalte])

Code: Alles auswählen

  | 0 1 ... N
---------------
0 | 3 7     51
1 | 9 ...
. | ...
. | ...
. | ...
N | ...

Die Indizes der Knoten (also 0 bis N) dienen auf der einen Hand dazu, immer den kürzesten Weg zu bestimmen, d.h. für beide Spieler müssen die Indizes des Knoten mitgeführt werden, auf dem er gerade steht.
Auf der anderen Hand dienen die Indizes zum Herauslesen der Knotenkoordinaten aus den zwei Arrays, um die Figur visuell über den Bildschirm zu bewegen.

[DieFüchsin]

Danke für deine Erklärung, perfektopheles. Mal sehen, ob ichs verstanden habe:

Die Bildschirmkoordinaten aller Knoten schreibst du in ein Array, aber weil es in AGS scheinbar keine 2-dimensionalen Arrays gibt (wie billig ), nehmen wir zwei 1-dimensionale Arrays für die X- und Y-Komponente der Knotenkoordinaten:

Code: Alles auswählen

int knoten_koord_x[N+1] = { 0, ... }
int knoten_koord_y[N+1] = { 0, ... }

Was genau beschreibt das N+1? Sind damit die Nummern der Knoten (k_0, k_1) schon abgedeckt oder müssen die nochmal extra irgendwo angegeben werden?

Bedeutet "knoten_koord_x[k_0]=640" dann, dass der x-Wert für k_0 bei 640 liegt?

Verwirrt es dich, dass die Matrix ein Raster darstellt, dein Feld aber keins ist?

Ja. Ich glaube, ich verstehe auch den Aufbau der Matrix nicht.

Unter dem Graphen habe ich mir nach der Erklärung auf Wikipedia bisher so etwas vorgestellt:



Wie das in diese rasterförmige Tabelle kommt, versteh ich nicht.

Code: Alles auswählen

  | 0 1 ... N
---------------
0 | 3 7     51
1 | 9 ...
. | ...
. | ...
. | ...
N | ...

Wofür stehen zB hier die beiden Nullen und die Zahl dazwischen? Stehen die Nullen für die Nummer des Feldes? Aber warum sind es zwei?

[perfektopheles]

Kein Problem, ich habe einige Posts von anderen zusammengefasst und vllt. vereinfacht

Was genau beschreibt das N+1? Sind damit die Nummern der Knoten (k_0, k_1) schon abgedeckt oder müssen die nochmal extra irgendwo angegeben werden?

N+1 ist die Anzahl der Knoten (Nummern von 0 bis N (N-0)+1 = N+1 Knoten). Zum Beispiel hast du 10 Knoten Nummern von 0 bis 9.
Mit

Code: Alles auswählen

int knoten_koord_x[N+1] = { 0, ... }

erstellst du ein Array, das N+1 Plätze hat und damit automatisch Platz für die Informationen (hier X-Koordinate) aller deiner N+1 Knoten bereithalten kann.

Bedeutet "knoten_koord_x[k_0]=640" dann, dass der x-Wert für k_0 bei 640 liegt?

Ja, nur nimmst du statt der Knotennamen ihre Nummern (bzw. Indizes): "knoten_koord_x[0]=640"

Ja. Ich glaube, ich verstehe auch den Aufbau der Matrix nicht.

Unter dem Graphen habe ich mir nach der Erklärung auf Wikipedia bisher so etwas vorgestellt: http://upload.wikimedia.org/wikipedia/d ... et.svg.png

Wie das in diese rasterförmige Tabelle kommt, versteh ich nicht.

Die Matrix beschreibt den Graphen nicht direkt. In der Matrix sind Zwischenknoten (je nachdem ob Vorgänger von w oder Nachfolger von v. Nachfolger ist besser, weil man dann gleich die Figur sukzessive forwärts bewegen kann.) abgespeichert, die man aufsuchen muss, wenn man von einem Knoten v zu einem Knoten w den kürzesten Weg braucht:

Dann könntest du außerhalb von AGS zum Beispiel die "All Pairs Shortest Path"-Matrix berechnen. Die enthält eine Zeile und eine Spalte für jeden Knoten im Graphen. Im Eintrag (v, w) steht dann der Knoten v', für den gilt: Auf dem kürzesten Weg von v nach w ist v' der Knoten, der auf v folgt.

Wofür stehen zB hier die beiden Nullen und die Zahl dazwischen? Stehen die Nullen für die Nummer des Feldes? Aber warum sind es zwei?

Ok, lass uns mal eine "All Pairs Shortest Path"-Matrix für den Graphen auf deinem Wikipedia-Bild machen:

Wir haben 4 Knoten (A = k_0, B = k_1, C = k_2, D = k_3), d.h. die Matrix hat 4 Zeilen und 4 Spalten: matrix[4][4]. In der Matrix speichern wir der Einfachheit halber die Nachfolger-Knoten.

Der Eintrag matrix[zeile][spalte] bedeutet: Wenn ich auf dem kürzesten Weg von k_zeile zu k_spalte laufen will, auf welchen Knoten soll ich von k_zeile aus gehen? (Hat DasJan oben geschrieben.)

Also von A nach A (also von k_0 nach k_0) sind wir schon da, d.h. matrix[0][0] ist irgendein Wert, der anzeigt, dass man schon auf dem Endknoten steht, also z.B. matrix[0][0] = -1. Mit -2 kann man z.B. anzeigen, dass kein Weg existiert.

Dann weiter: von A nach B ist der kürzeste Weg A-B (jetzt im Sinne von Anzahl der Kanten). D.h. B ist der Nachfolger von A. Von B nach B sind wir schon da:
matrix[0][1] = 1
matrix[1][1] = -1

Von A nach C ist der kürzeste Weg A-B-C oder A-D-C. Zwei Wege, da kann man sich für einen entscheiden, nehmen wir A-B-C: B ist der Nachfolger von A. Von B nach C ist B-C und dann C-C:
matrix[0][2] = 1
matrix[1][2] = 2
matrix[2][2] = -1

Von A nach D: A-D
matrix[0][3] = 3
matrix[3][3] = -1

usw.

Code: Alles auswählen

  |  0  1  2  3
---------------
0 | -1  1  1  3
1 |    -1  2
2 |       -1
3 |          -1

Ich gehe davon aus, dass der Spieler nach dem Würfeln auf ein Feld klickt und die Figur läuft auf dem kürzesten Wege auf das Feld, soweit die gewürfelten Schritte reichen? Dann gäbe es noch eine kleine Hürde, nämlich festzustellen, welcher Knoten sich am nächten zur angeklickten Bildschirmkoordinate befindet, aber dafür gibt es auch Alogrithmen: http://en.wikipedia.org/wiki/Nearest_neighbor_search

[DieFüchsin]

Ich glaube, ich habe es verstanden. Wenn ich den Weg zu einem x-beliebigen Feld suche, schaue ich also mit der Tabelle zunächst nach dem Nachbarfeld vom Startfeld, das in die richtige Richtung weist - und dann nach dem Nachbarfeld von diesem usw.?

Und diese Matrix muss ich für alle Felder mit der Hand eintragen?

Definiert mir

Code: Alles auswählen

int knoten_koord_x[N+1] = { 33, 44, 55, 68, ... }

also automatisch für den X-Wert von k_0 33, für den von k_1 44, für den von k_2 55 und für den von k_3 68?
Also kann ich die Koordinaten aller Felder in nur zwei Arrayzeilen abspeichern und zB. mit "knoten_koord_x[0]" abrufen?

Ich gehe davon aus, dass der Spieler nach dem Würfeln auf ein Feld klickt und die Figur läuft auf dem kürzesten Wege auf das Feld, soweit die gewürfelten Schritte reichen? Dann gäbe es noch eine kleine Hürde, nämlich festzustellen, welcher Knoten sich am nächten zur angeklickten Bildschirmkoordinate befindet, aber dafür gibt es auch Alogrithmen: http://en.wikipedia.org/wiki/Nearest_neighbor_search

Ich dachte es mir eher so, dass der Spieler Schritt für Schritt das nächste Feld anklicken muss, um sich vorzubewegen.


Wenn zwei mögliche Wege gleichlang sind, kann ich dann auch beide angeben oder muss ich mich für einen entscheiden?

[perfektopheles]

Ich glaube, ich habe es verstanden. Wenn ich den Weg zu einem x-beliebigen Feld suche, schaue ich also mit der Tabelle zunächst nach dem Nachbarfeld vom Startfeld, das in die richtige Richtung weist - und dann nach dem Nachbarfeld von diesem usw.?

Ja, genau. Ich habe mir den Floyd-Warshall-Algorithmus angeschaut und ich glaube, der kann aufgrund seines Prinzips unmittelbar nur die Vorgänger abspeichern (also den kürzesten Weg praktisch vom Endknoten her gesehen). Naja, dürfte nicht schwer sein, den Weg umzudrehen.

Und diese Matrix muss ich für alle Felder mit der Hand eintragen?

Wie DasJan hier http://www.adventure-treff.de/forum/vie ... 49#p291149 geschrieben hat, kannst du den PHP-Code benutzen, allerdings muss du zuerst eine Matrix W aufstellen mit folgenden Werten:
Da wir von Kantenanzahl als Kriterium für die Pfadlänge ausgehen, muss der Wert W[zeile][spalte] eine 1 oder 0 sein. 1 falls k_zeile und k_spalte direkt durch eine Kante verbunden sind, sonst 0.
Das dürfte eine große Matrix geben, danach macht der Algorithmus die Berechnung und du brauchst dann nur noch die Predecessors-Matrix, die er ausgibt. Mit dieser kannst du dann die kürzesten Wege rekonstruieren.
Für den Bsp-Graphen siehe angehängtes Bild (da ist Graph=W).

Definiert mir

Code: Alles auswählen

int knoten_koord_x[N+1] = { 33, 44, 55, 68, ... }

also automatisch für den X-Wert von k_0 33, für den von k_1 44, für den von k_2 55 und für den von k_3 68?
Also kann ich die Koordinaten aller Felder in nur zwei Arrayzeilen abspeichern und zB. mit "knoten_koord_x[0]" abrufen?

Ja.

Ich dachte es mir eher so, dass der Spieler Schritt für Schritt das nächste Feld anklicken muss, um sich vorzubewegen.

Das geht auch, da muss man aber bei jedem Schritt das zur angeklickten Stelle nächste Feld ermitteln. (Ich weiß nicht, ob diese Ermittlung überhaupt bei einem solchen verzerrten Feld reibungslos funktioniert).

Wenn zwei mögliche Wege gleichlang sind, kann ich dann auch beide angeben oder muss ich mich für einen entscheiden?

Das entscheidet allein der Algorithmus, der dir diese Predecessors-Matrix berechnet und in der Matrix ist nur einer von möglichen kürzesten Wegen gespeichert. Alles was von dir kommt ist diese Matrix W.

[DieFüchsin]

Wie DasJan geschrieben hat, kannst du den PHP-Code benutzen, allerdings muss du zuerst eine Matrix W aufstellen mit folgenden Werten:
Da wir von Kantenanzahl als Kriterium für die Pfadlänge ausgehen, muss der Wert W[zeile][spalte] eine 1 oder 0 sein. 1 falls k_zeile und k_spalte direkt durch eine Kante verbunden sind, sonst 0.

Achso, das PHP rechnet mir das also aus.

Wie genau muss denn diese Matrix W aussehen? Schreibe ich z.B. W[0][1]=1 oder W[0][50]=0?
Wenn ja, muss ich das Ganze zuvor als int W[zeile][spalte] definieren - oder wie?

Im PHP-Script vom Beispiel lese ich folgendes:

Code: Alles auswählen

 $graph = array(array(0,0,0,0,5,12),
                   array(15,0,9,0,0,0),
                   array(0,0,0,5,0,0),
                   array(0,2,0,0,0,0),
                   array(0,0,10,0,0,4),
                   array(0,0,17,20,0,0));
    $nodes = array("a", "b", "c", "d", "e", "f");

Kann ich das auch so machen, wie es das Beispiel vorgibt und das Ganze einfach erweitern? (Oder auch nicht einfach - ist ja eine Ganze Menge die dazukäme.)

[perfektopheles]

Im PHP-Script vom Beispiel lese ich folgendes:

Code: Alles auswählen

 $graph = array(array(0,0,0,0,5,12),
                   array(15,0,9,0,0,0),
                   array(0,0,0,5,0,0),
                   array(0,2,0,0,0,0),
                   array(0,0,10,0,0,4),
                   array(0,0,17,20,0,0));
    $nodes = array("a", "b", "c", "d", "e", "f");

Kann ich das auch so machen, wie es das Beispiel vorgibt und das Ganze einfach erweitern? (Oder auch nicht einfach - ist ja eine Ganze Menge die dazukäme.)

Ja, genau, einfach das Beispiel erweitern.
Das ist natürlich umständlich. Ideal wäre ein Programm, wo du das Bild als Hintergrund einblendest und dann einfach Knoten auf den Feldern platzierst und dir dann die Matrix W (und evtl. Kooordinaten) ausgeben lässt.
Schau dir die Programme an (hab sie nur als Links da und hab sie mir nicht näher angeschaut):
http://www.yworks.com/de/products_yed_about.htm
http://www.graphviz.org/

[Rondo]

Ich hab zufällig vor 2 Monaten ein Programm in java geschrieben um Graphen und den Dijkstraalg. umzusetzen könnte es dir helfen?