diff options
| -rw-r--r-- | Cargo.lock | 25 | ||||
| -rw-r--r-- | dungeon/Cargo.toml | 1 | ||||
| -rw-r--r-- | dungeon/src/astar.rs | 285 | ||||
| -rw-r--r-- | dungeon/src/enemy.rs | 150 | ||||
| -rw-r--r-- | dungeon/src/lib.rs | 4 | ||||
| -rw-r--r-- | dungeon/src/pos.rs | 31 | ||||
| -rw-r--r-- | game/src/main.rs | 9 |
7 files changed, 493 insertions, 12 deletions
@@ -12,6 +12,12 @@ dependencies = [ ] [[package]] +name = "autocfg" +version = "1.5.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "c08606f8c3cbf4ce6ec8e28fb0014a2c086708fe954eaa885384a6165172e7e8" + +[[package]] name = "bindgen" version = "0.70.1" source = "registry+https://github.com/rust-lang/crates.io-index" @@ -86,6 +92,7 @@ dependencies = [ name = "dungeon" version = "0.1.0" dependencies = [ + "ordered-float", "rand", "strum", "strum_macros", @@ -197,6 +204,24 @@ dependencies = [ ] [[package]] +name = "num-traits" +version = "0.2.19" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "071dfc062690e90b734c0b2273ce72ad0ffa95f0c74596bc250dcfd960262841" +dependencies = [ + "autocfg", +] + +[[package]] +name = "ordered-float" +version = "5.1.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "7f4779c6901a562440c3786d08192c6fbda7c1c2060edd10006b05ee35d10f2d" +dependencies = [ + "num-traits", +] + +[[package]] name = "paste" version = "1.0.15" source = "registry+https://github.com/rust-lang/crates.io-index" diff --git a/dungeon/Cargo.toml b/dungeon/Cargo.toml index 906058d..2e2e66c 100644 --- a/dungeon/Cargo.toml +++ b/dungeon/Cargo.toml @@ -8,6 +8,7 @@ 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 new file mode 100644 index 0000000..cfab5c4 --- /dev/null +++ b/dungeon/src/astar.rs @@ -0,0 +1,285 @@ +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::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))) + } + } +} +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)) + } + } +} +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(), + ) + }) +} + +/// 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 +/// +/// # 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, +{ + // 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(); + + // 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(); + + // 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(), + }); + + // Explore the nodes until we run out of nodes + while let Some(State { cost, node, .. }) = open_set.pop() { + // Goal reached! Reconstruct the path + if &node == goal { + return Some((reconstruct_path(&came_from, node), cost)); + } + + // Explore neighbors + for (neighbor, move_cost) in node.neighbors() { + let tentative_cost = cost + move_cost; + + // 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! + if let Some(known_cost) = known_cost_map.get(&neighbor) + && *known_cost <= tentative_cost + { + continue; + } + + // 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 { + cost: tentative_cost, + estimated_cost: tentative_cost + heuristic(&neighbor), + node: neighbor, + }); + } + } + + None // No path found +} + +/// 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()]; + + // Backtrack from goal to start + while let Some(prev) = came_from.get(¤t) { + current = prev.clone(); + path.push(current.clone()); + } + + path.reverse(); + path +} diff --git a/dungeon/src/enemy.rs b/dungeon/src/enemy.rs index 44fa764..0d432dd 100644 --- a/dungeon/src/enemy.rs +++ b/dungeon/src/enemy.rs @@ -1,24 +1,80 @@ -use crate::{Entity, EntityMoveSpeed, Pos}; +use crate::{Direction, Entity, EntityMoveSpeed, Pos, Tile, astar}; + +pub const MIN_ROAM_DIST: u16 = 1; +pub const MAX_ROAM_DIST: u16 = 4; pub const ZOMBIE_HEALTH: u32 = 50; +pub const ENEMY_VISION_RADIUS: u16 = 5; + +pub const IDLE_WAIT: f32 = 1.; + +#[derive(Clone, Debug, PartialEq)] +pub enum EnemyMoveState { + Idle(f32), + Roam(Vec<Pos>), + Attack(Vec<Pos>), +} -#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)] +impl EnemyMoveState { + pub fn new_idle() -> Self { + Self::Idle(0.) + } + + pub fn new_attack(starting_pos: Pos, player_pos: Pos, tiles: &[Tile]) -> Option<Self> { + if player_pos.manhattan(starting_pos) < ENEMY_VISION_RADIUS { + let data = astar::find_path(tiles, starting_pos, player_pos)?; + let mut path = data.0; + path.reverse(); + return Some(Self::Attack(path)); + } + None + } + + pub fn new_roam(starting_pos: Pos, tiles: &[Tile]) -> 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) { + let mut path = data.0; + path.reverse(); + return Self::Roam(path); + } + } + } + + rand_dir = Direction::get_random_dir(); + rand_tiles = rand::random_range(MIN_ROAM_DIST..=MAX_ROAM_DIST); + + // Safety check + loop_index += 1; + assert!( + loop_index < 100, + "EnemyMoveState::new_roam couldn't find a valid spot around {starting_pos:?} in between {MIN_ROAM_DIST}-{MAX_ROAM_DIST} tiles", + ); + } + } +} + +#[derive(Clone, Debug, PartialEq, Eq)] pub enum EnemyAttackType { Melee, Ranged, } -#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)] +#[derive(Clone, Debug, PartialEq, Eq, Copy)] pub enum EnemyType { Zombie, } -#[derive(Debug, Clone, Copy, PartialEq)] +#[derive(Clone, Debug, PartialEq)] pub struct Enemy { pub entity: Entity, pub enemy_type: EnemyType, pub attack_type: EnemyAttackType, - time_acc: f32, + move_state: EnemyMoveState, } impl Enemy { @@ -40,7 +96,7 @@ impl Enemy { entity, enemy_type, attack_type, - time_acc: 0., + move_state: EnemyMoveState::new_idle(), } } @@ -53,4 +109,86 @@ impl Enemy { EnemyAttackType::Melee, ) } + + pub fn handle_movement(&mut self, player_pos: Pos, delta_time: f32, tiles: &[Tile]) { + // Check if player is in range + if !matches!(self.move_state, EnemyMoveState::Attack { .. }) + && let Some(move_state) = + EnemyMoveState::new_attack(self.entity.pos, player_pos, tiles) + { + self.move_state = move_state; + return; + } + + match &mut self.move_state { + EnemyMoveState::Idle(idle_accum) => { + *idle_accum += delta_time; + if *idle_accum < IDLE_WAIT { + return; + } + + self.move_state = EnemyMoveState::new_roam(self.entity.pos, tiles); + } + EnemyMoveState::Roam(moves) => { + let p = if let Some(p) = moves.last() { + p + } else { + self.move_state = EnemyMoveState::new_idle(); + return; + }; + + Self::movement_helper(&mut self.entity, *p, moves, delta_time); + } + EnemyMoveState::Attack(moves) => { + // Stop at one move left so the enemy is flush with the player tile + if moves.len() == 1 { + return; + } + + Self::movement_helper( + &mut self.entity, + *moves.last().unwrap_or(&Pos::default()), + moves, + delta_time, + ); + } + } + } + + fn movement_helper( + entity: &mut Entity, + next_move: Pos, + moves: &mut Vec<Pos>, + delta_time: f32, + ) { + if entity.pos.y() > next_move.y() { + entity.move_by_dir(Direction::North, delta_time); + if entity.fpos.y() <= next_move.y() as f32 { + if let Some(p) = moves.pop() { + entity.pos = p; + } + } + } else if entity.pos.y() < next_move.y() { + entity.move_by_dir(Direction::South, delta_time); + if entity.fpos.y() >= next_move.y() as f32 { + if let Some(p) = moves.pop() { + entity.pos = p; + } + } + } else if entity.pos.x() < next_move.x() { + entity.move_by_dir(Direction::East, delta_time); + if entity.fpos.x() >= next_move.x() as f32 { + if let Some(p) = moves.pop() { + entity.pos = p; + } + } + } else { + entity.move_by_dir(Direction::West, delta_time); + if entity.fpos.x() <= next_move.x() as f32 { + if let Some(p) = moves.pop() { + entity.pos = p; + } + } + }; + } } diff --git a/dungeon/src/lib.rs b/dungeon/src/lib.rs index ee61632..cb57bf0 100644 --- a/dungeon/src/lib.rs +++ b/dungeon/src/lib.rs @@ -1,6 +1,7 @@ //! The `dungon` crate contains the core functionality for //! interacting with a `Dungeon` and its components. +pub mod astar; pub mod bsp; pub mod enemy; pub mod entity; @@ -69,8 +70,7 @@ impl From<Floor> for Dungeon { // TODO: initalize rest of game state - // TODO: How will we randomize enemy type/number per floor? - // For now, just create one enemy a few tiles to the right of the player + // TODO: Randomize enemy positions/types let enemies = vec![Enemy::new( EnemyType::Zombie, Pos::new(player.entity.pos.x() + 4, player.entity.pos.y()) diff --git a/dungeon/src/pos.rs b/dungeon/src/pos.rs index 2682261..a7b6080 100644 --- a/dungeon/src/pos.rs +++ b/dungeon/src/pos.rs @@ -5,6 +5,11 @@ use strum::IntoEnumIterator; use strum_macros::EnumIter; +use rand::{ + Rng, + distr::{Distribution, StandardUniform}, +}; + use std::ops::{AddAssign, SubAssign}; use crate::{MAP_SIZE_USIZE, map::MAP_SIZE}; @@ -44,6 +49,22 @@ impl Direction { pub fn values() -> impl Iterator<Item = Self> { Self::iter() } + + pub fn get_random_dir() -> Self { + rand::random() + } +} + +impl Distribution<Direction> for StandardUniform { + fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> Direction { + // match rng.gen_range(0, 3) { // rand 0.5, 0.6, 0.7 + match rng.random_range(0..=3) { + 0 => Direction::North, + 1 => Direction::East, + 2 => Direction::South, + _ => Direction::West, + } + } } /// The `Pos` type represents a 2D position inside the dungeon grid. @@ -280,6 +301,11 @@ impl Pos { Self(x, y) } + pub fn manhattan(self, other: Self) -> u16 { + let abs_diff = Self::abs_diff(self, other); + abs_diff.0 + abs_diff.1 + } + /// Returns of the given position is on the border of the map /// /// ``` @@ -473,6 +499,11 @@ impl FPos { let y = (self.1 - other.1).abs(); Self(x, y) } + + pub fn manhattan(self, other: Self) -> f32 { + let abs_diff = Self::abs_diff(self, other); + abs_diff.0 + abs_diff.1 + } } impl Default for FPos { /// Returns a default postion at the origin (0,0) diff --git a/game/src/main.rs b/game/src/main.rs index f26ece4..919e22c 100644 --- a/game/src/main.rs +++ b/game/src/main.rs @@ -11,11 +11,12 @@ fn main() -> Result<()> { while window.is_open() { // TODO update game state - // Enemy Tick for enemy in dungeon.enemies.iter_mut() { - enemy - .entity - .move_by_dir(Direction::West, window.delta_time()); + enemy.handle_movement( + dungeon.player.entity.pos, + window.delta_time(), + dungeon.floor.tiles_mut(), + ); } // Draw a single frame |