Manhattan Distance Heuristic
You'll learn: How to apply Manhattan distance as a powerful admissible heuristic for grid-based pathfinding problems.
What Is Manhattan Distance?
Manhattan distance measures the distance between two points on a grid by counting only horizontal and vertical moves—no diagonals. Imagine navigating city blocks in Manhattan, where you can't cut through buildings: you must walk along streets (horizontal) and avenues (vertical).
For two points (x₁, y₁) and (x₂, y₂), the Manhattan distance is:
h(n) = |x₁ - x₂| + |y₁ - y₂|
Why Use It as a Heuristic?
In grid-based pathfinding problems like sliding tile puzzles or maze navigation with four-directional movement, Manhattan distance provides an admissible heuristic for A* search. It never overestimates the actual cost to reach the goal because:
- You must make at least
|Δx|horizontal moves - You must make at least
|Δy|vertical moves - No shortcut through obstacles can reduce these minimum moves
Example: 8-Puzzle
In an 8-puzzle, calculate each tile's Manhattan distance from its current position to its goal position, then sum them all:
Current: 1 2 3 Goal: 1 2 3
4 _ 6 4 5 6
7 5 8 7 8 _
Tile 5: |2-1| + |1-2| = 2
Tile 6: |2-1| + |2-2| = 1
Tile 8: |2-2| + |2-0| = 2
h(state) = 2 + 1 + 2 = 5
This tells A* that we need at least 5 more moves—guiding the search efficiently toward the goal without ever being overly optimistic.
Key Takeaway: Manhattan distance is an admissible, easy-to-compute heuristic for grid-based problems with axis-aligned movement, making it ideal for guiding A* search efficiently.