No longer updated: new and updated blog (including old content) at http://roy-t.nl

Archive for http://roy-t.nl, please update your bookmarks

Posts Tagged ‘Speed’

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.

Advertisements

Posted in General Coding, General Gamedesign, XNA | Tagged: , , , | Leave a Comment »