A* pathfinding without a grid or graph
Author
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?
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.
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.
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.
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
