Heuristics: Manhattan vs Euclidean Distance
A heuristic is a guess about remaining cost; the right guess depends on how movement is allowed.
Motion, sensing, control loops, and plans made visible as a field of forces and trajectories.
Interactive model
Heuristic pressure changes the frontier
Toggle the demo and watch how the path frontier changes when the estimated distance changes.
Live HTML simulation · adjust the controls and watch the computed output respond.
Interactive
A* expands likely paths first instead of flooding the whole grid
Expanded 36 cells; path contains 14 cells.
This is a simplified teaching model. Its displayed values are computed from the controls; the article explains where the model stops.
Site connection
The path finder project supports taxicab and Euclidean heuristics, making this a natural comparison page.
Implemented: The project source explicitly supports taxicab and Euclidean modes. It does not document diagonal moves, terrain weights, or heuristic scaling, so those cases are taught as extensions rather than project claims.
What the Heuristic Is Doing
The heuristic does not move the agent. It ranks candidates by giving the algorithm a directional estimate.
A weak heuristic expands too much. An overconfident heuristic can become greedy and wrong.
Choosing the Distance
Manhattan distance exactly matches unobstructed unit-cost travel on a four-neighbor grid. Euclidean distance is the straight-line lower bound for movement in a plane. Both can be admissible on a four-neighbor unit grid, but Manhattan is more informed because it is never smaller there.
For eight-direction grids with cardinal cost 1 and diagonal cost √2, octile distance matches the empty-grid geometry more closely than either raw Manhattan or Euclidean.
| Movement model | Useful baseline |
|---|---|
| Four-direction, unit cost | Manhattan |
| Eight-direction, diagonal cost √2 | Octile |
| Continuous straight-line movement | Euclidean |
| Weighted terrain | A proven lower bound using minimum step cost |
Worked Example
From (1,2) to (5,5), the coordinate differences are dx=4 and dy=3. Manhattan distance is 4+3=7. Euclidean distance is √(4²+3²)=5.
On a four-neighbor unit grid, every legal path needs four horizontal and three vertical steps before obstacles, so 7 is exact in open space while 5 is a weaker lower bound. If unrestricted straight-line motion is legal, the 5-unit Euclidean segment is the relevant geometry.
A larger admissible heuristic is usually more informed, but only comparisons under the same movement and cost model are meaningful.
Scaling, Guarantees, and Limits
A heuristic is admissible when it never exceeds true remaining cost. Consistency additionally requires h(n) ≤ c(n,n′)+h(n′) for each edge. Scaling a valid heuristic upward can make it overestimate; scaling downward preserves admissibility but weakens guidance.
Terrain, one-way motion, turn penalties, and nonuniform action costs can make geometric distance poorly informed even when it remains a lower bound. Multiply geometric steps by a proven minimum per-step cost only when that bound truly applies.
The path finder source lets learners select taxicab or Euclidean distance, but does not establish which movement transitions its implementation permits. The demo should therefore make its movement model visible before claiming one heuristic is best.
Common Pitfalls
- Using Euclidean distance on a four-direction grid without checking admissibility.
- Assuming a more complex heuristic is automatically better.
- Forgetting that terrain costs can make geometric distance misleading.