optimize pathfinder more

azalea-rs · Oct 2, 2023 · d0505f7 · d0505f7
1 parent c3d2748
commit d0505f7
Show file tree

Hide file tree

Showing 13 changed files with 209 additions and 150 deletions.
diff --git a/Cargo.lock b/Cargo.lock
diff --git a/azalea-client/src/local_player.rs b/azalea-client/src/local_player.rs
@@ -127,7 +127,7 @@ impl InstanceHolder {
         InstanceHolder {
             instance: world,
             partial_instance: Arc::new(RwLock::new(PartialInstance::new(
-                azalea_world::calculate_chunk_storage_range(
+                azalea_world::chunk_storage::calculate_chunk_storage_range(
                     client_information.view_distance.into(),
                 ),
                 Some(entity),

diff --git a/azalea-client/src/packet_handling/game.rs b/azalea-client/src/packet_handling/game.rs
@@ -267,7 +267,7 @@ pub fn process_packet_events(ecs: &mut World) {
                     // instance_container)
 
                     *instance_holder.partial_instance.write() = PartialInstance::new(
-                        azalea_world::calculate_chunk_storage_range(
+                        azalea_world::chunk_storage::calculate_chunk_storage_range(
                             client_information.view_distance.into(),
                         ),
                         // this argument makes it so other clients don't update this player entity
@@ -1287,7 +1287,7 @@ pub fn process_packet_events(ecs: &mut World) {
                     // (when we add chunks or entities those will be in the
                     // instance_container)
                     *instance_holder.partial_instance.write() = PartialInstance::new(
-                        azalea_world::calculate_chunk_storage_range(
+                        azalea_world::chunk_storage::calculate_chunk_storage_range(
                             client_information.view_distance.into(),
                         ),
                         Some(player_entity),

diff --git a/azalea-core/Cargo.toml b/azalea-core/Cargo.toml
@@ -14,6 +14,7 @@ azalea-inventory = { version = "0.8.0", path = "../azalea-inventory" }
 azalea-nbt = { path = "../azalea-nbt", version = "0.8.0" }
 azalea-registry = { path = "../azalea-registry", version = "0.8.0" }
 bevy_ecs = { version = "0.11.2", default-features = false, optional = true }
+nohash-hasher = "0.2.0"
 num-traits = "0.2.16"
 serde = { version = "^1.0", optional = true }
 uuid = "^1.4.1"

diff --git a/azalea-core/src/position.rs b/azalea-core/src/position.rs
@@ -5,6 +5,7 @@
 
 use azalea_buf::{BufReadError, McBuf, McBufReadable, McBufWritable};
 use std::{
+    hash::Hash,
     io::{Cursor, Write},
     ops::{Add, AddAssign, Mul, Rem, Sub},
 };
@@ -193,7 +194,7 @@ impl BlockPos {
 
 /// Chunk coordinates are used to represent where a chunk is in the world. You
 /// can convert the x and z to block coordinates by multiplying them by 16.
-#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, Hash, McBuf)]
+#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, McBuf)]
 pub struct ChunkPos {
     pub x: i32,
     pub z: i32,
@@ -213,6 +214,16 @@ impl Add<ChunkPos> for ChunkPos {
         }
     }
 }
+impl Hash for ChunkPos {
+    fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
+        // optimized hash that only calls hash once
+        let combined = (self.x as u64) << 32 | (self.z as u64);
+        combined.hash(state);
+    }
+}
+/// nohash_hasher lets us have IntMap<ChunkPos, _> which is significantly faster
+/// than a normal HashMap
+impl nohash_hasher::IsEnabled for ChunkPos {}
 
 /// The coordinates of a chunk section in the world.
 #[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
@@ -273,6 +284,7 @@ pub struct GlobalPos {
 }
 
 impl From<&BlockPos> for ChunkPos {
+    #[inline]
     fn from(pos: &BlockPos) -> Self {
         ChunkPos {
             x: pos.x.div_floor(16),
@@ -298,6 +310,7 @@ impl From<ChunkSectionPos> for ChunkPos {
 }
 
 impl From<&BlockPos> for ChunkBlockPos {
+    #[inline]
     fn from(pos: &BlockPos) -> Self {
         ChunkBlockPos {
             x: pos.x.rem_euclid(16) as u8,
@@ -318,6 +331,7 @@ impl From<&BlockPos> for ChunkSectionBlockPos {
 }
 
 impl From<&ChunkBlockPos> for ChunkSectionBlockPos {
+    #[inline]
     fn from(pos: &ChunkBlockPos) -> Self {
         ChunkSectionBlockPos {
             x: pos.x,
@@ -327,6 +341,7 @@ impl From<&ChunkBlockPos> for ChunkSectionBlockPos {
     }
 }
 impl From<&Vec3> for BlockPos {
+    #[inline]
     fn from(pos: &Vec3) -> Self {
         BlockPos {
             x: pos.x.floor() as i32,
@@ -336,6 +351,7 @@ impl From<&Vec3> for BlockPos {
     }
 }
 impl From<Vec3> for BlockPos {
+    #[inline]
     fn from(pos: Vec3) -> Self {
         BlockPos::from(&pos)
     }

diff --git a/azalea-world/src/chunk_storage.rs b/azalea-world/src/chunk_storage.rs
@@ -7,6 +7,7 @@ use azalea_buf::{BufReadError, McBufReadable, McBufWritable};
 use azalea_core::position::{BlockPos, ChunkBlockPos, ChunkPos, ChunkSectionBlockPos};
 use azalea_nbt::NbtCompound;
 use log::{debug, trace, warn};
+use nohash_hasher::IntMap;
 use parking_lot::RwLock;
 use std::str::FromStr;
 use std::{
@@ -37,7 +38,7 @@ pub struct PartialChunkStorage {
 pub struct ChunkStorage {
     pub height: u32,
     pub min_y: i32,
-    pub map: HashMap<ChunkPos, Weak<RwLock<Chunk>>>,
+    pub map: IntMap<ChunkPos, Weak<RwLock<Chunk>>>,
 }
 
 /// A single chunk in a world (16*?*16 blocks). This only contains the blocks
@@ -214,7 +215,7 @@ impl ChunkStorage {
         ChunkStorage {
             height,
             min_y,
-            map: HashMap::new(),
+            map: IntMap::default(),
         }
     }
 

diff --git a/azalea-world/src/lib.rs b/azalea-world/src/lib.rs
@@ -3,7 +3,7 @@
 #![feature(error_generic_member_access)]
 
 mod bit_storage;
-mod chunk_storage;
+pub mod chunk_storage;
 mod container;
 pub mod heightmap;
 pub mod iterators;
@@ -13,9 +13,7 @@ mod world;
 use std::backtrace::Backtrace;
 
 pub use bit_storage::BitStorage;
-pub use chunk_storage::{
-    calculate_chunk_storage_range, Chunk, ChunkStorage, PartialChunkStorage, Section,
-};
+pub use chunk_storage::{Chunk, ChunkStorage, PartialChunkStorage, Section};
 pub use container::*;
 use thiserror::Error;
 pub use world::*;

diff --git a/azalea/benches/pathfinder.rs b/azalea/benches/pathfinder.rs
@@ -4,6 +4,7 @@ use azalea::{
     pathfinder::{
         astar::{self, a_star},
         goals::BlockPosGoal,
+        moves::PathfinderCtx,
         Goal,
     },
     BlockPos,
@@ -73,13 +74,14 @@ fn generate_bedrock_world(
 fn bench_pathfinder(c: &mut Criterion) {
     c.bench_function("bedrock", |b| {
         let mut partial_chunks = PartialChunkStorage::new(32);
-        let successors_fn = azalea::pathfinder::moves::parkour::parkour_move;
+        let successors_fn = azalea::pathfinder::moves::default_move;
 
         b.iter(|| {
             let (world, start, end) = generate_bedrock_world(&mut partial_chunks, 4);
+            let ctx = PathfinderCtx::new(&world);
             let goal = BlockPosGoal(end);
 
-            let successors = |pos: BlockPos| successors_fn(&world, pos);
+            let successors = |pos: BlockPos| successors_fn(&ctx, pos);
 
             let astar::Path { movements, partial } = a_star(
                 start,

diff --git a/azalea/src/pathfinder/astar.rs b/azalea/src/pathfinder/astar.rs
@@ -26,14 +26,14 @@ const MIN_IMPROVEMENT: f32 = 0.01;
 pub fn a_star<P, M, HeuristicFn, SuccessorsFn, SuccessFn>(
     start: P,
     heuristic: HeuristicFn,
-    successors: SuccessorsFn,
+    mut successors: SuccessorsFn,
     success: SuccessFn,
     timeout: Duration,
 ) -> Path<P, M>
 where
     P: Eq + Hash + Copy + Debug,
     HeuristicFn: Fn(P) -> f32,
-    SuccessorsFn: Fn(P) -> Vec<Edge<P, M>>,
+    SuccessorsFn: FnMut(P) -> Vec<Edge<P, M>>,
     SuccessFn: Fn(P) -> bool,
 {
     let start_time = Instant::now();

diff --git a/azalea/src/pathfinder/mod.rs b/azalea/src/pathfinder/mod.rs
@@ -19,6 +19,7 @@ use crate::ecs::{
     query::{With, Without},
     system::{Commands, Query, Res},
 };
+use crate::pathfinder::moves::PathfinderCtx;
 use azalea_client::movement::walk_listener;
 use azalea_client::{StartSprintEvent, StartWalkEvent};
 use azalea_core::position::BlockPos;
@@ -178,7 +179,8 @@ fn goto_listener(
             debug!("start: {start:?}");
 
             let world = &world_lock.read().chunks;
-            let successors = |pos: BlockPos| successors_fn(world, pos);
+            let ctx = PathfinderCtx::new(world);
+            let successors = |pos: BlockPos| successors_fn(&ctx, pos);
 
             let mut attempt_number = 0;
 
@@ -192,15 +194,20 @@ fn goto_listener(
                     |n| goal.heuristic(n),
                     successors,
                     |n| goal.success(n),
-                    Duration::from_secs(if attempt_number == 0 { 1 } else { 5 }),
+                    Duration::from_secs(if attempt_number == 0 { 10 } else { 10 }),
                 );
                 let end_time = std::time::Instant::now();
                 debug!("partial: {partial:?}");
-                debug!("time: {:?}", end_time - start_time);
+                let duration = end_time - start_time;
+                if partial {
+                    info!("Pathfinder took {duration:?} (timed out)");
+                } else {
+                    info!("Pathfinder took {duration:?}");
+                }
 
-                info!("Path:");
+                debug!("Path:");
                 for movement in &movements {
-                    info!("  {:?}", movement.target);
+                    debug!("  {:?}", movement.target);
                 }
 
                 path = movements.into_iter().collect::<VecDeque<_>>();
@@ -275,11 +282,10 @@ fn path_found_listener(
                         let world_lock = instance_container.get(instance_name).expect(
                             "Entity tried to pathfind but the entity isn't in a valid world",
                         );
+                        let world = &world_lock.read().chunks;
+                        let ctx = PathfinderCtx::new(&world);
                         let successors_fn: moves::SuccessorsFn = event.successors_fn;
-                        let successors = |pos: BlockPos| {
-                            let world = &world_lock.read().chunks;
-                            successors_fn(world, pos)
-                        };
+                        let successors = |pos: BlockPos| successors_fn(&ctx, pos);
 
                         if successors(last_node.target)
                             .iter()
@@ -439,10 +445,9 @@ fn tick_execute_path(
 
         {
             // obstruction check (the path we're executing isn't possible anymore)
-            let successors = |pos: BlockPos| {
-                let world = &world_lock.read().chunks;
-                successors_fn(world, pos)
-            };
+            let world = &world_lock.read().chunks;
+            let ctx = PathfinderCtx::new(&world);
+            let successors = |pos: BlockPos| successors_fn(&ctx, pos);
 
             if let Some(last_reached_node) = pathfinder.last_reached_node {
                 if let Some(obstructed_index) =

diff --git a/azalea/src/pathfinder/moves/basic.rs b/azalea/src/pathfinder/moves/basic.rs
@@ -5,33 +5,29 @@ use azalea_core::{
     direction::CardinalDirection,
     position::{BlockPos, Vec3},
 };
-use azalea_world::ChunkStorage;
 
 use crate::{
     pathfinder::{astar, costs::*},
     JumpEvent, LookAtEvent,
 };
 
-use super::{
-    default_is_reached, fall_distance, is_block_passable, is_passable, is_standable, Edge,
-    ExecuteCtx, IsReachedCtx, MoveData,
-};
+use super::{default_is_reached, Edge, ExecuteCtx, IsReachedCtx, MoveData, PathfinderCtx};
 
-pub fn basic_move(world: &ChunkStorage, node: BlockPos) -> Vec<Edge> {
+pub fn basic_move(ctx: &PathfinderCtx, node: BlockPos) -> Vec<Edge> {
     let mut edges = Vec::new();
-    edges.extend(forward_move(world, node));
-    edges.extend(ascend_move(world, node));
-    edges.extend(descend_move(world, node));
-    edges.extend(diagonal_move(world, node));
+    edges.extend(forward_move(ctx, node));
+    edges.extend(ascend_move(ctx, node));
+    edges.extend(descend_move(ctx, node));
+    edges.extend(diagonal_move(ctx, node));
     edges
 }
 
-fn forward_move(world: &ChunkStorage, pos: BlockPos) -> Vec<Edge> {
+fn forward_move(ctx: &PathfinderCtx, pos: BlockPos) -> Vec<Edge> {
     let mut edges = Vec::new();
     for dir in CardinalDirection::iter() {
         let offset = BlockPos::new(dir.x(), 0, dir.z());
 
-        if !is_standable(&(pos + offset), world) {
+        if !ctx.is_standable(&(pos + offset)) {
             continue;
         }
 
@@ -72,15 +68,15 @@ fn execute_forward_move(
     });
 }
 
-fn ascend_move(world: &ChunkStorage, pos: BlockPos) -> Vec<Edge> {
+fn ascend_move(ctx: &PathfinderCtx, pos: BlockPos) -> Vec<Edge> {
     let mut edges = Vec::new();
     for dir in CardinalDirection::iter() {
         let offset = BlockPos::new(dir.x(), 1, dir.z());
 
-        if !is_block_passable(&pos.up(2), world) {
+        if !ctx.is_block_passable(&pos.up(2)) {
             continue;
         }
-        if !is_standable(&(pos + offset), world) {
+        if !ctx.is_standable(&(pos + offset)) {
             continue;
         }
 
@@ -156,23 +152,23 @@ pub fn ascend_is_reached(
     BlockPos::from(position) == target || BlockPos::from(position) == target.down(1)
 }
 
-fn descend_move(world: &ChunkStorage, pos: BlockPos) -> Vec<Edge> {
+fn descend_move(ctx: &PathfinderCtx, pos: BlockPos) -> Vec<Edge> {
     let mut edges = Vec::new();
     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 = fall_distance(&new_horizontal_position, world);
+        let fall_distance = ctx.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 !is_passable(&new_horizontal_position, world) {
+        if !ctx.is_passable(&new_horizontal_position) {
             continue;
         }
         // check whether we can stand on the target position
-        if !is_standable(&new_position, world) {
+        if !ctx.is_standable(&new_position) {
             continue;
         }
 
@@ -258,22 +254,22 @@ pub fn descend_is_reached(
         && (position.y - target.y as f64) < 0.5
 }
 
-fn diagonal_move(world: &ChunkStorage, pos: BlockPos) -> Vec<Edge> {
+fn diagonal_move(ctx: &PathfinderCtx, pos: BlockPos) -> Vec<Edge> {
     let mut edges = Vec::new();
     for dir in CardinalDirection::iter() {
         let right = dir.right();
         let offset = BlockPos::new(dir.x() + right.x(), 0, dir.z() + right.z());
 
-        if !is_passable(
-            &BlockPos::new(pos.x + dir.x(), pos.y, pos.z + dir.z()),
-            world,
-        ) && !is_passable(
-            &BlockPos::new(pos.x + dir.right().x(), pos.y, pos.z + dir.right().z()),
-            world,
-        ) {
+        if !ctx.is_passable(&BlockPos::new(pos.x + dir.x(), pos.y, pos.z + dir.z()))
+            && !ctx.is_passable(&BlockPos::new(
+                pos.x + dir.right().x(),
+                pos.y,
+                pos.z + dir.right().z(),
+            ))
+        {
             continue;
         }
-        if !is_standable(&(pos + offset), world) {
+        if !ctx.is_standable(&(pos + offset)) {
             continue;
         }
         // +0.001 so it doesn't unnecessarily go diagonal sometimes