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.
D* Lite pathfinding algorithm
-
- Posts: 2
- Joined: Tue Jan 22, 2013 3:43 am [phpBB Debug] PHP Warning: in file [ROOT]/vendor/twig/twig/lib/Twig/Extension/Core.php on line 1266: count(): Parameter must be an array or an object that implements Countable
Re: D* Lite pathfinding algorithm
Have you seen HPA*? The authors claim it is up to 10 times faster than A*.
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 ), and the BWTA has no knowledge of the units.
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 ), and the BWTA has no knowledge of the units.
-
- Posts: 254
- Joined: Thu Dec 18, 2008 12:42 pm [phpBB Debug] PHP Warning: in file [ROOT]/vendor/twig/twig/lib/Twig/Extension/Core.php on line 1266: count(): Parameter must be an array or an object that implements Countable
Re: D* Lite pathfinding algorithm
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
[phpBB Debug] PHP Warning: in file [ROOT]/vendor/twig/twig/lib/Twig/Extension/Core.php on line 1266: count(): Parameter must be an array or an object that implements Countable
Return to “AI development (BWAPI Bots)”
Who is online
Users browsing this forum: No registered users and 9 guests