Search code examples
algorithma-star

A* for finding shortest path and avoiding lines as obstacles

I have to get the (shortest)/(an optimal) distance between two points in 2D. I have to avoid shapes that are lines, that may be connected together. Any suggestion on how to represent the nodes I can travel on? I have thought of making a grid, but this doesn't sound very accurate or elegant. I would consider a node as unwalkable if any point of a line is inside a square (with the node being the center of the square).

enter image description here

An example would be going from point A to B.

Is the grid the recommended way to solve this? Thanks A LOT in advance!

Solution

  • I think this is essentially Larsmans' answer made a bit more algorithmic:

    Nodes of the graph are the obstacle vertices. Each internal vertex actually represents two nodes: the concave and the convex side.

    1. Push the start node onto the priority queue with a Euclidean heuristic distance.
    2. Pop the top node from the priority queue.
    3. Do a line intersection test from the node to the goal(possibly using ray-tracing data-structure techniques for speedup). If it fails,
    4. Consider a ray from the current node to every other vertex. If there are no intersections between the current node the vertex under consideration, and the vertex is convex from the perspective of the current node, add the vertex to the priority queue, sorted using the accumulated distance in the current node plus the distance from the current node to the vertex plus the heuristic distance.
    5. Return to 2.

    You have to do extra pre-processing work if there are things like 'T' junctions in the obstacles and I wouldn't be surprised to discover that it breaks in a number of cases. You might be able to make things faster by only considering the vertices of the connected component that lies between the current node and the goal.

    So in your example, after first attempting A,B, you'd push A,8, A,5, A,1, A,11, and A,2. The first nodes of consideration would be A,8, A,1, and A,5, but they can't get out and the nodes they can reach are already pushed on the queue with shorter accumulated distance. A,2 and A,11 will be considered and things will go from there.

    Modified image.