Brauche Hilfe: Pathfinding

[-KD-]

Die Ergenisse sind gespalten. Ich habe gemerkt, dass die Suche in manchen Fällen sehr viel schneller und kürzer sein kann falls ich die Approx-Values für jeden node nur durch die Distanz Berechnen lasse und ohne die Kosten. Allerdings wird dann nur ein Weg zum Ziel gesucht, keinesfalls der kürzeste.

Ich bin mir noch nicht sicher wie ich die Korrelation zwischen Distanz und Kosten setzen sollte um in den meisten Fällen die beste Geschwindigkeit zu erreichen denn was ich beobachten konnte war folgendes Verhalten:
War die Distanz von einem Knoten zum Zielknoten sehr viel schwerer gewichtet bei der Berechnung der approx_values dieses Knotens als die tatsächlichen Kosten um ihn zu erreichen, so war der Rechenaufwand (Die Anzahl der Knoten die überprüft wurden) in den allermeisten Fällen sehr viel geringer, je stärker die Distanz gewichtet wurde desto weniger überflüssige Überprüfungen wurden durch den Algorithmus durchgeführt.

...

Dann brauchst du kein richtiges Pathfinding. Eine einfache Tiefensuche würde sich genauso verhalten. Das Problem ist: Wenn du die Approx-Kosten einfach überschätzt (oder nur noch mit ihnen arbeitest), fängt der Algorithmus an einfach immer in Himmelsrichtung auf das Ziel zuzulaufen. Dabei ist dann völlig unerheblich welches Terrain verwendet wird.
Logischerweise ist das echte Pathfinding langsamer, weil es ja den richtigen Weg berechnet und nicht einfach nur auf das Ziel zuläuft.

Ich hab mal einen kleinen Benchmark gemacht. Die 20x15 Map als wirres Labyrinth, für das ein Pathfinder schon etwas Aufwand braucht. Start und Ziel waren in entgegengesetzten Ecken der Map. Zeit für die ganze Berechnung: 1-2 Millisekunden. Damit die FPS nicht herabsinkt müsstest du aufpassen, nicht mehr als, sagen wir 20, solcher Pathfindings pro Frame durchzuführen. Ich weiß ja nicht wie viele Events bei dir jeden Frame ein Pathfinding durchführen müssen, aber im Normalfall sollte das in Ordnung gehen. Problematischer wird es höchstens bei sehr großen Maps. Aber da würde ich, sollte es wirklich Performanceprobleme geben, zu anderen Mitteln greifen (z.B. über vorausberechnete Wegpunkte)

[Cornix]

Es soll ein RTS-Spiel werden.
Das Maximum der Karten habe ich, eher willkürlich, auf 176x176 gesetzt, an Einheiten werden sicherlich zwischen 25 bis 100 Stück die Karte gleichzeitig vorhanden sein, doch wird das Pathfinding natürlich nicht regelmäßig für jede einzelne gleichzeitig benötigt werden.
Die Karten werden in den allermeisten Fällen nur sehr wenige völlig unpassierbare Tiles besitzen, und selbst wenn es mehrere sind werden diese eher in größeren Ansammlungen in kurzer Distanz zueinander liegen, ein Meer oder ein Fluss zum Beispiel.

Aber gut, ich werde ersteinmal weiterarbeiten und die Performance am Ende der Alpha nocheinmal zum Thema erklären und im Nachhinein schauen was verbessert werden kann.