1pub mod astar;
6pub mod costs;
7pub mod debug;
8pub mod goals;
9pub mod mining;
10pub mod moves;
11pub mod rel_block_pos;
12pub mod simulation;
13pub mod world;
14
15use std::collections::VecDeque;
16use std::ops::RangeInclusive;
17use std::sync::Arc;
18use std::sync::atomic::{self, AtomicUsize};
19use std::time::{Duration, Instant};
20use std::{cmp, thread};
21
22use astar::PathfinderTimeout;
23use azalea_client::inventory::{Inventory, InventorySet, SetSelectedHotbarSlotEvent};
24use azalea_client::mining::{Mining, StartMiningBlockEvent};
25use azalea_client::movement::MoveEventsSet;
26use azalea_client::{InstanceHolder, StartSprintEvent, StartWalkEvent};
27use azalea_core::position::BlockPos;
28use azalea_core::tick::GameTick;
29use azalea_entity::LocalEntity;
30use azalea_entity::metadata::Player;
31use azalea_entity::{Physics, Position};
32use azalea_physics::PhysicsSet;
33use azalea_world::{InstanceContainer, InstanceName};
34use bevy_app::{PreUpdate, Update};
35use bevy_ecs::prelude::*;
36use bevy_tasks::{AsyncComputeTaskPool, Task};
37use futures_lite::future;
38use goals::BlockPosGoal;
39use parking_lot::RwLock;
40use rel_block_pos::RelBlockPos;
41use tokio::sync::broadcast::error::RecvError;
42use tracing::{debug, error, info, trace, warn};
43
44use self::debug::debug_render_path_with_particles;
45use self::goals::Goal;
46use self::mining::MiningCache;
47use self::moves::{ExecuteCtx, IsReachedCtx, SuccessorsFn};
48use crate::app::{App, Plugin};
49use crate::bot::{JumpEvent, LookAtEvent};
50use crate::ecs::{
51 component::Component,
52 entity::Entity,
53 event::{EventReader, EventWriter},
54 query::{With, Without},
55 system::{Commands, Query, Res},
56};
57use crate::pathfinder::{astar::a_star, moves::PathfinderCtx, world::CachedWorld};
58use crate::{BotClientExt, WalkDirection};
59
60#[derive(Clone, Default)]
61pub struct PathfinderPlugin;
62impl Plugin for PathfinderPlugin {
63 fn build(&self, app: &mut App) {
64 app.add_event::<GotoEvent>()
65 .add_event::<PathFoundEvent>()
66 .add_event::<StopPathfindingEvent>()
67 .add_systems(
68 GameTick,
71 (
72 timeout_movement,
73 check_for_path_obstruction,
74 check_node_reached,
75 tick_execute_path,
76 debug_render_path_with_particles,
77 recalculate_near_end_of_path,
78 recalculate_if_has_goal_but_no_path,
79 )
80 .chain()
81 .after(PhysicsSet)
82 .after(azalea_client::movement::send_position),
83 )
84 .add_systems(PreUpdate, add_default_pathfinder)
85 .add_systems(
86 Update,
87 (
88 goto_listener,
89 handle_tasks,
90 stop_pathfinding_on_instance_change,
91 path_found_listener,
92 handle_stop_pathfinding_event,
93 )
94 .chain()
95 .before(MoveEventsSet)
96 .before(InventorySet),
97 );
98 }
99}
100
101#[derive(Component, Default, Clone)]
103pub struct Pathfinder {
104 pub goal: Option<Arc<dyn Goal>>,
105 pub successors_fn: Option<SuccessorsFn>,
106 pub is_calculating: bool,
107 pub allow_mining: bool,
108
109 pub min_timeout: Option<PathfinderTimeout>,
110 pub max_timeout: Option<PathfinderTimeout>,
111
112 pub goto_id: Arc<AtomicUsize>,
113}
114
115#[derive(Component, Clone)]
118pub struct ExecutingPath {
119 pub path: VecDeque<astar::Movement<BlockPos, moves::MoveData>>,
120 pub queued_path: Option<VecDeque<astar::Movement<BlockPos, moves::MoveData>>>,
121 pub last_reached_node: BlockPos,
122 pub last_node_reached_at: Instant,
123 pub is_path_partial: bool,
124}
125
126#[derive(Event)]
132pub struct GotoEvent {
133 pub entity: Entity,
135 pub goal: Arc<dyn Goal>,
136 pub successors_fn: SuccessorsFn,
139
140 pub allow_mining: bool,
142
143 pub min_timeout: PathfinderTimeout,
152 pub max_timeout: PathfinderTimeout,
159}
160#[derive(Event, Clone, Debug)]
161pub struct PathFoundEvent {
162 pub entity: Entity,
163 pub start: BlockPos,
164 pub path: Option<VecDeque<astar::Movement<BlockPos, moves::MoveData>>>,
165 pub is_partial: bool,
166 pub successors_fn: SuccessorsFn,
167 pub allow_mining: bool,
168}
169
170#[allow(clippy::type_complexity)]
171pub fn add_default_pathfinder(
172 mut commands: Commands,
173 mut query: Query<Entity, (Without<Pathfinder>, With<LocalEntity>, With<Player>)>,
174) {
175 for entity in &mut query {
176 commands.entity(entity).insert(Pathfinder::default());
177 }
178}
179
180pub trait PathfinderClientExt {
181 fn goto(&self, goal: impl Goal + 'static) -> impl Future<Output = ()>;
182 fn start_goto(&self, goal: impl Goal + 'static);
183 fn start_goto_without_mining(&self, goal: impl Goal + 'static);
184 fn stop_pathfinding(&self);
185 fn wait_until_goto_target_reached(&self) -> impl Future<Output = ()>;
186 fn is_goto_target_reached(&self) -> bool;
187}
188
189impl PathfinderClientExt for azalea_client::Client {
190 async fn goto(&self, goal: impl Goal + 'static) {
201 self.start_goto(goal);
202 self.wait_until_goto_target_reached().await;
203 }
204
205 fn start_goto(&self, goal: impl Goal + 'static) {
215 self.ecs.lock().send_event(GotoEvent {
216 entity: self.entity,
217 goal: Arc::new(goal),
218 successors_fn: moves::default_move,
219 allow_mining: true,
220 min_timeout: PathfinderTimeout::Time(Duration::from_secs(1)),
221 max_timeout: PathfinderTimeout::Time(Duration::from_secs(5)),
222 });
223 }
224
225 fn start_goto_without_mining(&self, goal: impl Goal + 'static) {
228 self.ecs.lock().send_event(GotoEvent {
229 entity: self.entity,
230 goal: Arc::new(goal),
231 successors_fn: moves::default_move,
232 allow_mining: false,
233 min_timeout: PathfinderTimeout::Time(Duration::from_secs(1)),
234 max_timeout: PathfinderTimeout::Time(Duration::from_secs(5)),
235 });
236 }
237
238 fn stop_pathfinding(&self) {
239 self.ecs.lock().send_event(StopPathfindingEvent {
240 entity: self.entity,
241 force: false,
242 });
243 }
244
245 async fn wait_until_goto_target_reached(&self) {
247 self.wait_one_update().await;
250
251 let mut tick_broadcaster = self.get_tick_broadcaster();
252 while !self.is_goto_target_reached() {
253 match tick_broadcaster.recv().await {
255 Ok(_) => (),
256 Err(RecvError::Closed) => return,
257 Err(err) => warn!("{err}"),
258 };
259 }
260 }
261
262 fn is_goto_target_reached(&self) -> bool {
263 self.map_get_component::<Pathfinder, _>(|p| {
264 p.map(|p| p.goal.is_none() && !p.is_calculating)
265 .unwrap_or(true)
266 })
267 }
268}
269
270#[derive(Component)]
271pub struct ComputePath(Task<Option<PathFoundEvent>>);
272
273pub fn goto_listener(
274 mut commands: Commands,
275 mut events: EventReader<GotoEvent>,
276 mut query: Query<(
277 &mut Pathfinder,
278 Option<&ExecutingPath>,
279 &Position,
280 &InstanceName,
281 &Inventory,
282 )>,
283 instance_container: Res<InstanceContainer>,
284) {
285 let thread_pool = AsyncComputeTaskPool::get();
286
287 for event in events.read() {
288 let Ok((mut pathfinder, executing_path, position, instance_name, inventory)) =
289 query.get_mut(event.entity)
290 else {
291 warn!("got goto event for an entity that can't pathfind");
292 continue;
293 };
294
295 if event.goal.success(BlockPos::from(position)) {
296 pathfinder.goal = None;
298 pathfinder.successors_fn = None;
299 pathfinder.is_calculating = false;
300 debug!("already at goal, not pathfinding");
301 continue;
302 }
303
304 pathfinder.goal = Some(event.goal.clone());
306 pathfinder.successors_fn = Some(event.successors_fn);
307 pathfinder.is_calculating = true;
308 pathfinder.allow_mining = event.allow_mining;
309 pathfinder.min_timeout = Some(event.min_timeout);
310 pathfinder.max_timeout = Some(event.max_timeout);
311
312 let start = if let Some(executing_path) = executing_path
313 && let Some(final_node) = executing_path.path.back()
314 {
315 executing_path.path.get(50).unwrap_or(final_node).target
317 } else {
318 BlockPos::from(position)
319 };
320
321 if start == BlockPos::from(position) {
322 info!("got goto {:?}, starting from {start:?}", event.goal);
323 } else {
324 info!(
325 "got goto {:?}, starting from {start:?} (currently at {:?})",
326 event.goal,
327 BlockPos::from(position)
328 );
329 }
330
331 let successors_fn: moves::SuccessorsFn = event.successors_fn;
332
333 let world_lock = instance_container
334 .get(instance_name)
335 .expect("Entity tried to pathfind but the entity isn't in a valid world");
336
337 let goal = event.goal.clone();
338 let entity = event.entity;
339
340 let goto_id_atomic = pathfinder.goto_id.clone();
341
342 let allow_mining = event.allow_mining;
343 let mining_cache = MiningCache::new(if allow_mining {
344 Some(inventory.inventory_menu.clone())
345 } else {
346 None
347 });
348
349 let min_timeout = event.min_timeout;
350 let max_timeout = event.max_timeout;
351
352 let task = thread_pool.spawn(async move {
353 calculate_path(CalculatePathOpts {
354 entity,
355 start,
356 goal,
357 successors_fn,
358 world_lock,
359 goto_id_atomic,
360 allow_mining,
361 mining_cache,
362 min_timeout,
363 max_timeout,
364 })
365 });
366
367 commands.entity(event.entity).insert(ComputePath(task));
368 }
369}
370
371pub struct CalculatePathOpts {
372 pub entity: Entity,
373 pub start: BlockPos,
374 pub goal: Arc<dyn Goal>,
375 pub successors_fn: SuccessorsFn,
376 pub world_lock: Arc<RwLock<azalea_world::Instance>>,
377 pub goto_id_atomic: Arc<AtomicUsize>,
378 pub allow_mining: bool,
379 pub mining_cache: MiningCache,
380 pub min_timeout: PathfinderTimeout,
382 pub max_timeout: PathfinderTimeout,
383}
384
385pub fn calculate_path(opts: CalculatePathOpts) -> Option<PathFoundEvent> {
394 debug!("start: {:?}", opts.start);
395
396 let goto_id = opts.goto_id_atomic.fetch_add(1, atomic::Ordering::SeqCst) + 1;
397
398 let origin = opts.start;
399 let cached_world = CachedWorld::new(opts.world_lock, origin);
400 let successors = |pos: RelBlockPos| {
401 call_successors_fn(&cached_world, &opts.mining_cache, opts.successors_fn, pos)
402 };
403
404 let start_time = Instant::now();
405
406 let astar::Path {
407 movements,
408 is_partial,
409 } = a_star(
410 RelBlockPos::get_origin(origin),
411 |n| opts.goal.heuristic(n.apply(origin)),
412 successors,
413 |n| opts.goal.success(n.apply(origin)),
414 opts.min_timeout,
415 opts.max_timeout,
416 );
417 let end_time = Instant::now();
418 debug!("partial: {is_partial:?}");
419 let duration = end_time - start_time;
420 if is_partial {
421 if movements.is_empty() {
422 info!("Pathfinder took {duration:?} (empty path)");
423 } else {
424 info!("Pathfinder took {duration:?} (incomplete path)");
425 }
426 thread::sleep(Duration::from_millis(100));
428 } else {
429 info!("Pathfinder took {duration:?}");
430 }
431
432 debug!("Path:");
433 for movement in &movements {
434 debug!(" {}", movement.target.apply(origin));
435 }
436
437 let path = movements.into_iter().collect::<VecDeque<_>>();
438
439 let goto_id_now = opts.goto_id_atomic.load(atomic::Ordering::SeqCst);
440 if goto_id != goto_id_now {
441 warn!("finished calculating a path, but it's outdated");
443 return None;
444 }
445
446 if path.is_empty() && is_partial {
447 debug!("this path is empty, we might be stuck :(");
448 }
449
450 let mapped_path = path
452 .into_iter()
453 .map(|movement| astar::Movement {
454 target: movement.target.apply(origin),
455 data: movement.data,
456 })
457 .collect();
458
459 Some(PathFoundEvent {
460 entity: opts.entity,
461 start: opts.start,
462 path: Some(mapped_path),
463 is_partial,
464 successors_fn: opts.successors_fn,
465 allow_mining: opts.allow_mining,
466 })
467}
468
469pub fn handle_tasks(
471 mut commands: Commands,
472 mut transform_tasks: Query<(Entity, &mut ComputePath)>,
473 mut path_found_events: EventWriter<PathFoundEvent>,
474) {
475 for (entity, mut task) in &mut transform_tasks {
476 if let Some(optional_path_found_event) = future::block_on(future::poll_once(&mut task.0)) {
477 if let Some(path_found_event) = optional_path_found_event {
478 path_found_events.write(path_found_event);
479 }
480
481 commands.entity(entity).remove::<ComputePath>();
483 }
484 }
485}
486
487pub fn path_found_listener(
489 mut events: EventReader<PathFoundEvent>,
490 mut query: Query<(
491 &mut Pathfinder,
492 Option<&mut ExecutingPath>,
493 &InstanceName,
494 &Inventory,
495 )>,
496 instance_container: Res<InstanceContainer>,
497 mut commands: Commands,
498) {
499 for event in events.read() {
500 let (mut pathfinder, executing_path, instance_name, inventory) = query
501 .get_mut(event.entity)
502 .expect("Path found for an entity that doesn't have a pathfinder");
503 if let Some(path) = &event.path {
504 if let Some(mut executing_path) = executing_path {
505 let mut new_path = VecDeque::new();
506
507 if let Some(last_node_of_current_path) = executing_path.path.back() {
510 let world_lock = instance_container
511 .get(instance_name)
512 .expect("Entity tried to pathfind but the entity isn't in a valid world");
513 let origin = event.start;
514 let successors_fn: moves::SuccessorsFn = event.successors_fn;
515 let cached_world = CachedWorld::new(world_lock, origin);
516 let mining_cache = MiningCache::new(if event.allow_mining {
517 Some(inventory.inventory_menu.clone())
518 } else {
519 None
520 });
521 let successors = |pos: RelBlockPos| {
522 call_successors_fn(&cached_world, &mining_cache, successors_fn, pos)
523 };
524
525 if let Some(first_node_of_new_path) = path.front() {
526 let last_target_of_current_path =
527 RelBlockPos::from_origin(origin, last_node_of_current_path.target);
528 let first_target_of_new_path =
529 RelBlockPos::from_origin(origin, first_node_of_new_path.target);
530
531 if successors(last_target_of_current_path)
532 .iter()
533 .any(|edge| edge.movement.target == first_target_of_new_path)
534 {
535 debug!("combining old and new paths");
536 debug!(
537 "old path: {:?}",
538 executing_path.path.iter().collect::<Vec<_>>()
539 );
540 debug!("new path: {:?}", path.iter().take(10).collect::<Vec<_>>());
541 new_path.extend(executing_path.path.iter().cloned());
542 }
543 } else {
544 new_path.extend(executing_path.path.iter().cloned());
545 }
546 }
547
548 new_path.extend(path.to_owned());
549
550 debug!(
551 "set queued path to {:?}",
552 new_path.iter().take(10).collect::<Vec<_>>()
553 );
554 executing_path.queued_path = Some(new_path);
555 executing_path.is_path_partial = event.is_partial;
556 } else if path.is_empty() {
557 debug!("calculated path is empty, so didn't add ExecutingPath");
558 } else {
559 commands.entity(event.entity).insert(ExecutingPath {
560 path: path.to_owned(),
561 queued_path: None,
562 last_reached_node: event.start,
563 last_node_reached_at: Instant::now(),
564 is_path_partial: event.is_partial,
565 });
566 debug!("set path to {:?}", path.iter().take(10).collect::<Vec<_>>());
567 debug!("partial: {}", event.is_partial);
568 }
569 } else {
570 error!("No path found");
571 if let Some(mut executing_path) = executing_path {
572 executing_path.queued_path = Some(VecDeque::new());
574 } else {
575 }
577 }
578 pathfinder.is_calculating = false;
579 }
580}
581
582#[allow(clippy::type_complexity)]
583pub fn timeout_movement(
584 mut query: Query<(
585 Entity,
586 &mut Pathfinder,
587 &mut ExecutingPath,
588 &Position,
589 Option<&Mining>,
590 &InstanceName,
591 &Inventory,
592 )>,
593 instance_container: Res<InstanceContainer>,
594) {
595 for (entity, mut pathfinder, mut executing_path, position, mining, instance_name, inventory) in
596 &mut query
597 {
598 if let Some(mining) = mining {
600 if mining.pos.distance_squared_to(&BlockPos::from(position)) < 6_i32.pow(2) {
602 executing_path.last_node_reached_at = Instant::now();
605 continue;
606 }
607 }
608
609 if executing_path.last_node_reached_at.elapsed() > Duration::from_secs(2)
610 && !pathfinder.is_calculating
611 && !executing_path.path.is_empty()
612 {
613 warn!("pathfinder timeout, trying to patch path");
614 executing_path.queued_path = None;
615 executing_path.last_reached_node = BlockPos::from(position);
616
617 let world_lock = instance_container
618 .get(instance_name)
619 .expect("Entity tried to pathfind but the entity isn't in a valid world");
620 let successors_fn: moves::SuccessorsFn = pathfinder.successors_fn.unwrap();
621
622 patch_path(
626 0..=cmp::min(20, executing_path.path.len() - 1),
627 &mut executing_path,
628 &mut pathfinder,
629 inventory,
630 entity,
631 successors_fn,
632 world_lock,
633 );
634 executing_path.last_node_reached_at = Instant::now();
636 }
637 }
638}
639
640pub fn check_node_reached(
641 mut query: Query<(
642 Entity,
643 &mut Pathfinder,
644 &mut ExecutingPath,
645 &Position,
646 &Physics,
647 )>,
648 mut walk_events: EventWriter<StartWalkEvent>,
649 mut commands: Commands,
650) {
651 for (entity, mut pathfinder, mut executing_path, position, physics) in &mut query {
652 'skip: loop {
653 for (i, movement) in executing_path
658 .path
659 .clone()
660 .into_iter()
661 .enumerate()
662 .take(20)
663 .rev()
664 {
665 let is_reached_ctx = IsReachedCtx {
666 target: movement.target,
667 start: executing_path.last_reached_node,
668 position: **position,
669 physics,
670 };
671 let extra_strict_if_last = if i == executing_path.path.len() - 1 {
672 let x_difference_from_center = position.x - (movement.target.x as f64 + 0.5);
673 let z_difference_from_center = position.z - (movement.target.z as f64 + 0.5);
674 physics.on_ground()
676 && BlockPos::from(position) == movement.target
677 && (x_difference_from_center + physics.velocity.x).abs() < 0.2
680 && (z_difference_from_center + physics.velocity.z).abs() < 0.2
681 } else {
682 true
683 };
684 if (movement.data.is_reached)(is_reached_ctx) && extra_strict_if_last {
685 executing_path.path = executing_path.path.split_off(i + 1);
686 executing_path.last_reached_node = movement.target;
687 executing_path.last_node_reached_at = Instant::now();
688 trace!("reached node {}", movement.target);
689
690 if let Some(new_path) = executing_path.queued_path.take() {
691 debug!(
692 "swapped path to {:?}",
693 new_path.iter().take(10).collect::<Vec<_>>()
694 );
695 executing_path.path = new_path;
696
697 if executing_path.path.is_empty() {
698 info!("the path we just swapped to was empty, so reached end of path");
699 walk_events.write(StartWalkEvent {
700 entity,
701 direction: WalkDirection::None,
702 });
703 commands.entity(entity).remove::<ExecutingPath>();
704 break;
705 }
706
707 continue 'skip;
709 }
710
711 if executing_path.path.is_empty() {
712 debug!("pathfinder path is now empty");
713 walk_events.write(StartWalkEvent {
714 entity,
715 direction: WalkDirection::None,
716 });
717 commands.entity(entity).remove::<ExecutingPath>();
718 if let Some(goal) = pathfinder.goal.clone() {
719 if goal.success(movement.target) {
720 info!("goal was reached!");
721 pathfinder.goal = None;
722 pathfinder.successors_fn = None;
723 }
724 }
725 }
726
727 break;
728 }
729 }
730 break;
731 }
732 }
733}
734
735pub fn check_for_path_obstruction(
736 mut query: Query<(
737 Entity,
738 &mut Pathfinder,
739 &mut ExecutingPath,
740 &InstanceName,
741 &Inventory,
742 )>,
743 instance_container: Res<InstanceContainer>,
744) {
745 for (entity, mut pathfinder, mut executing_path, instance_name, inventory) in &mut query {
746 let Some(successors_fn) = pathfinder.successors_fn else {
747 continue;
748 };
749
750 let world_lock = instance_container
751 .get(instance_name)
752 .expect("Entity tried to pathfind but the entity isn't in a valid world");
753
754 let origin = executing_path.last_reached_node;
756 let cached_world = CachedWorld::new(world_lock, origin);
757 let mining_cache = MiningCache::new(if pathfinder.allow_mining {
758 Some(inventory.inventory_menu.clone())
759 } else {
760 None
761 });
762 let successors =
763 |pos: RelBlockPos| call_successors_fn(&cached_world, &mining_cache, successors_fn, pos);
764
765 if let Some(obstructed_index) = check_path_obstructed(
766 origin,
767 RelBlockPos::from_origin(origin, executing_path.last_reached_node),
768 &executing_path.path,
769 successors,
770 ) {
771 warn!(
772 "path obstructed at index {obstructed_index} (starting at {:?}, path: {:?})",
773 executing_path.last_reached_node, executing_path.path
774 );
775 if obstructed_index + 5 > executing_path.path.len() {
778 debug!(
779 "obstruction is near the end of the path, truncating and marking path as partial"
780 );
781 executing_path.path.truncate(obstructed_index);
782 executing_path.is_path_partial = true;
783 continue;
784 }
785
786 let Some(successors_fn) = pathfinder.successors_fn else {
787 error!("got PatchExecutingPathEvent but the bot has no successors_fn");
788 continue;
789 };
790
791 let world_lock = instance_container
792 .get(instance_name)
793 .expect("Entity tried to pathfind but the entity isn't in a valid world");
794
795 let patch_end_index = cmp::min(obstructed_index + 20, executing_path.path.len() - 1);
797
798 patch_path(
799 obstructed_index..=patch_end_index,
800 &mut executing_path,
801 &mut pathfinder,
802 inventory,
803 entity,
804 successors_fn,
805 world_lock,
806 );
807 }
808 }
809}
810
811fn patch_path(
817 patch_nodes: RangeInclusive<usize>,
818 executing_path: &mut ExecutingPath,
819 pathfinder: &mut Pathfinder,
820 inventory: &Inventory,
821 entity: Entity,
822 successors_fn: SuccessorsFn,
823 world_lock: Arc<RwLock<azalea_world::Instance>>,
824) {
825 let patch_start = if *patch_nodes.start() == 0 {
826 executing_path.last_reached_node
827 } else {
828 executing_path.path[*patch_nodes.start() - 1].target
829 };
830
831 let patch_end = executing_path.path[*patch_nodes.end()].target;
832
833 let goal = Arc::new(BlockPosGoal(patch_end));
836
837 let goto_id_atomic = pathfinder.goto_id.clone();
838
839 let allow_mining = pathfinder.allow_mining;
840 let mining_cache = MiningCache::new(if allow_mining {
841 Some(inventory.inventory_menu.clone())
842 } else {
843 None
844 });
845
846 let path_found_event = calculate_path(CalculatePathOpts {
848 entity,
849 start: patch_start,
850 goal,
851 successors_fn,
852 world_lock,
853 goto_id_atomic,
854 allow_mining,
855 mining_cache,
856 min_timeout: PathfinderTimeout::Nodes(10_000),
857 max_timeout: PathfinderTimeout::Nodes(10_000),
858 });
859
860 pathfinder.is_calculating = false;
862
863 debug!("obstruction patch: {path_found_event:?}");
864
865 let mut new_path = VecDeque::new();
866 if *patch_nodes.start() > 0 {
867 new_path.extend(
868 executing_path
869 .path
870 .iter()
871 .take(*patch_nodes.start())
872 .cloned(),
873 );
874 }
875
876 let mut is_patch_complete = false;
877 if let Some(path_found_event) = path_found_event {
878 if let Some(found_path_patch) = path_found_event.path {
879 if !found_path_patch.is_empty() {
880 new_path.extend(found_path_patch);
881
882 if !path_found_event.is_partial {
883 new_path.extend(executing_path.path.iter().skip(*patch_nodes.end()).cloned());
884 is_patch_complete = true;
885 debug!("the patch is not partial :)");
886 } else {
887 debug!("the patch is partial, throwing away rest of path :(");
888 }
889 }
890 }
891 } else {
892 }
894
895 executing_path.path = new_path;
896 if !is_patch_complete {
897 executing_path.is_path_partial = true;
898 }
899}
900
901pub fn recalculate_near_end_of_path(
902 mut query: Query<(Entity, &mut Pathfinder, &mut ExecutingPath)>,
903 mut walk_events: EventWriter<StartWalkEvent>,
904 mut goto_events: EventWriter<GotoEvent>,
905 mut commands: Commands,
906) {
907 for (entity, mut pathfinder, mut executing_path) in &mut query {
908 let Some(successors_fn) = pathfinder.successors_fn else {
909 continue;
910 };
911
912 if (executing_path.path.len() == 50 || executing_path.path.len() < 5)
914 && !pathfinder.is_calculating
915 && executing_path.is_path_partial
916 {
917 match pathfinder.goal.as_ref().cloned() {
918 Some(goal) => {
919 debug!("Recalculating path because it's empty or ends soon");
920 debug!(
921 "recalculate_near_end_of_path executing_path.is_path_partial: {}",
922 executing_path.is_path_partial
923 );
924 goto_events.write(GotoEvent {
925 entity,
926 goal,
927 successors_fn,
928 allow_mining: pathfinder.allow_mining,
929 min_timeout: if executing_path.path.len() == 50 {
930 PathfinderTimeout::Time(Duration::from_secs(5))
934 } else {
935 PathfinderTimeout::Time(Duration::from_secs(1))
936 },
937 max_timeout: pathfinder.max_timeout.expect("max_timeout should be set"),
938 });
939 pathfinder.is_calculating = true;
940
941 if executing_path.path.is_empty() {
942 if let Some(new_path) = executing_path.queued_path.take() {
943 executing_path.path = new_path;
944 if executing_path.path.is_empty() {
945 info!(
946 "the path we just swapped to was empty, so reached end of path"
947 );
948 walk_events.write(StartWalkEvent {
949 entity,
950 direction: WalkDirection::None,
951 });
952 commands.entity(entity).remove::<ExecutingPath>();
953 break;
954 }
955 } else {
956 walk_events.write(StartWalkEvent {
957 entity,
958 direction: WalkDirection::None,
959 });
960 commands.entity(entity).remove::<ExecutingPath>();
961 }
962 }
963 }
964 _ => {
965 if executing_path.path.is_empty() {
966 walk_events.write(StartWalkEvent {
968 entity,
969 direction: WalkDirection::None,
970 });
971 }
972 }
973 }
974 }
975 }
976}
977
978#[allow(clippy::type_complexity)]
979pub fn tick_execute_path(
980 mut query: Query<(
981 Entity,
982 &mut ExecutingPath,
983 &Position,
984 &Physics,
985 Option<&Mining>,
986 &InstanceHolder,
987 &Inventory,
988 )>,
989 mut look_at_events: EventWriter<LookAtEvent>,
990 mut sprint_events: EventWriter<StartSprintEvent>,
991 mut walk_events: EventWriter<StartWalkEvent>,
992 mut jump_events: EventWriter<JumpEvent>,
993 mut start_mining_events: EventWriter<StartMiningBlockEvent>,
994 mut set_selected_hotbar_slot_events: EventWriter<SetSelectedHotbarSlotEvent>,
995) {
996 for (entity, executing_path, position, physics, mining, instance_holder, inventory_component) in
997 &mut query
998 {
999 if let Some(movement) = executing_path.path.front() {
1000 let ctx = ExecuteCtx {
1001 entity,
1002 target: movement.target,
1003 position: **position,
1004 start: executing_path.last_reached_node,
1005 physics,
1006 is_currently_mining: mining.is_some(),
1007 instance: instance_holder.instance.clone(),
1008 menu: inventory_component.inventory_menu.clone(),
1009
1010 look_at_events: &mut look_at_events,
1011 sprint_events: &mut sprint_events,
1012 walk_events: &mut walk_events,
1013 jump_events: &mut jump_events,
1014 start_mining_events: &mut start_mining_events,
1015 set_selected_hotbar_slot_events: &mut set_selected_hotbar_slot_events,
1016 };
1017 trace!(
1018 "executing move, position: {}, last_reached_node: {}",
1019 **position, executing_path.last_reached_node
1020 );
1021 (movement.data.execute)(ctx);
1022 }
1023 }
1024}
1025
1026pub fn recalculate_if_has_goal_but_no_path(
1027 mut query: Query<(Entity, &mut Pathfinder), Without<ExecutingPath>>,
1028 mut goto_events: EventWriter<GotoEvent>,
1029) {
1030 for (entity, mut pathfinder) in &mut query {
1031 if pathfinder.goal.is_some() && !pathfinder.is_calculating {
1032 if let Some(goal) = pathfinder.goal.as_ref().cloned() {
1033 debug!("Recalculating path because it has a goal but no ExecutingPath");
1034 goto_events.write(GotoEvent {
1035 entity,
1036 goal,
1037 successors_fn: pathfinder.successors_fn.unwrap(),
1038 allow_mining: pathfinder.allow_mining,
1039 min_timeout: pathfinder.min_timeout.expect("min_timeout should be set"),
1040 max_timeout: pathfinder.max_timeout.expect("max_timeout should be set"),
1041 });
1042 pathfinder.is_calculating = true;
1043 }
1044 }
1045 }
1046}
1047
1048#[derive(Event)]
1049pub struct StopPathfindingEvent {
1050 pub entity: Entity,
1051 pub force: bool,
1055}
1056
1057pub fn handle_stop_pathfinding_event(
1058 mut events: EventReader<StopPathfindingEvent>,
1059 mut query: Query<(&mut Pathfinder, &mut ExecutingPath)>,
1060 mut walk_events: EventWriter<StartWalkEvent>,
1061 mut commands: Commands,
1062) {
1063 for event in events.read() {
1064 commands.entity(event.entity).remove::<ComputePath>();
1066
1067 let Ok((mut pathfinder, mut executing_path)) = query.get_mut(event.entity) else {
1068 continue;
1069 };
1070 pathfinder.goal = None;
1071 if event.force {
1072 executing_path.path.clear();
1073 executing_path.queued_path = None;
1074 } else {
1075 executing_path.queued_path = Some(VecDeque::new());
1077 executing_path.is_path_partial = false;
1079 }
1080
1081 if executing_path.path.is_empty() {
1082 walk_events.write(StartWalkEvent {
1083 entity: event.entity,
1084 direction: WalkDirection::None,
1085 });
1086 commands.entity(event.entity).remove::<ExecutingPath>();
1087 }
1088 }
1089}
1090
1091pub fn stop_pathfinding_on_instance_change(
1092 mut query: Query<(Entity, &mut ExecutingPath), Changed<InstanceName>>,
1093 mut stop_pathfinding_events: EventWriter<StopPathfindingEvent>,
1094) {
1095 for (entity, mut executing_path) in &mut query {
1096 if !executing_path.path.is_empty() {
1097 debug!("instance changed, clearing path");
1098 executing_path.path.clear();
1099 stop_pathfinding_events.write(StopPathfindingEvent {
1100 entity,
1101 force: true,
1102 });
1103 }
1104 }
1105}
1106
1107pub fn check_path_obstructed<SuccessorsFn>(
1110 origin: BlockPos,
1111 mut current_position: RelBlockPos,
1112 path: &VecDeque<astar::Movement<BlockPos, moves::MoveData>>,
1113 successors_fn: SuccessorsFn,
1114) -> Option<usize>
1115where
1116 SuccessorsFn: Fn(RelBlockPos) -> Vec<astar::Edge<RelBlockPos, moves::MoveData>>,
1117{
1118 for (i, movement) in path.iter().enumerate() {
1119 let movement_target = RelBlockPos::from_origin(origin, movement.target);
1120
1121 let mut found_obstruction = false;
1122 for edge in successors_fn(current_position) {
1123 if edge.movement.target == movement_target {
1124 current_position = movement_target;
1125 found_obstruction = false;
1126 break;
1127 } else {
1128 found_obstruction = true;
1129 }
1130 }
1131 if found_obstruction {
1132 return Some(i);
1133 }
1134 }
1135
1136 None
1137}
1138
1139pub fn call_successors_fn(
1140 cached_world: &CachedWorld,
1141 mining_cache: &MiningCache,
1142 successors_fn: SuccessorsFn,
1143 pos: RelBlockPos,
1144) -> Vec<astar::Edge<RelBlockPos, moves::MoveData>> {
1145 let mut edges = Vec::with_capacity(16);
1146 let mut ctx = PathfinderCtx {
1147 edges: &mut edges,
1148 world: cached_world,
1149 mining_cache,
1150 };
1151 successors_fn(&mut ctx, pos);
1152 edges
1153}
1154
1155#[cfg(test)]
1156mod tests {
1157 use std::{
1158 collections::HashSet,
1159 sync::Arc,
1160 time::{Duration, Instant},
1161 };
1162
1163 use azalea_core::position::{BlockPos, ChunkPos, Vec3};
1164 use azalea_world::{Chunk, ChunkStorage, PartialChunkStorage};
1165
1166 use super::{
1167 GotoEvent,
1168 astar::PathfinderTimeout,
1169 goals::BlockPosGoal,
1170 moves,
1171 simulation::{SimulatedPlayerBundle, Simulation},
1172 };
1173
1174 fn setup_blockposgoal_simulation(
1175 partial_chunks: &mut PartialChunkStorage,
1176 start_pos: BlockPos,
1177 end_pos: BlockPos,
1178 solid_blocks: Vec<BlockPos>,
1179 ) -> Simulation {
1180 let mut simulation = setup_simulation_world(partial_chunks, start_pos, solid_blocks);
1181
1182 simulation.app.world_mut().send_event(GotoEvent {
1190 entity: simulation.entity,
1191 goal: Arc::new(BlockPosGoal(end_pos)),
1192 successors_fn: moves::default_move,
1193 allow_mining: false,
1194 min_timeout: PathfinderTimeout::Nodes(1_000_000),
1195 max_timeout: PathfinderTimeout::Nodes(5_000_000),
1196 });
1197 simulation
1198 }
1199
1200 fn setup_simulation_world(
1201 partial_chunks: &mut PartialChunkStorage,
1202 start_pos: BlockPos,
1203 solid_blocks: Vec<BlockPos>,
1204 ) -> Simulation {
1205 let mut chunk_positions = HashSet::new();
1206 for block_pos in &solid_blocks {
1207 chunk_positions.insert(ChunkPos::from(block_pos));
1208 }
1209
1210 let mut chunks = ChunkStorage::default();
1211 for chunk_pos in chunk_positions {
1212 partial_chunks.set(&chunk_pos, Some(Chunk::default()), &mut chunks);
1213 }
1214 for block_pos in solid_blocks {
1215 chunks.set_block_state(&block_pos, azalea_registry::Block::Stone.into());
1216 }
1217 let player = SimulatedPlayerBundle::new(Vec3::new(
1218 start_pos.x as f64 + 0.5,
1219 start_pos.y as f64,
1220 start_pos.z as f64 + 0.5,
1221 ));
1222 Simulation::new(chunks, player)
1223 }
1224
1225 pub fn assert_simulation_reaches(simulation: &mut Simulation, ticks: usize, end_pos: BlockPos) {
1226 wait_until_bot_starts_moving(simulation);
1227 for _ in 0..ticks {
1228 simulation.tick();
1229 }
1230 assert_eq!(BlockPos::from(simulation.position()), end_pos);
1231 }
1232
1233 pub fn wait_until_bot_starts_moving(simulation: &mut Simulation) {
1234 let start_pos = simulation.position();
1235 let start_time = Instant::now();
1236 while simulation.position() == start_pos
1237 && !simulation.is_mining()
1238 && start_time.elapsed() < Duration::from_millis(500)
1239 {
1240 simulation.tick();
1241 std::thread::yield_now();
1242 }
1243 }
1244
1245 #[test]
1246 fn test_simple_forward() {
1247 let mut partial_chunks = PartialChunkStorage::default();
1248 let mut simulation = setup_blockposgoal_simulation(
1249 &mut partial_chunks,
1250 BlockPos::new(0, 71, 0),
1251 BlockPos::new(0, 71, 1),
1252 vec![BlockPos::new(0, 70, 0), BlockPos::new(0, 70, 1)],
1253 );
1254 assert_simulation_reaches(&mut simulation, 20, BlockPos::new(0, 71, 1));
1255 }
1256
1257 #[test]
1258 fn test_double_diagonal_with_walls() {
1259 let mut partial_chunks = PartialChunkStorage::default();
1260 let mut simulation = setup_blockposgoal_simulation(
1261 &mut partial_chunks,
1262 BlockPos::new(0, 71, 0),
1263 BlockPos::new(2, 71, 2),
1264 vec![
1265 BlockPos::new(0, 70, 0),
1266 BlockPos::new(1, 70, 1),
1267 BlockPos::new(2, 70, 2),
1268 BlockPos::new(1, 72, 0),
1269 BlockPos::new(2, 72, 1),
1270 ],
1271 );
1272 assert_simulation_reaches(&mut simulation, 30, BlockPos::new(2, 71, 2));
1273 }
1274
1275 #[test]
1276 fn test_jump_with_sideways_momentum() {
1277 let mut partial_chunks = PartialChunkStorage::default();
1278 let mut simulation = setup_blockposgoal_simulation(
1279 &mut partial_chunks,
1280 BlockPos::new(0, 71, 3),
1281 BlockPos::new(5, 76, 0),
1282 vec![
1283 BlockPos::new(0, 70, 3),
1284 BlockPos::new(0, 70, 2),
1285 BlockPos::new(0, 70, 1),
1286 BlockPos::new(0, 70, 0),
1287 BlockPos::new(1, 71, 0),
1288 BlockPos::new(2, 72, 0),
1289 BlockPos::new(3, 73, 0),
1290 BlockPos::new(4, 74, 0),
1291 BlockPos::new(5, 75, 0),
1292 ],
1293 );
1294 assert_simulation_reaches(&mut simulation, 120, BlockPos::new(5, 76, 0));
1295 }
1296
1297 #[test]
1298 fn test_parkour_2_block_gap() {
1299 let mut partial_chunks = PartialChunkStorage::default();
1300 let mut simulation = setup_blockposgoal_simulation(
1301 &mut partial_chunks,
1302 BlockPos::new(0, 71, 0),
1303 BlockPos::new(0, 71, 3),
1304 vec![BlockPos::new(0, 70, 0), BlockPos::new(0, 70, 3)],
1305 );
1306 assert_simulation_reaches(&mut simulation, 40, BlockPos::new(0, 71, 3));
1307 }
1308
1309 #[test]
1310 fn test_descend_and_parkour_2_block_gap() {
1311 let mut partial_chunks = PartialChunkStorage::default();
1312 let mut simulation = setup_blockposgoal_simulation(
1313 &mut partial_chunks,
1314 BlockPos::new(0, 71, 0),
1315 BlockPos::new(3, 67, 4),
1316 vec![
1317 BlockPos::new(0, 70, 0),
1318 BlockPos::new(0, 69, 1),
1319 BlockPos::new(0, 68, 2),
1320 BlockPos::new(0, 67, 3),
1321 BlockPos::new(0, 66, 4),
1322 BlockPos::new(3, 66, 4),
1323 ],
1324 );
1325 assert_simulation_reaches(&mut simulation, 100, BlockPos::new(3, 67, 4));
1326 }
1327
1328 #[test]
1329 fn test_small_descend_and_parkour_2_block_gap() {
1330 let mut partial_chunks = PartialChunkStorage::default();
1331 let mut simulation = setup_blockposgoal_simulation(
1332 &mut partial_chunks,
1333 BlockPos::new(0, 71, 0),
1334 BlockPos::new(0, 70, 5),
1335 vec![
1336 BlockPos::new(0, 70, 0),
1337 BlockPos::new(0, 70, 1),
1338 BlockPos::new(0, 69, 2),
1339 BlockPos::new(0, 69, 5),
1340 ],
1341 );
1342 assert_simulation_reaches(&mut simulation, 40, BlockPos::new(0, 70, 5));
1343 }
1344
1345 #[test]
1346 fn test_quickly_descend() {
1347 let mut partial_chunks = PartialChunkStorage::default();
1348 let mut simulation = setup_blockposgoal_simulation(
1349 &mut partial_chunks,
1350 BlockPos::new(0, 71, 0),
1351 BlockPos::new(0, 68, 3),
1352 vec![
1353 BlockPos::new(0, 70, 0),
1354 BlockPos::new(0, 69, 1),
1355 BlockPos::new(0, 68, 2),
1356 BlockPos::new(0, 67, 3),
1357 ],
1358 );
1359 assert_simulation_reaches(&mut simulation, 60, BlockPos::new(0, 68, 3));
1360 }
1361
1362 #[test]
1363 fn test_2_gap_ascend_thrice() {
1364 let mut partial_chunks = PartialChunkStorage::default();
1365 let mut simulation = setup_blockposgoal_simulation(
1366 &mut partial_chunks,
1367 BlockPos::new(0, 71, 0),
1368 BlockPos::new(3, 74, 0),
1369 vec![
1370 BlockPos::new(0, 70, 0),
1371 BlockPos::new(0, 71, 3),
1372 BlockPos::new(3, 72, 3),
1373 BlockPos::new(3, 73, 0),
1374 ],
1375 );
1376 assert_simulation_reaches(&mut simulation, 60, BlockPos::new(3, 74, 0));
1377 }
1378
1379 #[test]
1380 fn test_consecutive_3_gap_parkour() {
1381 let mut partial_chunks = PartialChunkStorage::default();
1382 let mut simulation = setup_blockposgoal_simulation(
1383 &mut partial_chunks,
1384 BlockPos::new(0, 71, 0),
1385 BlockPos::new(4, 71, 12),
1386 vec![
1387 BlockPos::new(0, 70, 0),
1388 BlockPos::new(0, 70, 4),
1389 BlockPos::new(0, 70, 8),
1390 BlockPos::new(0, 70, 12),
1391 BlockPos::new(4, 70, 12),
1392 ],
1393 );
1394 assert_simulation_reaches(&mut simulation, 80, BlockPos::new(4, 71, 12));
1395 }
1396
1397 #[test]
1398 fn test_jumps_with_more_sideways_momentum() {
1399 let mut partial_chunks = PartialChunkStorage::default();
1400 let mut simulation = setup_blockposgoal_simulation(
1401 &mut partial_chunks,
1402 BlockPos::new(0, 71, 0),
1403 BlockPos::new(4, 74, 9),
1404 vec![
1405 BlockPos::new(0, 70, 0),
1406 BlockPos::new(0, 70, 1),
1407 BlockPos::new(0, 70, 2),
1408 BlockPos::new(0, 71, 3),
1409 BlockPos::new(0, 72, 6),
1410 BlockPos::new(0, 73, 9),
1411 BlockPos::new(2, 73, 9),
1413 BlockPos::new(4, 73, 9),
1414 ],
1415 );
1416 assert_simulation_reaches(&mut simulation, 80, BlockPos::new(4, 74, 9));
1417 }
1418}