Wegsuche für 2D und 3D Spiele.
Freeware, Version 1.0
 
© 2006  Frank Abbing, http//:frabbing.bplaced.net
 
 
Einleitung:
 
Das Ziel vieler Hobby-Programmierer ist die Erstellung eines Spieles mit intelligentem Computergegner. Nur, was anfangs noch spassig ist, kann in späteren Stadien zunehmend frustrierend enden. Oft zerplatzt der Traum vom eigenen Spiel daran, weil die Computerintelligenz einfach nicht dazu zu bewegen ist, sich vernünftig durch die liebevoll gestaltete Landschaft zu bewegen. Die Geister finden ihren Pacman nicht und die Reitertruppe verirrt sich im sauber gerenderten 3D-Wald. Da ist Frust pur angesagt.
Jetzt muss ein guter Algorithmus her, der vernünftig und schnell arbeitet, und auch noch leicht einzubauen ist. Ihr seid neugierig geworden? Gut, dann lest weiter, denn wir werden euer Problem beseitigen...
 
 
Der A*-Algorithmus:
 
Es gibt einige Algorithmen, die in der Lage sind, einen kurzen Weg durch ein Labyrinth zu finden. In den letzten Jahren hat sich zunehmend der A*-Algorithmus durchgesetzt, der heute von fast allen Spieleprogrammierern benutzt wird. Nicht zu unrecht, denn der A* findet immer den kürzesten Weg (bzw. einen sehr kurzen Weg) von einem Startpunkt zu einem Zielpunkt.
Leider ist die Umsetzung in ein Programm nicht so einfach und man benötigt schon eine schnelle Programmsprache, um gute Resultate zu erzielen. Das war auch der Grund, warum ich beschlossen hatte, den A* in Assembler zu erstellen. Assembler erzeugt die schnellsten Codes und hält Programme schön klein. Und in Form einer Dll kann der Algo so in nahezu jeder Sprache benutzt werden.
 
 
Die Pathfind.dll:
 
Zunächst aber einmal sollten wir uns fragen, was so eine Dll alles leisten muss. Hier mal ein Beispiel:
 
 
Diese Aufgabenstellung zeigt schön, welche Fehler ein Algo begehen könnte. Der Startpunkt liegt hier unten (rotes "S"). Oben (grünes "Z") befindet sich der Zielpunkt. Und dazwischen ist eine undurchdringliche Wand aus Steinen. Der Computer sollte nun versuchen, von Startpunkt zum Zielpunkt zu gelangen. Und das, ohne einen Umweg ins Mauerinnere zu beschreiten und bitte auf direktem Weg.
Ein ungeübter Programmierer, dessen Computerfiguren zunächst versuchen, direkt zum Ziel zu gelangen, wird hier scheitern. Die Folge ist zumindest ein grosser Umweg, der alles anderere als professionell aussieht.
Die Pathfind.dll berechnet den Weg zum Ziel hingegen ganz anders. Am Ende hat sie diese Aufgabenstellung folgendermassen gelöst:
 
 
Der berechnete Weg ist hier blau dargestellt. Man sieht sehr schön, das der Algorithmus gar nicht erst versucht, ins Innere der Mauern zu gelangen, sondern aussen herum direkt zum Ziel geht. Intern hat er natürlich ebenfalls versucht, zunächst den direkten Weg zu gehen. Aber nach und nach hat er seinen Weg korrigiert, bis er ihn für optimal befunden hat.
Diese Suche hat innerhalb eines 50x50 Felder grossen Matrix (das Bild zeigt nur einen Teil der Grafik) ca. 100 Millisekunden (ms) gedauert. Innerhalb einer Sekunde hätte der Algo also zehn dieser Berechnungen bewältigt. Und diese Suche war langsam, weil Level, welche viele freie Flächen besitzen, erheblich langsamer bearbeitet werden als labyrinthartige Level oder solche mit wenigen Freiflächen. Im Laufe dieser Anleitung werden wir noch Techniken kennenlernen, die Wegsuche weiter zu beschleunigen.
Zunächst noch ein Beispiel einer etwas anspruchsvolleren Wegsuche, deren Berechnung ca. 50 ms dauerte. Oder findet ihr einen kürzeren Weg?
 
 
 
Die Funktionen der Dll:
 
Bislang gibt es nur eine Funktion. Wenn es gewünscht wird, werde ich noch weitere Funktionen dazu nehmen, die vor allem den Umgang mit den Datenarrays betreffen.
 
ki_FindWay(W,S,Z,C,B,H,S,M,Z,-,F)
 
Startet die Wegsuche.
 
W : Zeiger auf einen Speicherbereich mit der Levelmatrix (Bytes)
S : Long - Offset des Startfelds
Z : Long - Offset des Zielfelds
C : Long - Bytes des freien Felds (0-255)
B : Long - Breite des Levels
H : Long - Höhe des Levels
P : Zeiger auf einen Speicherbereich für die gefundenen Wegpunkte
M : Zeiger auf einen Speicherbereich mit Terraindaten (Bytes), oder 0
Z : Long - Zufalls-Komponente
- : Long - 0 (nicht belegt)
F : Long - Flags
R : Long - Registriernummer
 
Ergebnis: Long - -1 = Fehler / 0 = kein Pfad gefunden / >0 = Anzahl gefundener Wegpunkte. 
 
W ist ein Zeiger auf einen Bereich mit Datenbytes. Darin muss der Gesamtplan eines Levels gespeichert sein, in etwa so:
 
Level  db 1,1,1,1,1,1,1,1
       db 1,0,1,0,0,0,0,1
       db 1,0,1,0,1,1,0,1
       db 1,0,1,0,0,1,0,1
       db 1,0,1,0,0,1,0,1
       db 1,0,1,1,1,1,0,1
       db 1,0,0,0,0,0,0,1
       db 1,1,1,1,1,1,1,1
 
Das Ganze ist also nichts anderes als die Karte eines Level, wobei die Karte in einzelne Kacheln aufgeteilt ist.
Es empfiehlt sich, für die Kacheln, die von der Kartenposition her von einer Figur betreten werden dürfen, eine Null zu verwenden. Wände und andere nicht begehbare Elemente sollten ein anderes Byte erhalten (1-255). Die Ränder eines Levels dürfen niemals begehbar sein.
 
Wählt die Kacheln auf eurer Karte bitte nicht zu klein. Ansonsten benötigt der Algorithmus zur Wegfindung zu lange. Macht sie aber auch nicht zu gross, sonst lauft ihr Gefahr, enge Wege nicht zu finden.
 
S ist der Startoffset. Von hier aus startet die Wegsuche. In unserem Beispiel wären Offsets von 0 bis 63 möglich, wenngleich der Startpunkt niemals direkt am Rand liegen darf (Rand darf ja nicht begehbar sein). S kann nach folgender Formel berechnet werden:
 
X-Position + (Y-Position * Breite des Levels)
 
Z ist der Zieloffset, bei der die Suche enden soll. Für ihn gilt das Gleiche wie für S. Z darf natürlich nicht = S sein.
 
C kann ein Wert zwischen 0 und 255 sein. Er kennzeichnet Felder innerhalb des Levels, die bei der Wegsuche verwendet werden können. Ich empfehle hier, den Wert Null zu verwenden.
 
B und H sind Breite und Höhe des Levels. In unserem Beispiel wären beide 8.
 
P ist ein Zeiger auf einen Bereich, in den ki_FindWay() einen gefundenen Weg komplett speicher kann. Dieser Speicher muss groß genug ausgelegt sein. Jeder einzelne Wegpunkt wird als Offset eingetragen, jeweils 4 Byte gross. Also als Long. Die Offsets können genauso gehandhabt werden, wie S und Z.
Ist Flag 2 gesetzt, dann wird der Weg in P als Koordinaten gespeichert. Immer jeweils eine X und eine Y-Koordinate, jeweils als Integer (2 Bytes). Für den Einen oder Anderen mag diese Art der Positionierung einfacher sein.
 
M ist optional. Wenn hier Null steht, passiert nichts weiter. M kann aber auch ein Zeiger auf einen Bereich sein, der Terrain-Daten enhält, ähnlich W. Diese Werte sind ebenfalls Bytes (0-255). So könnte ein Terrain-Speicher für unseren 8 x 8 Felder grossen Level aussehen:
 
Terrain  db 0,0,0,0,0,0,0,0
         db 0,0,0,2,2,0,0,0
         db 0,0,2,4,4,2,0,0
         db 0,2,4,6,6,4,2,0
         db 0,2,4,6,6,4,2,0
         db 0,0,2,4,4,2,0,0
         db 0,0,0,2,2,0,0,0
         db 0,0,0,0,0,0,0,0
 
Je höher ein Wert ist, desto ungerner wird ihn ki_FindWay() in den gefundenen Weg mit einbeziehen.
Einsatzgebiete für M gibt es zahlreiche. Stellt euch einen Level vor mit vielen Bergen. Der Computer soll dieses Gebiet nun durchqueren. Ein Gang über die Berge ist aber in der Realität viel beschwerlicher als deren Umgehung oder eine Durchquerung der Täler. Dennoch ist es trotzdem möglich, Berge direkt zu besteigen. Etwa, wenn es keinen anderen Weg gib, oder dieser ansonsten unverhältnissmässig lang ist. Experimentiert ruhig einmal mit unterschiedlichen Werten. Der Einsatz von M kann Spiele sehr realistisch wirken lassen.
 
Mittels Z ist es möglich, gefundene Wege mehr oder weniger viel zu "verfremden". Eine zufällige Komponete sorgt dafür, dass der Weg verändert wird. Testet das ruhig mal aus.
 
Nach Z folgt ein freier Parameter für zukünftige Erweiterungen. Tragt dort einfach 0 ein.
 
F ist ein Wert, der sich aus verschiedenen Flags zusammensetzten lässt. Sollen mehrere Flags aktiviert werden, dann müssen diese Werte addiert werden. Ist F = 0, dann ist kein Flag aktiv. Hier eine Auflistung der bisher vorhandenen:
 
1 = Keine diagonalen Züge bei der Wegsuche berücksichtigen. Der gefundene Weg führt somit nur nach oben/unten und rechts/links. Aber nicht schräg.
2 = Alternative Übergabe der Wegdaten in P. Der Weg wird jetzt als X/Y-Koordinaten (Integer) angelegt.
 
Parameter R habe ich nur dazu genommen, um in der Anfangsphase mal einen Überblick zu erhalten, von wem und von wievielen Leuten die Dll genutzt, und welche Programmsprache diese benutzen. Nach einiger Zeit werde ich diesen Parameter wohl wieder entfernen.
Die Registiernummer erhaltet ihr völlig kostenlos von mir per Mail. Schreibt dazu an mich eine Mail mit dem Betreff "Pathfind.dll Registrierung", und schreibt auch bitte kurz auf, mit welcher Programmsprache ihr die Dll benutzt und für was für eine Art Software ihr sie verwenden wollt. Die Nummer erhaltet ihr von mir in der Regel noch am selben Tag. Tragt diese einfach in R ein.
Meine Mailadresse ist frabbing@gmx.de.
 
 
Tipps & Tricks:
 
Es gibt einige Techniken, um eine Wegsuche effizienter und vor allem schneller zu machen:
  • Blendet unnötige Teile des Levels aus der Suche aus, z.B. diejenigen, die in eine Sackgasse führen. Dazu muss die Sackgasse während der Suche "versperrt" werden.
  • Fasst Kartenabschnitte zu größeren Sektoren zusammen und berechnet immer Wege von einem Sektor zum nächsten. Berechnet also immer nur Teilstücke des gesamten Weges.
  • Für weite Wege verwendet ihr am besten gesonderte Karten mit groben Rastern.
  • Oft gebrauchte Wege könnt ihr schon vor Beginn des Spiels berechnen lassen.
  • Benutzt Wegpunkte.
 
Weiteres:
 
In keinem Fall bin ich, Frank Abbing, verantwortlich für irgendwelche speziellen, zufälligen oder indirekten Beschädigungen jeglicher Art, die durch die Lieferung, Ausführung oder Anwendung dieser Software entstehen.
Die Pathfind.dll wurde mit großer Sorgfalt geschrieben, aber ich möchte nicht garantieren, daß sie fehlerfrei ist. Allerdings wurde die Software ausgiebig getestet, ohne das Schäden entstanden sind.
Sie dürfen nicht versuchen, diese Software ganz oder teilweise zu decompilieren, zu verändern, zu übersetzen oder zu disassemblieren, kein einzelnes Bit darf verändert werden.