Course contentsShow
← Computer Science
Lesson 1007 of 2,87223. Shortest Path AlgorithmsFree lesson

Common Heuristics for Grid Graphs

Study Manhattan, Euclidean, and Chebyshev distance heuristics for pathfinding on grid-based maps.

Common Heuristics for Grid Graphs

What you'll learn: The three most popular distance-based heuristics that guide A* pathfinding efficiently across grid-based maps.

Why Heuristics Matter for Grids

When applying A* to grid-based maps (like tile-based games or navigation systems), choosing the right heuristic dramatically affects both performance and path quality. Since you've learned that heuristics estimate the cost from a node to the goal, grids offer special geometric properties we can exploit.

The Three Classic Grid Heuristics

Manhattan Distance

Imagine a taxi driving through city blocks—it can only move north, south, east, or west (4-directional movement). Manhattan distance counts the total horizontal and vertical steps:

h(n) = |x_goal - x_current| + |y_goal - y_current|

Best for: Grids where only cardinal (up/down/left/right) movement is allowed.

Euclidean Distance

This is the "straight-line" or "as-the-crow-flies" distance—literally the geometric distance formula from school:

h(n) = sqrt((x_goal - x_current)² + (y_goal - y_current)²)

Best for: Grids allowing diagonal movement in any direction, or when you want the most accurate distance estimate.

Chebyshev Distance

Think of a chess king moving: it can step one square in any direction, including diagonals. Chebyshev distance is the maximum of horizontal or vertical distance:

h(n) = max(|x_goal - x_current|, |y_goal - y_current|)

Best for: Grids where diagonal moves cost the same as cardinal moves (8-directional movement with uniform cost).

Choosing the Right One

Match your heuristic to your movement model. Using Manhattan on a grid that allows diagonals will be admissible but inefficient. Using Euclidean when only 4-directional moves are allowed might overestimate in practice.

Key Takeaway: Manhattan, Euclidean, and Chebyshev heuristics provide admissible estimates tailored to different grid movement patterns—choose based on whether your grid allows 4-directional, 8-directional, or arbitrary-angle movement.