Hey guys,

Those of you who follow the Thermite3D twitter feed will know that I've been doing some work on pathfinding recently. I started off implementing the famous A* algorithm in Thermite3D, but eventually decided that it would be useful at a lower level and so have moved most of the code across to PolyVox. Hopefully this will be useful to some of you.

If you are not familiar with the A* algorithm then don't worry, neither was I until I read this excellent guide:

http://theory.stanford.edu/~amitp/GameProgramming/

Most of what I have implemented in the new AStarPathfinder class is based on the information in those pages. It's basically a popular way of finding a path between two points is a world while avoiding obstacles and adhering to other user-specified criteria. In our case the world is a volume, and the path is simply a list of voxels which can be passed through in order to get from the start point to the finish point.

I'm quite happy with the implementation though there may be more work that can be done to improve the speed. It's typically taking a few seconds to find the path, but this varies a lot depending on the size of the volumes, number of obstacles, etc.

I hope it works for you guys using VS2008 with Boost - I have started making use of std::function and std::hash for which I believe Boost provides equivelents. I've put in what I hope are the correct includes/defines to make it work with Boost but this is largely untested. Let me know if you have any problems/changes.

Oh, and I've even written some basic API documentation here:

http://www.thermite3d.org/resources/documentation/polyvox/library/doc/html/class_poly_vox_1_1_a_star_pathfinder.html
http://www.thermite3d.org/resources/documentation/polyvox/library/doc/html/struct_poly_vox_1_1_a_star_pathfinder_params.html

Ok, next I'm going to get a wiki up and running. Should be just a couple of days.

I will definitely check it out later.

Great, I know you were interested in A* at one point (along with other AI approaches) so I hope you find it useful. But I know from your blog that you have a lot of other priorities at the moment, and so I guess it might be a while before you look at this.

I'm using it in Thermite and it's working quite nicely. I have some post-processing of the path in Thermite, where I throw away 90% of the points and then interpolate between the remainder using Catmull-Rom splines. It works well as a method of getting smooth paths.

Doesn't work on OpenSUSE 11.3 with boost.. Had to comment it out from the cmake files.

I fixed a problem here yeaterday... you'll probably find it's working now.

I integrated the A* module into my game. You can find a short video here:

http://www.youtube.com/watch?v=C8y0OzL0 ... False&hd=1

It's really easy to use. Just will find everything you need to get started just by looking at the header file for the A* module.

My god, how do you guys work so fast? Are you all programming geniuses, or am I just slow as hell? I only program about 2 hours per day after work and it seems to be taking me forever to get anywhere....

Anyway on topic... interesting stuff. Nice demo beyzend.

It feels like that to everyone! Especially when you have a few hours and don't feel like programming and then feel like you wasted the day when it comes to your projects, bah!

Let's just say I have a lot of free time right now.

Add: Not only that. I'm using a bunch of libs. Like the great PolyVox! Also Ogre3d, Bullet Physics, etc. Not to mention the base for my engine is something I've been working on since 2009.

Very cool! I'm glad to have someone else testing this and that it seems to work out for you.