A* 3D update
Posted by Roy Triesscheijn on Tuesday 7 July, 2009
Just a small update so to keep you all who’ve been anxiously waiting for the updated version of A* happy :).
I’ve been working on implementing A* more efficiently using a MinHeap for storage instead of Lists<> add this time I made sure that I didn’t forget the H (heuristic) part of the scoring (silly me). To give you a bit of an idea how much better the algorithm is now.
Situation 10x10x10 grid, 1/3 of the nodes blocked, find a path from 0,0,0 to 9,5,8
Old code: +-600ms (If I’d just have profiled it before I would’ve known something was wrong)
New code: 8.86ms 6.82ms 5.27ms averaged over 100 runs.
So yeah that is allot better, however when decreasing the number of blocked nodes the time goes up slightly (average 19ms for 0 nodes blocked). And I really want to get that lower, so I’ve asked some people at http://gathering.tweakers.net if they saw more room for optimalisation and there are still a few tips that I haven’t explored there. So I’ll be releasing the new (correct/fast) source code soon, but not untill I’ve made sure that I’ve cramped out all the speed that I can.
There is atleast one method that will speed everything up significantly. A player can now make a step over 3 axis at the same time (x,y,z) ofcourse that is more expensive but sometimes gives a better path, however this means that each node has to consider 26 neighbours instead of just 18. I’m playing with the idea to restrict motion a bit for a faster algorithm.
Maybe I’ll build in some different motion types for speed, best path, or some average.