Sign in to follow this  
dv

A* pathfinding without a grid or graph

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

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this