Introduction

Adding teleporters to a grid makes A* more interesting because the obvious distance-to-goal estimate is no longer always safe or useful. A good heuristic still has to be admissible, which means it must never overestimate the true remaining path cost even when the cheapest route jumps across the map through a teleporter.

The A* Algorithm

A* evaluates each state with:

f(n) = g(n) + h(n)

Here:

• g(n) is the exact cost already paid to reach node n
• h(n) is the estimated cost from n to the goal

If h(n) is admissible, A* will still return an optimal path. If h(n) is also consistent, the search is usually easier to implement efficiently because nodes do not need to be reopened as often.

Understanding Admissible Heuristics

What Makes a Heuristic Admissible?

An admissible heuristic is any estimate that is always less than or equal to the real cheapest remaining cost.

That means:

• it can be too small
• it can be exact
• it must never be too large

In a plain four-direction grid with uniform movement cost, Manhattan distance is the standard admissible choice. In an eight-direction grid, Chebyshev distance or Euclidean distance may be appropriate depending on the movement rules.

Common Heuristic Functions on Grids

For a grid without teleporters, common choices are:

• Manhattan distance for four-direction movement
• Euclidean distance when true geometric movement cost matters
• Chebyshev distance when diagonal movement costs the same as orthogonal movement

Those heuristics are safe because they describe lower bounds on the real path cost. Teleporters complicate that because a long geometric distance might become cheap if a teleporter is nearby.

Introducing Teleporters in Grid Navigation

Teleporters act like extra edges in the graph. A teleporter may connect one location to another with:

• zero cost
• fixed cost
• or a cost smaller than walking the same distance

Once teleporters exist, a heuristic that only looks at direct geometric distance may still be admissible, but it can become weak because it ignores shortcuts that drastically reduce the real remaining cost.

Handling Teleporters in Heuristics

The safest general idea is to take the minimum of:

• the ordinary lower bound from the current cell to the goal
• every lower bound that goes through a teleporter path

In other words, if a teleporter might help, your heuristic can incorporate that possibility, but only as a lower bound.

A simple version looks like this:

1h(node) = min(
2    direct_grid_lower_bound(node, goal),
3    min over teleporters:
4        grid_lower_bound(node, teleporter_entry)
5        + teleporter_cost
6        + grid_lower_bound(teleporter_exit, goal)
7)

This remains admissible as long as each piece is itself a lower bound.

Example Scenario

Suppose:

• movement is four-directional with cost 1
• the goal is at (20, 20)
• a teleporter takes you from (2, 2) to (19, 19) at cost 0

If the current node is (0, 0), direct Manhattan distance to the goal is 40.

But a teleporter-aware lower bound is:

1distance to entry: 4
2teleport cost: 0
3distance from exit to goal: 2
4total lower bound through teleporter: 6

So an admissible heuristic could return min(40, 6), which is 6. That is far more informative than pretending the goal is always 40 steps away.

Integrating Teleporters into A*

The cleanest implementation is to treat teleporters as normal graph transitions and then compute a heuristic that knows about them.

For a small number of teleporters, you can evaluate every teleporter inside the heuristic directly:

1def manhattan(a, b):
2    return abs(a[0] - b[0]) + abs(a[1] - b[1])
3
4
5def heuristic(node, goal, teleporters):
6    best = manhattan(node, goal)
7    for entry, exit_, tele_cost in teleporters:
8        candidate = (
9            manhattan(node, entry)
10            + tele_cost
11            + manhattan(exit_, goal)
12        )
13        best = min(best, candidate)
14    return best
15
16
17goal = (20, 20)
18teleporters = [((2, 2), (19, 19), 0)]
19print(heuristic((0, 0), goal, teleporters))

For many teleporters, it can be better to precompute shortest-path distances between teleporter endpoints and the goal so the heuristic remains cheap to evaluate.

The main design rule is simple: teleporters belong in the graph expansion logic, and their lower-bound effect can also be included in the heuristic.

Common Pitfalls

The biggest mistake is using ordinary Manhattan distance as if teleporters did not exist and then trying to "correct" it with a bonus or penalty that is not mathematically safe. If that adjustment overshoots, the heuristic stops being admissible.

Another mistake is forgetting that the cost to reach the teleporter entry still matters. A teleporter on the far side of a wall is not a free shortcut unless the path to that entry is also feasible and cheap.

People also sometimes hardcode heuristics for one teleporter and break correctness once multiple teleporters or chained teleporters are introduced.

Finally, admissible is not the same as strong. A heuristic can be perfectly admissible and still too weak to help much. The goal is to stay admissible while incorporating as much teleporter structure as possible.

Summary

• A* stays optimal only if the heuristic never overestimates the remaining cost.
• On teleporter grids, plain geometric distance is often safe but weak.
• A stronger admissible heuristic is the minimum of direct distance and lower bounds through teleporters.
• Teleporters should be modeled as actual graph edges during expansion.
• The best heuristic design is usually a lower bound that explicitly includes possible teleporter routes.