///|
/// A 2D coordinate point on the grid.
/// Origin (0, 0) is top-left; x increases right, y increases down.
pub struct Point {
  x : Int
  y : Int
} derive(Debug, Eq, Compare)

///|
/// Creates a new Point.
pub fn Point::new(x : Int, y : Int) -> Point {
  { x, y }
}

///|
/// Returns the string representation "(x, y)".
pub fn Point::to_string(self : Point) -> String {
  "(" + self.x.to_string() + ", " + self.y.to_string() + ")"
}

///|
/// Terrain type for each grid cell.
pub(all) enum Cell {
  /// Traversable terrain with cost 1.
  Empty
  /// Impassable obstacle.
  Blocked
  /// Weighted terrain with a custom traversal cost (>= 1).
  Weighted(Int)
} derive(Debug, Eq)

///|
/// Returns the traversal cost for this cell.
/// Empty = 1.0, Blocked = -1.0 (sentinel), Weighted(c) = c as Double.
pub fn Cell::cost(self : Cell) -> Double {
  match self {
    Empty => 1.0
    Blocked => -1.0
    Weighted(c) => if c >= 1 { c.to_double() } else { -1.0 }
  }
}

///|
/// Returns true if this cell is passable (not blocked).
pub fn Cell::is_passable(self : Cell) -> Bool {
  match self {
    Empty => true
    Blocked => false
    Weighted(c) => c >= 1
  }
}

///|
/// Returns whether this value is a valid grid cell.
/// Weighted terrain must have a strictly positive traversal cost.
pub fn Cell::is_valid(self : Cell) -> Bool {
  match self {
    Weighted(cost) => cost >= 1
    _ => true
  }
}

///|
/// Movement mode for neighbor generation.
pub(all) enum Movement {
  /// Only cardinal directions (N, S, E, W) — 4 neighbors.
  FourWay
  /// Cardinal + diagonal directions — 8 neighbors.
  EightWay
} derive(Debug, Eq)

///|
/// A heuristic function estimates the cost from a point to the goal.
///
/// Common choices are Manhattan, Euclidean, and Chebyshev distance.
pub type Heuristic = (Point, Point) -> Double

///|
/// Configuration for a pathfinding search.
pub struct SearchOptions {
  movement : Movement
  heuristic : Heuristic
}

///|
/// Creates default A* options (four-way movement with Manhattan distance).
pub fn SearchOptions::default() -> SearchOptions {
  SearchOptions::four_way()
}

///|
/// Creates the recommended options for four-way movement.
pub fn SearchOptions::four_way() -> SearchOptions {
  { movement: Movement::FourWay, heuristic: manhattan }
}

///|
/// Creates the recommended options for eight-way movement.
pub fn SearchOptions::eight_way() -> SearchOptions {
  { movement: Movement::EightWay, heuristic: octile }
}

///|
/// Creates custom search options.
///
/// For optimal paths, the heuristic must be deterministic, finite,
/// non-negative, zero at the goal, and admissible for the movement model.
pub fn SearchOptions::new(
  movement : Movement,
  heuristic : Heuristic,
) -> SearchOptions {
  { movement, heuristic }
}

///|
/// Result of a pathfinding search.
pub struct SearchResult {
  /// The found path from start to goal, or None if unreachable.
  path : Array[Point]?
  /// Total accumulated cost along the path.
  total_cost : Double
  /// Number of distinct nodes discovered, including the start node.
  nodes_visited : Int
  /// Number of neighbor-generation events (the goal is excluded). A node that
  /// is reopened by an inconsistent custom heuristic can count more than once.
  nodes_expanded : Int
} derive(Debug)

///|
/// Creates a successful search result.
fn SearchResult::success(
  path : Array[Point],
  total_cost : Double,
  nodes_visited : Int,
  nodes_expanded : Int,
) -> SearchResult {
  { path: Some(path), total_cost, nodes_visited, nodes_expanded }
}

///|
/// Creates a failed search result (no path found).
fn SearchResult::failure(
  nodes_visited : Int,
  nodes_expanded : Int,
) -> SearchResult {
  { path: None, total_cost: -1.0, nodes_visited, nodes_expanded }
}

///|
/// Returns true if a valid path was found.
pub fn SearchResult::found(self : SearchResult) -> Bool {
  match self.path {
    Some(_) => true
    None => false
  }
}

///|
/// Returns the number of moves in the path, or -1 when no path was found.
pub fn SearchResult::steps(self : SearchResult) -> Int {
  match self.path {
    Some(path) => path.length() - 1
    None => -1
  }
}