Add mining to the pathfinder (#122)

* basic pathfinder mining poc

* mining descending and autotool

* pathfinder mining descending

* pathfinder fixes

* allow disabling pathfinder miner and other fixes

* small optimization to avoid chunk vec iter lookup sometimes

* seeded rng in pathfinder bench

* consistently use f32::INFINITY

this brings performance much closer to how it was before

* astar heuristic optimization from baritone

* add downward_move

* fix downward move execute

* avoid liquids and falling blocks when mining

* fix COST_HEURISTIC

* fix to not path through flowing liquids

* only reset pathfinder timeout while mining if the block is close enough

* cache mining costs of block positions

* fix mine_while_at_start and move PathfinderDebugParticles to its own module

* add ReachBlockPosGoal

in other news: azalea's sin/cos functions were broken this whole time and i never noticed

* clippy and add things that i accidentally didn't commit

* improve wording on doc for azalea::pathfinder

1 files changed, 228 insertions, 12 deletions

diff --git a/azalea/src/pathfinder/world.rs b/azalea/src/pathfinder/world.rs
index 4b48f921..a5a273fb 100644
--- a/azalea/src/pathfinder/world.rs
+++ b/azalea/src/pathfinder/world.rs
@@ -11,6 +11,9 @@ use azalea_core::{
 use azalea_physics::collision::BlockWithShape;
 use azalea_world::Instance;
 use parking_lot::RwLock;
+use rustc_hash::FxHashMap;
+
+use super::mining::MiningCache;
 
 /// An efficient representation of the world used for the pathfinder.
 pub struct CachedWorld {
@@ -20,8 +23,11 @@ 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>)>>,
+    last_chunk_cache_index: RefCell<Option<usize>>,
 
     cached_blocks: UnsafeCell<CachedSections>,
+
+    cached_mining_costs: RefCell<FxHashMap<BlockPos, f32>>,
 }
 
 #[derive(Default)]
@@ -82,7 +88,9 @@ impl CachedWorld {
             min_y,
             world_lock,
             cached_chunks: Default::default(),
+            last_chunk_cache_index: Default::default(),
             cached_blocks: Default::default(),
+            cached_mining_costs: Default::default(),
         }
     }
 
@@ -100,24 +108,50 @@ impl CachedWorld {
         section_pos: ChunkSectionPos,
         f: impl FnOnce(&azalea_world::palette::PalettedContainer) -> T,
     ) -> Option<T> {
+        if section_pos.y * 16 < self.min_y {
+            // y position is out of bounds
+            return None;
+        }
+
         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
+        // optimization: avoid doing the iter lookup if the last chunk we looked up is
+        // the same
+        if let Some(last_chunk_cache_index) = *self.last_chunk_cache_index.borrow() {
+            if cached_chunks[last_chunk_cache_index].0 == chunk_pos {
+                // don't bother with the iter lookup
+                let sections = &cached_chunks[last_chunk_cache_index].1;
+                if section_index >= sections.len() {
+                    // y position is out of bounds
+                    return None;
+                };
+                let section: &azalea_world::palette::PalettedContainer = &sections[section_index];
+                return Some(f(section));
             }
-        }) {
+        }
+
+        // get section from cache
+        if let Some((chunk_index, sections)) =
+            cached_chunks
+                .iter()
+                .enumerate()
+                .find_map(|(i, (pos, sections))| {
+                    if *pos == chunk_pos {
+                        Some((i, sections))
+                    } else {
+                        None
+                    }
+                })
+        {
             if section_index >= sections.len() {
                 // y position is out of bounds
                 return None;
             };
+            *self.last_chunk_cache_index.borrow_mut() = Some(chunk_index);
             let section: &azalea_world::palette::PalettedContainer = &sections[section_index];
             return Some(f(section));
         }
@@ -206,18 +240,189 @@ impl CachedWorld {
         solid
     }
 
+    /// Returns how much it costs to break this block. Returns 0 if the block is
+    /// already passable.
+    pub fn cost_for_breaking_block(&self, pos: BlockPos, mining_cache: &MiningCache) -> f32 {
+        let mut cached_mining_costs = self.cached_mining_costs.borrow_mut();
+
+        if let Some(&cost) = cached_mining_costs.get(&pos) {
+            return cost;
+        }
+
+        let cost = self.uncached_cost_for_breaking_block(pos, mining_cache);
+        cached_mining_costs.insert(pos, cost);
+        cost
+    }
+
+    fn uncached_cost_for_breaking_block(&self, pos: BlockPos, mining_cache: &MiningCache) -> f32 {
+        if self.is_block_passable(pos) {
+            // if the block is passable then it doesn't need to be broken
+            return 0.;
+        }
+
+        let (section_pos, section_block_pos) =
+            (ChunkSectionPos::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
+        let up_is_in_same_section = section_block_pos.y != 15;
+        let north_is_in_same_section = section_block_pos.z != 0;
+        let east_is_in_same_section = section_block_pos.x != 15;
+        let south_is_in_same_section = section_block_pos.z != 15;
+        let west_is_in_same_section = section_block_pos.x != 0;
+
+        let Some(mining_cost) = self.with_section(section_pos, |section| {
+            let block_state =
+                BlockState::try_from(section.get_at_index(u16::from(section_block_pos) as usize))
+                    .unwrap_or_default();
+            let mining_cost = mining_cache.cost_for(block_state);
+
+            if mining_cost == f32::INFINITY {
+                // the block is unbreakable
+                return f32::INFINITY;
+            }
+
+            // if there's a falling block or liquid above this block, abort
+            if up_is_in_same_section {
+                let up_block = BlockState::try_from(
+                    section.get_at_index(u16::from(section_block_pos.up(1)) as usize),
+                )
+                .unwrap_or_default();
+                if mining_cache.is_liquid(up_block) || mining_cache.is_falling_block(up_block) {
+                    return f32::INFINITY;
+                }
+            }
+
+            // if there's a liquid to the north of this block, abort
+            if north_is_in_same_section {
+                let north_block = BlockState::try_from(
+                    section.get_at_index(u16::from(section_block_pos.north(1)) as usize),
+                )
+                .unwrap_or_default();
+                if mining_cache.is_liquid(north_block) {
+                    return f32::INFINITY;
+                }
+            }
+
+            // liquid to the east
+            if east_is_in_same_section {
+                let east_block = BlockState::try_from(
+                    section.get_at_index(u16::from(section_block_pos.east(1)) as usize),
+                )
+                .unwrap_or_default();
+                if mining_cache.is_liquid(east_block) {
+                    return f32::INFINITY;
+                }
+            }
+
+            // liquid to the south
+            if south_is_in_same_section {
+                let south_block = BlockState::try_from(
+                    section.get_at_index(u16::from(section_block_pos.south(1)) as usize),
+                )
+                .unwrap_or_default();
+                if mining_cache.is_liquid(south_block) {
+                    return f32::INFINITY;
+                }
+            }
+
+            // liquid to the west
+            if west_is_in_same_section {
+                let west_block = BlockState::try_from(
+                    section.get_at_index(u16::from(section_block_pos.west(1)) as usize),
+                )
+                .unwrap_or_default();
+                if mining_cache.is_liquid(west_block) {
+                    return f32::INFINITY;
+                }
+            }
+
+            // the block is probably safe to break, we'll have to check the adjacent blocks
+            // that weren't in the same section next though
+            mining_cost
+        }) else {
+            // the chunk isn't loaded
+            let cost = if self.is_block_solid(pos) {
+                // assume it's unbreakable if it's solid and out of render distance
+                f32::INFINITY
+            } else {
+                0.
+            };
+            return cost;
+        };
+
+        if mining_cost == f32::INFINITY {
+            // the block is unbreakable
+            return f32::INFINITY;
+        }
+
+        let check_should_avoid_this_block = |pos: BlockPos, check: &dyn Fn(BlockState) -> bool| {
+            let block_state = self
+                .with_section(ChunkSectionPos::from(pos), |section| {
+                    BlockState::try_from(
+                        section.get_at_index(u16::from(ChunkSectionBlockPos::from(pos)) as usize),
+                    )
+                    .unwrap_or_default()
+                })
+                .unwrap_or_default();
+            check(block_state)
+        };
+
+        // check the adjacent blocks that weren't in the same section
+        if !up_is_in_same_section
+            && check_should_avoid_this_block(pos.up(1), &|b| {
+                mining_cache.is_liquid(b) || mining_cache.is_falling_block(b)
+            })
+        {
+            return f32::INFINITY;
+        }
+        if !north_is_in_same_section
+            && check_should_avoid_this_block(pos.north(1), &|b| mining_cache.is_liquid(b))
+        {
+            return f32::INFINITY;
+        }
+        if !east_is_in_same_section
+            && check_should_avoid_this_block(pos.east(1), &|b| mining_cache.is_liquid(b))
+        {
+            return f32::INFINITY;
+        }
+        if !south_is_in_same_section
+            && check_should_avoid_this_block(pos.south(1), &|b| mining_cache.is_liquid(b))
+        {
+            return f32::INFINITY;
+        }
+        if !west_is_in_same_section
+            && check_should_avoid_this_block(pos.west(1), &|b| mining_cache.is_liquid(b))
+        {
+            return f32::INFINITY;
+        }
+
+        mining_cost
+    }
+
     /// 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))
     }
 
+    pub fn cost_for_passing(&self, pos: BlockPos, mining_cache: &MiningCache) -> f32 {
+        self.cost_for_breaking_block(pos, mining_cache)
+            + self.cost_for_breaking_block(pos.up(1), mining_cache)
+    }
+
     /// 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)
     }
 
+    pub fn cost_for_standing(&self, pos: BlockPos, mining_cache: &MiningCache) -> f32 {
+        if !self.is_block_solid(pos.down(1)) {
+            return f32::INFINITY;
+        }
+        self.cost_for_passing(pos, mining_cache)
+    }
+
     /// 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;
@@ -235,7 +440,10 @@ impl CachedWorld {
 }
 
 /// whether this block is passable
-fn is_block_state_passable(block: BlockState) -> bool {
+pub fn is_block_state_passable(block: BlockState) -> bool {
+    // i already tried optimizing this by having it cache in an IntMap/FxHashMap but
+    // it wasn't measurably faster
+
     if block.is_air() {
         // fast path
         return true;
@@ -243,7 +451,8 @@ fn is_block_state_passable(block: BlockState) -> bool {
     if !block.is_shape_empty() {
         return false;
     }
-    if block == azalea_registry::Block::Water.into() {
+    let registry_block = azalea_registry::Block::from(block);
+    if registry_block == azalea_registry::Block::Water {
         return false;
     }
     if block
@@ -252,7 +461,7 @@ fn is_block_state_passable(block: BlockState) -> bool {
     {
         return false;
     }
-    if block == azalea_registry::Block::Lava.into() {
+    if registry_block == azalea_registry::Block::Lava {
         return false;
     }
     // block.waterlogged currently doesn't account for seagrass and some other water
@@ -261,11 +470,18 @@ fn is_block_state_passable(block: BlockState) -> bool {
         return false;
     }
 
+    // don't walk into fire
+    if registry_block == azalea_registry::Block::Fire
+        || registry_block == azalea_registry::Block::SoulFire
+    {
+        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 {
+pub fn is_block_state_solid(block: BlockState) -> bool {
     if block.is_air() {
         // fast path
         return false;