It is currently Mon Dec 16, 2019 12:14 am


All times are UTC




Post new topic Reply to topic  [ 10 posts ] 
Author Message
 Post subject: A* Pathfinding in PolyVox
PostPosted: Thu Dec 09, 2010 10:29 pm 
Developer
User avatar

Joined: Sun May 04, 2008 6:35 pm
Posts: 1827
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.


Top
Offline Profile  
Reply with quote  
 Post subject: Re: A* Pathfinding in PolyVox
PostPosted: Sat Dec 11, 2010 10:03 pm 

Joined: Sat Sep 18, 2010 9:45 pm
Posts: 189
I will definitely check it out later.


Top
Offline Profile  
Reply with quote  
 Post subject: Re: A* Pathfinding in PolyVox
PostPosted: Sat Dec 11, 2010 10:56 pm 
Developer
User avatar

Joined: Sun May 04, 2008 6:35 pm
Posts: 1827
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.


Top
Offline Profile  
Reply with quote  
 Post subject: Re: A* Pathfinding in PolyVox
PostPosted: Sun Dec 19, 2010 8:32 am 

Joined: Sun Dec 19, 2010 1:22 am
Posts: 2
Doesn't work on OpenSUSE 11.3 with boost.. Had to comment it out from the cmake files.


Top
Offline Profile  
Reply with quote  
 Post subject: Re: A* Pathfinding in PolyVox
PostPosted: Sun Dec 19, 2010 12:14 pm 
Developer
User avatar

Joined: Sun May 04, 2008 6:35 pm
Posts: 1827
elyzion wrote:
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.


Top
Offline Profile  
Reply with quote  
 Post subject: Re: A* Pathfinding in PolyVox
PostPosted: Thu Mar 10, 2011 5:52 am 

Joined: Sat Sep 18, 2010 9:45 pm
Posts: 189
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.


Top
Offline Profile  
Reply with quote  
 Post subject: Re: A* Pathfinding in PolyVox
PostPosted: Thu Mar 10, 2011 7:41 am 

Joined: Sun Jan 23, 2011 6:06 am
Posts: 92
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.


Top
Offline Profile  
Reply with quote  
 Post subject: Re: A* Pathfinding in PolyVox
PostPosted: Thu Mar 10, 2011 7:54 am 

Joined: Fri Feb 18, 2011 8:41 pm
Posts: 173
DefiniteIntegral wrote:
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!


Top
Offline Profile  
Reply with quote  
 Post subject: Re: A* Pathfinding in PolyVox
PostPosted: Thu Mar 10, 2011 4:35 pm 

Joined: Sat Sep 18, 2010 9:45 pm
Posts: 189
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.


Top
Offline Profile  
Reply with quote  
 Post subject: Re: A* Pathfinding in PolyVox
PostPosted: Thu Mar 10, 2011 8:17 pm 
Developer
User avatar

Joined: Sun May 04, 2008 6:35 pm
Posts: 1827
Very cool! I'm glad to have someone else testing this and that it seems to work out for you.


Top
Offline Profile  
Reply with quote  
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 10 posts ] 

All times are UTC


Who is online

Users browsing this forum: No registered users and 2 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
cron
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
Theme created StylerBB.net