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:
- Movement is unrestricted in continuous space (not confined to grid moves)
- Movement cost is proportional to distance traveled
- 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.