# Künstliche Intelligenz - Pathfinding



## Krypthor (22. Mrz 2012)

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 (22. Mrz 2012)

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 (22. Mrz 2012)

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 (22. Mrz 2012)

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 (22. Mrz 2012)

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 (22. Mrz 2012)

Krypthor hat gesagt.:


> 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 (25. Mrz 2012)

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.


----------

