Brauche Hilfe: Pathfinding

[Cornix]

Entschuldigung, dass ich dieses Thema wiederbeleben muss, aber ich habe noch einige Arbeiten am Pathfinding vorgenommen, unter anderem bin ich deinem (@-kd-) Tipp gefolgt und habe ein kleines Testprogramm geschrieben welches dazu dient die genauen exact- und approx Werte für jeden Node während einer Suche darzustellen.

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.
Allerdings war die Genauigkeit der Suche genauso gefallen wie die Performance stieg. Das heist die Chance nicht den kürzesten sondern lediglich einen möglichen Weg zu finden stieg.

Ich wäre euch sehr verbunden falls ihr dieses kleine Programm einmal testen könntet, euch die Ergenisse einmal anschaut und mir vielleicht sagen könnt ob ich vielleicht irgendwo einen Fehler gemacht haben muss, oder falls nicht, wie ich am besten die Gewichtung zwischen Distanz und Kosten bei der Berechnung der approx_values setzen sollte.

Hier der Download mit den benötigten DLL-Dateien um das Projekt auch ohne RTP testen zu können.
(1.58 mb)

Hier der Download ohne DLL-Dateien.
(104 kb)

Vielen Dank.

[-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.