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.
|
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!