Heuristics and Informed Search

What is a Heuristic?

Imagine you're trying to find a friend's house in an unfamiliar city. You could wander around randomly, checking every street. Or you could head toward the general direction where you know the house is—even without knowing the exact route, moving toward the destination is usually better than moving away from it.

A heuristic is exactly this: an educated guess about how far you still have to go. It answers the question, "From where I am now, roughly how far is the goal?"

We denote the heuristic function as $h(n)$, where $n$ is the current node. The value $h(n)$ estimates the cost from $n$ to the goal. A good heuristic points us in the right direction without requiring us to know the actual path.

Think of a heuristic as a compass pointing toward the goal. It doesn't tell you the exact route—there might be walls, rivers, or mountains in the way—but it gives you a sense of direction. When choosing between several paths, the one that brings you closer to the goal (according to the heuristic) is often worth exploring first.

The Power of Informed Search

Before diving into specific heuristics, let's see why they matter. Compare how an uninformed search (like BFS) explores versus an informed search that uses a heuristic.

The difference is striking. Without a heuristic, the search expands blindly in all directions. With a heuristic, it focuses on the direction that seems promising. This is the core insight: a good heuristic dramatically reduces the search space.

Common Heuristics for Grids

In grid-based pathfinding, we have three classic heuristics, each suited to different movement rules.

Manhattan Distance

Named after the grid-like street layout of Manhattan, this heuristic measures distance as if you can only move horizontally and vertically—no diagonals.

If you're at position $(2, 3)$ and the goal is at $(7, 6)$, the Manhattan distance is $|2-7| + |3-6| = 5 + 3 = 8$.

This heuristic is perfect for 4-directional movement: it tells you the minimum number of steps needed if there are no obstacles.

Euclidean Distance

This is the straight-line distance—the length of an imaginary string stretched directly from your position to the goal.

Using the same example, the Euclidean distance is $\sqrt{5^2 + 3^2} = \sqrt{34} \approx 5.83$.

Euclidean distance works well when you can move in any direction, not just along the grid lines. It's always less than or equal to the actual path length, which makes it a safe (admissible) heuristic.

Chebyshev Distance

Also called "chessboard distance," this measures how many moves a king in chess would need—moving one square in any of eight directions.

For our example, the Chebyshev distance is $\max(5, 3) = 5$.

This is the right choice for 8-directional movement where diagonal steps cost the same as cardinal steps.

Computing Heuristics Step by Step

Let's see exactly how each heuristic is calculated. Plug in your own coordinates and watch the math unfold.

Visualizing Heuristic Values

Different heuristics assign different "distances" to the same cells. Let's see how each heuristic views the grid from a goal's perspective.

The colors form a gradient from the goal (green) outward (red). The contour lines connect cells with equal h-values—like elevation lines on a topographic map. This "distance landscape" guides the search algorithm toward lower values.

Comparing the Heuristics

Let's see all three heuristics side by side on the same grid, with the same goal position.

Notice the distinct patterns:

• Manhattan creates a diamond shape centered on the goal
• Euclidean creates circular contours
• Chebyshev creates square contours

Each shape reflects the underlying assumption about how you can move through the grid. The animated overlay shows these characteristic shapes clearly.

Admissibility

Here's a critical property: a heuristic is admissible if it never overestimates the true distance to the goal.

Why does this matter? When we use an admissible heuristic with A*, we're guaranteed to find the optimal path. If we overestimate, we might skip the best route because we wrongly think it's too long.

Consider the three heuristics for 4-directional movement:

• Manhattan: Exactly right. It's the minimum steps needed, so it never overestimates.
• Euclidean: Always admissible. A straight line is the shortest possible distance, so actual paths can only be longer.
• Chebyshev: Can overestimate! It assumes you can move diagonally, but in 4-directional movement, diagonal moves take 2 steps, not 1.

When a heuristic overestimates, it can mislead A* into finding suboptimal paths. The visualization shows both the optimal path and the suboptimal path that an overestimating heuristic might lead to. Notice how the "Fix It" button restores admissibility.

Understanding "Never Overestimate"

To build intuition for admissibility, let's think about it in 3D. Imagine the actual path through a grid as a road that goes around obstacles. The heuristic is the straight-line distance—a bird flying directly to the goal.

The bird's path is always shorter than (or equal to) the road. That's why Euclidean distance is always admissible: the direct path through the air can never be longer than any path that has to go around obstacles.

The surface height represents heuristic values—cells near the goal are low (like valleys), cells far away are high (like peaks). The green dashed line shows the straight-line heuristic estimate, while the red line traces the actual path. No matter how the path winds around, it can never be shorter than that straight line.

The Trade-off

Not all heuristics are created equal. A more informed heuristic (one that gives estimates closer to the true distance) will help the search algorithm explore fewer nodes. But computing that heuristic takes time.

Consider the extremes:

• $h(n) = 0$ is always admissible but useless. The search has no guidance and explores blindly (becoming Dijkstra's algorithm).
• $h(n) =$ true distance would be perfect guidance, but if we knew the true distance, we wouldn't need to search!

The art is finding a heuristic that's:

1. Fast to compute — We'll evaluate it for many nodes
2. Informative — Guides the search toward the goal
3. Admissible — Guarantees optimal paths (if that's required)

For grid-based games, Manhattan distance hits the sweet spot: it's trivial to compute, provides good guidance, and is admissible for 4-directional movement.

Key Takeaways

• A heuristic estimates the remaining distance from a node to the goal, guiding the search toward promising directions
• Informed search can explore dramatically fewer cells than uninformed search
• Manhattan distance ($|Δx| + |Δy|$) is ideal for 4-directional grids, forming diamond-shaped contours
• Euclidean distance ($\sqrt{Δx^2 + Δy^2}$) works for any-angle movement, forming circular contours, and is always admissible
• Chebyshev distance ($\max(|Δx|, |Δy|)$) fits 8-directional grids with equal diagonal cost, forming square contours
• An admissible heuristic never overestimates, guaranteeing optimal paths with A*—overestimating can lead to suboptimal solutions
• Better heuristics explore fewer nodes, but there's a trade-off between heuristic quality and computation cost