backend/app/heuristics/euclidean.py

"""Euclidean distance heuristic."""

import math
from typing import Tuple


def euclidean_heuristic(state: Tuple[int, int], goal: Tuple[int, int]) -> float:
    """
    Euclidean distance heuristic.

    h(n) = sqrt((x1 - x2)^2 + (y1 - y2)^2)

    Admissible: Straight-line distance is always <= actual path distance.
    Since we can only move in cardinal directions, this will never overestimate the actual cost.

    Args:
        state: Current position (x, y)
        goal: Goal position (x, y)

    Returns:
        Estimated cost to reach goal
    """
    if goal is None:
        return 0.0
    return math.sqrt((state[0] - goal[0]) ** 2 + (state[1] - goal[1]) ** 2)