aboutsummaryrefslogtreecommitdiff
path: root/azalea/src/pathfinder
diff options
context:
space:
mode:
Diffstat (limited to 'azalea/src/pathfinder')
-rw-r--r--azalea/src/pathfinder/mod.rs341
-rw-r--r--azalea/src/pathfinder/moves.rs136
-rw-r--r--azalea/src/pathfinder/mtdstarlite.rs8
3 files changed, 314 insertions, 171 deletions
diff --git a/azalea/src/pathfinder/mod.rs b/azalea/src/pathfinder/mod.rs
index de62e9a7..5246290d 100644
--- a/azalea/src/pathfinder/mod.rs
+++ b/azalea/src/pathfinder/mod.rs
@@ -1,147 +1,255 @@
mod moves;
mod mtdstarlite;
-use crate::{prelude::*, SprintDirection, WalkDirection};
-use crate::{Client, Event};
-use async_trait::async_trait;
+use crate::bot::{JumpEvent, LookAtEvent};
+use crate::{SprintDirection, WalkDirection};
+
+use azalea_client::{StartSprintEvent, StartWalkEvent};
use azalea_core::{BlockPos, CardinalDirection};
-use azalea_world::entity::EntityData;
+use azalea_ecs::{
+ app::{App, Plugin},
+ component::Component,
+ entity::Entity,
+ event::{EventReader, EventWriter},
+ query::{With, Without},
+ schedule::IntoSystemDescriptor,
+ system::{Commands, Query, Res},
+ AppTickExt,
+};
+use azalea_world::entity::metadata::Player;
+use azalea_world::Local;
+use azalea_world::{
+ entity::{Physics, Position, WorldName},
+ WorldContainer,
+};
+use bevy_tasks::{AsyncComputeTaskPool, Task};
+use futures_lite::future;
use log::{debug, error};
use mtdstarlite::Edge;
pub use mtdstarlite::MTDStarLite;
-use parking_lot::Mutex;
use std::collections::VecDeque;
use std::sync::Arc;
#[derive(Clone, Default)]
-pub struct Plugin;
-impl crate::Plugin for Plugin {
- type State = State;
-
- fn build(&self) -> State {
- State::default()
+pub struct PathfinderPlugin;
+impl Plugin for PathfinderPlugin {
+ fn build(&self, app: &mut App) {
+ app.add_event::<GotoEvent>()
+ .add_event::<PathFoundEvent>()
+ .add_tick_system(tick_execute_path.before("walk_listener"))
+ .add_system(goto_listener)
+ .add_system(add_default_pathfinder.after("deduplicate_entities"))
+ .add_system(handle_tasks)
+ .add_system(path_found_listener);
}
}
-#[derive(Default, Clone)]
-pub struct State {
- // pathfinder: Option<MTDStarLite<Node, f32>>,
- pub path: Arc<Mutex<VecDeque<Node>>>,
+/// A component that makes this entity able to pathfind.
+#[derive(Component, Default)]
+pub struct Pathfinder {
+ pub path: VecDeque<Node>,
+}
+#[allow(clippy::type_complexity)]
+fn add_default_pathfinder(
+ mut commands: Commands,
+ mut query: Query<Entity, (Without<Pathfinder>, With<Local>, With<Player>)>,
+) {
+ for entity in &mut query {
+ commands.entity(entity).insert(Pathfinder::default());
+ }
}
-#[async_trait]
-impl crate::PluginState for State {
- async fn handle(self: Box<Self>, event: Event, mut bot: Client) {
- if let Event::Tick = event {
- let mut path = self.path.lock();
+pub trait PathfinderClientExt {
+ fn goto(&self, goal: impl Goal + Send + Sync + 'static);
+}
- if !path.is_empty() {
- tick_execute_path(&mut bot, &mut path);
- }
- }
+impl PathfinderClientExt for azalea_client::Client {
+ fn goto(&self, goal: impl Goal + Send + Sync + 'static) {
+ self.ecs.lock().send_event(GotoEvent {
+ entity: self.entity,
+ goal: Arc::new(goal),
+ });
}
}
-
-pub trait Trait {
- fn goto(&self, goal: impl Goal);
+pub struct GotoEvent {
+ pub entity: Entity,
+ pub goal: Arc<dyn Goal + Send + Sync>,
}
+pub struct PathFoundEvent {
+ pub entity: Entity,
+ pub path: VecDeque<Node>,
+}
+
+#[derive(Component)]
+pub struct ComputePath(Task<Option<PathFoundEvent>>);
-impl Trait for azalea_client::Client {
- fn goto(&self, goal: impl Goal) {
+fn goto_listener(
+ mut commands: Commands,
+ mut events: EventReader<GotoEvent>,
+ mut query: Query<(&Position, &WorldName)>,
+ world_container: Res<WorldContainer>,
+) {
+ let thread_pool = AsyncComputeTaskPool::get();
+
+ for event in events.iter() {
+ let (position, world_name) = query
+ .get_mut(event.entity)
+ .expect("Called goto on an entity that's not in the world");
let start = Node {
- pos: BlockPos::from(self.entity().pos()),
+ pos: BlockPos::from(position),
vertical_vel: VerticalVel::None,
};
- let end = goal.goal_node();
- debug!("start: {start:?}, end: {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 world = &self.world.read().shared;
- for possible_move in possible_moves.iter() {
- edges.push(Edge {
- target: possible_move.next_node(node),
- cost: possible_move.cost(world, node),
- });
+
+ let world_lock = world_container
+ .get(world_name)
+ .expect("Entity tried to pathfind but the entity isn't in a valid world");
+ let end = event.goal.goal_node();
+
+ let goal = event.goal.clone();
+ let entity = event.entity;
+
+ let task = thread_pool.spawn(async move {
+ debug!("start: {start:?}, end: {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 world = world_lock.read();
+ for possible_move in &possible_moves {
+ edges.push(Edge {
+ target: possible_move.next_node(node),
+ cost: possible_move.cost(&world, node),
+ });
+ }
+ edges
+ };
+
+ let mut pf = MTDStarLite::new(
+ start,
+ end,
+ |n| goal.heuristic(n),
+ successors,
+ successors,
+ |n| goal.success(n),
+ );
+
+ let start_time = std::time::Instant::now();
+ let p = pf.find_path();
+ let end_time = std::time::Instant::now();
+ debug!("path: {p:?}");
+ debug!("time: {:?}", end_time - start_time);
+
+ // convert the Option<Vec<Node>> to a VecDeque<Node>
+ if let Some(p) = p {
+ let path = p.into_iter().collect::<VecDeque<_>>();
+ // commands.entity(event.entity).insert(Pathfinder { path: p });
+ Some(PathFoundEvent { entity, path })
+ } else {
+ error!("no path found");
+ None
}
- 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();
- debug!("path: {p:?}");
- debug!("time: {:?}", end - start);
-
- let state = self
- .plugins
- .get::<State>()
- .expect("Pathfinder plugin not installed!")
- .clone();
- // convert the Option<Vec<Node>> to a VecDeque<Node>
- if let Some(p) = p {
- *state.path.lock() = p.into_iter().collect();
- } else {
- error!("no path found");
+ commands.spawn(ComputePath(task));
+ }
+}
+
+// poll the tasks and send the PathFoundEvent if they're done
+fn handle_tasks(
+ mut commands: Commands,
+ mut transform_tasks: Query<(Entity, &mut ComputePath)>,
+ mut path_found_events: EventWriter<PathFoundEvent>,
+) {
+ for (entity, mut task) in &mut transform_tasks {
+ if let Some(optional_path_found_event) = future::block_on(future::poll_once(&mut task.0)) {
+ if let Some(path_found_event) = optional_path_found_event {
+ path_found_events.send(path_found_event);
+ }
+
+ // Task is complete, so remove task component from entity
+ commands.entity(entity).remove::<ComputePath>();
}
}
}
-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();
+// set the path for the target entity when we get the PathFoundEvent
+fn path_found_listener(mut events: EventReader<PathFoundEvent>, mut query: Query<&mut Pathfinder>) {
+ for event in events.iter() {
+ let mut pathfinder = query
+ .get_mut(event.entity)
+ .expect("Path found for an entity that doesn't have a pathfinder");
+ pathfinder.path = event.path.clone();
}
+}
- if target.is_reached(&bot.entity()) {
- // println!("ok target {target:?} reached");
- path.pop_front();
- if path.is_empty() {
- bot.walk(WalkDirection::None);
+fn tick_execute_path(
+ mut query: Query<(Entity, &mut Pathfinder, &Position, &Physics)>,
+ mut look_at_events: EventWriter<LookAtEvent>,
+ mut sprint_events: EventWriter<StartSprintEvent>,
+ mut walk_events: EventWriter<StartWalkEvent>,
+ mut jump_events: EventWriter<JumpEvent>,
+) {
+ for (entity, mut pathfinder, position, physics) in &mut query {
+ loop {
+ let Some(target) = pathfinder.path.front() else {
+ break;
+ };
+ let center = target.pos.center();
+ // println!("going to {center:?} (at {pos:?})", pos = bot.entity().pos());
+ look_at_events.send(LookAtEvent {
+ entity,
+ position: center,
+ });
+ debug!(
+ "tick: pathfinder {entity:?}; going to {:?}; currently at {position:?}",
+ target.pos
+ );
+ sprint_events.send(StartSprintEvent {
+ entity,
+ direction: SprintDirection::Forward,
+ });
+ // check if we should jump
+ if target.pos.y > position.y.floor() as i32 {
+ jump_events.send(JumpEvent(entity));
+ }
+
+ if target.is_reached(position, physics) {
+ // println!("reached target");
+ pathfinder.path.pop_front();
+ if pathfinder.path.is_empty() {
+ // println!("reached goal");
+ walk_events.send(StartWalkEvent {
+ entity,
+ direction: WalkDirection::None,
+ });
+ }
+ // tick again, maybe we already reached the next node!
+ } else {
+ break;
+ }
}
- // tick again, maybe we already reached the next node!
- tick_execute_path(bot, path);
}
}
@@ -172,7 +280,8 @@ pub trait Goal {
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 {
+ #[must_use]
+ pub fn is_reached(&self, position: &Position, physics: &Physics) -> bool {
// println!(
// "entity.delta.y: {} {:?}=={:?}, self.vertical_vel={:?}",
// entity.delta.y,
@@ -180,11 +289,11 @@ impl Node {
// self.pos,
// self.vertical_vel
// );
- BlockPos::from(entity.pos()) == self.pos
+ BlockPos::from(position) == 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,
+ VerticalVel::NoneMidair => physics.delta.y > -0.1 && physics.delta.y < 0.1,
+ VerticalVel::None => physics.on_ground,
+ VerticalVel::FallingLittle => physics.delta.y < -0.1,
}
}
}
diff --git a/azalea/src/pathfinder/moves.rs b/azalea/src/pathfinder/moves.rs
index ccf8ba1a..9bb5c7c1 100644
--- a/azalea/src/pathfinder/moves.rs
+++ b/azalea/src/pathfinder/moves.rs
@@ -1,11 +1,11 @@
use super::{Node, VerticalVel};
use azalea_core::{BlockPos, CardinalDirection};
use azalea_physics::collision::{self, BlockWithShape};
-use azalea_world::WeakWorld;
+use azalea_world::World;
/// whether this block is passable
-fn is_block_passable(pos: &BlockPos, world: &WeakWorld) -> bool {
- if let Some(block) = world.get_block_state(pos) {
+fn is_block_passable(pos: &BlockPos, world: &World) -> bool {
+ if let Some(block) = world.chunks.get_block_state(pos) {
block.shape() == &collision::empty_shape()
} else {
false
@@ -13,8 +13,8 @@ fn is_block_passable(pos: &BlockPos, world: &WeakWorld) -> bool {
}
/// whether this block has a solid hitbox (i.e. we can stand on it)
-fn is_block_solid(pos: &BlockPos, world: &WeakWorld) -> bool {
- if let Some(block) = world.get_block_state(pos) {
+fn is_block_solid(pos: &BlockPos, world: &World) -> bool {
+ if let Some(block) = world.chunks.get_block_state(pos) {
block.shape() == &collision::block_shape()
} else {
false
@@ -22,22 +22,22 @@ fn is_block_solid(pos: &BlockPos, world: &WeakWorld) -> bool {
}
/// Whether this block and the block above are passable
-fn is_passable(pos: &BlockPos, world: &WeakWorld) -> bool {
+fn is_passable(pos: &BlockPos, world: &World) -> bool {
is_block_passable(pos, world) && is_block_passable(&pos.up(1), world)
}
/// 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, world: &WeakWorld) -> bool {
+fn is_standable(pos: &BlockPos, world: &World) -> bool {
is_block_solid(&pos.down(1), world) && is_passable(pos, world)
}
const JUMP_COST: f32 = 0.5;
const WALK_ONE_BLOCK_COST: f32 = 1.0;
-pub trait Move {
- fn cost(&self, world: &WeakWorld, node: &Node) -> f32;
+pub trait Move: Send + Sync {
+ fn cost(&self, world: &World, node: &Node) -> f32;
/// Returns by how much the entity's position should be changed when this
/// move is executed.
fn offset(&self) -> BlockPos;
@@ -51,7 +51,7 @@ pub trait Move {
pub struct ForwardMove(pub CardinalDirection);
impl Move for ForwardMove {
- fn cost(&self, world: &WeakWorld, node: &Node) -> f32 {
+ fn cost(&self, world: &World, node: &Node) -> f32 {
if is_standable(&(node.pos + self.offset()), world)
&& node.vertical_vel == VerticalVel::None
{
@@ -67,7 +67,7 @@ impl Move for ForwardMove {
pub struct AscendMove(pub CardinalDirection);
impl Move for AscendMove {
- fn cost(&self, world: &WeakWorld, node: &Node) -> f32 {
+ fn cost(&self, world: &World, node: &Node) -> f32 {
if node.vertical_vel == VerticalVel::None
&& is_block_passable(&node.pos.up(2), world)
&& is_standable(&(node.pos + self.offset()), world)
@@ -89,7 +89,7 @@ impl Move for AscendMove {
}
pub struct DescendMove(pub CardinalDirection);
impl Move for DescendMove {
- fn cost(&self, world: &WeakWorld, node: &Node) -> f32 {
+ fn cost(&self, world: &World, node: &Node) -> f32 {
// check whether 3 blocks vertically forward are passable
if node.vertical_vel == VerticalVel::None
&& is_standable(&(node.pos + self.offset()), world)
@@ -112,7 +112,7 @@ impl Move for DescendMove {
}
pub struct DiagonalMove(pub CardinalDirection);
impl Move for DiagonalMove {
- fn cost(&self, world: &WeakWorld, node: &Node) -> f32 {
+ fn cost(&self, world: &World, node: &Node) -> f32 {
if node.vertical_vel != VerticalVel::None {
return f32::INFINITY;
}
@@ -151,56 +151,92 @@ mod tests {
use super::*;
use azalea_block::BlockState;
use azalea_core::ChunkPos;
- use azalea_world::{Chunk, PartialWorld};
+ use azalea_world::{Chunk, ChunkStorage, PartialWorld};
#[test]
fn test_is_passable() {
- let mut world = PartialWorld::default();
- world
- .set_chunk(&ChunkPos { x: 0, z: 0 }, Some(Chunk::default()))
- .unwrap();
- world.set_block_state(&BlockPos::new(0, 0, 0), BlockState::Stone);
- world.set_block_state(&BlockPos::new(0, 1, 0), BlockState::Air);
-
- assert_eq!(
- is_block_passable(&BlockPos::new(0, 0, 0), &world.shared),
- false
+ let mut partial_world = PartialWorld::default();
+ let mut chunk_storage = ChunkStorage::default();
+
+ partial_world.chunks.set(
+ &ChunkPos { x: 0, z: 0 },
+ Some(Chunk::default()),
+ &mut chunk_storage,
+ );
+ partial_world.chunks.set_block_state(
+ &BlockPos::new(0, 0, 0),
+ BlockState::Stone,
+ &mut chunk_storage,
);
- assert_eq!(
- is_block_passable(&BlockPos::new(0, 1, 0), &world.shared),
- true
+ partial_world.chunks.set_block_state(
+ &BlockPos::new(0, 1, 0),
+ BlockState::Air,
+ &mut chunk_storage,
);
+
+ let world = chunk_storage.into();
+ assert_eq!(is_block_passable(&BlockPos::new(0, 0, 0), &world), false);
+ assert_eq!(is_block_passable(&BlockPos::new(0, 1, 0), &world), true);
}
#[test]
fn test_is_solid() {
- let mut world = PartialWorld::default();
- world
- .set_chunk(&ChunkPos { x: 0, z: 0 }, Some(Chunk::default()))
- .unwrap();
- world.set_block_state(&BlockPos::new(0, 0, 0), BlockState::Stone);
- world.set_block_state(&BlockPos::new(0, 1, 0), BlockState::Air);
-
- assert_eq!(is_block_solid(&BlockPos::new(0, 0, 0), &world.shared), true);
- assert_eq!(
- is_block_solid(&BlockPos::new(0, 1, 0), &world.shared),
- false
+ let mut partial_world = PartialWorld::default();
+ let mut chunk_storage = ChunkStorage::default();
+ partial_world.chunks.set(
+ &ChunkPos { x: 0, z: 0 },
+ Some(Chunk::default()),
+ &mut chunk_storage,
);
+ partial_world.chunks.set_block_state(
+ &BlockPos::new(0, 0, 0),
+ BlockState::Stone,
+ &mut chunk_storage,
+ );
+ partial_world.chunks.set_block_state(
+ &BlockPos::new(0, 1, 0),
+ BlockState::Air,
+ &mut chunk_storage,
+ );
+
+ let world = chunk_storage.into();
+ assert_eq!(is_block_solid(&BlockPos::new(0, 0, 0), &world), true);
+ assert_eq!(is_block_solid(&BlockPos::new(0, 1, 0), &world), false);
}
#[test]
fn test_is_standable() {
- let mut world = PartialWorld::default();
- world
- .set_chunk(&ChunkPos { x: 0, z: 0 }, Some(Chunk::default()))
- .unwrap();
- world.set_block_state(&BlockPos::new(0, 0, 0), BlockState::Stone);
- world.set_block_state(&BlockPos::new(0, 1, 0), BlockState::Air);
- world.set_block_state(&BlockPos::new(0, 2, 0), BlockState::Air);
- world.set_block_state(&BlockPos::new(0, 3, 0), BlockState::Air);
-
- assert!(is_standable(&BlockPos::new(0, 1, 0), &world.shared));
- assert!(!is_standable(&BlockPos::new(0, 0, 0), &world.shared));
- assert!(!is_standable(&BlockPos::new(0, 2, 0), &world.shared));
+ let mut partial_world = PartialWorld::default();
+ let mut chunk_storage = ChunkStorage::default();
+ partial_world.chunks.set(
+ &ChunkPos { x: 0, z: 0 },
+ Some(Chunk::default()),
+ &mut chunk_storage,
+ );
+ partial_world.chunks.set_block_state(
+ &BlockPos::new(0, 0, 0),
+ BlockState::Stone,
+ &mut chunk_storage,
+ );
+ partial_world.chunks.set_block_state(
+ &BlockPos::new(0, 1, 0),
+ BlockState::Air,
+ &mut chunk_storage,
+ );
+ partial_world.chunks.set_block_state(
+ &BlockPos::new(0, 2, 0),
+ BlockState::Air,
+ &mut chunk_storage,
+ );
+ partial_world.chunks.set_block_state(
+ &BlockPos::new(0, 3, 0),
+ BlockState::Air,
+ &mut chunk_storage,
+ );
+
+ let world = chunk_storage.into();
+ assert!(is_standable(&BlockPos::new(0, 1, 0), &world));
+ assert!(!is_standable(&BlockPos::new(0, 0, 0), &world));
+ assert!(!is_standable(&BlockPos::new(0, 2, 0), &world));
}
}
diff --git a/azalea/src/pathfinder/mtdstarlite.rs b/azalea/src/pathfinder/mtdstarlite.rs
index 50a467df..ce463279 100644
--- a/azalea/src/pathfinder/mtdstarlite.rs
+++ b/azalea/src/pathfinder/mtdstarlite.rs
@@ -3,9 +3,9 @@
//!
//! Future optimization attempt ideas:
//! - Use a different priority queue (e.g. fibonacci heap)
-//! - Use FxHash instead of the default hasher
+//! - 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)
+//! - Try borrowing vs copying the Node in several places (like `state_mut`)
//! - Store edge costs in their own map
use priority_queue::DoublePriorityQueue;
@@ -260,9 +260,7 @@ impl<
// 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 {
+ let Some(this_target) = target else {
break;
};
// hunter follows path from start to goal;
generated by cgit v1.2.3 (git 2.39.1) at 2026-06-08 05:15:52 +0000