/// Heuristic functions for A* pathfinding.
///
/// Each function takes two Points (current, goal) and returns
/// an estimated distance as a Double. All heuristics must be
/// **admissible** (never overestimate) for A* to produce
/// optimal paths.

///|
/// Manhattan distance: |dx| + |dy|
///
/// Admissible for four-way movement on grid maps.
/// This is the most commonly used heuristic for grid-based pathfinding.
pub fn manhattan(a : Point, b : Point) -> Double {
  let dx = (a.x.to_double() - b.x.to_double()).abs()
  let dy = (a.y.to_double() - b.y.to_double()).abs()
  dx + dy
}

///|
/// Euclidean distance: sqrt(dx^2 + dy^2)
///
/// Admissible for both four-way and eight-way movement on grid maps.
/// More accurate than Manhattan for diagonal movement but slower
/// due to the square root calculation.
pub fn euclidean(a : Point, b : Point) -> Double {
  let dx = a.x.to_double() - b.x.to_double()
  let dy = a.y.to_double() - b.y.to_double()
  (dx * dx + dy * dy).sqrt()
}

///|
/// Chebyshev distance: max(|dx|, |dy|)
///
/// Admissible for eight-way movement on grid maps where diagonal
/// moves have the same cost as cardinal moves.
pub fn chebyshev(a : Point, b : Point) -> Double {
  let dx = (a.x.to_double() - b.x.to_double()).abs()
  let dy = (a.y.to_double() - b.y.to_double()).abs()
  if dx > dy {
    dx
  } else {
    dy
  }
}

///|
/// Octile distance: |dx| + |dy| + (sqrt(2) - 2) * min(|dx|, |dy|)
///
/// Admissible for eight-way movement where diagonal moves cost √2
/// and cardinal moves cost 1. This is the most accurate admissible
/// heuristic for standard eight-way grid movement.
pub fn octile(a : Point, b : Point) -> Double {
  let dx = (a.x.to_double() - b.x.to_double()).abs()
  let dy = (a.y.to_double() - b.y.to_double()).abs()
  let sqrt2_minus_2 = 1.4142135623730951 - 2.0
  if dx < dy {
    dx + dy + sqrt2_minus_2 * dx
  } else {
    dx + dy + sqrt2_minus_2 * dy
  }
}

///|
/// Zero heuristic — turns A* into Dijkstra's algorithm.
///
/// Useful as a baseline for comparison. Always admissible
/// but provides no guidance toward the goal.
pub fn zero(_a : Point, _b : Point) -> Double {
  0.0
}