D* Lite pathfinding algorithm

Anything related on how to build / improve your AI using BWAPI, BWTA, BWSAL, etc.
krasi0
Posts: 254
Joined: Thu Dec 18, 2008 12:42 pm

D* Lite pathfinding algorithm

Postby krasi0 » Thu Jan 03, 2013 9:48 pm

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
Posts: 2
Joined: Tue Jan 22, 2013 3:43 am

Re: D* Lite pathfinding algorithm

Postby telamon » Thu Jan 31, 2013 3:55 pm

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
Posts: 254
Joined: Thu Dec 18, 2008 12:42 pm

Re: D* Lite pathfinding algorithm

Postby krasi0 » Sat Feb 02, 2013 7:11 pm

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

Return to “AI development (BWAPI Bots)”

Who is online

Users browsing this forum: No registered users and 1 guest