backend/app/heuristics/manhattan.py

"""Manhattan distance heuristic."""

from typing import Tuple


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

    h(n) = |x1 - x2| + |y1 - y2|

    Admissible: Assumes minimum cost of 1 per step, which is the minimum possible traffic level.

    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 abs(state[0] - goal[0]) + abs(state[1] - goal[1])