D* Lite pathfinding algorithm

[krasi0]

Due to the heavy usage of ground distance calculations for my land units (army movement, strategic positioning, etc.) I needed something faster than BWTA's A* implementation so I've searched for some top edge pathfinding algorithms and found D* Lite. I've tried to integrate two implementations in my code:

1) http://freecode.com/projects/dstar --- made it to work but it's very very slow due to the inefficient implementation. Maybe someone better at C++ will be able to optimize the code
2) https://github.com/azampagl/robotics-d-star-lite --- couldn't make it to work properly. it causes the AI module to crash for some reason. It says it's very efficient as an implementation though

So if anyone else is interested in more efficient path finding algorithms for his bot (or any other purpose) and is able to make the above to work, please share. BWTA definitely needs improvements / replacements.

[telamon]

Have you seen HPA*? The authors claim it is up to 10 times faster than A*. http://abotea.rsise.anu.edu.au/data/hpastar.pdf
I don't think that the terrain analyzer is the best place to do pathfinding. To avoid traffic problems at chokes you need the units to be aware of each other( see http://www0.cs.ucl.ac.uk/staff/D.Silver/web/Publications_files/coop-path-AIWisdom.pdf ), and the BWTA has no knowledge of the units.

[krasi0]

The authors' claims are really interesting. I'll have to write an implementation of this at some point in the future to check how it'll perform