Jump to content
  • Advertisement
Sign in to follow this  
dv

A* pathfinding without a grid or graph

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

Hello, I am trying to use A* in a continuous 2D environment. It contains rectangles, which are the blockers. However, all positions are floating point numbers, and no grid or graph exists - just a list of blockers. Now, how could I solve this? Discretization of the environment has the potential pitfall of passages that are so narrow they dont fully fill a grid cell. I can't find anything about "continuous A*" in the net, and related threads in gd.net so far didn't help (they ultimately resorted to discretization). Does anybody have some insight in this?

Share this post


Link to post
Share on other sites
Advertisement
just turn the scene into a graph. you can easily do this with something like a bsp tree. but since your just using rectangles, there are probably even easier options. if they are axis alignged rects, it should be trivial.

Share this post


Link to post
Share on other sites
Expand each rectangle by a small amount and use those expanded vertices as path nodes. Make connections between every point that has clear visibility with every other point. This is called points of visibility, and is a simple way to generate a path graph, particularly for the situation you describe.

Share this post


Link to post
Share on other sites
A* is inherently graph/grid based. if there is no graph then what is a step? If a step is some distance X then you have just made a grid of blocks sized X. If you have non concave geometry then just heading in the right direction and sliding around obstacles should be good enough.

Share this post


Link to post
Share on other sites
A* is a graph search algorithm. Either find a way to make a navigation graph (there are various algorithms to do this) or use a different algorithm.

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!