Jump to content
  • Advertisement
Sign in to follow this  
Zukarakox

A* Pathfinding in 3D Environment

This topic is 3825 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I'm currently working on the theory behind the next few phases on my AI engine, but I can't figure out how to find the 'best' path. The navmesh is saved in terms of a set of convex planar polygons (nodes), each of which contain a set of edges, which hold connection info. Heres the problem -- when using A*, you obviously have to be able to tell the distance between nodes, but if I use the center of each edge, the actual distance the unit would travel between those edges could be much less, or much more than it actually is, depending on the place hes coming from and going to. I have already worked out a method to find the 'best' crossing points on edges once it has the set of nodes its going to cross, however, this method checks ahead to find the optimal path, and as such, won't work with A*. Any ideas ?:P PS: I'd like to avoid massive amounts of string-pulling :(

Share this post


Link to post
Share on other sites
Advertisement
You can get a more accurate estimate of the cost by using the cost to travel from one edge to another, instead of using the center of the polygon (which is nearly meaningless in this case). As long as the costs are close to those of the final path, A* will find a decent path. If the costs seen by A* are within a factor of 1 to 2 of the costs of the real path, A* will never suggest a path that is more than twice as long as the real optimal path.

Share this post


Link to post
Share on other sites
Already using that method, and it can return rediculously off results in some cases :
Thinking about finding the closest point on the edge to the start point, then the closest point on the next edge from that point, ect, ect. That would return equally bad results for all paths.

Share this post


Link to post
Share on other sites
Take a look at the 'Framed Quad Tree' approach... it should give you the inspiration you need. ;)

Cheers,

Timkin

Share this post


Link to post
Share on other sites
Mmmm, I dont think that'll work for me, Im using N-sided polygons, thanks for replying tho.

[Edited by - Zukarakox on February 17, 2008 3:08:22 PM]

Share this post


Link to post
Share on other sites
I wasn't implying that you directly apply the framed-quadtree... but that you use it for inspiration. N-sided polygons can still have their edges discretised and a cost matrix can be devised for crossing the polygon. It's the use of this information during your search algorithm that is most relevant and that's what you'll get out of looking at the framed-quadtree approach.

Share this post


Link to post
Share on other sites
Oh sorry, I guess I didn't look deep enough to find anything about cost matricies, I was having trouble finding a good article on it, and ended up just reading over a few that had applied it and vaguely described how it worked.

I'll take another look tommorow.

Share this post


Link to post
Share on other sites
Holler if you have any difficulties findin good information on the technique. Some articles are not accessible to the general public.

Cheers,

Timkin

Share this post


Link to post
Share on other sites
Cant find crap. :( Google searchs either end up with abstracts from books that look promising, but I can't actually access, or references to your post. Wiki/GameDev Article searches end up with great tutorials on quadtrees, but nothing about cost matricies. :P

I did find a neat article on how they made the pathfinding for the Mars drone. :)

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!