add FastFixedBitSet and use it in the pathfinder

2 files changed, 55 insertions, 9 deletions

diff --git a/azalea-core/src/bitset.rs b/azalea-core/src/bitset.rs
index 1cac4a9c..2a3e5b51 100644
--- a/azalea-core/src/bitset.rs
+++ b/azalea-core/src/bitset.rs
@@ -131,8 +131,8 @@ impl From<Vec<u8>> for BitSet {
 ///
 /// Note that this is optimized for fast serialization and deserialization for
 /// Minecraft, and may not be as performant as it could be for other purposes.
-/// Notably, the internal representation is an array of `u8`s even though
-/// `usize` would be slightly faster.
+/// Consider using [`FastFixedBitSet`] if you don't need the
+/// `AzaleaRead`/`AzaleaWrite` implementation.
 #[derive(Debug, Clone, PartialEq, Eq, Hash)]
 pub struct FixedBitSet<const N: usize>
 where
@@ -198,6 +198,52 @@ pub const fn bits_to_bytes(n: usize) -> usize {
     n.div_ceil(8)
 }
 
+/// A slightly faster compact fixed-size array of bits.
+///
+/// The `N` is the number of bits reserved for the bitset. You're encouraged to
+/// use it like `FastFixedBitSet<20>` if you need 20 bits.
+///
+/// This is almost identical to [`FixedBitSet`], but more efficient (~20% faster
+/// access) and doesn't implement `AzaleaRead`/`AzaleaWrite`.
+#[derive(Debug, Clone, PartialEq, Eq, Hash)]
+pub struct FastFixedBitSet<const N: usize>
+where
+    [u64; bits_to_longs(N)]: Sized,
+{
+    data: [u64; bits_to_longs(N)],
+}
+impl<const N: usize> FastFixedBitSet<N>
+where
+    [u64; bits_to_longs(N)]: Sized,
+{
+    pub const fn new() -> Self {
+        FastFixedBitSet {
+            data: [0; bits_to_longs(N)],
+        }
+    }
+
+    #[inline]
+    pub fn index(&self, index: usize) -> bool {
+        (self.data[index / 64] & (1u64 << (index % 64))) != 0
+    }
+
+    #[inline]
+    pub fn set(&mut self, bit_index: usize) {
+        self.data[bit_index / 64] |= 1u64 << (bit_index % 64);
+    }
+}
+impl<const N: usize> Default for FastFixedBitSet<N>
+where
+    [u64; bits_to_longs(N)]: Sized,
+{
+    fn default() -> Self {
+        Self::new()
+    }
+}
+pub const fn bits_to_longs(n: usize) -> usize {
+    n.div_ceil(64)
+}
+
 #[cfg(test)]
 mod tests {
     use super::*;
diff --git a/azalea/src/pathfinder/world.rs b/azalea/src/pathfinder/world.rs
index e9337503..d130855d 100644
--- a/azalea/src/pathfinder/world.rs
+++ b/azalea/src/pathfinder/world.rs
@@ -5,7 +5,7 @@ use std::{
 
 use azalea_block::{BlockState, properties};
 use azalea_core::{
-    bitset::FixedBitSet,
+    bitset::FastFixedBitSet,
     position::{BlockPos, ChunkPos, ChunkSectionBlockPos, ChunkSectionPos},
 };
 use azalea_physics::collision::BlockWithShape;
@@ -87,11 +87,11 @@ impl CachedSections {
 pub struct CachedSection {
     pub pos: ChunkSectionPos,
     /// Blocks that we can fully pass through (like air).
-    pub passable_bitset: FixedBitSet<4096>,
+    pub passable_bitset: FastFixedBitSet<4096>,
     /// Blocks that we can stand on and do parkour from.
-    pub solid_bitset: FixedBitSet<4096>,
+    pub solid_bitset: FastFixedBitSet<4096>,
     /// Blocks that we can stand on but might not be able to parkour from.
-    pub standable_bitset: FixedBitSet<4096>,
+    pub standable_bitset: FastFixedBitSet<4096>,
 }
 
 impl CachedWorld {
@@ -200,9 +200,9 @@ impl CachedWorld {
 
     fn calculate_bitsets_for_section(&self, section_pos: ChunkSectionPos) -> Option<CachedSection> {
         self.with_section(section_pos, |section| {
-            let mut passable_bitset = FixedBitSet::<4096>::new();
-            let mut solid_bitset = FixedBitSet::<4096>::new();
-            let mut standable_bitset = FixedBitSet::<4096>::new();
+            let mut passable_bitset = FastFixedBitSet::<4096>::new();
+            let mut solid_bitset = FastFixedBitSet::<4096>::new();
+            let mut standable_bitset = FastFixedBitSet::<4096>::new();
             for i in 0..4096 {
                 let block_state = section.get_at_index(i);
                 if is_block_state_passable(block_state) {