CODEWITHSUNDEEP
algorithma-star
Clash
Clash

Reputation: 5025

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!

Upvotes: 3

Views: 3366

Answers (3)

Fred Foo
Fred Foo

Reputation: 363517

I think you can solve this by an A* search on a graph defined as:

  • Vertices: origin, destination and all endpoints of obstacle edges.
  • Edges (successor function): any pair of the previous where the corresponding line does not cross any obstacle's edges. A naive implementation would just check for intersection between a potential edge and all obstacle edges. A faster implementation might use some kind of 2-d ray tracing algorithm.

I.e., it's not necessary to discretize the plane into a grid, but without it, the successor function becomes difficult to define.

Upvotes: 4

JCooper
JCooper

Reputation: 6525

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.

Upvotes: 5

Bernd Elkemann
Bernd Elkemann

Reputation: 23550

A grid, and A* running through it is the way to go. All games i am aware of use A* or an adaptation of it for the global route and complement it with steering behaviour for local accuracy. Maybe you were not aware that using steering behaviour will resolve all your concerns about accuracy (search-engine it).

EDIT: i just remember a strategy game that uses flow-field. But it is not main-stream.

BTW: to get a feel for what steering behavior does for your objects take a look at the many youtube-videos about it. Some of them use the term path-finding in a more general sense: including the global algorithm (A*) as well as collision-avoidance, path-smoothing and object-inertia involved in steering-behavior.

Upvotes: 2

Related Questions