Pathfinding with teleporters

Question

I'm working on a project with a virtual robot (Turtles in the ComputerCraft mod for Minecraft), where the robot would be in a maze of tunnels and have to navigate around in them. The world is conveniently already divided into tiles (a 2D Cartesian graph of them, with a boolean passable/nonpassable value for each), and the robot building the tunnels will map them as he goes.

In addition, there are teleporter "shortcuts" scattered around in areas where robots need to get between them quickly.

The question is: What's the best way to have the robot pathfind to his destination? How would the system identify areas that need teleporters? A* is the most famous algorithm, but are there others that might suit the application better? Please keep in mind that I have very little experience with pathfinding algorithms, so you might have to break things down into base terms for me to understand. Any suggestions?

I certainly could, but I'd assume A* doesn't take "shortcuts" like the teleporters into account without a hack. I'll have to look into how to algorithm works a little bit more. — Schilcote, Feb 24 '13 at 16:54
What hack? I think A* can work with zero-length edges just fine. I'm curious. — n. m. could be an AI, Feb 24 '13 at 17:06
Hmm. I'll do some research and write an implementation. Might work out of the box, who knows. — Schilcote, Feb 24 '13 at 17:19

score 3 · Accepted Answer · edited May 23 '17 at 12:08

The only problem with using A* is finding an admissible heuristic for your problem. Fortunately, this has already been answered here.

How would the system identify areas that need teleporters?

That depends on where the turtle is actually moving to/from. If he's always moving to/from the same start/end points, the answer is trivial: add teleports at the start and finish. For more complicated setups, my guess would be that this is NP-hard; if true, you'll have to look into global-optimization strategies (or just try a bunch of random positions and take the best one).

Pathfinding with teleporters

1 Answers1