CODEWITHSUNDEEP
algorithmpath-finding
Mafi
Mafi

Reputation: 172

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

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

Here, the shortest is way from start s to target x is

Upvotes: 0

Views: 1558

Answers (3)

Imus
Imus

Reputation: 822

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:

  1. you hit the marked spot -> the shortest path goes from start in the direction of the mark and reaches the end without teleporters.
  2. 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).

Upvotes: 0

BlueRaja - Danny Pflughoeft
BlueRaja - Danny Pflughoeft

Reputation: 86116

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.

Upvotes: 0

Jakob Borg
Jakob Borg

Reputation: 24495

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.

Upvotes: 2

Related Questions