Pathfinder (#25)

Pathfinding is very much not done, but it works enough and I want to get this merged.
TODO: fast replanning, goals that aren't a single node, falling moves (it should be able to play the dropper), parkour moves

6 files changed, 924 insertions, 49 deletions

diff --git a/azalea/src/bot.rs b/azalea/src/bot.rs
index 566ab1e7..961f093d 100644..100755
--- a/azalea/src/bot.rs
+++ b/azalea/src/bot.rs
@@ -1,7 +1,8 @@
 use crate::{Client, Event};
 use async_trait::async_trait;
+use azalea_core::Vec3;
 use parking_lot::Mutex;
-use std::sync::Arc;
+use std::{f64::consts::PI, sync::Arc};
 
 #[derive(Default, Clone)]
 pub struct Plugin {
@@ -14,20 +15,22 @@ pub struct State {
 }
 
 pub trait BotTrait {
-    fn jump(&self);
+    fn jump(&mut self);
+    fn look_at(&mut self, pos: &Vec3);
 }
 
 impl BotTrait for azalea_client::Client {
     /// Queue a jump for the next tick.
-    fn jump(&self) {
-        let player_lock = self.player.lock();
-        let mut dimension_lock = self.dimension.lock();
-
-        let mut player_entity = player_lock
-            .entity_mut(&mut dimension_lock)
-            .expect("Player must exist");
+    fn jump(&mut self) {
+        self.set_jumping(true);
+        let state = self.plugins.get::<Plugin>().unwrap().state.clone();
+        *state.jumping_once.lock() = true;
+    }
 
-        player_entity.jumping = true;
+    /// Turn the bot's head to look at the coordinate in the world.
+    fn look_at(&mut self, pos: &Vec3) {
+        let (y_rot, x_rot) = direction_looking_at(self.entity().pos(), pos);
+        self.set_rotation(y_rot, x_rot);
     }
 }
 
@@ -38,10 +41,18 @@ impl crate::Plugin for Plugin {
             if *self.state.jumping_once.lock() {
                 if bot.jumping() {
                     *self.state.jumping_once.lock() = false;
-                } else {
-                    bot.set_jumping(true);
+                    bot.set_jumping(false);
                 }
             }
         }
     }
 }
+
+fn direction_looking_at(current: &Vec3, target: &Vec3) -> (f32, f32) {
+    // borrowed from mineflayer's Bot.lookAt because i didn't want to do math
+    let delta = target - current;
+    let y_rot = (PI - f64::atan2(-delta.x, -delta.z)) * (180.0 / PI);
+    let ground_distance = f64::sqrt(delta.x * delta.x + delta.z * delta.z);
+    let x_rot = f64::atan2(delta.y, ground_distance) * -(180.0 / PI);
+    (y_rot as f32, x_rot as f32)
+}
diff --git a/azalea/src/lib.rs b/azalea/src/lib.rs
index 83ad8d36..89754409 100644..100755
--- a/azalea/src/lib.rs
+++ b/azalea/src/lib.rs
@@ -51,7 +51,7 @@
 //!         account,
 //!         address: "localhost",
 //!         state: State::default(),
-//!         plugins: vec![],
+//!         plugins: plugins![],
 //!         handle,
 //!     })
 //!     .await
@@ -76,39 +76,15 @@
 //! [`azalea_client`]: https://crates.io/crates/azalea-client
 
 mod bot;
+pub mod pathfinder;
 pub mod prelude;
 
-use async_trait::async_trait;
 pub use azalea_client::*;
+pub use azalea_core::{BlockPos, Vec3};
 use azalea_protocol::ServerAddress;
-use std::future::Future;
+use std::{future::Future, sync::Arc};
 use thiserror::Error;
 
-/// Plugins can keep their own personal state, listen to events, and add new functions to Client.
-#[async_trait]
-pub trait Plugin: Send + Sync + PluginClone + 'static {
-    async fn handle(self: Box<Self>, event: Event, bot: Client);
-}
-
-/// An internal trait that allows Plugin to be cloned.
-#[doc(hidden)]
-pub trait PluginClone {
-    fn clone_box(&self) -> Box<dyn Plugin>;
-}
-impl<T> PluginClone for T
-where
-    T: 'static + Plugin + Clone,
-{
-    fn clone_box(&self) -> Box<dyn Plugin> {
-        Box::new(self.clone())
-    }
-}
-impl Clone for Box<dyn Plugin> {
-    fn clone(&self) -> Self {
-        self.clone_box()
-    }
-}
-
 pub type HandleFn<Fut, S> = fn(Client, Event, S) -> Fut;
 
 /// The options that are passed to [`azalea::start`].
@@ -127,9 +103,14 @@ where
     pub address: A,
     /// The account that's going to join the server.
     pub account: Account,
-    /// A list of plugins that are going to be used. Plugins are external
-    /// crates that add extra functionality to Azalea.
-    pub plugins: Vec<Box<dyn Plugin>>,
+    /// The plugins that are going to be used. Plugins are external crates that
+    /// add extra functionality to Azalea. You should use the [`plugins`] macro
+    /// for this field.
+    ///
+    /// ```rust,no_run
+    /// plugins![azalea_pathfinder::Plugin::default()]
+    /// ```
+    pub plugins: Plugins,
     /// A struct that contains the data that you want your bot to remember
     /// across events.
     ///
@@ -177,7 +158,7 @@ pub enum Error {
 ///     account,
 ///     address: "localhost",
 ///     state: State::default(),
-///     plugins: vec![Box::new(autoeat::Plugin::default())],
+///     plugins: plugins![azalea_pathfinder::Plugin::default()],
 ///     handle,
 /// }).await;
 /// ```
@@ -193,24 +174,53 @@ pub async fn start<
         Err(_) => return Err(Error::InvalidAddress),
     };
 
-    let (bot, mut rx) = Client::join(&options.account, address).await?;
+    let (mut bot, mut rx) = Client::join(&options.account, address).await?;
+
+    let mut plugins = options.plugins;
+    plugins.add(bot::Plugin::default());
+    plugins.add(pathfinder::Plugin::default());
+    bot.plugins = Arc::new(plugins);
 
     let state = options.state;
-    let bot_plugin = bot::Plugin::default();
 
     while let Some(event) = rx.recv().await {
-        for plugin in &options.plugins {
-            let plugin = plugin.clone();
+        let cloned_plugins = (*bot.plugins).clone();
+        for plugin in cloned_plugins.into_iter() {
             tokio::spawn(plugin.handle(event.clone(), bot.clone()));
         }
 
         tokio::spawn(bot::Plugin::handle(
-            Box::new(bot_plugin.clone()),
+            Box::new(bot.plugins.get::<bot::Plugin>().unwrap().clone()),
+            event.clone(),
+            bot.clone(),
+        ));
+        tokio::spawn(pathfinder::Plugin::handle(
+            Box::new(bot.plugins.get::<pathfinder::Plugin>().unwrap().clone()),
             event.clone(),
             bot.clone(),
         ));
+
         tokio::spawn((options.handle)(bot.clone(), event.clone(), state.clone()));
     }
 
     Ok(())
 }
+
+/// A helper macro that generates a [`Plugins`] struct from a list of objects
+/// that implement [`Plugin`].
+///
+/// ```rust,no_run
+/// plugins![azalea_pathfinder::Plugin::default()];
+/// ```
+#[macro_export]
+macro_rules! plugins {
+    ($($plugin:expr),*) => {
+        {
+            let mut plugins = azalea::Plugins::new();
+            $(
+                plugins.add($plugin);
+            )*
+            plugins
+        }
+    };
+}
diff --git a/azalea/src/pathfinder/mod.rs b/azalea/src/pathfinder/mod.rs
new file mode 100644
index 00000000..d62b3e05
--- /dev/null
+++ b/azalea/src/pathfinder/mod.rs
@@ -0,0 +1,208 @@
+mod moves;
+mod mtdstarlite;
+
+use crate::{prelude::*, SprintDirection, WalkDirection};
+use crate::{Client, Event};
+use async_trait::async_trait;
+use azalea_core::{BlockPos, CardinalDirection};
+use azalea_world::entity::EntityData;
+use mtdstarlite::Edge;
+pub use mtdstarlite::MTDStarLite;
+use parking_lot::Mutex;
+use std::collections::VecDeque;
+use std::sync::Arc;
+
+#[derive(Default, Clone)]
+pub struct Plugin {
+    pub state: State,
+}
+
+#[derive(Default, Clone)]
+pub struct State {
+    // pathfinder: Option<MTDStarLite<Node, f32>>,
+    pub path: Arc<Mutex<VecDeque<Node>>>,
+}
+
+#[async_trait]
+impl crate::Plugin for Plugin {
+    async fn handle(self: Box<Self>, event: Event, mut bot: Client) {
+        if let Event::Tick = event {
+            let mut path = self.state.path.lock();
+
+            if !path.is_empty() {
+                tick_execute_path(&mut bot, &mut path);
+            }
+        }
+    }
+}
+
+pub trait Trait {
+    fn goto(&self, goal: impl Goal);
+}
+
+impl Trait for azalea_client::Client {
+    fn goto(&self, goal: impl Goal) {
+        let start = Node {
+            pos: BlockPos::from(self.entity().pos()),
+            vertical_vel: VerticalVel::None,
+        };
+        let end = goal.goal_node();
+        println!("start: {:?}, end: {:?}", start, end);
+
+        let possible_moves: Vec<&dyn moves::Move> = vec![
+            &moves::ForwardMove(CardinalDirection::North),
+            &moves::ForwardMove(CardinalDirection::East),
+            &moves::ForwardMove(CardinalDirection::South),
+            &moves::ForwardMove(CardinalDirection::West),
+            //
+            &moves::AscendMove(CardinalDirection::North),
+            &moves::AscendMove(CardinalDirection::East),
+            &moves::AscendMove(CardinalDirection::South),
+            &moves::AscendMove(CardinalDirection::West),
+            //
+            &moves::DescendMove(CardinalDirection::North),
+            &moves::DescendMove(CardinalDirection::East),
+            &moves::DescendMove(CardinalDirection::South),
+            &moves::DescendMove(CardinalDirection::West),
+            //
+            &moves::DiagonalMove(CardinalDirection::North),
+            &moves::DiagonalMove(CardinalDirection::East),
+            &moves::DiagonalMove(CardinalDirection::South),
+            &moves::DiagonalMove(CardinalDirection::West),
+        ];
+
+        let successors = |node: &Node| {
+            let mut edges = Vec::new();
+
+            let dimension = self.dimension.read();
+            for possible_move in possible_moves.iter() {
+                edges.push(Edge {
+                    target: possible_move.next_node(&node),
+                    cost: possible_move.cost(&dimension, node),
+                });
+            }
+            edges
+        };
+
+        let mut pf = MTDStarLite::new(
+            start,
+            end,
+            |n| goal.heuristic(n),
+            successors,
+            successors,
+            |n| goal.success(n),
+        );
+
+        let start = std::time::Instant::now();
+        let p = pf.find_path();
+        let end = std::time::Instant::now();
+        println!("path: {:?}", p);
+        println!("time: {:?}", end - start);
+
+        let state = self
+            .plugins
+            .get::<Plugin>()
+            .expect("Pathfinder plugin not installed!")
+            .state
+            .clone();
+        // convert the Option<Vec<Node>> to a VecDeque<Node>
+        *state.path.lock() = p.expect("no path").into_iter().collect();
+    }
+}
+
+fn tick_execute_path(bot: &mut Client, path: &mut VecDeque<Node>) {
+    let target = if let Some(target) = path.front() {
+        target
+    } else {
+        return;
+    };
+    let center = target.pos.center();
+    // println!("going to {center:?} (at {pos:?})", pos = bot.entity().pos());
+    bot.look_at(&center);
+    bot.sprint(SprintDirection::Forward);
+    // check if we should jump
+    if target.pos.y > bot.entity().pos().y.floor() as i32 {
+        bot.jump();
+    }
+
+    if target.is_reached(&bot.entity()) {
+        println!("ok target {target:?} reached");
+        path.pop_front();
+        if path.is_empty() {
+            bot.walk(WalkDirection::None);
+        }
+        // tick again, maybe we already reached the next node!
+        tick_execute_path(bot, path);
+    }
+}
+
+/// Information about our vertical velocity
+#[derive(Eq, PartialEq, Hash, Clone, Copy, Debug)]
+pub enum VerticalVel {
+    None,
+    /// No vertical velocity, but we're not on the ground
+    NoneMidair,
+    // less than 3 blocks (no fall damage)
+    FallingLittle,
+}
+
+#[derive(Eq, PartialEq, Hash, Clone, Copy, Debug)]
+pub struct Node {
+    pub pos: BlockPos,
+    pub vertical_vel: VerticalVel,
+}
+
+pub trait Goal {
+    fn heuristic(&self, n: &Node) -> f32;
+    fn success(&self, n: &Node) -> bool;
+    // TODO: this should be removed and mtdstarlite should stop depending on
+    // being given a goal node
+    fn goal_node(&self) -> Node;
+}
+
+impl Node {
+    /// Returns whether the entity is at the node and should start going to the
+    /// next node.
+    pub fn is_reached(&self, entity: &EntityData) -> bool {
+        println!(
+            "entity.delta.y: {} {:?}=={:?}, self.vertical_vel={:?}",
+            entity.delta.y,
+            BlockPos::from(entity.pos()),
+            self.pos,
+            self.vertical_vel
+        );
+        BlockPos::from(entity.pos()) == self.pos
+            && match self.vertical_vel {
+                VerticalVel::NoneMidair => entity.delta.y > -0.1 && entity.delta.y < 0.1,
+                VerticalVel::None => entity.on_ground,
+                VerticalVel::FallingLittle => entity.delta.y < -0.1,
+            }
+    }
+}
+
+pub struct BlockPosGoal {
+    pub pos: BlockPos,
+}
+impl Goal for BlockPosGoal {
+    fn heuristic(&self, n: &Node) -> f32 {
+        let dx = (self.pos.x - n.pos.x) as f32;
+        let dy = (self.pos.y - n.pos.y) as f32;
+        let dz = (self.pos.z - n.pos.z) as f32;
+        dx * dx + dy * dy + dz * dz
+    }
+    fn success(&self, n: &Node) -> bool {
+        n.pos == self.pos
+    }
+    fn goal_node(&self) -> Node {
+        Node {
+            pos: self.pos,
+            vertical_vel: VerticalVel::None,
+        }
+    }
+}
+
+impl From<BlockPos> for BlockPosGoal {
+    fn from(pos: BlockPos) -> Self {
+        Self { pos }
+    }
+}
diff --git a/azalea/src/pathfinder/moves.rs b/azalea/src/pathfinder/moves.rs
new file mode 100644
index 00000000..ed98b70d
--- /dev/null
+++ b/azalea/src/pathfinder/moves.rs
@@ -0,0 +1,191 @@
+use super::{Node, VerticalVel};
+use azalea_core::{BlockPos, CardinalDirection};
+use azalea_physics::collision::{self, BlockWithShape};
+use azalea_world::Dimension;
+
+/// whether this block is passable
+fn is_block_passable(pos: &BlockPos, dim: &Dimension) -> bool {
+    if let Some(block) = dim.get_block_state(pos) {
+        block.shape() == &collision::empty_shape()
+    } else {
+        false
+    }
+}
+
+/// whether this block has a solid hitbox (i.e. we can stand on it)
+fn is_block_solid(pos: &BlockPos, dim: &Dimension) -> bool {
+    if let Some(block) = dim.get_block_state(pos) {
+        block.shape() == &collision::block_shape()
+    } else {
+        false
+    }
+}
+
+/// Whether this block and the block above are passable
+fn is_passable(pos: &BlockPos, dim: &Dimension) -> bool {
+    is_block_passable(pos, dim) && is_block_passable(&pos.up(1), dim)
+}
+
+/// Whether we can stand in this position. Checks if the block below is solid,
+/// and that the two blocks above that are passable.
+fn is_standable(pos: &BlockPos, dim: &Dimension) -> bool {
+    is_block_solid(&pos.down(1), dim) && is_passable(&pos, dim)
+}
+
+const JUMP_COST: f32 = 0.5;
+const WALK_ONE_BLOCK_COST: f32 = 1.0;
+
+pub trait Move {
+    fn cost(&self, dim: &Dimension, node: &Node) -> f32;
+    /// Returns by how much the entity's position should be changed when this move is executed.
+    fn offset(&self) -> BlockPos;
+    fn next_node(&self, node: &Node) -> Node {
+        Node {
+            pos: node.pos + self.offset(),
+            vertical_vel: VerticalVel::None,
+        }
+    }
+}
+
+pub struct ForwardMove(pub CardinalDirection);
+impl Move for ForwardMove {
+    fn cost(&self, dim: &Dimension, node: &Node) -> f32 {
+        if is_standable(&(node.pos + self.offset()), dim) && node.vertical_vel == VerticalVel::None
+        {
+            WALK_ONE_BLOCK_COST
+        } else {
+            f32::INFINITY
+        }
+    }
+    fn offset(&self) -> BlockPos {
+        BlockPos::new(self.0.x(), 0, self.0.z())
+    }
+}
+
+pub struct AscendMove(pub CardinalDirection);
+impl Move for AscendMove {
+    fn cost(&self, dim: &Dimension, node: &Node) -> f32 {
+        if node.vertical_vel == VerticalVel::None
+            && is_block_passable(&node.pos.up(2), dim)
+            && is_standable(&(node.pos + self.offset()), dim)
+        {
+            WALK_ONE_BLOCK_COST + JUMP_COST
+        } else {
+            f32::INFINITY
+        }
+    }
+    fn offset(&self) -> BlockPos {
+        BlockPos::new(self.0.x(), 1, self.0.z())
+    }
+    fn next_node(&self, node: &Node) -> Node {
+        Node {
+            pos: node.pos + self.offset(),
+            vertical_vel: VerticalVel::None,
+        }
+    }
+}
+pub struct DescendMove(pub CardinalDirection);
+impl Move for DescendMove {
+    fn cost(&self, dim: &Dimension, node: &Node) -> f32 {
+        // check whether 3 blocks vertically forward are passable
+        if node.vertical_vel == VerticalVel::None
+            && is_standable(&(node.pos + self.offset()), dim)
+            && is_block_passable(&(node.pos + self.offset().up(2)), dim)
+        {
+            WALK_ONE_BLOCK_COST
+        } else {
+            f32::INFINITY
+        }
+    }
+    fn offset(&self) -> BlockPos {
+        BlockPos::new(self.0.x(), -1, self.0.z())
+    }
+    fn next_node(&self, node: &Node) -> Node {
+        Node {
+            pos: node.pos + self.offset(),
+            vertical_vel: VerticalVel::None,
+        }
+    }
+}
+pub struct DiagonalMove(pub CardinalDirection);
+impl Move for DiagonalMove {
+    fn cost(&self, dim: &Dimension, node: &Node) -> f32 {
+        if node.vertical_vel != VerticalVel::None {
+            return f32::INFINITY;
+        }
+        if !is_passable(
+            &BlockPos::new(node.pos.x + self.0.x(), node.pos.y, node.pos.z + self.0.z()),
+            dim,
+        ) && !is_passable(
+            &BlockPos::new(
+                node.pos.x + self.0.right().x(),
+                node.pos.y,
+                node.pos.z + self.0.right().z(),
+            ),
+            dim,
+        ) {
+            return f32::INFINITY;
+        }
+        if !is_standable(&(node.pos + self.offset()), dim) {
+            return f32::INFINITY;
+        }
+        WALK_ONE_BLOCK_COST * 1.4
+    }
+    fn offset(&self) -> BlockPos {
+        let right = self.0.right();
+        BlockPos::new(self.0.x() + right.x(), 0, self.0.z() + right.z())
+    }
+    fn next_node(&self, node: &Node) -> Node {
+        Node {
+            pos: node.pos + self.offset(),
+            vertical_vel: VerticalVel::None,
+        }
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+    use azalea_block::BlockState;
+    use azalea_core::ChunkPos;
+    use azalea_world::Chunk;
+
+    #[test]
+    fn test_is_passable() {
+        let mut dim = Dimension::default();
+        dim.set_chunk(&ChunkPos { x: 0, z: 0 }, Some(Chunk::default()))
+            .unwrap();
+        dim.set_block_state(&BlockPos::new(0, 0, 0), BlockState::Stone);
+        dim.set_block_state(&BlockPos::new(0, 1, 0), BlockState::Air);
+
+        assert_eq!(is_block_passable(&BlockPos::new(0, 0, 0), &dim), false);
+        assert_eq!(is_block_passable(&BlockPos::new(0, 1, 0), &dim), true);
+    }
+
+    #[test]
+    fn test_is_solid() {
+        let mut dim = Dimension::default();
+        dim.set_chunk(&ChunkPos { x: 0, z: 0 }, Some(Chunk::default()))
+            .unwrap();
+        dim.set_block_state(&BlockPos::new(0, 0, 0), BlockState::Stone);
+        dim.set_block_state(&BlockPos::new(0, 1, 0), BlockState::Air);
+
+        assert_eq!(is_block_solid(&BlockPos::new(0, 0, 0), &dim), true);
+        assert_eq!(is_block_solid(&BlockPos::new(0, 1, 0), &dim), false);
+    }
+
+    #[test]
+    fn test_is_standable() {
+        let mut dim = Dimension::default();
+        dim.set_chunk(&ChunkPos { x: 0, z: 0 }, Some(Chunk::default()))
+            .unwrap();
+        dim.set_block_state(&BlockPos::new(0, 0, 0), BlockState::Stone);
+        dim.set_block_state(&BlockPos::new(0, 1, 0), BlockState::Air);
+        dim.set_block_state(&BlockPos::new(0, 2, 0), BlockState::Air);
+        dim.set_block_state(&BlockPos::new(0, 3, 0), BlockState::Air);
+
+        assert!(is_standable(&BlockPos::new(0, 1, 0), &dim));
+        assert!(!is_standable(&BlockPos::new(0, 0, 0), &dim));
+        assert!(!is_standable(&BlockPos::new(0, 2, 0), &dim));
+    }
+}
diff --git a/azalea/src/pathfinder/mtdstarlite.rs b/azalea/src/pathfinder/mtdstarlite.rs
new file mode 100644
index 00000000..8a40ec37
--- /dev/null
+++ b/azalea/src/pathfinder/mtdstarlite.rs
@@ -0,0 +1,453 @@
+//! An implementation of Moving Target D* Lite as described in
+//! <http://idm-lab.org/bib/abstracts/papers/aamas10a.pdf>
+//!
+//! Future optimization attempt ideas:
+//! - Use a different priority queue (e.g. fibonacci heap)
+//! - Use FxHash instead of the default hasher
+//! - Have `par` be a raw pointer
+//! - Try borrowing vs copying the Node in several places (like state_mut)
+//! - Store edge costs in their own map
+
+use priority_queue::DoublePriorityQueue;
+use std::{collections::HashMap, fmt::Debug, hash::Hash, ops::Add};
+
+/// Nodes are coordinates.
+pub struct MTDStarLite<
+    N: Eq + Hash + Copy + Debug,
+    W: PartialOrd + Default + Copy + num_traits::Bounded + Debug,
+    HeuristicFn: Fn(&N) -> W,
+    SuccessorsFn: Fn(&N) -> Vec<Edge<N, W>>,
+    PredecessorsFn: Fn(&N) -> Vec<Edge<N, W>>,
+    SuccessFn: Fn(&N) -> bool,
+> {
+    /// Returns a rough estimate of how close we are to the goal. Lower = closer.
+    pub heuristic: HeuristicFn,
+    /// Returns the nodes that can be reached from the given node.
+    pub successors: SuccessorsFn,
+    /// Returns the nodes that would direct us to the given node. If the graph
+    /// isn't directed (i.e. you can always return to the previous node), this
+    /// can be the same as `successors`.
+    pub predecessors: PredecessorsFn,
+    /// Returns true if the given node is at the goal.
+    /// A simple implementation is to check if the given node is equal to the goal.
+    pub success: SuccessFn,
+
+    start: N,
+    goal: N,
+
+    old_start: N,
+    old_goal: N,
+
+    k_m: W,
+    open: DoublePriorityQueue<N, Priority<W>>,
+    node_states: HashMap<N, NodeState<N, W>>,
+    updated_edge_costs: Vec<ChangedEdge<N, W>>,
+
+    /// This only exists so it can be referenced by `state()` when there's no state.
+    default_state: NodeState<N, W>,
+}
+
+impl<
+        N: Eq + Hash + Copy + Debug,
+        W: PartialOrd + Add<Output = W> + Default + Copy + num_traits::Bounded + Debug,
+        HeuristicFn: Fn(&N) -> W,
+        SuccessorsFn: Fn(&N) -> Vec<Edge<N, W>>,
+        PredecessorsFn: Fn(&N) -> Vec<Edge<N, W>>,
+        SuccessFn: Fn(&N) -> bool,
+    > MTDStarLite<N, W, HeuristicFn, SuccessorsFn, PredecessorsFn, SuccessFn>
+{
+    fn calculate_key(&self, n: &N) -> Priority<W> {
+        let s = self.state(n);
+        let min_score = if s.g < s.rhs { s.g } else { s.rhs };
+        Priority(
+            if min_score == W::max_value() {
+                min_score
+            } else {
+                min_score + (self.heuristic)(n) + self.k_m
+            },
+            min_score,
+        )
+    }
+
+    pub fn new(
+        start: N,
+        goal: N,
+        heuristic: HeuristicFn,
+        successors: SuccessorsFn,
+        predecessors: PredecessorsFn,
+        success: SuccessFn,
+    ) -> Self {
+        let open = DoublePriorityQueue::default();
+        let k_m = W::default();
+
+        let known_nodes = vec![start, goal];
+
+        let mut pf = MTDStarLite {
+            heuristic,
+            successors,
+            predecessors,
+            success,
+
+            start,
+            goal,
+
+            old_start: start,
+            old_goal: goal,
+
+            k_m,
+            open,
+            node_states: HashMap::new(),
+            updated_edge_costs: Vec::new(),
+
+            default_state: NodeState::default(),
+        };
+
+        for n in &known_nodes {
+            *pf.state_mut(n) = NodeState::default();
+        }
+        (*pf.state_mut(&start)).rhs = W::default();
+        pf.open.push(start, pf.calculate_key(&start));
+
+        pf
+    }
+
+    fn update_state(&mut self, n: &N) {
+        let u = self.state_mut(n);
+        if u.g != u.rhs {
+            if self.open.get(n).is_some() {
+                self.open.change_priority(n, self.calculate_key(n));
+            } else {
+                self.open.push(*n, self.calculate_key(n));
+            }
+        } else if self.open.get(n).is_some() {
+            self.open.remove(n);
+        }
+    }
+
+    fn compute_cost_minimal_path(&mut self) {
+        while {
+            if let Some((_, top_key)) = self.open.peek_min() {
+                (top_key < &self.calculate_key(&self.goal)) || {
+                    let goal_state = self.state(&self.goal);
+                    goal_state.rhs > goal_state.g
+                }
+            } else {
+                false
+            }
+        } {
+            let (u_node, k_old) = self.open.pop_min().unwrap();
+            let k_new = self.calculate_key(&u_node);
+            if k_old < k_new {
+                self.open.change_priority(&u_node, k_new);
+                continue;
+            }
+            let u = self.state_mut(&u_node);
+            if u.g > u.rhs {
+                u.g = u.rhs;
+                self.open.remove(&u_node);
+                for edge in (self.successors)(&u_node) {
+                    let s_node = edge.target;
+                    let s = self.state(&s_node);
+                    let u = self.state(&u_node);
+                    if s_node != self.start && (s.rhs > u.g + edge.cost) {
+                        let s_rhs = u.g + edge.cost;
+                        let s = self.state_mut(&s_node);
+                        s.par = Some(u_node);
+                        s.rhs = s_rhs;
+                        self.update_state(&s_node);
+                    }
+                }
+            } else {
+                u.g = W::max_value();
+                let u_edge = Edge {
+                    target: u_node,
+                    cost: W::default(),
+                };
+                for edge in (self.successors)(&u_node)
+                    .iter()
+                    .chain([&u_edge].into_iter())
+                {
+                    let s_node = edge.target;
+                    let s = self.state(&s_node);
+                    if s_node != self.start && s.par == Some(u_node) {
+                        let mut min_pred = u_node;
+                        let mut min_score = W::max_value();
+
+                        for edge in (self.predecessors)(&s_node) {
+                            let s = self.state(&edge.target);
+                            let score = s.g + edge.cost;
+                            if score < min_score {
+                                min_score = score;
+                                min_pred = edge.target;
+                            }
+                        }
+
+                        let s = self.state_mut(&s_node);
+                        s.rhs = min_score;
+                        if s.rhs == W::max_value() {
+                            s.par = None;
+                        } else {
+                            s.par = Some(min_pred);
+                        }
+                    }
+                    self.update_state(&s_node);
+                }
+            }
+        }
+    }
+
+    pub fn find_path(&mut self) -> Option<Vec<N>> {
+        if (self.success)(&self.start) {
+            return None;
+        }
+
+        //
+        self.k_m = self.k_m + (self.heuristic)(&self.old_goal);
+
+        if self.old_start != self.start {
+            self.optimized_deletion();
+        }
+
+        while let Some(edge) = self.updated_edge_costs.pop() {
+            let (u_node, v_node) = (edge.predecessor, edge.successor);
+            // update the edge cost c(u, v);
+            if edge.old_cost > edge.cost {
+                let u_g = self.state(&u_node).g;
+                if v_node != self.start && self.state(&v_node).rhs > u_g + edge.cost {
+                    let v = self.state_mut(&v_node);
+                    v.par = Some(u_node);
+                    v.rhs = u_g + edge.cost;
+                }
+            } else if v_node != self.start && self.state(&v_node).par == Some(u_node) {
+                let mut min_pred = u_node;
+                let mut min_score = W::max_value();
+
+                for edge in (self.predecessors)(&v_node) {
+                    let s = self.state(&edge.target);
+                    let score = s.g + edge.cost;
+                    if score < min_score {
+                        min_score = score;
+                        min_pred = edge.target;
+                    }
+                }
+
+                let v = self.state_mut(&v_node);
+                v.rhs = min_score;
+                if v.rhs == W::max_value() {
+                    v.par = None;
+                } else {
+                    v.par = Some(min_pred);
+                }
+                self.update_state(&v_node);
+            }
+        }
+        //
+
+        self.old_start = self.start;
+        self.old_goal = self.goal;
+
+        self.compute_cost_minimal_path();
+        if self.state(&self.goal).rhs == W::max_value() {
+            // no path exists
+            return None;
+        }
+
+        let mut reverse_path = vec![self.goal];
+
+        // identify a path from sstart to sgoal using the parent pointers
+        let mut target = self.state(&self.goal).par;
+        while !(Some(self.start) == target) {
+            let this_target = if let Some(this_target) = target {
+                this_target
+            } else {
+                break;
+            };
+            // hunter follows path from start to goal;
+            reverse_path.push(this_target);
+            target = self.state(&this_target).par;
+        }
+
+        // if hunter caught target {
+        //     return None;
+        // }
+
+        let path: Vec<N> = reverse_path.into_iter().rev().collect();
+
+        Some(path)
+    }
+
+    fn optimized_deletion(&mut self) {
+        let start = self.start;
+        self.state_mut(&start).par = None;
+
+        let mut min_pred = self.old_start;
+        let mut min_score = W::max_value();
+
+        for edge in (self.predecessors)(&self.old_start) {
+            let s = self.state(&edge.target);
+            let score = s.g + edge.cost;
+            if score < min_score {
+                min_score = score;
+                min_pred = edge.target;
+            }
+        }
+
+        let old_start = self.old_start;
+        let s = self.state_mut(&old_start);
+        s.rhs = min_score;
+        if s.rhs == W::max_value() {
+            s.par = None;
+        } else {
+            s.par = Some(min_pred);
+        }
+        self.update_state(&old_start);
+    }
+
+    fn state(&self, n: &N) -> &NodeState<N, W> {
+        self.node_states.get(n).unwrap_or(&self.default_state)
+    }
+
+    fn state_mut(&mut self, n: &N) -> &mut NodeState<N, W> {
+        self.node_states.entry(*n).or_default()
+    }
+}
+
+#[derive(PartialEq, Debug)]
+pub struct Priority<W>(W, W)
+where
+    W: PartialOrd + Debug;
+
+impl<W: PartialOrd + Debug> PartialOrd for Priority<W> {
+    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
+        if self.0 < other.0 {
+            Some(std::cmp::Ordering::Less)
+        } else if self.0 > other.0 {
+            Some(std::cmp::Ordering::Greater)
+        } else if self.1 < other.1 {
+            Some(std::cmp::Ordering::Less)
+        } else if self.1 > other.1 {
+            Some(std::cmp::Ordering::Greater)
+        } else {
+            Some(std::cmp::Ordering::Equal)
+        }
+    }
+}
+impl<W: PartialOrd + Debug> Ord for Priority<W> {
+    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
+        self.partial_cmp(other)
+            .expect("Partial compare should not fail for Priority")
+    }
+}
+impl<W: PartialOrd + Debug> Eq for Priority<W> {}
+
+#[derive(Debug)]
+pub struct NodeState<N: Eq + Hash + Copy + Debug, W: Default + num_traits::Bounded + Debug> {
+    pub g: W,
+    pub rhs: W,
+    // future possible optimization: try making this a pointer
+    pub par: Option<N>,
+}
+
+impl<N: Eq + Hash + Copy + Debug, W: Default + num_traits::Bounded + Debug> Default
+    for NodeState<N, W>
+{
+    fn default() -> Self {
+        NodeState {
+            g: W::max_value(),
+            rhs: W::max_value(),
+            par: None,
+        }
+    }
+}
+
+pub struct Edge<N: Eq + Hash + Copy, W: PartialOrd + Copy> {
+    pub target: N,
+    pub cost: W,
+}
+
+pub struct ChangedEdge<N: Eq + Hash + Clone, W: PartialOrd + Copy> {
+    pub predecessor: N,
+    pub successor: N,
+    pub old_cost: W,
+    pub cost: W,
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    #[test]
+    fn test_mtdstarlite() {
+        let maze = [
+            [0, 1, 0, 0, 0],
+            [0, 1, 0, 1, 0],
+            [0, 0, 0, 1, 0],
+            [0, 1, 0, 1, 0],
+            [0, 0, 1, 0, 0],
+        ];
+        let width = maze[0].len();
+        let height = maze.len();
+
+        let goal = (4, 4);
+
+        let heuristic = |n: &(usize, usize)| -> usize {
+            ((n.0 as isize - goal.0 as isize).abs() + (n.1 as isize - goal.1 as isize).abs())
+                as usize
+        };
+        let successors = |n: &(usize, usize)| -> Vec<Edge<(usize, usize), usize>> {
+            let mut successors = Vec::with_capacity(4);
+            let (x, y) = *n;
+
+            if x > 0 && maze[y][x - 1] == 0 {
+                successors.push(Edge {
+                    target: ((x - 1, y)),
+                    cost: 1,
+                });
+            }
+            if x < width - 1 && maze[y][x + 1] == 0 {
+                successors.push(Edge {
+                    target: ((x + 1, y)),
+                    cost: 1,
+                });
+            }
+            if y > 0 && maze[y - 1][x] == 0 {
+                successors.push(Edge {
+                    target: ((x, y - 1)),
+                    cost: 1,
+                });
+            }
+            if y < height - 1 && maze[y + 1][x] == 0 {
+                successors.push(Edge {
+                    target: ((x, y + 1)),
+                    cost: 1,
+                });
+            }
+
+            successors
+        };
+        let predecessors =
+            |n: &(usize, usize)| -> Vec<Edge<(usize, usize), usize>> { successors(n) };
+
+        let mut pf = MTDStarLite::new((0, 0), goal, heuristic, successors, predecessors, |n| {
+            n == &goal
+        });
+        let path = pf.find_path().unwrap();
+        assert_eq!(
+            path,
+            vec![
+                (0, 1),
+                (0, 2),
+                (1, 2),
+                (2, 2),
+                (2, 1),
+                (2, 0),
+                (3, 0),
+                (4, 0),
+                (4, 1),
+                (4, 2),
+                (4, 3),
+                (4, 4),
+            ]
+        );
+    }
+}
diff --git a/azalea/src/prelude.rs b/azalea/src/prelude.rs
index c09d85e2..9fa1ac1a 100644..100755
--- a/azalea/src/prelude.rs
+++ b/azalea/src/prelude.rs
@@ -1,4 +1,6 @@
 //! The Azalea prelude. Things that are necessary for a bare-bones bot are re-exported here.
 
 pub use crate::bot::BotTrait;
+pub use crate::pathfinder::Trait;
+pub use crate::plugins;
 pub use azalea_client::{Account, Client, Event};