aboutsummaryrefslogtreecommitdiff
path: root/azalea
diff options
context:
space:
mode:
Diffstat (limited to 'azalea')
-rw-r--r--azalea/src/pathfinder/astar/heap.rs108
-rw-r--r--azalea/src/pathfinder/astar/mod.rs (renamed from azalea/src/pathfinder/astar.rs)108
-rw-r--r--azalea/src/pathfinder/goals.rs5
-rw-r--r--azalea/src/pathfinder/world.rs9
4 files changed, 117 insertions, 113 deletions
diff --git a/azalea/src/pathfinder/astar/heap.rs b/azalea/src/pathfinder/astar/heap.rs
new file mode 100644
index 00000000..3b20c0d2
--- /dev/null
+++ b/azalea/src/pathfinder/astar/heap.rs
@@ -0,0 +1,108 @@
+use std::{
+ cmp::{self, Reverse},
+ collections::BinaryHeap,
+};
+
+use radix_heap::RadixHeapMap;
+
+#[derive(Default)]
+pub struct PathfinderHeap {
+ /// Key is f_score.to_bits(), value is (g_score, index)
+ ///
+ /// As long as the f_score is positive, comparing it as bits is fine. Also,
+ /// it has to be `Reverse`d to make it a min-heap.
+ radix_heap: RadixHeapMap<Reverse<u32>, (f32, u32)>,
+ // fallback
+ binary_heap: BinaryHeap<WeightedNode>,
+}
+impl PathfinderHeap {
+ pub fn new() -> Self {
+ Self::default()
+ }
+
+ pub fn push(&mut self, item: WeightedNode) {
+ if let Some(top) = self.radix_heap.top() {
+ // this can happen when the heuristic wasn't an underestimate, so just fall back
+ // to a binary heap in those cases
+ if item.f_score < f32::from_bits(top.0) {
+ self.binary_heap.push(item);
+ return;
+ }
+ }
+ self.radix_heap
+ .push(Reverse(item.f_score.to_bits()), (item.g_score, item.index))
+ }
+ pub fn pop(&mut self) -> Option<WeightedNode> {
+ self.binary_heap.pop().or_else(|| {
+ self.radix_heap
+ .pop()
+ .map(|(f_score, (g_score, index))| WeightedNode {
+ f_score: f32::from_bits(f_score.0),
+ g_score,
+ index,
+ })
+ })
+ }
+}
+
+#[derive(PartialEq, Debug)]
+#[repr(C)]
+pub struct WeightedNode {
+ /// Sum of the g_score and heuristic
+ pub f_score: f32,
+ /// The actual cost to get to this node
+ pub g_score: f32,
+ pub index: u32,
+}
+
+impl Ord for WeightedNode {
+ #[inline]
+ fn cmp(&self, other: &Self) -> cmp::Ordering {
+ // intentionally inverted to make the BinaryHeap a min-heap
+ match other.f_score.total_cmp(&self.f_score) {
+ cmp::Ordering::Equal => self.g_score.total_cmp(&other.g_score),
+ s => s,
+ }
+ }
+}
+impl Eq for WeightedNode {}
+impl PartialOrd for WeightedNode {
+ #[inline]
+ fn partial_cmp(&self, other: &Self) -> Option<cmp::Ordering> {
+ Some(self.cmp(other))
+ }
+}
+
+#[cfg(test)]
+mod tests {
+ use super::*;
+
+ fn weighted_node(f: f32, g: f32) -> WeightedNode {
+ WeightedNode {
+ f_score: f,
+ g_score: g,
+ index: 0,
+ }
+ }
+
+ #[test]
+ fn test_weighted_node_eq() {
+ let a = weighted_node(0., 0.);
+ let b = weighted_node(0., 0.);
+ assert!(a == b);
+ }
+ #[test]
+ fn test_weighted_node_le() {
+ let a = weighted_node(1., 0.);
+ let b = weighted_node(0., 0.);
+ assert_eq!(a.cmp(&b), cmp::Ordering::Less);
+ assert!(a.le(&b));
+ }
+ #[test]
+ fn test_weighted_node_le_g() {
+ let a = weighted_node(0., 1.);
+ let b = weighted_node(0., 0.);
+ assert_eq!(a.cmp(&b), cmp::Ordering::Greater);
+ assert!(!a.le(&b));
+ }
+}
diff --git a/azalea/src/pathfinder/astar.rs b/azalea/src/pathfinder/astar/mod.rs
index 8eecd016..484ab572 100644
--- a/azalea/src/pathfinder/astar.rs
+++ b/azalea/src/pathfinder/astar/mod.rs
@@ -1,6 +1,6 @@
+pub mod heap;
+
use std::{
- cmp::{self, Reverse},
- collections::BinaryHeap,
fmt::{self, Debug},
hash::{BuildHasherDefault, Hash},
time::{Duration, Instant},
@@ -8,10 +8,11 @@ use std::{
use indexmap::IndexMap;
use num_format::ToFormattedString;
-use radix_heap::RadixHeapMap;
use rustc_hash::FxHasher;
use tracing::{debug, trace, warn};
+use crate::pathfinder::astar::heap::{PathfinderHeap, WeightedNode};
+
pub struct Path<P, M>
where
P: Eq + Hash + Copy + Debug,
@@ -287,73 +288,6 @@ impl<P: Hash + Copy + Clone, M: Clone> Clone for Movement<P, M> {
}
}
-#[derive(Default)]
-struct PathfinderHeap {
- binary_heap: BinaryHeap<WeightedNode>,
- /// Key is f_score.to_bits(), value is (g_score, index)
- ///
- /// As long as the f_score is positive, comparing it as bits is fine. Also,
- /// it has to be `Reverse`d to make it a min-heap.
- radix_heap: RadixHeapMap<Reverse<u32>, (f32, u32)>,
-}
-impl PathfinderHeap {
- pub fn new() -> Self {
- Self::default()
- }
-
- pub fn push(&mut self, item: WeightedNode) {
- if let Some(top) = self.radix_heap.top() {
- // this can happen when the heuristic wasn't an underestimate, so just fall back
- // to a binary heap in those cases
- if item.f_score < f32::from_bits(top.0) {
- self.binary_heap.push(item);
- return;
- }
- }
- self.radix_heap
- .push(Reverse(item.f_score.to_bits()), (item.g_score, item.index))
- }
- pub fn pop(&mut self) -> Option<WeightedNode> {
- self.binary_heap.pop().or_else(|| {
- self.radix_heap
- .pop()
- .map(|(f_score, (g_score, index))| WeightedNode {
- f_score: f32::from_bits(f_score.0),
- g_score,
- index,
- })
- })
- }
-}
-
-#[derive(PartialEq, Debug)]
-#[repr(C)]
-pub struct WeightedNode {
- /// Sum of the g_score and heuristic
- pub f_score: f32,
- /// The actual cost to get to this node
- pub g_score: f32,
- pub index: u32,
-}
-
-impl Ord for WeightedNode {
- #[inline]
- fn cmp(&self, other: &Self) -> cmp::Ordering {
- // intentionally inverted to make the BinaryHeap a min-heap
- match other.f_score.total_cmp(&self.f_score) {
- cmp::Ordering::Equal => self.g_score.total_cmp(&other.g_score),
- s => s,
- }
- }
-}
-impl Eq for WeightedNode {}
-impl PartialOrd for WeightedNode {
- #[inline]
- fn partial_cmp(&self, other: &Self) -> Option<cmp::Ordering> {
- Some(self.cmp(other))
- }
-}
-
/// A timeout that the pathfinder will consider when calculating a path.
///
/// See [`PathfinderOpts::min_timeout`] and [`PathfinderOpts::max_timeout`] if
@@ -379,37 +313,3 @@ impl Default for PathfinderTimeout {
Self::Time(Duration::from_secs(1))
}
}
-
-#[cfg(test)]
-mod tests {
- use super::*;
-
- fn weighted_node(f: f32, g: f32) -> WeightedNode {
- WeightedNode {
- f_score: f,
- g_score: g,
- index: 0,
- }
- }
-
- #[test]
- fn test_weighted_node_eq() {
- let a = weighted_node(0., 0.);
- let b = weighted_node(0., 0.);
- assert!(a == b);
- }
- #[test]
- fn test_weighted_node_le() {
- let a = weighted_node(1., 0.);
- let b = weighted_node(0., 0.);
- assert_eq!(a.cmp(&b), cmp::Ordering::Less);
- assert!(a.le(&b));
- }
- #[test]
- fn test_weighted_node_le_g() {
- let a = weighted_node(0., 1.);
- let b = weighted_node(0., 0.);
- assert_eq!(a.cmp(&b), cmp::Ordering::Greater);
- assert!(!a.le(&b));
- }
-}
diff --git a/azalea/src/pathfinder/goals.rs b/azalea/src/pathfinder/goals.rs
index 26915b2f..25db9c8e 100644
--- a/azalea/src/pathfinder/goals.rs
+++ b/azalea/src/pathfinder/goals.rs
@@ -98,6 +98,7 @@ impl From<BlockPos> for XZGoal {
fn y_heuristic(dy: f32) -> f32 {
if dy > 0. {
if BARITONE_COMPAT {
+ // this is wrong because it can be an overestimate
return *JUMP_ONE_BLOCK_COST * dy;
}
@@ -107,8 +108,8 @@ fn y_heuristic(dy: f32) -> f32 {
(f32::max(*JUMP_ONE_BLOCK_COST, WALK_ONE_BLOCK_COST) + JUMP_PENALTY - SPRINT_ONE_BLOCK_COST)
* dy
} else if dy < 0. {
- // this is an overestimate (copied from baritone), but fixing it makes perf
- // worse
+ // this is also an overestimate (copied from baritone), but fixing it makes perf
+ // too much worse
(FALL_N_BLOCKS_COST[2] / 2.) * -dy
} else {
0.
diff --git a/azalea/src/pathfinder/world.rs b/azalea/src/pathfinder/world.rs
index ec2dbe80..9970de8d 100644
--- a/azalea/src/pathfinder/world.rs
+++ b/azalea/src/pathfinder/world.rs
@@ -29,12 +29,7 @@ pub struct CachedWorld {
// 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<BlockState>>,
- )>,
- >,
+ cached_chunks: RefCell<Vec<(ChunkPos, Box<[PalettedContainer<BlockState>]>)>>,
last_chunk_cache_index: RefCell<Option<usize>>,
cached_blocks: UnsafeCell<CachedSections>,
@@ -194,7 +189,7 @@ impl CachedWorld {
.sections
.iter()
.map(|section| section.states.clone())
- .collect::<Vec<PalettedContainer<BlockState>>>();
+ .collect::<Box<[PalettedContainer<BlockState>]>>();
if section_index >= sections.len() {
// y position is out of bounds
generated by cgit v1.2.3 (git 2.39.1) at 2026-05-17 06:01:14 +0000