From 74ef7d19b2bc4453f5368cc39c838582f2f3bafd Mon Sep 17 00:00:00 2001 From: mat Date: Sat, 17 Jan 2026 11:58:37 -1030 Subject: use more compact chunk section positions in pathfinder --- azalea-core/src/position.rs | 4 +- azalea/benches/pathfinder.rs | 2 +- azalea/examples/testbot/commands/debug.rs | 2 +- azalea/src/pathfinder/mod.rs | 4 +- azalea/src/pathfinder/moves/basic.rs | 2 +- azalea/src/pathfinder/moves/mod.rs | 2 +- azalea/src/pathfinder/moves/parkour.rs | 2 +- azalea/src/pathfinder/moves/uncommon.rs | 2 +- azalea/src/pathfinder/positions.rs | 170 ++++++++++++++++++++++++++++++ azalea/src/pathfinder/rel_block_pos.rs | 133 ----------------------- azalea/src/pathfinder/world.rs | 34 +++--- 11 files changed, 201 insertions(+), 156 deletions(-) create mode 100644 azalea/src/pathfinder/positions.rs delete mode 100644 azalea/src/pathfinder/rel_block_pos.rs diff --git a/azalea-core/src/position.rs b/azalea-core/src/position.rs index 3f2a724f..f664957f 100644 --- a/azalea-core/src/position.rs +++ b/azalea-core/src/position.rs @@ -787,7 +787,7 @@ impl From for ChunkPos { impl From for ChunkSectionPos { #[inline] fn from(pos: BlockPos) -> Self { - ChunkSectionPos { + Self { x: pos.x >> 4, y: pos.y >> 4, z: pos.z >> 4, @@ -797,7 +797,7 @@ impl From for ChunkSectionPos { impl From<&BlockPos> for ChunkSectionPos { #[inline] fn from(pos: &BlockPos) -> Self { - ChunkSectionPos { + Self { x: pos.x >> 4, y: pos.y >> 4, z: pos.z >> 4, diff --git a/azalea/benches/pathfinder.rs b/azalea/benches/pathfinder.rs index 5c06474b..bdb4b3c4 100644 --- a/azalea/benches/pathfinder.rs +++ b/azalea/benches/pathfinder.rs @@ -7,7 +7,7 @@ use azalea::{ custom_state::CustomPathfinderStateRef, goals::{BlockPosGoal, Goal}, mining::MiningCache, - rel_block_pos::RelBlockPos, + positions::RelBlockPos, world::CachedWorld, }, }; diff --git a/azalea/examples/testbot/commands/debug.rs b/azalea/examples/testbot/commands/debug.rs index 3c72c85f..ac1f31e9 100644 --- a/azalea/examples/testbot/commands/debug.rs +++ b/azalea/examples/testbot/commands/debug.rs @@ -10,7 +10,7 @@ use azalea::{ packet::game, pathfinder::{ ExecutingPath, Pathfinder, custom_state::CustomPathfinderStateRef, mining::MiningCache, - moves::PathfinderCtx, rel_block_pos::RelBlockPos, world::CachedWorld, + moves::PathfinderCtx, positions::RelBlockPos, world::CachedWorld, }, }; use azalea_core::hit_result::HitResult; diff --git a/azalea/src/pathfinder/mod.rs b/azalea/src/pathfinder/mod.rs index cab30f7a..9a75f868 100644 --- a/azalea/src/pathfinder/mod.rs +++ b/azalea/src/pathfinder/mod.rs @@ -13,7 +13,7 @@ pub mod goals; mod goto_event; pub mod mining; pub mod moves; -pub mod rel_block_pos; +pub mod positions; pub mod simulation; #[cfg(test)] mod tests; @@ -55,7 +55,7 @@ use futures_lite::future; use goals::BlockPosGoal; pub use goto_event::{GotoEvent, PathfinderOpts}; use parking_lot::RwLock; -use rel_block_pos::RelBlockPos; +use positions::RelBlockPos; use tokio::sync::broadcast::error::RecvError; use tracing::{debug, error, info, trace, warn}; diff --git a/azalea/src/pathfinder/moves/basic.rs b/azalea/src/pathfinder/moves/basic.rs index 69c949d7..1e8b7c64 100644 --- a/azalea/src/pathfinder/moves/basic.rs +++ b/azalea/src/pathfinder/moves/basic.rs @@ -9,7 +9,7 @@ use azalea_core::{ use super::{Edge, ExecuteCtx, IsReachedCtx, MoveData, PathfinderCtx, default_is_reached}; use crate::pathfinder::{ - astar, costs::*, moves::BARITONE_COMPAT, player_pos_to_block_pos, rel_block_pos::RelBlockPos, + astar, costs::*, moves::BARITONE_COMPAT, player_pos_to_block_pos, positions::RelBlockPos, }; pub fn basic_move(ctx: &mut PathfinderCtx, node: RelBlockPos) { diff --git a/azalea/src/pathfinder/moves/mod.rs b/azalea/src/pathfinder/moves/mod.rs index e62ae516..95d3ae35 100644 --- a/azalea/src/pathfinder/moves/mod.rs +++ b/azalea/src/pathfinder/moves/mod.rs @@ -23,7 +23,7 @@ use super::{ astar, custom_state::CustomPathfinderStateRef, mining::MiningCache, - rel_block_pos::RelBlockPos, + positions::RelBlockPos, world::{CachedWorld, is_block_state_passable}, }; use crate::{ diff --git a/azalea/src/pathfinder/moves/parkour.rs b/azalea/src/pathfinder/moves/parkour.rs index 09f4078a..b6b97465 100644 --- a/azalea/src/pathfinder/moves/parkour.rs +++ b/azalea/src/pathfinder/moves/parkour.rs @@ -3,7 +3,7 @@ use azalea_core::{direction::CardinalDirection, position::BlockPos}; use tracing::trace; use super::{Edge, ExecuteCtx, IsReachedCtx, MoveData, PathfinderCtx}; -use crate::pathfinder::{astar, costs::*, player_pos_to_block_pos, rel_block_pos::RelBlockPos}; +use crate::pathfinder::{astar, costs::*, player_pos_to_block_pos, positions::RelBlockPos}; pub fn parkour_move(ctx: &mut PathfinderCtx, node: RelBlockPos) { if !ctx.world.is_block_solid(node.down(1)) { diff --git a/azalea/src/pathfinder/moves/uncommon.rs b/azalea/src/pathfinder/moves/uncommon.rs index 43df3334..bc85333e 100644 --- a/azalea/src/pathfinder/moves/uncommon.rs +++ b/azalea/src/pathfinder/moves/uncommon.rs @@ -9,7 +9,7 @@ use crate::pathfinder::{ BARITONE_COMPAT, MoveData, PathfinderCtx, basic::{descend_is_reached, execute_descend_move}, }, - rel_block_pos::RelBlockPos, + positions::RelBlockPos, }; pub fn uncommon_move(ctx: &mut PathfinderCtx, node: RelBlockPos) { diff --git a/azalea/src/pathfinder/positions.rs b/azalea/src/pathfinder/positions.rs new file mode 100644 index 00000000..ca2768b2 --- /dev/null +++ b/azalea/src/pathfinder/positions.rs @@ -0,0 +1,170 @@ +use std::{ + cmp, + hash::{Hash, Hasher}, + mem::{self, transmute}, + ops::{Add, Mul}, +}; + +use azalea_core::position::BlockPos; + +/// An offset from a block position. +/// +/// This fits in 64 bits, so it's more efficient than a BlockPos in some cases. +/// +/// The X and Z are limited to ±32k. +#[derive(Clone, Copy, Debug, Eq, PartialEq)] +#[repr(C)] +pub struct RelBlockPos { + /// The actual non-relative Y coordinate of the block. + pub y: i32, + /// The X coordinate of the block, relative to some origin. + pub x: i16, + /// The Y coordinate of the block, relative to some origin. + pub z: i16, +} + +impl RelBlockPos { + pub fn get_origin(origin: BlockPos) -> Self { + Self::new(0, origin.y, 0) + } + + #[inline] + pub const fn new(x: i16, y: i32, z: i16) -> Self { + Self { x, y, z } + } + + #[inline] + pub fn apply(self, origin: BlockPos) -> BlockPos { + BlockPos::new(origin.x + self.x as i32, self.y, origin.z + self.z as i32) + } + + /// Create a new [`RelBlockPos`] from a given origin and new position. + #[inline] + pub fn from_origin(origin: BlockPos, new: BlockPos) -> Self { + Self { + x: (new.x - origin.x) as i16, + y: new.y, + z: (new.z - origin.z) as i16, + } + } + + #[inline] + pub fn up(&self, y: i32) -> Self { + Self { + x: self.x, + y: self.y + y, + z: self.z, + } + } + #[inline] + pub fn down(&self, y: i32) -> Self { + Self { + x: self.x, + y: self.y - y, + z: self.z, + } + } + #[inline] + pub fn north(&self, z: i16) -> Self { + Self { + x: self.x, + y: self.y, + z: self.z - z, + } + } + #[inline] + pub fn south(&self, z: i16) -> Self { + Self { + x: self.x, + y: self.y, + z: self.z + z, + } + } + #[inline] + pub fn east(&self, x: i16) -> Self { + Self { + x: self.x + x, + y: self.y, + z: self.z, + } + } + #[inline] + pub fn west(&self, x: i16) -> Self { + Self { + x: self.x - x, + y: self.y, + z: self.z, + } + } + + #[inline] + pub fn as_u64(self) -> u64 { + // SAFETY: RelBlockPos can be represented as a u64 + unsafe { transmute::(self) } + } +} + +impl Add for RelBlockPos { + type Output = RelBlockPos; + + fn add(self, rhs: RelBlockPos) -> Self::Output { + Self { + x: self.x + rhs.x, + y: self.y + rhs.y, + z: self.z + rhs.z, + } + } +} +impl Mul for RelBlockPos { + type Output = RelBlockPos; + + fn mul(self, rhs: i16) -> Self::Output { + Self { + x: self.x * rhs, + y: self.y * rhs as i32, + z: self.z * rhs, + } + } +} + +impl Hash for RelBlockPos { + fn hash(&self, state: &mut H) { + self.as_u64().hash(state); + } +} + +/// Similar to [`ChunkSectionPos`] but fits in 64 bits. +/// +/// [`ChunkSectionPos`]: azalea_core::position::ChunkSectionPos +#[derive(Clone, Copy, PartialEq, Eq)] +#[repr(C)] +pub struct SmallChunkSectionPos { + pub y: i32, + pub x: i16, + pub z: i16, +} +impl SmallChunkSectionPos { + pub fn as_u64(self) -> u64 { + unsafe { mem::transmute::<_, u64>(self) } + } +} +impl From for SmallChunkSectionPos { + #[inline] + fn from(pos: BlockPos) -> Self { + Self { + x: (pos.x >> 4) as i16, + y: pos.y >> 4, + z: (pos.z >> 4) as i16, + } + } +} +impl PartialOrd for SmallChunkSectionPos { + fn partial_cmp(&self, other: &Self) -> Option { + self.as_u64().partial_cmp(&other.as_u64()) + } +} +impl Ord for SmallChunkSectionPos { + fn cmp(&self, other: &Self) -> cmp::Ordering { + self.as_u64().cmp(&other.as_u64()) + } +} diff --git a/azalea/src/pathfinder/rel_block_pos.rs b/azalea/src/pathfinder/rel_block_pos.rs deleted file mode 100644 index 0900ac91..00000000 --- a/azalea/src/pathfinder/rel_block_pos.rs +++ /dev/null @@ -1,133 +0,0 @@ -use std::{ - hash::{Hash, Hasher}, - mem::transmute, - ops::{Add, Mul}, -}; - -use azalea_core::position::BlockPos; - -/// An offset from a block position. -/// -/// This fits in 64 bits, so it's more efficient than a BlockPos in some cases. -/// -/// The X and Z are limited to ±32k. -#[derive(Clone, Copy, Debug, Eq, PartialEq)] -#[repr(C)] -pub struct RelBlockPos { - /// The actual non-relative Y coordinate of the block. - pub y: i32, - /// The X coordinate of the block, relative to some origin. - pub x: i16, - /// The Y coordinate of the block, relative to some origin. - pub z: i16, -} - -impl RelBlockPos { - pub fn get_origin(origin: BlockPos) -> Self { - Self::new(0, origin.y, 0) - } - - #[inline] - pub const fn new(x: i16, y: i32, z: i16) -> Self { - Self { x, y, z } - } - - #[inline] - pub fn apply(self, origin: BlockPos) -> BlockPos { - BlockPos::new(origin.x + self.x as i32, self.y, origin.z + self.z as i32) - } - - /// Create a new [`RelBlockPos`] from a given origin and new position. - #[inline] - pub fn from_origin(origin: BlockPos, new: BlockPos) -> Self { - Self { - x: (new.x - origin.x) as i16, - y: new.y, - z: (new.z - origin.z) as i16, - } - } - - #[inline] - pub fn up(&self, y: i32) -> Self { - Self { - x: self.x, - y: self.y + y, - z: self.z, - } - } - #[inline] - pub fn down(&self, y: i32) -> Self { - Self { - x: self.x, - y: self.y - y, - z: self.z, - } - } - #[inline] - pub fn north(&self, z: i16) -> Self { - Self { - x: self.x, - y: self.y, - z: self.z - z, - } - } - #[inline] - pub fn south(&self, z: i16) -> Self { - Self { - x: self.x, - y: self.y, - z: self.z + z, - } - } - #[inline] - pub fn east(&self, x: i16) -> Self { - Self { - x: self.x + x, - y: self.y, - z: self.z, - } - } - #[inline] - pub fn west(&self, x: i16) -> Self { - Self { - x: self.x - x, - y: self.y, - z: self.z, - } - } - - #[inline] - pub fn as_u64(self) -> u64 { - // SAFETY: RelBlockPos can be represented as a u64 - unsafe { transmute::(self) } - } -} - -impl Add for RelBlockPos { - type Output = RelBlockPos; - - fn add(self, rhs: RelBlockPos) -> Self::Output { - Self { - x: self.x + rhs.x, - y: self.y + rhs.y, - z: self.z + rhs.z, - } - } -} -impl Mul for RelBlockPos { - type Output = RelBlockPos; - - fn mul(self, rhs: i16) -> Self::Output { - Self { - x: self.x * rhs, - y: self.y * rhs as i32, - z: self.z * rhs, - } - } -} - -impl Hash for RelBlockPos { - fn hash(&self, state: &mut H) { - self.as_u64().hash(state); - } -} diff --git a/azalea/src/pathfinder/world.rs b/azalea/src/pathfinder/world.rs index 9970de8d..ec8aa259 100644 --- a/azalea/src/pathfinder/world.rs +++ b/azalea/src/pathfinder/world.rs @@ -1,6 +1,7 @@ use core::f32; use std::{ cell::{RefCell, UnsafeCell}, + cmp, mem, sync::Arc, }; @@ -14,7 +15,8 @@ use azalea_registry::{builtin::BlockKind, tags}; use azalea_world::{World, palette::PalettedContainer}; use parking_lot::RwLock; -use super::{mining::MiningCache, rel_block_pos::RelBlockPos}; +use super::{mining::MiningCache, positions::RelBlockPos}; +use crate::pathfinder::positions::SmallChunkSectionPos; /// An efficient representation of the world used for the pathfinder. pub struct CachedWorld { @@ -46,7 +48,7 @@ pub struct CachedSections { impl CachedSections { #[inline] - pub fn get_mut(&mut self, pos: ChunkSectionPos) -> Option<&mut CachedSection> { + pub fn get_mut(&mut self, pos: SmallChunkSectionPos) -> 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]); @@ -83,7 +85,7 @@ impl CachedSections { } pub struct CachedSection { - pub pos: ChunkSectionPos, + pub pos: SmallChunkSectionPos, pub bitsets: Box, } #[derive(Default)] @@ -130,7 +132,7 @@ impl CachedWorld { fn with_section( &self, - section_pos: ChunkSectionPos, + section_pos: SmallChunkSectionPos, f: impl FnOnce(&azalea_world::palette::PalettedContainer) -> T, ) -> Option { if section_pos.y * 16 < self.min_y { @@ -138,7 +140,7 @@ impl CachedWorld { return None; } - let chunk_pos = ChunkPos::from(section_pos); + let chunk_pos = ChunkPos::new(section_pos.x as i32, section_pos.z as i32); let section_index = azalea_world::chunk_storage::section_index(section_pos.y * 16, self.min_y) as usize; @@ -205,7 +207,7 @@ impl CachedWorld { Some(r) } - fn calculate_bitsets_for_section(&self, section_pos: ChunkSectionPos) -> CachedSection { + fn calculate_bitsets_for_section(&self, section_pos: SmallChunkSectionPos) -> CachedSection { let bitsets = self .with_section(section_pos, |section| { let mut passable_bitset = FastFixedBitSet::<4096>::new(); @@ -248,8 +250,10 @@ impl CachedWorld { pos: BlockPos, cb: impl FnOnce(&SectionBitsets, usize) -> bool, ) -> bool { - let (section_pos, section_block_pos) = - (ChunkSectionPos::from(pos), ChunkSectionBlockPos::from(pos)); + let (section_pos, section_block_pos) = ( + SmallChunkSectionPos::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() }; @@ -285,8 +289,10 @@ impl CachedWorld { } fn get_block_state_at_pos(&self, pos: BlockPos) -> BlockState { - let (section_pos, section_block_pos) = - (ChunkSectionPos::from(pos), ChunkSectionBlockPos::from(pos)); + let (section_pos, section_block_pos) = ( + SmallChunkSectionPos::from(pos), + ChunkSectionBlockPos::from(pos), + ); let index = u16::from(section_block_pos) as usize; self.with_section(section_pos, |section| section.get_at_index(index)) @@ -342,8 +348,10 @@ impl CachedWorld { let rel_pos = pos; let pos = pos.apply(self.origin); - let (section_pos, section_block_pos) = - (ChunkSectionPos::from(pos), ChunkSectionBlockPos::from(pos)); + let (section_pos, section_block_pos) = ( + SmallChunkSectionPos::from(pos), + ChunkSectionBlockPos::from(pos), + ); // we use this as an optimization to avoid getting the section again if the // block is in the same section @@ -436,7 +444,7 @@ impl CachedWorld { check: impl FnOnce(BlockState) -> bool, ) -> bool { let block_state = world - .with_section(ChunkSectionPos::from(pos), |section| { + .with_section(SmallChunkSectionPos::from(pos), |section| { section.get_at_index(u16::from(ChunkSectionBlockPos::from(pos)) as usize) }) .unwrap_or_default(); -- cgit v1.2.3