Hallo zusammen,

ich plane ein Aufbaustrategiespiel. Momentan stehe ich vor der Aufgabe, ein vernünftiges, stabiles und performantes Pathfinding zu realisieren.
Die Entities können sich nur auf den Linien eines gedachten Gitters bewegen. Dieses kann man sich wie ein kariertes Blatt papier vorstellen. Die einzelnen Punkte sind dann die Schnittstellen der linien. Sie werden in einem Array (coord[x][y]) gespeichert. Links unten ist dann der Punkt 0/0 und oben rechts z.B. 200/200.

Jetzt kann jeder dieser Knotenpunkte zwei zustände einnehmen: frei oder belegt. Wenn sich eine Entity von einem Punkt zum anderen bewegen soll, muss natürlich berücksichtigt werden, dass einige dazwischen evt belegt sind. Die Aufgabe ist es nun, dass der kürzeste freie Weg gefunden wird. Dabei ist es auch sinnvoll, dass die Entity nicht unbeding immer zuerste die eine Achse entlang läuft und dann die andere. Sie soll viel mehr die Punkte ablaufen, die praktisch am nächsten an der Luftlinie liegen, soweit dies möglich ist.

Hier mal zur Veranschaulichung:


Wie realisiere ich soetwas?

Dank und Gruß
derGarv