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

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

1. 1
Rutin
47
2. 2
3. 3
4. 4
5. 5
JoeJ
19

• 11
• 16
• 9
• 10
• 13
• ### Forum Statistics

• Total Topics
633003
• Total Posts
3009844
• ### Who's Online (See full list)

There are no registered users currently online

×