Another faster version of A* (2D+3D) in C#
Posted by Roy Triesscheijn on September 24th, 2011
As you might know I once wrote an A* sample for C# more than 2 years ago. The first version worked but was very slow because of a bug. The second version was faster, and a third version (made by one of the readers of this blog) was even faster.
Btw did you know that the excellent game Dysomnia shipped with (a modified) version of my C#/A* code? Ok it’s just a few lines to get people started but it’s really cool to see how people use this little start for their cool projects!
Anyway, back on topic: during my internship at Nixxes an interested co-worker (thanks Marcel!) tweaked the heuristic, removed some unnecessary checks, and added a faster way to check if a tile was processed yet.
There is not much else to say, it’s still A*, it supports 2D and 3D, it uses a MinHeap and is faster than ever! (Note: this is a pure C# solution, so it doesn’t require XNA, but it will work nicely with XNA even on WP7 and the Xbox360).
Download the latest version here
Older relevant blog posts about A* (from older to newer)
http://roy-t.nl/index.php/2009/02/24/implementing-a-path-finding-in-c-and-xna-source-code-can-we-cut-the-corner/
http://roy-t.nl/index.php/2009/07/07/new-version-a-pathfinding-in-3d/
http://roy-t.nl/index.php/2010/06/27/more-a-improvements/
September 30th, 2011 at 2:18 PM
Fantastic! About a year ago I made a dll out of your original pathfinder and used it many times for various projects but on my latest it just wasn’t cutting it for speed.
Long story short I hit the google for a replacement and here we are, you saved me again. This version is beyond fantastic. The old one would take over 4 seconds to handle my grid for each pathfind and this one does it in 6ms.
Thank you again for saving me!
September 30th, 2011 at 5:45 PM
Hey John Sams,
Wow great to hear you’re having so much fun with it. Sorry the earlier versions where so sucky in comparison
. What kind of project(s) do you use the code for? I’d love to take a look to see what you’re using it for.
December 4th, 2011 at 1:24 PM
Hi Roy, I am using a modified version of your pathfinder for a project for my Game Programming master course. What I have changed is making the position a generic type so the code is more reusable. You can read about it here and let me know what you think. Thanks, and keep up the good work
December 29th, 2011 at 12:06 AM
Hi Roy, had long wanted to test this condigo. I uploaded some videos of the prototype project to tinker with this. In my opinion an excellent code.
Thank you very much, it is a pleasure to visit this blog.
http://www.youtube.com/watch?v=QwQ8pxNlMZU&list=UUotDXSUeJbhCXGh0nTpF10A&index=2&feature=plcp
http://www.youtube.com/watch?v=JkUiw7AL1fY&list=UUotDXSUeJbhCXGh0nTpF10A&index=1&feature=plcp
February 16th, 2012 at 7:29 AM
How can I change the code so it only search in a 2D world and add weight to each point instead of 2 states block and non-block?
February 16th, 2012 at 10:49 AM
Hey Ethan,
You can just modify the array that contains all the adjacent positions, but you dont have to modify the code percee, if you just define a world with 1 height it will work perfectly. As for how to add weight to each point, I dont really understand what you would want to do with that, it would no longer be A* pathfinding if I get your meaning.
February 20th, 2012 at 12:48 AM
A* handles cost within it’s aggregate cost F = G + H (G= cost to get to that node + H= estimate to get to the goal). You add weights per node by including it in G (previous cost + current node cost)