Swarm (#36)

* make azalea-pathfinder dir

* start writing d* lite impl

* more work on d* lite

* work more on implementing d* lite

* full d* lite impl

* updated edges

* add next() function

* add NoPathError

* why does dstar lite not work

* fix d* lite implementation

* make the test actually check the coords

* replace while loop with if statement

* fix clippy complaints

* make W only have to be PartialOrd

* fix PartialOrd issues

* implement mtd* lite

* add a test to mtd* lite

* remove normal d* lite

* make heuristic only take in one arg

* add `success` function

* Update README.md

* evil black magic to make .entity not need dimension

* start adding moves

* slightly improve the vec3/position situation

new macro that implements all the useful functions

* moves stuff

* make it compile

* update deps in az-pathfinder

* make it compile again

* more pathfinding stuff

* add Bot::look_at

* replace EntityMut and EntityRef with just Entity

* block pos pathfinding stuff

* rename movedirection to walkdirection

* execute path every tick

* advance path

* change az-pf version

* make azalea_client keep plugin state

* fix Plugins::get

* why does it think there is air

* start debugging incorrect air

* update some From methods to use rem_euclid

* start adding swarm

* fix deadlock

i still don't understand why it was happening but the solution was to keep the Client::player lock for shorter so it didn't overlap with the Client::dimension lock

* make lookat actually work probably

* fix going too fast

* Update main.rs

* make a thing immutable

* direction_looking_at

* fix rotations

* import swarm in an example

* fix stuff from merge

* remove azalea_pathfinder import

* delete azalea-pathfinder crate

already in azalea::pathfinder module

* swarms

* start working on shared dimensions

* Shared worlds work

* start adding Swarm::add_account

* add_account works

* change "client" to "bot" in some places

* Fix issues from merge

* Update world.rs

* add SwarmEvent::Disconnect(Account)

* almost add SwarmEvent::Chat and new plugin system

it panics rn

* make plugins have to provide the State associated type

* improve comments

* make fn build slightly cleaner

* fix SwarmEvent::Chat

* change a println in bot/main.rs

* Client::shutdown -> disconnect

* polish

fix clippy warnings + improve some docs a bit

* fix shared worlds*

*there's a bug that entities and bots will have their positions exaggerated because the relative movement packet is applied for every entity once per bot

* i am being trolled by rust

for some reason some stuff is really slow for literally no reason and it makes no sense i am going insane

* make world an RwLock again

* remove debug messages

* fix skipping event ticks

unfortunately now sending events is `.send().await?` instead of just `.send()`

* fix deadlock + warnings

* turns out my floor_mod impl was wrong

and i32::rem_euclid has the correct behavior LOL

* still errors with lots of bots

* make swarm iter & fix new chunks not loading

* improve docs

* start fixing tests

* fix all the tests

except the examples i don't know how to exclude them from the tests

* improve docs some more

1 files changed, 128 insertions, 39 deletions

diff --git a/azalea-world/src/chunk_storage.rs b/azalea-world/src/chunk_storage.rs
index a03cbe7b..6a8a995e 100755
--- a/azalea-world/src/chunk_storage.rs
+++ b/azalea-world/src/chunk_storage.rs
@@ -4,36 +4,61 @@ use crate::World;
 use azalea_block::BlockState;
 use azalea_buf::BufReadError;
 use azalea_buf::{McBufReadable, McBufWritable};
-use azalea_core::floor_mod;
 use azalea_core::{BlockPos, ChunkBlockPos, ChunkPos, ChunkSectionBlockPos};
 use log::debug;
 use log::trace;
+use log::warn;
 use parking_lot::Mutex;
+use parking_lot::RwLock;
+use std::collections::HashMap;
 use std::fmt::Debug;
 use std::io::Cursor;
-use std::{
-    io::Write,
-    ops::{Index, IndexMut},
-    sync::Arc,
-};
+use std::sync::Weak;
+use std::{io::Write, sync::Arc};
 
 const SECTION_HEIGHT: u32 = 16;
 
-pub struct ChunkStorage {
+/// An efficient storage of chunks for a client that has a limited render
+/// distance. This has support for using a shared [`WeakChunkStorage`]. If you
+/// have an infinite render distance (like a server), you should use
+/// [`ChunkStorage`] instead.
+pub struct PartialChunkStorage {
+    /// Chunk storage that can be shared by clients.
+    shared: Arc<RwLock<WeakChunkStorage>>,
+
     pub view_center: ChunkPos,
     chunk_radius: u32,
     view_range: u32,
-    pub height: u32,
-    pub min_y: i32,
     // chunks is a list of size chunk_radius * chunk_radius
     chunks: Vec<Option<Arc<Mutex<Chunk>>>>,
 }
 
+/// A storage for chunks where they're only stored weakly, so if they're not
+/// actively being used somewhere else they'll be forgotten. This is used for
+/// shared worlds.
+pub struct WeakChunkStorage {
+    pub height: u32,
+    pub min_y: i32,
+    pub chunks: HashMap<ChunkPos, Weak<Mutex<Chunk>>>,
+}
+
+/// A storage of potentially infinite chunks in a world. Chunks are stored as
+/// an `Arc<Mutex>` so they can be shared across threads.
+pub struct ChunkStorage {
+    pub height: u32,
+    pub min_y: i32,
+    pub chunks: HashMap<ChunkPos, Arc<Mutex<Chunk>>>,
+}
+
+/// A single chunk in a world (16*?*16 blocks). This only contains the blocks and biomes. You
+/// can derive the height of the chunk from the number of sections, but you
+/// need a [`ChunkStorage`] to get the minimum Y coordinate.
 #[derive(Debug)]
 pub struct Chunk {
     pub sections: Vec<Section>,
 }
 
+/// A section of a chunk, i.e. a 16*16*16 block area.
 #[derive(Clone, Debug)]
 pub struct Section {
     pub block_count: u16,
@@ -59,22 +84,28 @@ impl Default for Chunk {
     }
 }
 
-impl ChunkStorage {
-    pub fn new(chunk_radius: u32, height: u32, min_y: i32) -> Self {
+impl PartialChunkStorage {
+    pub fn new(chunk_radius: u32, shared: Arc<RwLock<WeakChunkStorage>>) -> Self {
         let view_range = chunk_radius * 2 + 1;
-        ChunkStorage {
+        PartialChunkStorage {
+            shared,
             view_center: ChunkPos::new(0, 0),
             chunk_radius,
             view_range,
-            height,
-            min_y,
             chunks: vec![None; (view_range * view_range) as usize],
         }
     }
 
+    pub fn min_y(&self) -> i32 {
+        self.shared.read().min_y
+    }
+    pub fn height(&self) -> u32 {
+        self.shared.read().height
+    }
+
     fn get_index(&self, chunk_pos: &ChunkPos) -> usize {
-        (floor_mod(chunk_pos.x, self.view_range) * self.view_range
-            + floor_mod(chunk_pos.z, self.view_range)) as usize
+        (i32::rem_euclid(chunk_pos.x, self.view_range as i32) * (self.view_range as i32)
+            + i32::rem_euclid(chunk_pos.z, self.view_range as i32)) as usize
     }
 
     pub fn in_range(&self, chunk_pos: &ChunkPos) -> bool {
@@ -84,19 +115,19 @@ impl ChunkStorage {
 
     pub fn get_block_state(&self, pos: &BlockPos) -> Option<BlockState> {
         let chunk_pos = ChunkPos::from(pos);
-        let chunk = self[&chunk_pos].as_ref()?;
+        let chunk = self.get(&chunk_pos)?;
         let chunk = chunk.lock();
-        chunk.get(&ChunkBlockPos::from(pos), self.min_y)
+        chunk.get(&ChunkBlockPos::from(pos), self.min_y())
     }
 
     pub fn set_block_state(&self, pos: &BlockPos, state: BlockState) -> Option<BlockState> {
-        if pos.y < self.min_y || pos.y >= (self.min_y + self.height as i32) {
+        if pos.y < self.min_y() || pos.y >= (self.min_y() + self.height() as i32) {
             return None;
         }
         let chunk_pos = ChunkPos::from(pos);
-        let chunk = self[&chunk_pos].as_ref()?;
+        let chunk = self.get(&chunk_pos)?;
         let mut chunk = chunk.lock();
-        Some(chunk.get_and_set(&ChunkBlockPos::from(pos), state, self.min_y))
+        Some(chunk.get_and_set(&ChunkBlockPos::from(pos), state, self.min_y()))
     }
 
     pub fn replace_with_packet_data(
@@ -116,27 +147,77 @@ impl ChunkStorage {
 
         let chunk = Arc::new(Mutex::new(Chunk::read_with_dimension_height(
             data,
-            self.height,
+            self.height(),
         )?));
 
         trace!("Loaded chunk {:?}", pos);
-        self[pos] = Some(chunk);
+        self.set(pos, Some(chunk));
 
         Ok(())
     }
-}
 
-impl Index<&ChunkPos> for ChunkStorage {
-    type Output = Option<Arc<Mutex<Chunk>>>;
+    /// Get a [`Chunk`] within render distance, or `None` if it's not loaded.
+    /// Use [`PartialChunkStorage::get`] to get a chunk from the shared storage.
+    pub fn limited_get(&self, pos: &ChunkPos) -> Option<&Arc<Mutex<Chunk>>> {
+        if !self.in_range(pos) {
+            warn!(
+                "Chunk at {:?} is not in the render distance (center: {:?}, {} chunks)",
+                pos, self.view_center, self.chunk_radius,
+            );
+            return None;
+        }
 
-    fn index(&self, pos: &ChunkPos) -> &Self::Output {
-        &self.chunks[self.get_index(pos)]
+        let index = self.get_index(pos);
+        self.chunks[index].as_ref()
     }
-}
-impl IndexMut<&ChunkPos> for ChunkStorage {
-    fn index_mut<'a>(&'a mut self, pos: &ChunkPos) -> &'a mut Self::Output {
+    /// Get a mutable reference to a [`Chunk`] within render distance, or
+    /// `None` if it's not loaded. Use [`PartialChunkStorage::get`] to get
+    /// a chunk from the shared storage.
+    pub fn limited_get_mut(&mut self, pos: &ChunkPos) -> Option<&mut Option<Arc<Mutex<Chunk>>>> {
+        if !self.in_range(pos) {
+            return None;
+        }
+
         let index = self.get_index(pos);
-        &mut self.chunks[index]
+        Some(&mut self.chunks[index])
+    }
+
+    /// Get a chunk,
+    pub fn get(&self, pos: &ChunkPos) -> Option<Arc<Mutex<Chunk>>> {
+        self.shared
+            .read()
+            .chunks
+            .get(pos)
+            .and_then(|chunk| chunk.upgrade())
+    }
+
+    /// Set a chunk in the shared storage and reference it from the limited
+    /// storage.
+    ///
+    /// # Panics
+    /// If the chunk is not in the render distance.
+    pub fn set(&mut self, pos: &ChunkPos, chunk: Option<Arc<Mutex<Chunk>>>) {
+        if let Some(chunk) = &chunk {
+            self.shared
+                .write()
+                .chunks
+                .insert(*pos, Arc::downgrade(chunk));
+        } else {
+            // don't remove it from the shared storage, since it'll be removed
+            // automatically if this was the last reference
+        }
+        if let Some(chunk_mut) = self.limited_get_mut(pos) {
+            *chunk_mut = chunk;
+        }
+    }
+}
+impl WeakChunkStorage {
+    pub fn new(height: u32, min_y: i32) -> Self {
+        WeakChunkStorage {
+            height,
+            min_y,
+            chunks: HashMap::new(),
+        }
     }
 }
 
@@ -214,14 +295,14 @@ impl McBufWritable for Chunk {
     }
 }
 
-impl Debug for ChunkStorage {
+impl Debug for PartialChunkStorage {
     fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
         f.debug_struct("ChunkStorage")
             .field("view_center", &self.view_center)
             .field("chunk_radius", &self.chunk_radius)
             .field("view_range", &self.view_range)
-            .field("height", &self.height)
-            .field("min_y", &self.min_y)
+            .field("height", &self.height())
+            .field("min_y", &self.min_y())
             // .field("chunks", &self.chunks)
             .field("chunks", &format_args!("{} items", self.chunks.len()))
             .finish()
@@ -292,9 +373,14 @@ impl Section {
     }
 }
 
-impl Default for ChunkStorage {
+impl Default for PartialChunkStorage {
+    fn default() -> Self {
+        Self::new(8, Arc::new(RwLock::new(WeakChunkStorage::default())))
+    }
+}
+impl Default for WeakChunkStorage {
     fn default() -> Self {
-        Self::new(8, 384, -64)
+        Self::new(384, -64)
     }
 }
 
@@ -317,8 +403,11 @@ mod tests {
 
     #[test]
     fn test_out_of_bounds_y() {
-        let mut chunk_storage = ChunkStorage::default();
-        chunk_storage[&ChunkPos { x: 0, z: 0 }] = Some(Arc::new(Mutex::new(Chunk::default())));
+        let mut chunk_storage = PartialChunkStorage::default();
+        chunk_storage.set(
+            &ChunkPos { x: 0, z: 0 },
+            Some(Arc::new(Mutex::new(Chunk::default()))),
+        );
         assert!(chunk_storage
             .get_block_state(&BlockPos { x: 0, y: 319, z: 0 })
             .is_some());