Page 1 of 1

D* Lite pathfinding algorithm

Posted: Thu Jan 03, 2013 9:48 pm
by 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.

Re: D* Lite pathfinding algorithm

Posted: Thu Jan 31, 2013 3:55 pm
by 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.

Re: D* Lite pathfinding algorithm

Posted: Sat Feb 02, 2013 7:11 pm
by 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