Künstliche Intelligenz - Pathfinding

[Krypthor]

Hi,

ich hab mich in letzter Zeit ein bischen mit dem Thema "Pathfinding" beschäftigt, damit die Gegner
in meinem 2D Spiel nicht nur gegen die Wand rennen .
Dabei hab ich versucht den A*Algorythmus bzw. Dijkstra zu verstehen, wo mir das Prinzip schon klar ist, allerdings hab ich da noch überhaupt nichts gefunden wie man das in Java einfach umsetzen kann.

Man kann in Tutorials immer sehen wie die Felder "gescannt" werden und dann ein Pfad gefunden wird,
wie aber speichert man die gescannten Felder und vor allem wie wird der kürzeste Weg um die Mauer
gespeichert und dann auch vom Gegner umgesetzt?
Würde mich über Hilfe freuen,

Mit freundlichen Grüßen,

Krypthor

 

[Apo]

Wenn du ein typisches tilebasiertes Spiel hast, ist es recht leicht umsetzbar.

Ich habe dafür mal ein kleines Tutorial geschrieben.

Ich würde einfach mit Listen in Java arbeiten bzw. habe es damit umgesetzt und diese Liste läuft der Spieler oder der Gegner einfach ab. In dieser Liste stehen die Schritte die er ablaufen soll.

 

[Krypthor]

Wow das Tutorial ist echt gut!
Mein Spiel hat zwar auch ein Mapraster, jedoch kann sich der Spieler bzw. Gegner darauf frei bewegen also auch nochmal in jedem Feld, geht das dann trozdem?

Und was ich noch nicht ganz verstanden habe ist wie man das abfragt.

wenn der Gegner z.B. die Koordinaten x,y hat und der Spieler a,b wäre das dann ungefähr so:

wenn x + 1 frei ist, dann g + 1; (das mit allen richtungen)
und dann h1 = a - x; h2 = b - y; (wenn der Gegner oben links vom Spieler ist)
h = h1 + h2
Damit hat man dann g und h und kann F ausrechnen, alles speichern und den nächsten
Wert nehmen.

Ist das so ungefähr richtig?

 

[Apo]

Das ist richtig.
Das neue H setzt sich aus den absoluten Abständen zwischen den x-Werten und den y-Werten des Punktes und des Zielpunktes zusammen.

oder anders ausgedrückt für dein Beispiel:
h = |x - a| + |y - b|

Das g wird im Tutorial immer um 1 erhöht, aber im Wegfindungsapplet ist auch mal gezeigt, dass es unterschiedliche Untergründe geben kann und damit auch unterschiedliche g Additionswerte.
Wenn du magst kann ich dir auch den Java-Code zuschicken, aber ich finde ich lerne am Besten durch ausprobieren.

 

[Krypthor]

Würde mich freuen wenn du mir das schicken könntest, natürlich werd ichs erstmal so ausprobieren,
nur dann kann ich gleich nach Fehlern suchen wenn meins nicht ganz funktioniert.

 

[Landei]

A*Algorythmus

<klugs*****>
... hat mit Rhythmus rein gar nichts zu tun, sondern mit dem lateinisierten Version von "al-Chwarizmi" (von dem ein damals populäres Rechenbuch stammte), weshalb es "Algorithmus" heißt.
</klugs*****>

 

[Apo]

Ich habe mal meinen AStern-Algorithmus hochgeladen. Ist nur ein kleines Eclipseprojekt mit Konsolenausgabe und einigen kleinen Kommentaren. Aber im Zusammenhang mit meinem Tutorial sollte es verständlich sein (hoffe ich jedenfalls). Vielleicht kann es ja jemand gebrauchen.