diff options
| -rw-r--r-- | azalea/benches/pathfinder.rs | 8 | ||||
| -rw-r--r-- | azalea/src/pathfinder/mod.rs | 41 | ||||
| -rw-r--r-- | azalea/src/pathfinder/moves/basic.rs | 60 | ||||
| -rw-r--r-- | azalea/src/pathfinder/moves/mod.rs | 361 | ||||
| -rw-r--r-- | azalea/src/pathfinder/moves/parkour.rs | 66 | ||||
| -rw-r--r-- | azalea/src/pathfinder/world.rs | 353 |
6 files changed, 452 insertions, 437 deletions
diff --git a/azalea/benches/pathfinder.rs b/azalea/benches/pathfinder.rs index 5152e71d..3fb1c7b2 100644 --- a/azalea/benches/pathfinder.rs +++ b/azalea/benches/pathfinder.rs @@ -4,7 +4,7 @@ use azalea::{ pathfinder::{ astar::{self, a_star}, goals::BlockPosGoal, - moves::PathfinderCtx, + world::CachedWorld, Goal, }, BlockPos, @@ -79,13 +79,11 @@ fn bench_pathfinder(c: &mut Criterion) { b.iter(|| { let (world, start, end) = generate_bedrock_world(&mut partial_chunks, 4); - let ctx = PathfinderCtx::new(Arc::new(RwLock::new(world.into()))); + let cached_world = CachedWorld::new(Arc::new(RwLock::new(world.into()))); let goal = BlockPosGoal(end); let successors = |pos: BlockPos| { - let mut edges = Vec::with_capacity(16); - successors_fn(&mut edges, &ctx, pos); - edges + azalea::pathfinder::call_successors_fn(&cached_world, successors_fn, pos) }; let astar::Path { movements, partial } = a_star( diff --git a/azalea/src/pathfinder/mod.rs b/azalea/src/pathfinder/mod.rs index 0e7c021a..e92457b8 100644 --- a/azalea/src/pathfinder/mod.rs +++ b/azalea/src/pathfinder/mod.rs @@ -6,6 +6,7 @@ pub mod costs; pub mod goals; pub mod moves; pub mod simulation; +pub mod world; use crate::bot::{JumpEvent, LookAtEvent}; use crate::pathfinder::astar::a_star; @@ -20,6 +21,7 @@ use crate::ecs::{ system::{Commands, Query, Res}, }; use crate::pathfinder::moves::PathfinderCtx; +use crate::pathfinder::world::CachedWorld; use azalea_client::chat::SendChatEvent; use azalea_client::movement::walk_listener; use azalea_client::{StartSprintEvent, StartWalkEvent}; @@ -219,12 +221,8 @@ fn goto_listener( let task = thread_pool.spawn(async move { debug!("start: {start:?}"); - let ctx = PathfinderCtx::new(world_lock); - let successors = |pos: BlockPos| { - let mut edges = Vec::with_capacity(16); - successors_fn(&mut edges, &ctx, pos); - edges - }; + let cached_world = CachedWorld::new(world_lock); + let successors = |pos: BlockPos| call_successors_fn(&cached_world, successors_fn, pos); let mut attempt_number = 0; @@ -332,12 +330,9 @@ fn path_found_listener( .get(instance_name) .expect("Entity tried to pathfind but the entity isn't in a valid world"); let successors_fn: moves::SuccessorsFn = event.successors_fn; - let ctx = PathfinderCtx::new(world_lock); - let successors = |pos: BlockPos| { - let mut edges = Vec::with_capacity(16); - successors_fn(&mut edges, &ctx, pos); - edges - }; + let cached_world = CachedWorld::new(world_lock); + let successors = + |pos: BlockPos| call_successors_fn(&cached_world, successors_fn, pos); if let Some(first_node_of_new_path) = path.front() { if successors(last_node_of_current_path.target) @@ -521,12 +516,8 @@ fn check_for_path_obstruction( .expect("Entity tried to pathfind but the entity isn't in a valid world"); // obstruction check (the path we're executing isn't possible anymore) - let ctx = PathfinderCtx::new(world_lock); - let successors = |pos: BlockPos| { - let mut edges = Vec::with_capacity(16); - successors_fn(&mut edges, &ctx, pos); - edges - }; + let cached_world = CachedWorld::new(world_lock); + let successors = |pos: BlockPos| call_successors_fn(&cached_world, successors_fn, pos); if let Some(obstructed_index) = check_path_obstructed( executing_path.last_reached_node, @@ -816,6 +807,20 @@ where None } +pub fn call_successors_fn( + cached_world: &CachedWorld, + successors_fn: SuccessorsFn, + pos: BlockPos, +) -> Vec<astar::Edge<BlockPos, moves::MoveData>> { + let mut edges = Vec::with_capacity(16); + let mut ctx = PathfinderCtx { + edges: &mut edges, + world: cached_world, + }; + successors_fn(&mut ctx, pos); + edges +} + #[cfg(test)] mod tests { use std::{collections::HashSet, sync::Arc}; diff --git a/azalea/src/pathfinder/moves/basic.rs b/azalea/src/pathfinder/moves/basic.rs index 531a2d00..4780798c 100644 --- a/azalea/src/pathfinder/moves/basic.rs +++ b/azalea/src/pathfinder/moves/basic.rs @@ -10,25 +10,25 @@ use crate::pathfinder::{astar, costs::*}; use super::{default_is_reached, Edge, ExecuteCtx, IsReachedCtx, MoveData, PathfinderCtx}; -pub fn basic_move(edges: &mut Vec<Edge>, ctx: &PathfinderCtx, node: BlockPos) { - forward_move(edges, ctx, node); - ascend_move(edges, ctx, node); - descend_move(edges, ctx, node); - diagonal_move(edges, ctx, node); - descend_forward_1_move(edges, ctx, node); +pub fn basic_move(ctx: &mut PathfinderCtx, node: BlockPos) { + forward_move(ctx, node); + ascend_move(ctx, node); + descend_move(ctx, node); + diagonal_move(ctx, node); + descend_forward_1_move(ctx, node); } -fn forward_move(edges: &mut Vec<Edge>, ctx: &PathfinderCtx, pos: BlockPos) { +fn forward_move(ctx: &mut PathfinderCtx, pos: BlockPos) { for dir in CardinalDirection::iter() { let offset = BlockPos::new(dir.x(), 0, dir.z()); - if !ctx.is_standable(pos + offset) { + if !ctx.world.is_standable(pos + offset) { continue; } let cost = SPRINT_ONE_BLOCK_COST; - edges.push(Edge { + ctx.edges.push(Edge { movement: astar::Movement { target: pos + offset, data: MoveData { @@ -47,20 +47,20 @@ fn execute_forward_move(mut ctx: ExecuteCtx) { ctx.sprint(SprintDirection::Forward); } -fn ascend_move(edges: &mut Vec<Edge>, ctx: &PathfinderCtx, pos: BlockPos) { +fn ascend_move(ctx: &mut PathfinderCtx, pos: BlockPos) { for dir in CardinalDirection::iter() { let offset = BlockPos::new(dir.x(), 1, dir.z()); - if !ctx.is_block_passable(pos.up(2)) { + if !ctx.world.is_block_passable(pos.up(2)) { continue; } - if !ctx.is_standable(pos + offset) { + if !ctx.world.is_standable(pos + offset) { continue; } let cost = SPRINT_ONE_BLOCK_COST + JUMP_PENALTY + *JUMP_ONE_BLOCK_COST; - edges.push(Edge { + ctx.edges.push(Edge { movement: astar::Movement { target: pos + offset, data: MoveData { @@ -119,22 +119,22 @@ pub fn ascend_is_reached( BlockPos::from(position) == target || BlockPos::from(position) == target.down(1) } -fn descend_move(edges: &mut Vec<Edge>, ctx: &PathfinderCtx, pos: BlockPos) { +fn descend_move(ctx: &mut PathfinderCtx, pos: BlockPos) { for dir in CardinalDirection::iter() { let dir_delta = BlockPos::new(dir.x(), 0, dir.z()); let new_horizontal_position = pos + dir_delta; - let fall_distance = ctx.fall_distance(new_horizontal_position); + let fall_distance = ctx.world.fall_distance(new_horizontal_position); if fall_distance == 0 || fall_distance > 3 { continue; } let new_position = new_horizontal_position.down(fall_distance as i32); // check whether 3 blocks vertically forward are passable - if !ctx.is_passable(new_horizontal_position) { + if !ctx.world.is_passable(new_horizontal_position) { continue; } // check whether we can stand on the target position - if !ctx.is_standable(new_position) { + if !ctx.world.is_standable(new_position) { continue; } @@ -149,7 +149,7 @@ fn descend_move(edges: &mut Vec<Edge>, ctx: &PathfinderCtx, pos: BlockPos) { CENTER_AFTER_FALL_COST, ); - edges.push(Edge { + ctx.edges.push(Edge { movement: astar::Movement { target: new_position, data: MoveData { @@ -214,14 +214,14 @@ pub fn descend_is_reached( && (position.y - target.y as f64) < 0.5 } -fn descend_forward_1_move(edges: &mut Vec<Edge>, ctx: &PathfinderCtx, pos: BlockPos) { +fn descend_forward_1_move(ctx: &mut PathfinderCtx, pos: BlockPos) { for dir in CardinalDirection::iter() { let dir_delta = BlockPos::new(dir.x(), 0, dir.z()); let gap_horizontal_position = pos + dir_delta; let new_horizontal_position = pos + dir_delta * 2; - let gap_fall_distance = ctx.fall_distance(gap_horizontal_position); - let fall_distance = ctx.fall_distance(new_horizontal_position); + let gap_fall_distance = ctx.world.fall_distance(gap_horizontal_position); + let fall_distance = ctx.world.fall_distance(new_horizontal_position); if fall_distance == 0 || fall_distance > 3 || gap_fall_distance < fall_distance { continue; @@ -230,14 +230,14 @@ fn descend_forward_1_move(edges: &mut Vec<Edge>, ctx: &PathfinderCtx, pos: Block let new_position = new_horizontal_position.down(fall_distance as i32); // check whether 2 blocks vertically forward are passable - if !ctx.is_passable(new_horizontal_position) { + if !ctx.world.is_passable(new_horizontal_position) { continue; } - if !ctx.is_passable(gap_horizontal_position) { + if !ctx.world.is_passable(gap_horizontal_position) { continue; } // check whether we can stand on the target position - if !ctx.is_standable(new_position) { + if !ctx.world.is_standable(new_position) { continue; } @@ -253,7 +253,7 @@ fn descend_forward_1_move(edges: &mut Vec<Edge>, ctx: &PathfinderCtx, pos: Block CENTER_AFTER_FALL_COST, ); - edges.push(Edge { + ctx.edges.push(Edge { movement: astar::Movement { target: new_position, data: MoveData { @@ -266,7 +266,7 @@ fn descend_forward_1_move(edges: &mut Vec<Edge>, ctx: &PathfinderCtx, pos: Block } } -fn diagonal_move(edges: &mut Vec<Edge>, ctx: &PathfinderCtx, pos: BlockPos) { +fn diagonal_move(ctx: &mut PathfinderCtx, pos: BlockPos) { for dir in CardinalDirection::iter() { let right = dir.right(); let offset = BlockPos::new(dir.x() + right.x(), 0, dir.z() + right.z()); @@ -276,8 +276,8 @@ fn diagonal_move(edges: &mut Vec<Edge>, ctx: &PathfinderCtx, pos: BlockPos) { // +0.001 so it doesn't unnecessarily go diagonal sometimes let mut cost = SPRINT_ONE_BLOCK_COST * SQRT_2 + 0.001; - let left_passable = ctx.is_passable(left_pos); - let right_passable = ctx.is_passable(right_pos); + let left_passable = ctx.world.is_passable(left_pos); + let right_passable = ctx.world.is_passable(right_pos); if !left_passable && !right_passable { continue; @@ -288,11 +288,11 @@ fn diagonal_move(edges: &mut Vec<Edge>, ctx: &PathfinderCtx, pos: BlockPos) { cost += WALK_ONE_BLOCK_COST / 2.; } - if !ctx.is_standable(pos + offset) { + if !ctx.world.is_standable(pos + offset) { continue; } - edges.push(Edge { + ctx.edges.push(Edge { movement: astar::Movement { target: pos + offset, data: MoveData { diff --git a/azalea/src/pathfinder/moves/mod.rs b/azalea/src/pathfinder/moves/mod.rs index 47a909e1..bf1fc5f4 100644 --- a/azalea/src/pathfinder/moves/mod.rs +++ b/azalea/src/pathfinder/moves/mod.rs @@ -1,33 +1,22 @@ pub mod basic; pub mod parkour; -use std::{ - cell::{RefCell, UnsafeCell}, - fmt::Debug, - sync::Arc, -}; +use std::fmt::Debug; use crate::{JumpEvent, LookAtEvent}; -use super::astar; -use azalea_block::BlockState; +use super::{astar, world::CachedWorld}; use azalea_client::{SprintDirection, StartSprintEvent, StartWalkEvent, WalkDirection}; -use azalea_core::{ - bitset::FixedBitSet, - position::{BlockPos, ChunkPos, ChunkSectionBlockPos, ChunkSectionPos, Vec3}, -}; -use azalea_physics::collision::BlockWithShape; -use azalea_world::Instance; +use azalea_core::position::{BlockPos, Vec3}; use bevy_ecs::{entity::Entity, event::EventWriter}; -use parking_lot::RwLock; type Edge = astar::Edge<BlockPos, MoveData>; -pub type SuccessorsFn = fn(&mut Vec<Edge>, &PathfinderCtx, BlockPos); +pub type SuccessorsFn = fn(&mut PathfinderCtx, BlockPos); -pub fn default_move(edges: &mut Vec<Edge>, ctx: &PathfinderCtx, node: BlockPos) { - basic::basic_move(edges, ctx, node); - parkour::parkour_move(edges, ctx, node); +pub fn default_move(ctx: &mut PathfinderCtx, node: BlockPos) { + basic::basic_move(ctx, node); + parkour::parkour_move(ctx, node); } #[derive(Clone)] @@ -46,262 +35,6 @@ impl Debug for MoveData { } } -pub struct PathfinderCtx { - min_y: i32, - world_lock: Arc<RwLock<Instance>>, - // we store `PalettedContainer`s instead of `Chunk`s or `Section`s because it doesn't contain - // any unnecessary data like heightmaps or biomes. - cached_chunks: RefCell<Vec<(ChunkPos, Vec<azalea_world::palette::PalettedContainer>)>>, - - cached_blocks: UnsafeCell<CachedSections>, -} - -#[derive(Default)] -pub struct CachedSections { - pub last_index: usize, - pub second_last_index: usize, - pub sections: Vec<CachedSection>, -} - -impl CachedSections { - #[inline] - pub fn get_mut(&mut self, pos: ChunkSectionPos) -> Option<&mut CachedSection> { - if let Some(last_item) = self.sections.get(self.last_index) { - if last_item.pos == pos { - return Some(&mut self.sections[self.last_index]); - } else if let Some(second_last_item) = self.sections.get(self.second_last_index) { - if second_last_item.pos == pos { - return Some(&mut self.sections[self.second_last_index]); - } - } - } - - let index = self - .sections - .binary_search_by(|section| section.pos.cmp(&pos)) - .ok(); - - if let Some(index) = index { - self.second_last_index = self.last_index; - self.last_index = index; - return Some(&mut self.sections[index]); - } - None - } - - #[inline] - pub fn insert(&mut self, section: CachedSection) { - // self.sections.push(section); - // self.sections.sort_unstable_by(|a, b| a.pos.cmp(&b.pos)); - let index = self - .sections - .binary_search_by(|s| s.pos.cmp(§ion.pos)) - .unwrap_or_else(|e| e); - self.sections.insert(index, section); - } -} - -pub struct CachedSection { - pub pos: ChunkSectionPos, - pub passable_bitset: FixedBitSet<4096>, - pub solid_bitset: FixedBitSet<4096>, -} - -impl PathfinderCtx { - pub fn new(world_lock: Arc<RwLock<Instance>>) -> Self { - let min_y = world_lock.read().chunks.min_y; - Self { - min_y, - world_lock, - cached_chunks: Default::default(), - cached_blocks: Default::default(), - } - } - - // ``` - // fn get_block_state(&self, pos: BlockPos) -> Option<BlockState> { - // self.with_section(ChunkSectionPos::from(pos), |section| { - // let state = section.get(pos.x as usize, pos.y as usize, pos.z as usize); - // BlockState::try_from(state).unwrap_or(BlockState::AIR) - // }) - // } - // ``` - - fn with_section<T>( - &self, - section_pos: ChunkSectionPos, - f: impl FnOnce(&azalea_world::palette::PalettedContainer) -> T, - ) -> Option<T> { - let chunk_pos = ChunkPos::from(section_pos); - let section_index = - azalea_world::chunk_storage::section_index(section_pos.y * 16, self.min_y) as usize; - - let mut cached_chunks = self.cached_chunks.borrow_mut(); - - // get section from cache - if let Some(sections) = cached_chunks.iter().find_map(|(pos, sections)| { - if *pos == chunk_pos { - Some(sections) - } else { - None - } - }) { - if section_index >= sections.len() { - // y position is out of bounds - return None; - }; - let section: &azalea_world::palette::PalettedContainer = §ions[section_index]; - return Some(f(section)); - } - - let world = self.world_lock.read(); - let Some(chunk) = world.chunks.get(&chunk_pos) else { - return None; - }; - let chunk = chunk.read(); - - let sections: Vec<azalea_world::palette::PalettedContainer> = chunk - .sections - .iter() - .map(|section| section.states.clone()) - .collect(); - - if section_index >= sections.len() { - // y position is out of bounds - return None; - }; - - let section = §ions[section_index]; - let r = f(section); - - // add the sections to the chunk cache - cached_chunks.push((chunk_pos, sections)); - - Some(r) - } - - fn calculate_bitsets_for_section(&self, section_pos: ChunkSectionPos) -> Option<CachedSection> { - self.with_section(section_pos, |section| { - let mut passable_bitset = FixedBitSet::<4096>::new(); - let mut solid_bitset = FixedBitSet::<4096>::new(); - for i in 0..4096 { - let block_state_id = section.get_at_index(i); - let block_state = BlockState::try_from(block_state_id).unwrap_or(BlockState::AIR); - if is_block_state_passable(block_state) { - passable_bitset.set(i); - } - if is_block_state_solid(block_state) { - solid_bitset.set(i); - } - } - CachedSection { - pos: section_pos, - passable_bitset, - solid_bitset, - } - }) - } - - pub fn is_block_passable(&self, pos: BlockPos) -> bool { - let (section_pos, section_block_pos) = - (ChunkSectionPos::from(pos), ChunkSectionBlockPos::from(pos)); - let index = u16::from(section_block_pos) as usize; - // SAFETY: we're only accessing this from one thread - let cached_blocks = unsafe { &mut *self.cached_blocks.get() }; - if let Some(cached) = cached_blocks.get_mut(section_pos) { - return cached.passable_bitset.index(index); - } - - let Some(cached) = self.calculate_bitsets_for_section(section_pos) else { - return false; - }; - let passable = cached.passable_bitset.index(index); - cached_blocks.insert(cached); - passable - } - - pub fn is_block_solid(&self, pos: BlockPos) -> bool { - let (section_pos, section_block_pos) = - (ChunkSectionPos::from(pos), ChunkSectionBlockPos::from(pos)); - let index = u16::from(section_block_pos) as usize; - // SAFETY: we're only accessing this from one thread - let cached_blocks = unsafe { &mut *self.cached_blocks.get() }; - if let Some(cached) = cached_blocks.get_mut(section_pos) { - return cached.solid_bitset.index(index); - } - - let Some(cached) = self.calculate_bitsets_for_section(section_pos) else { - return false; - }; - let solid = cached.solid_bitset.index(index); - cached_blocks.insert(cached); - solid - } - - /// Whether this block and the block above are passable - pub fn is_passable(&self, pos: BlockPos) -> bool { - self.is_block_passable(pos) && self.is_block_passable(pos.up(1)) - } - - /// Whether we can stand in this position. Checks if the block below is - /// solid, and that the two blocks above that are passable. - - pub fn is_standable(&self, pos: BlockPos) -> bool { - self.is_block_solid(pos.down(1)) && self.is_passable(pos) - } - - /// Get the amount of air blocks until the next solid block below this one. - pub fn fall_distance(&self, pos: BlockPos) -> u32 { - let mut distance = 0; - let mut current_pos = pos.down(1); - while self.is_block_passable(current_pos) { - distance += 1; - current_pos = current_pos.down(1); - - if current_pos.y < self.min_y { - return u32::MAX; - } - } - distance - } -} - -/// whether this block is passable -fn is_block_state_passable(block: BlockState) -> bool { - if block.is_air() { - // fast path - return true; - } - if !block.is_shape_empty() { - return false; - } - if block == azalea_registry::Block::Water.into() { - return false; - } - if block.waterlogged() { - return false; - } - if block == azalea_registry::Block::Lava.into() { - return false; - } - // block.waterlogged currently doesn't account for seagrass and some other water - // blocks - if block == azalea_registry::Block::Seagrass.into() { - return false; - } - - true -} - -/// whether this block has a solid hitbox (i.e. we can stand on it) -fn is_block_state_solid(block: BlockState) -> bool { - if block.is_air() { - // fast path - return false; - } - block.is_shape_full() -} - pub struct ExecuteCtx<'w1, 'w2, 'w3, 'w4, 'a> { pub entity: Entity, /// The node that we're trying to reach. @@ -371,81 +104,7 @@ pub fn default_is_reached( BlockPos::from(position) == target } -#[cfg(test)] -mod tests { - use super::*; - use azalea_block::BlockState; - use azalea_core::position::ChunkPos; - use azalea_world::{Chunk, ChunkStorage, PartialInstance}; - - #[test] - fn test_is_passable() { - let mut partial_world = PartialInstance::default(); - let mut world = ChunkStorage::default(); - - partial_world - .chunks - .set(&ChunkPos { x: 0, z: 0 }, Some(Chunk::default()), &mut world); - partial_world.chunks.set_block_state( - &BlockPos::new(0, 0, 0), - azalea_registry::Block::Stone.into(), - &world, - ); - partial_world - .chunks - .set_block_state(&BlockPos::new(0, 1, 0), BlockState::AIR, &world); - - let ctx = PathfinderCtx::new(Arc::new(RwLock::new(world.into()))); - assert!(!ctx.is_block_passable(BlockPos::new(0, 0, 0))); - assert!(ctx.is_block_passable(BlockPos::new(0, 1, 0),)); - } - - #[test] - fn test_is_solid() { - let mut partial_world = PartialInstance::default(); - let mut world = ChunkStorage::default(); - partial_world - .chunks - .set(&ChunkPos { x: 0, z: 0 }, Some(Chunk::default()), &mut world); - partial_world.chunks.set_block_state( - &BlockPos::new(0, 0, 0), - azalea_registry::Block::Stone.into(), - &world, - ); - partial_world - .chunks - .set_block_state(&BlockPos::new(0, 1, 0), BlockState::AIR, &world); - - let ctx = PathfinderCtx::new(Arc::new(RwLock::new(world.into()))); - assert!(ctx.is_block_solid(BlockPos::new(0, 0, 0))); - assert!(!ctx.is_block_solid(BlockPos::new(0, 1, 0))); - } - - #[test] - fn test_is_standable() { - let mut partial_world = PartialInstance::default(); - let mut world = ChunkStorage::default(); - partial_world - .chunks - .set(&ChunkPos { x: 0, z: 0 }, Some(Chunk::default()), &mut world); - partial_world.chunks.set_block_state( - &BlockPos::new(0, 0, 0), - azalea_registry::Block::Stone.into(), - &world, - ); - partial_world - .chunks - .set_block_state(&BlockPos::new(0, 1, 0), BlockState::AIR, &world); - partial_world - .chunks - .set_block_state(&BlockPos::new(0, 2, 0), BlockState::AIR, &world); - partial_world - .chunks - .set_block_state(&BlockPos::new(0, 3, 0), BlockState::AIR, &world); - - let ctx = PathfinderCtx::new(Arc::new(RwLock::new(world.into()))); - assert!(ctx.is_standable(BlockPos::new(0, 1, 0))); - assert!(!ctx.is_standable(BlockPos::new(0, 0, 0))); - assert!(!ctx.is_standable(BlockPos::new(0, 2, 0))); - } +pub struct PathfinderCtx<'a> { + pub edges: &'a mut Vec<Edge>, + pub world: &'a CachedWorld, } diff --git a/azalea/src/pathfinder/moves/parkour.rs b/azalea/src/pathfinder/moves/parkour.rs index 832d0f4a..66f02197 100644 --- a/azalea/src/pathfinder/moves/parkour.rs +++ b/azalea/src/pathfinder/moves/parkour.rs @@ -5,29 +5,29 @@ use crate::pathfinder::{astar, costs::*}; use super::{Edge, ExecuteCtx, IsReachedCtx, MoveData, PathfinderCtx}; -pub fn parkour_move(edges: &mut Vec<Edge>, ctx: &PathfinderCtx, node: BlockPos) { - parkour_forward_1_move(edges, ctx, node); - parkour_forward_2_move(edges, ctx, node); - parkour_forward_3_move(edges, ctx, node); +pub fn parkour_move(ctx: &mut PathfinderCtx, node: BlockPos) { + parkour_forward_1_move(ctx, node); + parkour_forward_2_move(ctx, node); + parkour_forward_3_move(ctx, node); } -fn parkour_forward_1_move(edges: &mut Vec<Edge>, ctx: &PathfinderCtx, pos: BlockPos) { +fn parkour_forward_1_move(ctx: &mut PathfinderCtx, pos: BlockPos) { for dir in CardinalDirection::iter() { let gap_offset = BlockPos::new(dir.x(), 0, dir.z()); let offset = BlockPos::new(dir.x() * 2, 0, dir.z() * 2); // make sure we actually have to jump - if ctx.is_block_solid((pos + gap_offset).down(1)) { + if ctx.world.is_block_solid((pos + gap_offset).down(1)) { continue; } - if !ctx.is_passable(pos + gap_offset) { + if !ctx.world.is_passable(pos + gap_offset) { continue; } - let ascend: i32 = if ctx.is_standable(pos + offset.up(1)) { + let ascend: i32 = if ctx.world.is_standable(pos + offset.up(1)) { // ascend 1 - } else if ctx.is_standable(pos + offset) { + } else if ctx.world.is_standable(pos + offset) { // forward 0 } else { @@ -35,22 +35,22 @@ fn parkour_forward_1_move(edges: &mut Vec<Edge>, ctx: &PathfinderCtx, pos: Block }; // make sure we have space to jump - if !ctx.is_block_passable((pos + gap_offset).up(2)) { + if !ctx.world.is_block_passable((pos + gap_offset).up(2)) { continue; } // make sure there's not a block above us - if !ctx.is_block_passable(pos.up(2)) { + if !ctx.world.is_block_passable(pos.up(2)) { continue; } // make sure there's not a block above the target - if !ctx.is_block_passable((pos + offset).up(2)) { + if !ctx.world.is_block_passable((pos + offset).up(2)) { continue; } let cost = JUMP_PENALTY + WALK_ONE_BLOCK_COST * 2. + CENTER_AFTER_FALL_COST; - edges.push(Edge { + ctx.edges.push(Edge { movement: astar::Movement { target: pos + offset.up(ascend), data: MoveData { @@ -63,22 +63,22 @@ fn parkour_forward_1_move(edges: &mut Vec<Edge>, ctx: &PathfinderCtx, pos: Block } } -fn parkour_forward_2_move(edges: &mut Vec<Edge>, ctx: &PathfinderCtx, pos: BlockPos) { +fn parkour_forward_2_move(ctx: &mut PathfinderCtx, pos: BlockPos) { 'dir: for dir in CardinalDirection::iter() { let gap_1_offset = BlockPos::new(dir.x(), 0, dir.z()); let gap_2_offset = BlockPos::new(dir.x() * 2, 0, dir.z() * 2); let offset = BlockPos::new(dir.x() * 3, 0, dir.z() * 3); // make sure we actually have to jump - if ctx.is_block_solid((pos + gap_1_offset).down(1)) - || ctx.is_block_solid((pos + gap_2_offset).down(1)) + if ctx.world.is_block_solid((pos + gap_1_offset).down(1)) + || ctx.world.is_block_solid((pos + gap_2_offset).down(1)) { continue; } - let ascend: i32 = if ctx.is_standable(pos + offset.up(1)) { + let ascend: i32 = if ctx.world.is_standable(pos + offset.up(1)) { 1 - } else if ctx.is_standable(pos + offset) { + } else if ctx.world.is_standable(pos + offset) { 0 } else { continue; @@ -86,25 +86,25 @@ fn parkour_forward_2_move(edges: &mut Vec<Edge>, ctx: &PathfinderCtx, pos: Block // make sure we have space to jump for offset in [gap_1_offset, gap_2_offset] { - if !ctx.is_passable(pos + offset) { + if !ctx.world.is_passable(pos + offset) { continue 'dir; } - if !ctx.is_block_passable((pos + offset).up(2)) { + if !ctx.world.is_block_passable((pos + offset).up(2)) { continue 'dir; } } // make sure there's not a block above us - if !ctx.is_block_passable(pos.up(2)) { + if !ctx.world.is_block_passable(pos.up(2)) { continue; } // make sure there's not a block above the target - if !ctx.is_block_passable((pos + offset).up(2)) { + if !ctx.world.is_block_passable((pos + offset).up(2)) { continue; } let cost = JUMP_PENALTY + WALK_ONE_BLOCK_COST * 3. + CENTER_AFTER_FALL_COST; - edges.push(Edge { + ctx.edges.push(Edge { movement: astar::Movement { target: pos + offset.up(ascend), data: MoveData { @@ -117,7 +117,7 @@ fn parkour_forward_2_move(edges: &mut Vec<Edge>, ctx: &PathfinderCtx, pos: Block } } -fn parkour_forward_3_move(edges: &mut Vec<Edge>, ctx: &PathfinderCtx, pos: BlockPos) { +fn parkour_forward_3_move(ctx: &mut PathfinderCtx, pos: BlockPos) { 'dir: for dir in CardinalDirection::iter() { let gap_1_offset = BlockPos::new(dir.x(), 0, dir.z()); let gap_2_offset = BlockPos::new(dir.x() * 2, 0, dir.z() * 2); @@ -125,38 +125,38 @@ fn parkour_forward_3_move(edges: &mut Vec<Edge>, ctx: &PathfinderCtx, pos: Block let offset = BlockPos::new(dir.x() * 4, 0, dir.z() * 4); // make sure we actually have to jump - if ctx.is_block_solid((pos + gap_1_offset).down(1)) - || ctx.is_block_solid((pos + gap_2_offset).down(1)) - || ctx.is_block_solid((pos + gap_3_offset).down(1)) + if ctx.world.is_block_solid((pos + gap_1_offset).down(1)) + || ctx.world.is_block_solid((pos + gap_2_offset).down(1)) + || ctx.world.is_block_solid((pos + gap_3_offset).down(1)) { continue; } - if !ctx.is_standable(pos + offset) { + if !ctx.world.is_standable(pos + offset) { continue; }; // make sure we have space to jump for offset in [gap_1_offset, gap_2_offset, gap_3_offset] { - if !ctx.is_passable(pos + offset) { + if !ctx.world.is_passable(pos + offset) { continue 'dir; } - if !ctx.is_block_passable((pos + offset).up(2)) { + if !ctx.world.is_block_passable((pos + offset).up(2)) { continue 'dir; } } // make sure there's not a block above us - if !ctx.is_block_passable(pos.up(2)) { + if !ctx.world.is_block_passable(pos.up(2)) { continue; } // make sure there's not a block above the target - if !ctx.is_block_passable((pos + offset).up(2)) { + if !ctx.world.is_block_passable((pos + offset).up(2)) { continue; } let cost = JUMP_PENALTY + SPRINT_ONE_BLOCK_COST * 4. + CENTER_AFTER_FALL_COST; - edges.push(Edge { + ctx.edges.push(Edge { movement: astar::Movement { target: pos + offset, data: MoveData { diff --git a/azalea/src/pathfinder/world.rs b/azalea/src/pathfinder/world.rs new file mode 100644 index 00000000..f73a6641 --- /dev/null +++ b/azalea/src/pathfinder/world.rs @@ -0,0 +1,353 @@ +use std::{ + cell::{RefCell, UnsafeCell}, + sync::Arc, +}; + +use azalea_block::BlockState; +use azalea_core::{ + bitset::FixedBitSet, + position::{BlockPos, ChunkPos, ChunkSectionBlockPos, ChunkSectionPos}, +}; +use azalea_physics::collision::BlockWithShape; +use azalea_world::Instance; +use parking_lot::RwLock; + +/// An efficient representation of the world used for the pathfinder. +pub struct CachedWorld { + min_y: i32, + world_lock: Arc<RwLock<Instance>>, + + // we store `PalettedContainer`s instead of `Chunk`s or `Section`s because it doesn't contain + // any unnecessary data like heightmaps or biomes. + cached_chunks: RefCell<Vec<(ChunkPos, Vec<azalea_world::palette::PalettedContainer>)>>, + + cached_blocks: UnsafeCell<CachedSections>, +} + +#[derive(Default)] +pub struct CachedSections { + pub last_index: usize, + pub second_last_index: usize, + pub sections: Vec<CachedSection>, +} + +impl CachedSections { + #[inline] + pub fn get_mut(&mut self, pos: ChunkSectionPos) -> Option<&mut CachedSection> { + if let Some(last_item) = self.sections.get(self.last_index) { + if last_item.pos == pos { + return Some(&mut self.sections[self.last_index]); + } else if let Some(second_last_item) = self.sections.get(self.second_last_index) { + if second_last_item.pos == pos { + return Some(&mut self.sections[self.second_last_index]); + } + } + } + + let index = self + .sections + .binary_search_by(|section| section.pos.cmp(&pos)) + .ok(); + + if let Some(index) = index { + self.second_last_index = self.last_index; + self.last_index = index; + return Some(&mut self.sections[index]); + } + None + } + + #[inline] + pub fn insert(&mut self, section: CachedSection) { + // self.sections.push(section); + // self.sections.sort_unstable_by(|a, b| a.pos.cmp(&b.pos)); + let index = self + .sections + .binary_search_by(|s| s.pos.cmp(§ion.pos)) + .unwrap_or_else(|e| e); + self.sections.insert(index, section); + } +} + +pub struct CachedSection { + pub pos: ChunkSectionPos, + pub passable_bitset: FixedBitSet<4096>, + pub solid_bitset: FixedBitSet<4096>, +} + +impl CachedWorld { + pub fn new(world_lock: Arc<RwLock<Instance>>) -> Self { + let min_y = world_lock.read().chunks.min_y; + Self { + min_y, + world_lock, + cached_chunks: Default::default(), + cached_blocks: Default::default(), + } + } + + // ``` + // fn get_block_state(&self, pos: BlockPos) -> Option<BlockState> { + // self.with_section(ChunkSectionPos::from(pos), |section| { + // let state = section.get(pos.x as usize, pos.y as usize, pos.z as usize); + // BlockState::try_from(state).unwrap_or(BlockState::AIR) + // }) + // } + // ``` + + fn with_section<T>( + &self, + section_pos: ChunkSectionPos, + f: impl FnOnce(&azalea_world::palette::PalettedContainer) -> T, + ) -> Option<T> { + let chunk_pos = ChunkPos::from(section_pos); + let section_index = + azalea_world::chunk_storage::section_index(section_pos.y * 16, self.min_y) as usize; + + let mut cached_chunks = self.cached_chunks.borrow_mut(); + + // get section from cache + if let Some(sections) = cached_chunks.iter().find_map(|(pos, sections)| { + if *pos == chunk_pos { + Some(sections) + } else { + None + } + }) { + if section_index >= sections.len() { + // y position is out of bounds + return None; + }; + let section: &azalea_world::palette::PalettedContainer = §ions[section_index]; + return Some(f(section)); + } + + let world = self.world_lock.read(); + let Some(chunk) = world.chunks.get(&chunk_pos) else { + return None; + }; + let chunk = chunk.read(); + + let sections: Vec<azalea_world::palette::PalettedContainer> = chunk + .sections + .iter() + .map(|section| section.states.clone()) + .collect(); + + if section_index >= sections.len() { + // y position is out of bounds + return None; + }; + + let section = §ions[section_index]; + let r = f(section); + + // add the sections to the chunk cache + cached_chunks.push((chunk_pos, sections)); + + Some(r) + } + + fn calculate_bitsets_for_section(&self, section_pos: ChunkSectionPos) -> Option<CachedSection> { + self.with_section(section_pos, |section| { + let mut passable_bitset = FixedBitSet::<4096>::new(); + let mut solid_bitset = FixedBitSet::<4096>::new(); + for i in 0..4096 { + let block_state_id = section.get_at_index(i); + let block_state = BlockState::try_from(block_state_id).unwrap_or(BlockState::AIR); + if is_block_state_passable(block_state) { + passable_bitset.set(i); + } + if is_block_state_solid(block_state) { + solid_bitset.set(i); + } + } + CachedSection { + pos: section_pos, + passable_bitset, + solid_bitset, + } + }) + } + + pub fn is_block_passable(&self, pos: BlockPos) -> bool { + let (section_pos, section_block_pos) = + (ChunkSectionPos::from(pos), ChunkSectionBlockPos::from(pos)); + let index = u16::from(section_block_pos) as usize; + // SAFETY: we're only accessing this from one thread + let cached_blocks = unsafe { &mut *self.cached_blocks.get() }; + if let Some(cached) = cached_blocks.get_mut(section_pos) { + return cached.passable_bitset.index(index); + } + + let Some(cached) = self.calculate_bitsets_for_section(section_pos) else { + return false; + }; + let passable = cached.passable_bitset.index(index); + cached_blocks.insert(cached); + passable + } + + pub fn is_block_solid(&self, pos: BlockPos) -> bool { + let (section_pos, section_block_pos) = + (ChunkSectionPos::from(pos), ChunkSectionBlockPos::from(pos)); + let index = u16::from(section_block_pos) as usize; + // SAFETY: we're only accessing this from one thread + let cached_blocks = unsafe { &mut *self.cached_blocks.get() }; + if let Some(cached) = cached_blocks.get_mut(section_pos) { + return cached.solid_bitset.index(index); + } + + let Some(cached) = self.calculate_bitsets_for_section(section_pos) else { + return false; + }; + let solid = cached.solid_bitset.index(index); + cached_blocks.insert(cached); + solid + } + + /// Whether this block and the block above are passable + pub fn is_passable(&self, pos: BlockPos) -> bool { + self.is_block_passable(pos) && self.is_block_passable(pos.up(1)) + } + + /// Whether we can stand in this position. Checks if the block below is + /// solid, and that the two blocks above that are passable. + + pub fn is_standable(&self, pos: BlockPos) -> bool { + self.is_block_solid(pos.down(1)) && self.is_passable(pos) + } + + /// Get the amount of air blocks until the next solid block below this one. + pub fn fall_distance(&self, pos: BlockPos) -> u32 { + let mut distance = 0; + let mut current_pos = pos.down(1); + while self.is_block_passable(current_pos) { + distance += 1; + current_pos = current_pos.down(1); + + if current_pos.y < self.min_y { + return u32::MAX; + } + } + distance + } +} + +/// whether this block is passable +fn is_block_state_passable(block: BlockState) -> bool { + if block.is_air() { + // fast path + return true; + } + if !block.is_shape_empty() { + return false; + } + if block == azalea_registry::Block::Water.into() { + return false; + } + if block.waterlogged() { + return false; + } + if block == azalea_registry::Block::Lava.into() { + return false; + } + // block.waterlogged currently doesn't account for seagrass and some other water + // blocks + if block == azalea_registry::Block::Seagrass.into() { + return false; + } + + true +} + +/// whether this block has a solid hitbox (i.e. we can stand on it) +fn is_block_state_solid(block: BlockState) -> bool { + if block.is_air() { + // fast path + return false; + } + block.is_shape_full() +} + +#[cfg(test)] +mod tests { + use std::sync::Arc; + + use super::*; + use azalea_block::BlockState; + use azalea_core::position::ChunkPos; + use azalea_world::{Chunk, ChunkStorage, PartialInstance}; + use parking_lot::RwLock; + + #[test] + fn test_is_passable() { + let mut partial_world = PartialInstance::default(); + let mut world = ChunkStorage::default(); + + partial_world + .chunks + .set(&ChunkPos { x: 0, z: 0 }, Some(Chunk::default()), &mut world); + partial_world.chunks.set_block_state( + &BlockPos::new(0, 0, 0), + azalea_registry::Block::Stone.into(), + &world, + ); + partial_world + .chunks + .set_block_state(&BlockPos::new(0, 1, 0), BlockState::AIR, &world); + + let ctx = CachedWorld::new(Arc::new(RwLock::new(world.into()))); + assert!(!ctx.is_block_passable(BlockPos::new(0, 0, 0))); + assert!(ctx.is_block_passable(BlockPos::new(0, 1, 0),)); + } + + #[test] + fn test_is_solid() { + let mut partial_world = PartialInstance::default(); + let mut world = ChunkStorage::default(); + partial_world + .chunks + .set(&ChunkPos { x: 0, z: 0 }, Some(Chunk::default()), &mut world); + partial_world.chunks.set_block_state( + &BlockPos::new(0, 0, 0), + azalea_registry::Block::Stone.into(), + &world, + ); + partial_world + .chunks + .set_block_state(&BlockPos::new(0, 1, 0), BlockState::AIR, &world); + + let ctx = CachedWorld::new(Arc::new(RwLock::new(world.into()))); + assert!(ctx.is_block_solid(BlockPos::new(0, 0, 0))); + assert!(!ctx.is_block_solid(BlockPos::new(0, 1, 0))); + } + + #[test] + fn test_is_standable() { + let mut partial_world = PartialInstance::default(); + let mut world = ChunkStorage::default(); + partial_world + .chunks + .set(&ChunkPos { x: 0, z: 0 }, Some(Chunk::default()), &mut world); + partial_world.chunks.set_block_state( + &BlockPos::new(0, 0, 0), + azalea_registry::Block::Stone.into(), + &world, + ); + partial_world + .chunks + .set_block_state(&BlockPos::new(0, 1, 0), BlockState::AIR, &world); + partial_world + .chunks + .set_block_state(&BlockPos::new(0, 2, 0), BlockState::AIR, &world); + partial_world + .chunks + .set_block_state(&BlockPos::new(0, 3, 0), BlockState::AIR, &world); + + let ctx = CachedWorld::new(Arc::new(RwLock::new(world.into()))); + assert!(ctx.is_standable(BlockPos::new(0, 1, 0))); + assert!(!ctx.is_standable(BlockPos::new(0, 0, 0))); + assert!(!ctx.is_standable(BlockPos::new(0, 2, 0))); + } +} |