Suppose that you have a 2D grid of cells, some of which are filled in with walls. Characters can take a step from one square to any square that is one step horizontal or vertical from it but cannot cross walls.

Given a start position and an end position, we can find the shortest path from the start position to the end position by using the A* algorithm with an admissible heuristic. In this current setup, the Manhattan distance would be admissible, since it never overestimates the distance to the destination.

Now suppose that in addition to walls, the world has pairs of teleporters. Stepping onto a teleporter immediately transports a character to the linked teleporter. The existence of teleporters breaks the admissible heuristic given above since it might be possible to get to the destination faster than taking the optimal Manhattan distance walk by using a teleporter to cut down on the distance. For example, consider this linear world with teleporters marked T, start position marked S, and end position marked E:

T.S. . . . . . . . . . . . . E.T

Here, the best route is to walk to the teleporter on the left, then take two steps to the left.

My question is this: **what is a good admissible heuristic for A* in a grid world with teleporters?**

Thanks!