Jump to content
  • Advertisement
Sign in to follow this  
VladimirM

Pathfinding through a bunch of polygons

This topic is 2993 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

What algorithm should i use to find the shortest path from A to B in a level where the obstacles are described as convex polygons?

Share this post


Link to post
Share on other sites
Advertisement
Quote:
What algorithm should i use to find the shortest path from A to B in a level where the obstacles are described as convex polygons?
You'll most likely want to use A* as your graph search algorithm. As for how to represent the search space, there are several options:

1. Navigation mesh.

Can be non-trivial to implement, but along with the funnel algorithm, can return perfect geodesic paths. (With some extra effort, the same navigation mesh can even be used for agents of varying radius.)

2. Waypoint system.

I've also seen mention of 'polygon maps', which I believe are somewhat similar, but I haven't investigated them myself. (The impression I got though was that with a polygon map, the vertices of the polygon obstacles are treated as the graph nodes.)

3. Grid.

If you don't need perfect accuracy, you can create a grid at the appropriate resolution, and then mark cells that are covered or partially covered by a polygon as impassable. Less accurate than a navigation mesh, and may also be less efficient due to (possibly) having to examine a greater number of nodes. However, would probably be quite a bit more straightforward to implement than the alternatives.

Share this post


Link to post
Share on other sites
Do you now where I could learn more about those navigation meshes and their implementation? Or that Waypoint system? thanks

Share this post


Link to post
Share on other sites
Books like AI Wisdom are a good place to start. There are also loads of presentations from conferences like GDC... You can also download Recast/Detour and play around with it to get an understanding of the problem.

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!