Hi, The situation is fairly simple: Given a list of line segments, calculate the shortest path from a point A to a point B. This sounds really simple, however I am having a lot of trouble with it. My current algorithm: - Create a new line segment from point A to point B - Loop through all the line segments (or a part of them, determined by RDC/BIN/...) - If the created line intersects an existing line segment, calculate the shortest deviation (either below/above/left/right from the segment) and apply the method from 'start' to 'new point' and from 'new point' to end. To make this more clear, I've added some pseudocode:

calculate(start,end)
{
for(i->obstacles.length)
{
if(collide(start,end,obstacle))
{
newPoint = getDeviation(start,end,obstacle)
path = calc(start,newPoint)
path += newPoint
path += calc(newPoint,end)

return path

}
return start + end;
}

Can anyone point me in the right direction ? All help is welcome! :) [Edited by - DauntlessCrowd on November 13, 2008 4:00:43 PM]

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!