dungeon: refactor astar to not be generic

5 files changed, 63 insertions, 232 deletions

diff --git a/dungeon/Cargo.toml b/dungeon/Cargo.toml
index 2e2e66c..906058d 100644
--- a/dungeon/Cargo.toml
+++ b/dungeon/Cargo.toml
@@ -8,7 +8,6 @@ publish.workspace = true
 rust-version.workspace = true
 
 [dependencies]
-ordered-float = "5.1.0"
 rand.workspace = true
 strum.workspace = true
 strum_macros.workspace = true
diff --git a/dungeon/src/astar.rs b/dungeon/src/astar.rs
index cfab5c4..a2ae4d3 100644
--- a/dungeon/src/astar.rs
+++ b/dungeon/src/astar.rs
@@ -1,248 +1,70 @@
-use ordered_float::OrderedFloat;
 use std::{
 	collections::{BinaryHeap, HashMap},
 	hash::Hash,
-	ops::Add,
 };
 
-/// Module for grid node implementation
-/// Uses lifetime-bound references to the grid for obstacle checking
-mod node {
-	use crate::Pos;
-	use crate::astar::OrderedFloat;
+use crate::{Floor, Pos};
 
-	use crate::Direction;
-	use crate::Tile;
-	use std::hash::Hash;
-
-	/// Implementation of a simple grid node for demonstration
-	#[derive(Clone, Copy)]
-	pub struct NodeStruct<'a> {
-		pub pos: Pos,
-		grid: &'a [Tile],
-	}
-	impl<'a> NodeStruct<'a> {
-		pub fn new(pos: Pos, grid: &'a [Tile]) -> Self {
-			Self { pos, grid }
-		}
-
-		/// Step the node in a given direction, returning None if out of bounds or obstacle
-		fn step(self, dir: Direction) -> Option<Self> {
-			let pos = self.pos.step(dir)?;
-			if self.grid[pos.idx()].is_wall() {
-				return None;
-			}
-
-			Some(Self {
-				pos,
-				grid: self.grid,
-			})
-		}
-	}
-
-	impl PartialEq for NodeStruct<'_> {
-		fn eq(&self, other: &Self) -> bool {
-			self.pos == other.pos
-		}
-	}
-	impl Eq for NodeStruct<'_> {}
-
-	impl PartialOrd for NodeStruct<'_> {
-		fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
-			Some(self.cmp(other))
-		}
-	}
-	impl Ord for NodeStruct<'_> {
-		fn cmp(&self, other: &Self) -> std::cmp::Ordering {
-			self.pos.cmp(&other.pos)
-		}
-	}
-
-	impl Hash for NodeStruct<'_> {
-		fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
-			self.pos.hash(state);
-		}
-	}
-
-	impl crate::astar::Node<OrderedFloat<f64>> for NodeStruct<'_> {
-		/// Get neighbors of this node with their movement costs
-		fn neighbors(&self) -> impl IntoIterator<Item = (Self, OrderedFloat<f64>)> {
-			use Direction as D;
-			[
-				self.step(D::North),
-				self.step(D::South),
-				self.step(D::East),
-				self.step(D::West),
-			]
-			.into_iter()
-			.flatten()
-			.map(|node| (node, OrderedFloat(1.0)))
-		}
-	}
+#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
+struct Node {
+	estimated_cost: u16,
+	cost: u16,
+	pos: Pos,
 }
-use node::NodeStruct;
-
-/// Trait representing a node in the graph
-pub trait Node<C>
-where
-	Self: Sized,
-{
-	/// Get neighbors of this node with their movement costs
-	/// Returns an iterator of (neighbor_node, cost) pairs
-	fn neighbors(&self) -> impl IntoIterator<Item = (Self, C)>;
-}
-
-mod state {
-	use super::Node;
-	use std::cmp::Ordering;
-
-	/// State wrapper for priority queue ordering
-	pub struct State<N, C>
-	where
-		N: Node<C>,
-	{
-		pub cost: C,
-		pub estimated_cost: C,
-		pub node: N,
-	}
-
-	impl<N, C> Clone for State<N, C>
-	where
-		N: Node<C> + Clone,
-		C: Clone,
-	{
-		fn clone(&self) -> Self {
-			let cost = self.cost.clone();
-			let estimated_cost = self.estimated_cost.clone();
-			let node = self.node.clone();
-			Self {
-				cost,
-				estimated_cost,
-				node,
-			}
-		}
-	}
-
-	impl<N, C> Copy for State<N, C>
-	where
-		N: Node<C> + Copy,
-		C: Copy,
-	{
-	}
-
-	impl<N, C> PartialEq for State<N, C>
-	where
-		N: Node<C>,
-		C: PartialEq,
-	{
-		fn eq(&self, other: &Self) -> bool {
-			self.estimated_cost.eq(&other.estimated_cost) && self.cost.eq(&other.cost)
-		}
-	}
-
-	impl<N, C> Eq for State<N, C>
-	where
-		N: Node<C>,
-		C: Eq,
-	{
-	}
-
-	impl<N, C> PartialOrd for State<N, C>
-	where
-		N: Node<C>,
-		C: Ord,
-	{
-		fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
-			Some(self.cmp(other))
-		}
-	}
-
-	impl<N, C> Ord for State<N, C>
-	where
-		N: Node<C>,
-		C: Ord,
-	{
-		fn cmp(&self, other: &Self) -> Ordering {
-			other
-				.estimated_cost
-				.cmp(&self.estimated_cost)
-				.then_with(|| other.cost.cmp(&self.cost))
-		}
+impl PartialOrd for Node {
+	fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
+		Some(self.cmp(other))
 	}
 }
-use state::State;
-
-use crate::{Pos, Tile};
-
-pub fn find_path(grid: &[Tile], start: Pos, goal: Pos) -> Option<(Vec<Pos>, f64)> {
-	// Create nodes for astar
-	let start_node = NodeStruct::new(start, grid);
-	let goal_node = NodeStruct::new(goal, grid);
-
-	// Use closure for heuristic with lifetime-bound reference
-	let heuristic = |node: &NodeStruct| {
-		let abs_pos = node.pos.abs_diff(goal);
-		OrderedFloat((abs_pos.x() + abs_pos.y()) as f64)
-	};
-
-	// Call A* algorithm
-	astar(&start_node, &goal_node, heuristic).map(|(path, cost)| {
-		(
-			path.into_iter().map(|node| node.pos).collect(),
-			cost.into_inner(),
-		)
-	})
+impl Ord for Node {
+	fn cmp(&self, other: &Self) -> std::cmp::Ordering {
+		self.estimated_cost
+			.cmp(&other.estimated_cost)
+			.then(self.cost.cmp(&other.cost))
+			.reverse()
+	}
 }
 
 /// A* pathfinding implementation
 ///
-/// # Type Parameters
-/// * `N` - Node type implementing the Node trait
-/// * `H` - Heuristic function type (closure)
-///
 /// # Arguments
 /// * `start` - Starting node (owned)
 /// * `goal` - Goal node (borrowed reference)
-/// * `heuristic` - Heuristic function estimating cost from any node to goal
+/// * `floor` - Dungeon floor contaning all tiles
 ///
 /// # Returns
 /// * `Some((path, total_cost))` if path found
 /// * `None` if no path exists
-fn astar<N, C, H>(start: &N, goal: &N, heuristic: H) -> Option<(Vec<N>, C)>
-where
-	N: Node<C> + Eq + Hash + Clone,
-	H: Fn(&N) -> C,
-	C: Default + Add<Output = C> + Ord + Copy,
-{
+pub fn astar(start: Pos, goal: Pos, floor: &Floor) -> Option<(Vec<Pos>, u16)> {
 	// list of nodes we need to look at next (BinaryHeap for priority queue behavior)
 	let mut open_set = BinaryHeap::new();
 
 	// The best known source node to get to a
 	// destination node with minimum weight cost (HashMap for O(1) access)
-	let mut came_from: HashMap<N, N> = HashMap::new();
+	let mut came_from: HashMap<Pos, Pos> = HashMap::new();
 
 	// The current known cost to get to a given node from the start node
 	// (HashMap for O(1) access)
-	let mut known_cost_map: HashMap<N, C> = HashMap::new();
+	let mut known_cost_map: HashMap<Pos, u16> = HashMap::new();
 
 	// Initialize with start node (add to known cost map and nodes to explore)
-	known_cost_map.insert(start.clone(), C::default());
-	open_set.push(State {
-		cost: C::default(),
-		estimated_cost: C::default(),
-		node: start.clone(),
+	known_cost_map.insert(start, 0);
+	open_set.push(Node {
+		cost: 0,
+		estimated_cost: 0,
+		pos: start,
 	});
 
 	// Explore the nodes until we run out of nodes
-	while let Some(State { cost, node, .. }) = open_set.pop() {
+	while let Some(Node { cost, pos, .. }) = open_set.pop() {
 		// Goal reached! Reconstruct the path
-		if &node == goal {
-			return Some((reconstruct_path(&came_from, node), cost));
+		if pos == goal {
+			return Some((reconstruct_path(&came_from, pos), cost));
 		}
 
 		// Explore neighbors
-		for (neighbor, move_cost) in node.neighbors() {
-			let tentative_cost = cost + move_cost;
+		for neighbor in floor.neighbors(&pos) {
+			let tentative_cost = cost + 1;
 
 			// If the path we are about to take is worse then the best known so far
 			// for out neighbor, then we should not take it!
@@ -254,12 +76,12 @@ where
 
 			// We have found a better path, we should update, so
 			// our structures to reflect this
-			came_from.insert(neighbor.clone(), node.clone());
-			known_cost_map.insert(neighbor.clone(), tentative_cost);
-			open_set.push(State {
+			came_from.insert(neighbor, pos);
+			known_cost_map.insert(neighbor, tentative_cost);
+			open_set.push(Node {
 				cost: tentative_cost,
-				estimated_cost: tentative_cost + heuristic(&neighbor),
-				node: neighbor,
+				estimated_cost: tentative_cost + goal.manhattan(neighbor),
+				pos: neighbor,
 			});
 		}
 	}
@@ -268,16 +90,13 @@ where
 }
 
 /// Reconstruct path from goal to start using came_from map
-fn reconstruct_path<N, C>(came_from: &HashMap<N, N>, mut current: N) -> Vec<N>
-where
-	N: Node<C> + Eq + Hash + Clone,
-{
-	let mut path = vec![current.clone()];
+fn reconstruct_path(came_from: &HashMap<Pos, Pos>, mut current: Pos) -> Vec<Pos> {
+	let mut path = vec![current];
 
 	// Backtrack from goal to start
 	while let Some(prev) = came_from.get(&current) {
-		current = prev.clone();
-		path.push(current.clone());
+		current = *prev;
+		path.push(current);
 	}
 
 	path.reverse();
diff --git a/dungeon/src/entity.rs b/dungeon/src/entity.rs
index aa77d98..ebdd332 100644
--- a/dungeon/src/entity.rs
+++ b/dungeon/src/entity.rs
@@ -1,6 +1,6 @@
 //! The `entity` module contains structures of all entities including players and enimies.
 
-use crate::{Direction, FPos, Pos, Tile, astar, const_pos};
+use crate::{Direction, FPos, Floor, Pos, astar, const_pos};
 
 /// `PLAYER_FULL_HEALTH` is the starting health of the player entity
 pub const PLAYER_FULL_HEALTH: u32 = 10;
@@ -57,9 +57,9 @@ impl EnemyMoveState {
 		Self::Idle(0.)
 	}
 
-	pub fn new_attack(starting_pos: Pos, player_pos: Pos, tiles: &[Tile]) -> Option<Self> {
+	pub fn new_attack(starting_pos: Pos, player_pos: Pos, floor: &Floor) -> Option<Self> {
 		if player_pos.manhattan(starting_pos) < ENEMY_VISION_RADIUS {
-			let data = astar::find_path(tiles, starting_pos, player_pos)?;
+			let data = astar::astar(starting_pos, player_pos, floor)?;
 			let mut path = data.0;
 			path.reverse();
 			return Some(Self::Attack(path));
@@ -67,14 +67,14 @@ impl EnemyMoveState {
 		None
 	}
 
-	pub fn new_roam(starting_pos: Pos, tiles: &[Tile]) -> Self {
+	pub fn new_roam(starting_pos: Pos, floor: &Floor) -> Self {
 		let mut rand_dir = Direction::get_random_dir();
 		let mut rand_tiles = rand::random_range(MIN_ROAM_DIST..=MAX_ROAM_DIST);
 		let mut loop_index = 0;
 		loop {
 			if let Some(p) = starting_pos.step_by(rand_dir, rand_tiles) {
-				if !tiles[p.idx()].is_wall() {
-					if let Some(data) = astar::find_path(tiles, starting_pos, p) {
+				if !floor.get(p).is_wall() {
+					if let Some(data) = astar::astar(starting_pos, p, floor) {
 						let mut path = data.0;
 						path.reverse();
 						return Self::Roam(path);
@@ -183,10 +183,10 @@ impl Entity {
 		}
 	}
 
-	pub fn handle_movement(&mut self, player_pos: Pos, tiles: &[Tile], delta_time: f32) {
+	pub fn handle_movement(&mut self, player_pos: Pos, floor: &Floor, delta_time: f32) {
 		match &self.kind {
 			EntityKind::Zombie(move_state) => {
-				self.zombie_movement(move_state.clone(), player_pos, delta_time, tiles);
+				self.zombie_movement(move_state.clone(), player_pos, delta_time, floor);
 			}
 			EntityKind::Player => {}
 			_ => {}
@@ -198,11 +198,11 @@ impl Entity {
 		move_state: EnemyMoveState,
 		player_pos: Pos,
 		delta_time: f32,
-		tiles: &[Tile],
+		floor: &Floor,
 	) {
 		// Check if player is in range
 		if !matches!(move_state, EnemyMoveState::Attack { .. })
-			&& let Some(m_state) = EnemyMoveState::new_attack(self.pos, player_pos, tiles)
+			&& let Some(m_state) = EnemyMoveState::new_attack(self.pos, player_pos, floor)
 		{
 			self.kind = EntityKind::Zombie(m_state);
 			return;
@@ -216,7 +216,7 @@ impl Entity {
 					return;
 				}
 
-				self.kind = EntityKind::Zombie(EnemyMoveState::new_roam(self.pos, tiles));
+				self.kind = EntityKind::Zombie(EnemyMoveState::new_roam(self.pos, floor));
 			}
 			EnemyMoveState::Roam(mut moves) => {
 				let p = if let Some(p) = moves.last() {
diff --git a/dungeon/src/map.rs b/dungeon/src/map.rs
index 6daa3c7..eda467c 100644
--- a/dungeon/src/map.rs
+++ b/dungeon/src/map.rs
@@ -162,6 +162,13 @@ impl Floor {
 		&mut *self.tiles
 	}
 
+	/// Returns the neighbors of a tile inside the floor, checking
+	/// that the neighbor positions are the same tile type as in `pos`.
+	pub fn neighbors(&self, pos: &Pos) -> impl Iterator<Item = Pos> {
+		let tile = self.get(*pos);
+		pos.neighbors().filter(move |p| self.get(*p) == tile)
+	}
+
 	/// Computes the hash of the tile map
 	#[must_use]
 	pub fn hash(&self) -> u64 {
diff --git a/dungeon/src/pos.rs b/dungeon/src/pos.rs
index d31ba95..ac2d6d0 100644
--- a/dungeon/src/pos.rs
+++ b/dungeon/src/pos.rs
@@ -314,6 +314,7 @@ impl Pos {
 		Self(x, y)
 	}
 
+	/// Returns the manhattan distance between `self` and `other`
 	pub fn manhattan(self, other: Self) -> u16 {
 		let abs_diff = Self::abs_diff(self, other);
 		abs_diff.0 + abs_diff.1
@@ -343,6 +344,11 @@ impl Pos {
 		self.0 == 0 || self.0 == MAP_SIZE - 1 || self.1 == 0 || self.1 == MAP_SIZE - 1
 	}
 
+	/// Returns the cardinal neighbors of this positions
+	pub fn neighbors(&self) -> impl Iterator<Item = Self> {
+		Direction::values().filter_map(|dir| self.step(dir))
+	}
+
 	/// Returns an iterator over all possible `Pos`
 	pub fn values() -> impl Iterator<Item = Self> {
 		(0..MAP_SIZE).flat_map(|y| (0..MAP_SIZE).filter_map(move |x| Self::new(x, y)))