Shortest path between points, avoiding line segments

This doesn't necessarily give you the shortest path. Consider:

           * B--------------- y          ----- x           * A

Your approach, if it processes x and then y, will move left, then right, then left (but the optimal solution is right, then forward, then left). This is because when considering segment x, you don't consider the impact of segment y on the final path. So, you must allow backtracking in your algorithm if you're looking for a shortest path.

I would suggest using A* on the graph formed by the ends of the segments (as vertices) and the lines between these ends that don't intersect any segments (as the edges). There's a simple optimization you can add to lazy-evaluate segment intersections for edges you didn't visit yet just in case you don't need to test them.

Yeah, sorry, I knew that it wouldn't work, precisely for the reason you just said, but I couldn't find a better way.

A* would of course work, but the timecomplexity would become huge: The general idea is that all segments are 'passed' by an NPC in a specific order. This means that I have to find the shortest path between (n-1) line segments. Every 'shortest path calculation' would require n*n paths to be added to a graph. In total, this would be n*n*(n-1) and that doesn't even include running the A* algorithm...

Isn't there another way ?

Quote:

Original post by DauntlessCrowd A* would of course work, but the timecomplexity would become huge: The general idea is that all segments are 'passed' by an NPC in a specific order. This means that I have to find the shortest path between (n-1) line segments. Every 'shortest path calculation' would require n*n paths to be added to a graph.

In A* you most often expand the nodes only as you travel through them, i.e. if you have a 2D grid, you don't add each square to the search, but add them whenever you visit a node. Just do the same here.
Suppose you're travelling from start point A to finish point B, and the you've got N line segments, x_i->y_i. When you expand a node at an arbitrary point C (point A to start with), check the intersection of the line C->B with all the lines x_i->y_i (to optimize, you can forget the lines you've passed to reach C as you stated). If there is no intersection, there is a straight passable line C->B and the so-far found path A->C->B is the optimal by A*. If there is an intersection, find the first such intersection x_j->y_j. Then the neighbors of the node at point C will be the two nodes at points x_j and y_j.

Edit: Err, of course you need to iterate here. If the line C->B is obstructed by line j, then you're tasked to find if lines C->x_j and C->y_j are obstructed. If not, add x_j and y_j to be the neighbors of the point C, otherwise, there's a line x_k->y_k that obstructs, say, C->x_j. Then you need to find if C->x_k and C->y_k are unobstructed. Eventually you'll find the line endpoints that are unobstructed when viewed from C.

This kind of node expansion method will let you perform an optimal A* search without doing redundant node data structure creations. There are algorithms for calculating the intersections of several line segments at once, so you can try one of those for optimization if necessary.

Hope I managed to be clear and didn't mess the thought up too bad.

Suppose there are 3 vertical line segments with point A to the left (middle) and point B to the right (middle):

         |         |   |         |   |A    |   |   |   B         |   |         |

It will first check for a path from A to B. That path isn't possible and the first intersection is the most left segment (=1). It then checks for a path from 'the top of 1' to B. That doesn't work either so it constructs a path from 'top of 1' to 'top of 2'. BUT, It would be shorter to go directly from A to 'top of 2' and thereby completely ignoring 1.

Am I not understanding this right?

[Edited by - DauntlessCrowd on November 13, 2008 2:57:02 PM]

Ah yes, of course. You're totally correct.

To fix the expansion of nodes, instead of "If there is an intersection, find the first such intersection x_j->y_j", use "For each such intersection x_j->y_j". That *should* work, but on the other hand, you proved me wrong already once. :)

With a naive expansion method, you might end up having the same line endpoint as a neighbor several times, so you should check and prune that so you don't do extra work.

Quote:

Original post by DauntlessCrowd A* would of course work, but the timecomplexity would become huge: The general idea is that all segments are 'passed' by an NPC in a specific order. This means that I have to find the shortest path between (n-1) line segments. Every 'shortest path calculation' would require n*n paths to be added to a graph. In total, this would be n*n*(n-1) and that doesn't even include running the A* algorithm...

The point of the A* algorithm is precisely to find a path among these n*n edges without having to explore all of them.

Don't construct the graph beforehand (as that would be costly) and instead construct it when you're exploring it so that nodes you never explore will never need their nodes explored.

I am experienced with A*, but so far, I've only implemented it in TileBased environments. In those environments, it's easy to say: "tile x,y is to the right of tile x-1,y". The thing I'm having difficulties with, is the 'getNeighbors' method ("d'uh, that's what this thread is about"). I can see how a possible neighbors function would be to bruteForce all the possible target points and see if they are un-intersected, but as was discussed earlier, that's really a good / the best way.

Could someone maybe re-explain the algorithm I would need? I'm also not sure I understand your notation: Does "x_i->y_j" stand for "the top/bottom of segment j to the top/bottom of segment j" ?

Thanks for your help so far, you guys are great :)

Ok, I'll take a stab at it if I can get it clear this time.

So, you're familiar with A*, and the only question is what are the nodes in our search and to how to generate the successors of each node, right?
Let's denote the start position by A, and the finish/goal position by B. Also, let's denote by I the set of line segments given as input. x->y is the line segment with the two 2D points x and y as its endpoints.

In our search, we represent 2D points as our nodes.
We start A* with a single node that is the point A as our open set.

To generate the successors of a point/node C:

V := {B}; // V is the set of vertices we're still processing.F := {};  // F is the set of final vertices we have unobstructed visibility to.foreach(v in V)  L := the set of line segments that intersect C->v.  if (L empty)    F := F union v; // No line intersected C->v, so v is successor of C.  else // There were intersections, try travelling to their endpoints.    V := V union all the endpoints of lines in L.end foreachreturn F as the set of successors of C.

As a sanity check/numeric stability check, an endpoint of a line can't be added twice to V during the expansion. I didn't want to make the pseudo look any more complex so I omitted the check. Also, if the vertex we're currently travelling from is the endpoint of line i, skip intersecting i with itself when generating L.

Now to think of it, this formulation assumes that no two line segments in I intersect each other, and no line segments share the same endpoint. If any line segments intersect, that above naive method doesn't give correct results unless an explicit check is added (in case of input intersections, a vertex will be added twice to V so checking that will identify it).
If the input line segments form closed polygons, then this method doesn't work either (but it can be modified to do so by altering the visibility check).

The bottom idea is that the successors of a point P are all the other 2D points that P has an unobstructed visibility to. And the fact that an optimal route goes through line segment endpoints lets us go from the infinite number of points of the plane to a finite amount of cases to check.

Thank you clb, this will definitely help. I'm still reading it over and over again, but I get the idea.

The endpoints will not collide (no polygons are formed) but they can intersect. Why would a vertex from crossing segments be added twice? I can see how this would be the case if they have the same endpoint, but not when they simply cross ?

Also: "L:= the set of segments that intersect C->". Is this done by brute-forcing?

Again, thanks for your help so far!

Quote:

Original post by DauntlessCrowd The endpoints will not collide (no polygons are formed) but they can intersect. Why would a vertex from crossing segments be added twice? I can see how this would be the case if they have the same endpoint, but not when they simply cross ?

Draw the following situation:
A=(0,0)
B=(10,0)
Line L1=x_1->y_1=(0,5)->(5,-5)
Line L2=x_2->y_2=(0,-5)->(5,5)

Now, when trying to find the neighbors of A to start with, you get that both L1 and L2 intersect A->B, i.e. L := {L1, L2}. Then you pick all their endpoints for further processing, V:= {x_1, x_2, y_1, y_2}. Now A->x_1 and A->x_2 are unobstructed, and are added to F, like they are supposed to. But then, you find that L1 intersects A->y_2 and L2 intersects A->y_1, so if you don't keep any track of these additions, you'll add L1 and L2 again to L, and add the same endpoints to V again, and will end up looping forever. To break this loop, don't add to V any endpoints that have been added to it in an earlier iteration, so you'll end up discarding y_1 and y_2 from being visible from A.

Quote:

Also: "L:= the set of segments that intersect C->". Is this done by brute-forcing?

If you've got lots of lines (>50), I think you might fare better by constructing a quadtree or a 2D kD-tree to accelerate the intersection tests.
Also you might try a structure where you store the lines sorted by increasing x or y-coordinates to be quickly able to cull out lines that possibly can't intersect.
Even if doing brute-forcing, you can exploit the observation you said that after passing line i, lines 0->i-1 don't need to be considered.
It's hard to tell which of these would be the fastest in practice.

Thanks Clb, it's all clear to me now ! :)

There are several optimizations you can apply due to the nature of the problem.

A* sorts the nodes by h + g where g(X) is the shortest path from the start to X, and h(X) is the shortest possible distance from X to the end. This means that if g(Z) + h(X) > g(Y) + h(Y), you don't need to even consider X as a destination from Z until you're done with Y. And since h(X) is a constant (it's the straight-line distance from X to the end) you can sort your points by increasing h(X) and stop every expansion when you reach an h(X) that's greater than your current g(Y) + h(Y) - g(Z). Of course, you have to remember that you were computing the nodes outgoing from g(Z), and resume that computation when either Y or g(Y) changes.

The result of this is that you greatly reduce the number of useless outgoing edges from every explored node: you don't even have to think about testing if these edges intersect segments, because these edges cannot possibly be part of the shortest path even if they exist.

Another optimization is that you don't need to test for intersection until you actually explore a node. That is, for every node, you would store in the priority queue both that node (and its distance) and the edge that goes to that node. If that edge ever appears as the "next edge", you test if it is actually passable, and eliminate it if it intersects segments.

This greatly reduces the number of useless edge intersection tests: you don't really care whether an edge exists or not, until you actually need to pass through it, and you only need to pass through a small number of edges on a typical A* search.

I have a similar problem except I deal with a circle entity and line intersections or lines sharing the same point. How would I go about this?

Gamasutra article.