1D path finding with 'teleporters'

Problem

I want ot write a simple 1D RTS game and have the following path finding problem: There are many one-dimensional lines and everywhere are teleporters which can be used to travel between the lines but also to travel inside the current line. The teleporters are the only way to travle between lines. What algorithm or pseudo code can used to determine the shortest path between position po1 on line li1 to po2 on li2? We have a set of teleporters T (each has a po and li) which are connected with each other with a cost of zero.

Why not A* or Dijkstra-algorithm

It's because I think these would be an overkill in 1D.

Clarification

• It's maybe sounds a bit two dimensional but it isn't because you can only travel left or right on one line.
• There are costs to travel to a teleporter but teleporting from one to another has no cost. See this ascii art:

    ...0....s..0
    ......0.x...

H开发者_如何学Cere, the shortest is way from start s to target x is

• to go to the right teleporter
• teleport one line down (only in this graphic; really planes are unordered)
• and go right to the target (final cost = 5)

---

You can go from any teleporter from any other? In that case, there are only two possible ways: right and left from your starting position. Once you reach a teleporter, go the teleporter closest to the destination. Done. Ok, if you don't know which teleporter is closest to the destination, you might try them all on the same plane, but still.

---

Since moving left or right you can only hit one other teleport, you can essentially consider every teleport to be connected to the ones to the left and right of it, on either side of the teleport; so each teleport is connected to four other teleports.

This just makes a graph with each node having a max of four edges. So, just construct that graph in memory, and solve your problem using Dijkstra's algorithm (which isn't overkill, since we are no longer "in" one-dimension). This will be much faster than the brute-force algorithm suggested by @Jakob.

---

I believe you can improve on Jakob's answer by combining search from starting point with search from end point.

In your first step, start at the starting point and consider 2 search paths. A path going left and a path going right

Each iteration take a step on both paths until on one of the paths ...

1. ... you hit x (search over, this is the shortest path)
2. ... you hit a teleporter

In case (2) put a mark on the path that didn't hit a teleporter yet.

Now start from your end point x and start searching on 2 paths as well. So going left and right, 1 step each iteration. Now there are 2 possible outcomes again:

3. you hit the marked spot -> the shortest path goes from start in the direction of the mark and reaches the end without teleporters.
4. you hit a teleporter -> your shortest path goes from start to the teleporter in step (2) and then from the teleporter in step (4) towards the end x.

This will find the shortest path in 2n steps where n is the length of that path. (Since you are always looking in 2 directions).