Course contentsShow
← Computer Science
Lesson 2757 of 2,87261. AI and Search AlgorithmsFree lesson

Euclidean Distance Heuristic

Use Euclidean distance for continuous space problems and understand when it's admissible.

Euclidean Distance Heuristic

What you'll learn: How to apply straight-line distance as a heuristic for continuous space pathfinding and when it guarantees optimal A* solutions.

The Core Idea

The Euclidean distance heuristic measures the straight-line distance between two points in continuous space, just like measuring the "as-the-crow-flies" distance on a map. For a point (x₁, y₁) to goal (x₂, y₂), it's calculated as:

h(n) = √[(x₂ - x₁)² + (y₂ - y₁)²]

This extends naturally to 3D or higher dimensions by adding more squared differences under the square root.

When Is It Admissible?

A heuristic is admissible if it never overestimates the true cost to reach the goal. Euclidean distance is admissible when:

  1. Movement is unrestricted in continuous space (not confined to grid moves)
  2. Movement cost is proportional to distance traveled
  3. There are no obstacles, or you're measuring optimistic distance ignoring them

Think of it like this: if you could walk directly to your destination through any terrain, the straight-line distance is the shortest possible path. Any actual path must be at least this long, making Euclidean distance a safe lower bound.

Euclidean vs Manhattan

Unlike Manhattan distance (which sums absolute differences, like city-block movement), Euclidean distance works beautifully for robotics, drone navigation, and continuous 2D/3D environments where diagonal or curved movements are possible. It's tighter (closer to true cost) than Manhattan when diagonal moves are allowed, making A* expand fewer nodes.

Key Takeaway: Euclidean distance heuristic uses straight-line geometry to guide search in continuous spaces and is admissible when agents can move freely and cost scales with distance—making it ideal for pathfinding in open, realistic environments.