keep working on find_block

azalea-rs · mat-1 · Mar 8, 2023 · Feb 27, 2023 · Mar 7, 2023 · Mar 8, 2023
commit 7d20b8c6945ae79e207305f087a3a79a41daa188
diff --git a/azalea-block/src/range.rs b/azalea-block/src/range.rs
@@ -1,6 +1,6 @@
 use std::ops::RangeInclusive;
 
-#[derive(Debug, Clone, )]
+#[derive(Debug, Clone)]
 pub struct BlockStateRange {
     pub id: RangeInclusive<u32>,
 }
diff --git a/azalea-core/src/position.rs b/azalea-core/src/position.rs
@@ -153,7 +153,7 @@ impl ChunkPos {
         ChunkPos { x, z }
     }
 }
-impl Add for ChunkPos {
+impl Add<ChunkPos> for ChunkPos {
     type Output = Self;
 
     fn add(self, rhs: Self) -> Self::Output {

diff --git a/azalea-physics/src/lib.rs b/azalea-physics/src/lib.rs
@@ -463,8 +463,8 @@ mod tests {
             .id();
         let block_state = partial_world.chunks.set_block_state(
             &BlockPos { x: 0, y: 69, z: 0 },
-            azalea_block::StoneSlabBlock {
-                kind: azalea_block::Type::Bottom,
+            azalea_block::blocks::StoneSlabBlock {
+                kind: azalea_block::blocks::Type::Bottom,
                 waterlogged: false,
             }
             .into(),
@@ -516,8 +516,8 @@ mod tests {
             .id();
         let block_state = world_lock.write().chunks.set_block_state(
             &BlockPos { x: 0, y: 69, z: 0 },
-            azalea_block::StoneSlabBlock {
-                kind: azalea_block::Type::Top,
+            azalea_block::blocks::StoneSlabBlock {
+                kind: azalea_block::blocks::Type::Top,
                 waterlogged: false,
             }
             .into(),
@@ -568,11 +568,11 @@ mod tests {
             .id();
         let block_state = world_lock.write().chunks.set_block_state(
             &BlockPos { x: 0, y: 69, z: 0 },
-            azalea_block::CobblestoneWallBlock {
-                east: azalea_block::EastWall::Low,
-                north: azalea_block::NorthWall::Low,
-                south: azalea_block::SouthWall::Low,
-                west: azalea_block::WestWall::Low,
+            azalea_block::blocks::CobblestoneWallBlock {
+                east: azalea_block::blocks::EastWall::Low,
+                north: azalea_block::blocks::NorthWall::Low,
+                south: azalea_block::blocks::SouthWall::Low,
+                west: azalea_block::blocks::WestWall::Low,
                 up: false,
                 waterlogged: false,
             }
@@ -629,11 +629,11 @@ mod tests {
                 y: 69,
                 z: -8,
             },
-            azalea_block::CobblestoneWallBlock {
-                east: azalea_block::EastWall::Low,
-                north: azalea_block::NorthWall::Low,
-                south: azalea_block::SouthWall::Low,
-                west: azalea_block::WestWall::Low,
+            azalea_block::blocks::CobblestoneWallBlock {
+                east: azalea_block::blocks::EastWall::Low,
+                north: azalea_block::blocks::NorthWall::Low,
+                south: azalea_block::blocks::SouthWall::Low,
+                west: azalea_block::blocks::WestWall::Low,
                 up: false,
                 waterlogged: false,
             }

diff --git a/azalea-world/src/bit_storage.rs b/azalea-world/src/bit_storage.rs
@@ -158,13 +158,13 @@ impl BitStorage {
             .unwrap()
     }
 
+    /// Get the data at the given index.
+    ///
+    /// # Panics
+    ///
+    /// This function will panic if the given index is greater than or equal to
+    /// the size of this storage.
     pub fn get(&self, index: usize) -> u64 {
-        // Validate.inclusiveBetween(0L, (long)(this.size - 1), (long)var1);
-        // int var2 = this.cellIndex(var1);
-        // long var3 = this.data[var2];
-        // int var5 = (var1 - var2 * this.valuesPerLong) * this.bits;
-        // return (int)(var3 >> var5 & this.mask);
-
         assert!(
             index < self.size,
             "Index {} out of bounds (must be less than {})",

diff --git a/azalea-world/src/iterators.rs b/azalea-world/src/iterators.rs
@@ -1,11 +1,15 @@
-//! Iterators, based on [prismarine-world's iterators](https://github.com/PrismarineJS/prismarine-world/blob/master/src/iterators.js).
+//! Iterators for iterating over Minecraft blocks and chunks, based on
+//! [prismarine-world's iterators](https://github.com/PrismarineJS/prismarine-world/blob/master/src/iterators.js).
 
 use azalea_core::{BlockPos, ChunkPos};
 
 /// An octahedron iterator, useful for iterating over blocks in a world.
 ///
 /// ```
-/// let mut iter = OctahedronIterator::new(BlockPos::default(), 4);
+/// # use azalea_core::BlockPos;
+/// # use azalea_world::iterators::BlockIterator;
+///
+/// let mut iter = BlockIterator::new(BlockPos::default(), 4);
 /// for block_pos in iter {
 ///    println!("{:?}", block_pos);
 /// }
@@ -76,6 +80,9 @@ impl Iterator for BlockIterator {
 /// A spiral iterator, useful for iterating over chunks in a world.
 ///
 /// ```
+/// # use azalea_core::ChunkPos;
+/// # use azalea_world::iterators::ChunkIterator;
+///
 /// let mut iter = ChunkIterator::new(ChunkPos::default(), 4);
 /// for chunk_pos in iter {
 ///   println!("{:?}", chunk_pos);
@@ -106,6 +113,25 @@ impl ChunkIterator {
             current_iter: 0,
         }
     }
+
+    /// Change the distance that this iterator won't go past.
+    ///
+    /// ```
+    /// # use azalea_core::ChunkPos;
+    /// # use azalea_world::iterators::ChunkIterator;
+    ///
+    /// let mut iter = ChunkIterator::new(ChunkPos::default(), 2);
+    /// for chunk_pos in iter {
+    ///   println!("{:?}", chunk_pos);
+    /// }
+    /// iter.set_max_distance(4);
+    /// for chunk_pos in iter {
+    ///   println!("{:?}", chunk_pos);
+    /// }
+    /// ```
+    pub fn set_max_distance(&mut self, max_distance: u32) {
+        self.number_of_points = u32::pow(max_distance * 2 - 1, 2);
+    }
 }
 impl Iterator for ChunkIterator {
     type Item = ChunkPos;

diff --git a/azalea-world/src/lib.rs b/azalea-world/src/lib.rs
@@ -7,7 +7,7 @@ mod bit_storage;
 mod chunk_storage;
 mod container;
 pub mod entity;
-mod iterators;
+pub mod iterators;
 pub mod palette;
 mod world;
 

diff --git a/azalea-world/src/palette.rs b/azalea-world/src/palette.rs
@@ -12,6 +12,11 @@ pub enum PalettedContainerType {
 #[derive(Clone, Debug)]
 pub struct PalettedContainer {
     pub bits_per_entry: u8,
+    /// This is usually a list of unique values that appear in the container so
+    /// they can be indexed by the bit storage.
+    ///
+    /// Sometimes it doesn't contain anything if there's too many unique items
+    /// in the bit storage, though.
     pub palette: Palette,
     /// Compacted list of indices pointing to entry IDs in the Palette.
     pub storage: BitStorage,
@@ -57,30 +62,48 @@ impl PalettedContainer {
     }
 
     /// Calculates the index of the given coordinates.
-    pub fn get_index(&self, x: usize, y: usize, z: usize) -> usize {
+    pub fn index_from_coords(&self, x: usize, y: usize, z: usize) -> usize {
         let size_bits = self.container_type.size_bits();
 
         (((y << size_bits) | z) << size_bits) | x
     }
 
+    pub fn coords_from_index(&self, index: usize) -> (usize, usize, usize) {
+        let size_bits = self.container_type.size_bits();
+        let mask = (1 << size_bits) - 1;
+        (
+            index & mask,
+            (index >> size_bits >> size_bits) & mask,
+            (index >> size_bits) & mask,
+        )
+    }
+
     /// Returns the value at the given index.
+    ///
+    /// # Panics
+    ///
+    /// This function panics if the index is greater than or equal to the number
+    /// of things in the storage. (So for block states, it must be less than
+    /// 4096).
     pub fn get_at_index(&self, index: usize) -> u32 {
+        // first get the pallete id
         let paletted_value = self.storage.get(index);
+        // and then get the value from that id
         self.palette.value_for(paletted_value as usize)
     }
 
     /// Returns the value at the given coordinates.
     pub fn get(&self, x: usize, y: usize, z: usize) -> u32 {
         // let paletted_value = self.storage.get(self.get_index(x, y, z));
         // self.palette.value_for(paletted_value as usize)
-        self.get_at_index(self.get_index(x, y, z))
+        self.get_at_index(self.index_from_coords(x, y, z))
     }
 
     /// Sets the id at the given coordinates and return the previous id
     pub fn get_and_set(&mut self, x: usize, y: usize, z: usize, value: u32) -> u32 {
         let paletted_value = self.id_for(value);
         self.storage
-            .get_and_set(self.get_index(x, y, z), paletted_value as u64) as u32
+            .get_and_set(self.index_from_coords(x, y, z), paletted_value as u64) as u32
     }
 
     /// Sets the id at the given index and return the previous id. You probably
@@ -92,7 +115,7 @@ impl PalettedContainer {
 
     /// Sets the id at the given coordinates and return the previous id
     pub fn set(&mut self, x: usize, y: usize, z: usize, value: u32) {
-        self.set_at_index(self.get_index(x, y, z), value);
+        self.set_at_index(self.index_from_coords(x, y, z), value);
     }
 
     fn create_or_reuse_data(&self, bits_per_entry: u8) -> PalettedContainer {
@@ -354,4 +377,22 @@ mod tests {
         palette_container.set_at_index(16, 16); // 5 bits
         assert_eq!(palette_container.bits_per_entry, 5);
     }
+
+    #[test]
+    fn test_coords_from_index() {
+        let palette_container =
+            PalettedContainer::new(&PalettedContainerType::BlockStates).unwrap();
+
+        for x in 0..15 {
+            for y in 0..15 {
+                for z in 0..15 {
+                    assert_eq!(
+                        palette_container
+                            .coords_from_index(palette_container.index_from_coords(x, y, z)),
+                        (x, y, z)
+                    );
+                }
+            }
+        }
+    }
 }
diff --git a/azalea-world/src/world.rs b/azalea-world/src/world.rs
@@ -2,7 +2,7 @@ use crate::{
     entity::{
         EntityInfos, EntityUuid, LoadedBy, Local, MinecraftEntityId, PartialEntityInfos, WorldName,
     },
-    iterators::{BlockIterator, ChunkIterator},
+    iterators::ChunkIterator,
     palette::Palette,
     ChunkStorage, PartialChunkStorage, WorldContainer,
 };
@@ -191,30 +191,78 @@ impl World {
         self.entity_by_id.get(entity_id).copied()
     }
 
-    pub fn find_block(&self, nearest_to: impl Into<BlockPos>, block_states: HashSet<BlockState>) {
+    /// Find the coordinates of a block in the world.
+    ///
+    /// Note that this is sorted by `x+y+z` and not `x^2+y^2+z^2`, for
+    /// optimization purposes.
+    pub fn find_block(
+        &self,
+        nearest_to: impl Into<BlockPos>,
+        block_states: impl Into<HashSet<BlockState>>,
+    ) -> Option<BlockPos> {
         // iterate over every chunk in a 3d spiral pattern
         // and then check the palette for the block state
-        // borrowed from https://github.com/PrismarineJS/prismarine-world/blob/master/src/iterators.js#L65
 
+        let block_states = block_states.into();
         let nearest_to: BlockPos = nearest_to.into();
         let start_chunk: ChunkPos = (&nearest_to).into();
+        // todo (correctness): rename this to something like SquareChunkIterator and
+        // also have another one that iterates in a diagonal shape and use that
+        // here
         let iter = ChunkIterator::new(start_chunk, 32);
 
         for chunk_pos in iter {
             let chunk = self.chunks.get(&chunk_pos).unwrap();
-            for section in &chunk.read().sections {
-                let maybe_has_block = match section.states.palette {
-                    Palette::SingleValue(id) => block_states.contains(&BlockState { id }),
+
+            let mut nearest_found_pos: Option<BlockPos> = None;
+
+            for (section_index, section) in chunk.read().sections.iter().enumerate() {
+                let maybe_has_block = match &section.states.palette {
+                    Palette::SingleValue(id) => block_states.contains(&BlockState { id: *id }),
                     Palette::Linear(ids) => ids
                         .iter()
-                        .any(|id| block_states.contains(&BlockState { id })),
+                        .any(|&id| block_states.contains(&BlockState { id })),
                     Palette::Hashmap(ids) => ids
                         .iter()
-                        .any(|id| block_states.contains(&BlockState { id })),
+                        .any(|&id| block_states.contains(&BlockState { id })),
                     Palette::Global => true,
                 };
+                if !maybe_has_block {
+                    continue;
+                }
+
+                for i in 0..4096 {
+                    let block_state = section.states.get_at_index(i);
+                    let block_state = BlockState { id: block_state };
+
+                    if block_states.contains(&block_state) {
+                        let (section_x, section_y, section_z) = section.states.coords_from_index(i);
+                        let (x, y, z) = (
+                            chunk_pos.x * 16 + (section_x as i32),
+                            self.chunks.min_y + (section_index * 16) as i32 + section_y as i32,
+                            chunk_pos.z * 16 + (section_z as i32),
+                        );
+                        let this_block_pos = BlockPos { x, y, z };
+                        // only update if it's closer
+                        if let Some(nearest_found_pos) = nearest_found_pos {
+                            if this_block_pos.x + this_block_pos.y + this_block_pos.z
+                                >= nearest_found_pos.x + nearest_found_pos.y + nearest_found_pos.z
+                            {
+                                continue;
+                            }
+                        }
+                        nearest_found_pos = Some(this_block_pos);
+                    }
+                }
+            }
+
+            // if we found the position, return it
+            if nearest_found_pos.is_some() {
+                return nearest_found_pos;
             }
         }
+
+        None
     }
 }
 

diff --git a/azalea/examples/craft_dig_straight_down.rs → .../examples/todo/craft_dig_straight_down.rs b/azalea/examples/craft_dig_straight_down.rs → .../examples/todo/craft_dig_straight_down.rs
diff --git a/azalea/examples/mine_a_chunk.rs → azalea/examples/todo/mine_a_chunk.rs b/azalea/examples/mine_a_chunk.rs → azalea/examples/todo/mine_a_chunk.rs
diff --git a/azalea/examples/pvp.rs → azalea/examples/todo/pvp.rs b/azalea/examples/pvp.rs → azalea/examples/todo/pvp.rs