azalea/pathfinder/
mod.rs

1//! A pathfinding plugin to make bots able to traverse the world.
2//!
3//! Much of this code is based on [Baritone](https://github.com/cabaletta/baritone).
4
5pub mod astar;
6pub mod costs;
7pub mod custom_state;
8pub mod debug;
9pub mod goals;
10mod goto_event;
11pub mod mining;
12pub mod moves;
13pub mod rel_block_pos;
14pub mod simulation;
15#[cfg(test)]
16mod tests;
17pub mod world;
18
19use std::{
20    cmp,
21    collections::VecDeque,
22    ops::RangeInclusive,
23    sync::{
24        Arc,
25        atomic::{self, AtomicUsize},
26    },
27    thread,
28    time::{Duration, Instant},
29};
30
31use astar::{Edge, PathfinderTimeout};
32use azalea_client::{
33    StartSprintEvent, StartWalkEvent,
34    inventory::{Inventory, InventorySet, SetSelectedHotbarSlotEvent},
35    local_player::InstanceHolder,
36    mining::{Mining, MiningSet, StartMiningBlockEvent},
37    movement::MoveEventsSet,
38};
39use azalea_core::{position::BlockPos, tick::GameTick};
40use azalea_entity::{LocalEntity, Physics, Position, metadata::Player};
41use azalea_physics::PhysicsSet;
42use azalea_world::{InstanceContainer, InstanceName};
43use bevy_app::{PreUpdate, Update};
44use bevy_ecs::prelude::*;
45use bevy_tasks::{AsyncComputeTaskPool, Task};
46use custom_state::{CustomPathfinderState, CustomPathfinderStateRef};
47use futures_lite::future;
48use goals::BlockPosGoal;
49pub use goto_event::GotoEvent;
50use parking_lot::RwLock;
51use rel_block_pos::RelBlockPos;
52use tokio::sync::broadcast::error::RecvError;
53use tracing::{debug, error, info, trace, warn};
54
55use self::{
56    debug::debug_render_path_with_particles,
57    goals::Goal,
58    mining::MiningCache,
59    moves::{ExecuteCtx, IsReachedCtx, SuccessorsFn},
60};
61use crate::{
62    BotClientExt, WalkDirection,
63    app::{App, Plugin},
64    bot::{JumpEvent, LookAtEvent},
65    ecs::{
66        component::Component,
67        entity::Entity,
68        event::{EventReader, EventWriter},
69        query::{With, Without},
70        system::{Commands, Query, Res},
71    },
72    pathfinder::{astar::a_star, moves::PathfinderCtx, world::CachedWorld},
73};
74
75#[derive(Clone, Default)]
76pub struct PathfinderPlugin;
77impl Plugin for PathfinderPlugin {
78    fn build(&self, app: &mut App) {
79        app.add_event::<GotoEvent>()
80            .add_event::<PathFoundEvent>()
81            .add_event::<StopPathfindingEvent>()
82            .add_systems(
83                // putting systems in the GameTick schedule makes them run every Minecraft tick
84                // (every 50 milliseconds).
85                GameTick,
86                (
87                    timeout_movement,
88                    check_for_path_obstruction,
89                    check_node_reached,
90                    tick_execute_path,
91                    debug_render_path_with_particles,
92                    recalculate_near_end_of_path,
93                    recalculate_if_has_goal_but_no_path,
94                )
95                    .chain()
96                    .after(PhysicsSet)
97                    .after(azalea_client::movement::send_position)
98                    .after(MiningSet),
99            )
100            .add_systems(PreUpdate, add_default_pathfinder)
101            .add_systems(
102                Update,
103                (
104                    goto_listener,
105                    handle_tasks,
106                    stop_pathfinding_on_instance_change,
107                    path_found_listener,
108                    handle_stop_pathfinding_event,
109                )
110                    .chain()
111                    .before(MoveEventsSet)
112                    .before(InventorySet),
113            );
114    }
115}
116
117/// A component that makes this client able to pathfind.
118#[derive(Component, Default, Clone)]
119#[non_exhaustive]
120pub struct Pathfinder {
121    pub goal: Option<Arc<dyn Goal>>,
122    pub successors_fn: Option<SuccessorsFn>,
123    pub is_calculating: bool,
124    pub allow_mining: bool,
125    pub retry_on_no_path: bool,
126
127    pub min_timeout: Option<PathfinderTimeout>,
128    pub max_timeout: Option<PathfinderTimeout>,
129
130    pub goto_id: Arc<AtomicUsize>,
131}
132
133/// A component that's present on clients that are actively following a
134/// pathfinder path.
135#[derive(Component, Clone)]
136pub struct ExecutingPath {
137    pub path: VecDeque<astar::Edge<BlockPos, moves::MoveData>>,
138    pub queued_path: Option<VecDeque<astar::Edge<BlockPos, moves::MoveData>>>,
139    pub last_reached_node: BlockPos,
140    pub last_node_reached_at: Instant,
141    pub is_path_partial: bool,
142}
143
144#[derive(Event, Clone, Debug)]
145#[non_exhaustive]
146pub struct PathFoundEvent {
147    pub entity: Entity,
148    pub start: BlockPos,
149    pub path: Option<VecDeque<astar::Edge<BlockPos, moves::MoveData>>>,
150    pub is_partial: bool,
151    pub successors_fn: SuccessorsFn,
152    pub allow_mining: bool,
153}
154
155#[allow(clippy::type_complexity)]
156pub fn add_default_pathfinder(
157    mut commands: Commands,
158    mut query: Query<Entity, (Without<Pathfinder>, With<LocalEntity>, With<Player>)>,
159) {
160    for entity in &mut query {
161        commands.entity(entity).insert(Pathfinder::default());
162    }
163}
164
165pub trait PathfinderClientExt {
166    fn goto(&self, goal: impl Goal + 'static) -> impl Future<Output = ()>;
167    fn start_goto(&self, goal: impl Goal + 'static);
168    fn start_goto_without_mining(&self, goal: impl Goal + 'static);
169    fn stop_pathfinding(&self);
170    fn force_stop_pathfinding(&self);
171    fn wait_until_goto_target_reached(&self) -> impl Future<Output = ()>;
172    fn is_goto_target_reached(&self) -> bool;
173}
174
175impl PathfinderClientExt for azalea_client::Client {
176    /// Pathfind to the given goal and wait until either the target is reached
177    /// or the pathfinding is canceled.
178    ///
179    /// You can use [`Self::start_goto`] instead if you don't want to wait.
180    ///
181    /// ```
182    /// # use azalea::prelude::*;
183    /// # use azalea::{BlockPos, pathfinder::goals::BlockPosGoal};
184    /// # async fn example(bot: &Client) {
185    /// bot.goto(BlockPosGoal(BlockPos::new(0, 70, 0))).await;
186    /// # }
187    /// ```
188    async fn goto(&self, goal: impl Goal + 'static) {
189        self.start_goto(goal);
190        self.wait_until_goto_target_reached().await;
191    }
192
193    /// Start pathfinding to a given goal.
194    ///
195    /// ```
196    /// # use azalea::prelude::*;
197    /// # use azalea::{BlockPos, pathfinder::goals::BlockPosGoal};
198    /// # fn example(bot: &Client) {
199    /// bot.start_goto(BlockPosGoal(BlockPos::new(0, 70, 0)));
200    /// # }
201    /// ```
202    fn start_goto(&self, goal: impl Goal + 'static) {
203        self.ecs
204            .lock()
205            .send_event(GotoEvent::new(self.entity, goal));
206    }
207
208    /// Same as [`start_goto`](Self::start_goto). but the bot won't break any
209    /// blocks while executing the path.
210    fn start_goto_without_mining(&self, goal: impl Goal + 'static) {
211        self.ecs
212            .lock()
213            .send_event(GotoEvent::new(self.entity, goal).with_allow_mining(false));
214    }
215
216    /// Stop calculating a path, and stop moving once the current movement is
217    /// finished.
218    ///
219    /// This behavior exists to prevent the bot from taking damage if
220    /// `stop_pathfinding` was called while executing a parkour jump, but if
221    /// it's undesirable then you may want to consider using
222    /// [`Self::force_stop_pathfinding`] instead.
223    fn stop_pathfinding(&self) {
224        self.ecs.lock().send_event(StopPathfindingEvent {
225            entity: self.entity,
226            force: false,
227        });
228    }
229
230    /// Stop calculating a path and stop executing the current movement
231    /// immediately.
232    fn force_stop_pathfinding(&self) {
233        self.ecs.lock().send_event(StopPathfindingEvent {
234            entity: self.entity,
235            force: true,
236        });
237    }
238
239    /// Waits forever until the bot no longer has a pathfinder goal.
240    async fn wait_until_goto_target_reached(&self) {
241        // we do this to make sure the event got handled before we start checking
242        // is_goto_target_reached
243        self.wait_updates(1).await;
244
245        let mut tick_broadcaster = self.get_tick_broadcaster();
246        while !self.is_goto_target_reached() {
247            // check every tick
248            match tick_broadcaster.recv().await {
249                Ok(_) => (),
250                Err(RecvError::Closed) => return,
251                Err(err) => warn!("{err}"),
252            };
253        }
254    }
255
256    fn is_goto_target_reached(&self) -> bool {
257        self.map_get_component::<Pathfinder, _>(|p| p.goal.is_none() && !p.is_calculating)
258            .unwrap_or(true)
259    }
260}
261
262#[derive(Component)]
263pub struct ComputePath(Task<Option<PathFoundEvent>>);
264
265#[allow(clippy::type_complexity)]
266pub fn goto_listener(
267    mut commands: Commands,
268    mut events: EventReader<GotoEvent>,
269    mut query: Query<(
270        &mut Pathfinder,
271        Option<&ExecutingPath>,
272        &Position,
273        &InstanceName,
274        &Inventory,
275        Option<&CustomPathfinderState>,
276    )>,
277    instance_container: Res<InstanceContainer>,
278) {
279    let thread_pool = AsyncComputeTaskPool::get();
280
281    for event in events.read() {
282        let Ok((mut pathfinder, executing_path, position, instance_name, inventory, custom_state)) =
283            query.get_mut(event.entity)
284        else {
285            warn!("got goto event for an entity that can't pathfind");
286            continue;
287        };
288
289        if event.goal.success(BlockPos::from(position)) {
290            // we're already at the goal, nothing to do
291            pathfinder.goal = None;
292            pathfinder.successors_fn = None;
293            pathfinder.is_calculating = false;
294            debug!("already at goal, not pathfinding");
295            continue;
296        }
297
298        // we store the goal so it can be recalculated later if necessary
299        pathfinder.goal = Some(event.goal.clone());
300        pathfinder.successors_fn = Some(event.successors_fn);
301        pathfinder.is_calculating = true;
302        pathfinder.allow_mining = event.allow_mining;
303        pathfinder.min_timeout = Some(event.min_timeout);
304        pathfinder.max_timeout = Some(event.max_timeout);
305
306        let start = if let Some(executing_path) = executing_path
307            && let Some(final_node) = executing_path.path.back()
308        {
309            // if we're currently pathfinding and got a goto event, start a little ahead
310            executing_path
311                .path
312                .get(50)
313                .unwrap_or(final_node)
314                .movement
315                .target
316        } else {
317            BlockPos::from(position)
318        };
319
320        if start == BlockPos::from(position) {
321            info!("got goto {:?}, starting from {start:?}", event.goal);
322        } else {
323            info!(
324                "got goto {:?}, starting from {start:?} (currently at {:?})",
325                event.goal,
326                BlockPos::from(position)
327            );
328        }
329
330        let successors_fn: moves::SuccessorsFn = event.successors_fn;
331
332        let world_lock = instance_container
333            .get(instance_name)
334            .expect("Entity tried to pathfind but the entity isn't in a valid world");
335
336        let goal = event.goal.clone();
337        let entity = event.entity;
338
339        let goto_id_atomic = pathfinder.goto_id.clone();
340
341        let allow_mining = event.allow_mining;
342        let retry_on_no_path = event.retry_on_no_path;
343        let mining_cache = MiningCache::new(if allow_mining {
344            Some(inventory.inventory_menu.clone())
345        } else {
346            None
347        });
348
349        let custom_state = custom_state.cloned().unwrap_or_default();
350
351        let min_timeout = event.min_timeout;
352        let max_timeout = event.max_timeout;
353
354        let task = thread_pool.spawn(async move {
355            calculate_path(CalculatePathOpts {
356                entity,
357                start,
358                goal,
359                successors_fn,
360                world_lock,
361                goto_id_atomic,
362                allow_mining,
363                mining_cache,
364                retry_on_no_path,
365                custom_state,
366                min_timeout,
367                max_timeout,
368            })
369        });
370
371        commands.entity(event.entity).insert(ComputePath(task));
372    }
373}
374
375pub struct CalculatePathOpts {
376    pub entity: Entity,
377    pub start: BlockPos,
378    pub goal: Arc<dyn Goal>,
379    pub successors_fn: SuccessorsFn,
380    pub world_lock: Arc<RwLock<azalea_world::Instance>>,
381    pub goto_id_atomic: Arc<AtomicUsize>,
382    pub allow_mining: bool,
383    pub mining_cache: MiningCache,
384    /// See [`GotoEvent::retry_on_no_path`].
385    pub retry_on_no_path: bool,
386
387    /// See [`GotoEvent::min_timeout`].
388    pub min_timeout: PathfinderTimeout,
389    pub max_timeout: PathfinderTimeout,
390
391    pub custom_state: CustomPathfinderState,
392}
393
394/// Calculate the [`PathFoundEvent`] for the given pathfinder options.
395///
396/// You usually want to just use [`PathfinderClientExt::goto`] or send a
397/// [`GotoEvent`] instead of calling this directly.
398///
399/// You are expected to immediately send the `PathFoundEvent` you received after
400/// calling this function. `None` will be returned if the pathfinding was
401/// interrupted by another path calculation.
402pub fn calculate_path(opts: CalculatePathOpts) -> Option<PathFoundEvent> {
403    debug!("start: {:?}", opts.start);
404
405    let goto_id = opts.goto_id_atomic.fetch_add(1, atomic::Ordering::SeqCst) + 1;
406
407    let origin = opts.start;
408    let cached_world = CachedWorld::new(opts.world_lock, origin);
409    let successors = |pos: RelBlockPos| {
410        call_successors_fn(
411            &cached_world,
412            &opts.mining_cache,
413            &opts.custom_state.0.read(),
414            opts.successors_fn,
415            pos,
416        )
417    };
418
419    let start_time = Instant::now();
420
421    let astar::Path {
422        movements,
423        is_partial,
424    } = a_star(
425        RelBlockPos::get_origin(origin),
426        |n| opts.goal.heuristic(n.apply(origin)),
427        successors,
428        |n| opts.goal.success(n.apply(origin)),
429        opts.min_timeout,
430        opts.max_timeout,
431    );
432    let end_time = Instant::now();
433    debug!("partial: {is_partial:?}");
434    let duration = end_time - start_time;
435    if is_partial {
436        if movements.is_empty() {
437            info!("Pathfinder took {duration:?} (empty path)");
438        } else {
439            info!("Pathfinder took {duration:?} (incomplete path)");
440        }
441        // wait a bit so it's not a busy loop
442        thread::sleep(Duration::from_millis(100));
443    } else {
444        info!("Pathfinder took {duration:?}");
445    }
446
447    debug!("Path:");
448    for movement in &movements {
449        debug!("  {}", movement.target.apply(origin));
450    }
451
452    let path = movements.into_iter().collect::<VecDeque<_>>();
453
454    let goto_id_now = opts.goto_id_atomic.load(atomic::Ordering::SeqCst);
455    if goto_id != goto_id_now {
456        // we must've done another goto while calculating this path, so throw it away
457        warn!("finished calculating a path, but it's outdated");
458        return None;
459    }
460
461    if path.is_empty() && is_partial {
462        debug!("this path is empty, we might be stuck :(");
463    }
464
465    let mut mapped_path = VecDeque::with_capacity(path.len());
466    let mut current_position = RelBlockPos::get_origin(origin);
467    for movement in path {
468        let mut found_edge = None;
469        for edge in successors(current_position) {
470            if edge.movement.target == movement.target {
471                found_edge = Some(edge);
472                break;
473            }
474        }
475
476        let found_edge = found_edge.expect(
477            "path should always still be possible because we're using the same world cache",
478        );
479        current_position = found_edge.movement.target;
480
481        // we don't just clone the found_edge because we're using BlockPos instead of
482        // RelBlockPos as the target type
483        mapped_path.push_back(Edge {
484            movement: astar::Movement {
485                target: movement.target.apply(origin),
486                data: movement.data,
487            },
488            cost: found_edge.cost,
489        });
490    }
491
492    Some(PathFoundEvent {
493        entity: opts.entity,
494        start: opts.start,
495        path: Some(mapped_path),
496        is_partial,
497        successors_fn: opts.successors_fn,
498        allow_mining: opts.allow_mining,
499    })
500}
501
502// poll the tasks and send the PathFoundEvent if they're done
503pub fn handle_tasks(
504    mut commands: Commands,
505    mut transform_tasks: Query<(Entity, &mut ComputePath)>,
506    mut path_found_events: EventWriter<PathFoundEvent>,
507) {
508    for (entity, mut task) in &mut transform_tasks {
509        if let Some(optional_path_found_event) = future::block_on(future::poll_once(&mut task.0)) {
510            if let Some(path_found_event) = optional_path_found_event {
511                path_found_events.write(path_found_event);
512            }
513
514            // Task is complete, so remove task component from entity
515            commands.entity(entity).remove::<ComputePath>();
516        }
517    }
518}
519
520// set the path for the target entity when we get the PathFoundEvent
521#[allow(clippy::type_complexity)]
522pub fn path_found_listener(
523    mut events: EventReader<PathFoundEvent>,
524    mut query: Query<(
525        &mut Pathfinder,
526        Option<&mut ExecutingPath>,
527        &InstanceName,
528        &Inventory,
529        Option<&CustomPathfinderState>,
530    )>,
531    instance_container: Res<InstanceContainer>,
532    mut commands: Commands,
533) {
534    for event in events.read() {
535        let (mut pathfinder, executing_path, instance_name, inventory, custom_state) = query
536            .get_mut(event.entity)
537            .expect("Path found for an entity that doesn't have a pathfinder");
538        if let Some(path) = &event.path {
539            if let Some(mut executing_path) = executing_path {
540                let mut new_path = VecDeque::new();
541
542                // combine the old and new paths if the first node of the new path is a
543                // successor of the last node of the old path
544                if let Some(last_node_of_current_path) = executing_path.path.back() {
545                    let world_lock = instance_container
546                        .get(instance_name)
547                        .expect("Entity tried to pathfind but the entity isn't in a valid world");
548                    let origin = event.start;
549                    let successors_fn: moves::SuccessorsFn = event.successors_fn;
550                    let cached_world = CachedWorld::new(world_lock, origin);
551                    let mining_cache = MiningCache::new(if event.allow_mining {
552                        Some(inventory.inventory_menu.clone())
553                    } else {
554                        None
555                    });
556                    let custom_state = custom_state.cloned().unwrap_or_default();
557                    let custom_state_ref = custom_state.0.read();
558                    let successors = |pos: RelBlockPos| {
559                        call_successors_fn(
560                            &cached_world,
561                            &mining_cache,
562                            &custom_state_ref,
563                            successors_fn,
564                            pos,
565                        )
566                    };
567
568                    if let Some(first_node_of_new_path) = path.front() {
569                        let last_target_of_current_path = RelBlockPos::from_origin(
570                            origin,
571                            last_node_of_current_path.movement.target,
572                        );
573                        let first_target_of_new_path = RelBlockPos::from_origin(
574                            origin,
575                            first_node_of_new_path.movement.target,
576                        );
577
578                        if successors(last_target_of_current_path)
579                            .iter()
580                            .any(|edge| edge.movement.target == first_target_of_new_path)
581                        {
582                            debug!("combining old and new paths");
583                            debug!(
584                                "old path: {:?}",
585                                executing_path.path.iter().collect::<Vec<_>>()
586                            );
587                            debug!("new path: {:?}", path.iter().take(10).collect::<Vec<_>>());
588                            new_path.extend(executing_path.path.iter().cloned());
589                        }
590                    } else {
591                        new_path.extend(executing_path.path.iter().cloned());
592                    }
593                }
594
595                new_path.extend(path.to_owned());
596
597                debug!(
598                    "set queued path to {:?}",
599                    new_path.iter().take(10).collect::<Vec<_>>()
600                );
601                executing_path.queued_path = Some(new_path);
602                executing_path.is_path_partial = event.is_partial;
603            } else if path.is_empty() {
604                debug!("calculated path is empty, so didn't add ExecutingPath");
605                if !pathfinder.retry_on_no_path {
606                    debug!("retry_on_no_path is set to false, removing goal");
607                    pathfinder.goal = None;
608                }
609            } else {
610                commands.entity(event.entity).insert(ExecutingPath {
611                    path: path.to_owned(),
612                    queued_path: None,
613                    last_reached_node: event.start,
614                    last_node_reached_at: Instant::now(),
615                    is_path_partial: event.is_partial,
616                });
617                debug!("set path to {:?}", path.iter().take(10).collect::<Vec<_>>());
618                debug!("partial: {}", event.is_partial);
619            }
620        } else {
621            error!("No path found");
622            if let Some(mut executing_path) = executing_path {
623                // set the queued path so we don't stop in the middle of a move
624                executing_path.queued_path = Some(VecDeque::new());
625            } else {
626                // wasn't executing a path, don't need to do anything
627            }
628        }
629        pathfinder.is_calculating = false;
630    }
631}
632
633#[allow(clippy::type_complexity)]
634pub fn timeout_movement(
635    mut query: Query<(
636        Entity,
637        &mut Pathfinder,
638        &mut ExecutingPath,
639        &Position,
640        Option<&Mining>,
641        &InstanceName,
642        &Inventory,
643        Option<&CustomPathfinderState>,
644    )>,
645    instance_container: Res<InstanceContainer>,
646) {
647    for (
648        entity,
649        mut pathfinder,
650        mut executing_path,
651        position,
652        mining,
653        instance_name,
654        inventory,
655        custom_state,
656    ) in &mut query
657    {
658        // don't timeout if we're mining
659        if let Some(mining) = mining {
660            // also make sure we're close enough to the block that's being mined
661            if mining.pos.distance_squared_to(position.into()) < 6_i32.pow(2) {
662                // also reset the last_node_reached_at so we don't timeout after we finish
663                // mining
664                executing_path.last_node_reached_at = Instant::now();
665                continue;
666            }
667        }
668
669        if executing_path.last_node_reached_at.elapsed() > Duration::from_secs(2)
670            && !pathfinder.is_calculating
671            && !executing_path.path.is_empty()
672        {
673            warn!("pathfinder timeout, trying to patch path");
674            executing_path.queued_path = None;
675            executing_path.last_reached_node = BlockPos::from(position);
676
677            let world_lock = instance_container
678                .get(instance_name)
679                .expect("Entity tried to pathfind but the entity isn't in a valid world");
680            let Some(successors_fn) = pathfinder.successors_fn else {
681                warn!(
682                    "pathfinder was going to patch path because of timeout, but there was no successors_fn"
683                );
684                return;
685            };
686
687            let custom_state = custom_state.cloned().unwrap_or_default();
688
689            // try to fix the path without recalculating everything.
690            // (though, it'll still get fully recalculated by `recalculate_near_end_of_path`
691            // if the new path is too short)
692            patch_path(
693                0..=cmp::min(20, executing_path.path.len() - 1),
694                &mut executing_path,
695                &mut pathfinder,
696                inventory,
697                entity,
698                successors_fn,
699                world_lock,
700                custom_state,
701            );
702            // reset last_node_reached_at so we don't immediately try to patch again
703            executing_path.last_node_reached_at = Instant::now();
704        }
705    }
706}
707
708pub fn check_node_reached(
709    mut query: Query<(
710        Entity,
711        &mut Pathfinder,
712        &mut ExecutingPath,
713        &Position,
714        &Physics,
715    )>,
716    mut walk_events: EventWriter<StartWalkEvent>,
717    mut commands: Commands,
718) {
719    for (entity, mut pathfinder, mut executing_path, position, physics) in &mut query {
720        'skip: loop {
721            // we check if the goal was reached *before* actually executing the movement so
722            // we don't unnecessarily execute a movement when it wasn't necessary
723
724            // see if we already reached any future nodes and can skip ahead
725            for (i, edge) in executing_path
726                .path
727                .clone()
728                .into_iter()
729                .enumerate()
730                .take(20)
731                .rev()
732            {
733                let movement = edge.movement;
734                let is_reached_ctx = IsReachedCtx {
735                    target: movement.target,
736                    start: executing_path.last_reached_node,
737                    position: **position,
738                    physics,
739                };
740                let extra_strict_if_last = if i == executing_path.path.len() - 1 {
741                    let x_difference_from_center = position.x - (movement.target.x as f64 + 0.5);
742                    let z_difference_from_center = position.z - (movement.target.z as f64 + 0.5);
743                    // this is to make sure we don't fall off immediately after finishing the path
744                    physics.on_ground()
745                    // 0.5 to handle non-full blocks
746                    && BlockPos::from(position.up(0.5)) == movement.target
747                    // adding the delta like this isn't a perfect solution but it helps to make
748                    // sure we don't keep going if our delta is high
749                    && (x_difference_from_center + physics.velocity.x).abs() < 0.2
750                    && (z_difference_from_center + physics.velocity.z).abs() < 0.2
751                } else {
752                    true
753                };
754                if (movement.data.is_reached)(is_reached_ctx) && extra_strict_if_last {
755                    executing_path.path = executing_path.path.split_off(i + 1);
756                    executing_path.last_reached_node = movement.target;
757                    executing_path.last_node_reached_at = Instant::now();
758                    trace!("reached node {}", movement.target);
759
760                    if let Some(new_path) = executing_path.queued_path.take() {
761                        debug!(
762                            "swapped path to {:?}",
763                            new_path.iter().take(10).collect::<Vec<_>>()
764                        );
765                        executing_path.path = new_path;
766
767                        if executing_path.path.is_empty() {
768                            info!("the path we just swapped to was empty, so reached end of path");
769                            walk_events.write(StartWalkEvent {
770                                entity,
771                                direction: WalkDirection::None,
772                            });
773                            commands.entity(entity).remove::<ExecutingPath>();
774                            break;
775                        }
776
777                        // run the function again since we just swapped
778                        continue 'skip;
779                    }
780
781                    if executing_path.path.is_empty() {
782                        debug!("pathfinder path is now empty");
783                        walk_events.write(StartWalkEvent {
784                            entity,
785                            direction: WalkDirection::None,
786                        });
787                        commands.entity(entity).remove::<ExecutingPath>();
788                        if let Some(goal) = pathfinder.goal.clone()
789                            && goal.success(movement.target)
790                        {
791                            info!("goal was reached!");
792                            pathfinder.goal = None;
793                            pathfinder.successors_fn = None;
794                        }
795                    }
796
797                    break;
798                }
799            }
800            break;
801        }
802    }
803}
804
805#[allow(clippy::type_complexity)]
806pub fn check_for_path_obstruction(
807    mut query: Query<(
808        Entity,
809        &mut Pathfinder,
810        &mut ExecutingPath,
811        &InstanceName,
812        &Inventory,
813        Option<&CustomPathfinderState>,
814    )>,
815    instance_container: Res<InstanceContainer>,
816) {
817    for (entity, mut pathfinder, mut executing_path, instance_name, inventory, custom_state) in
818        &mut query
819    {
820        let Some(successors_fn) = pathfinder.successors_fn else {
821            continue;
822        };
823
824        let world_lock = instance_container
825            .get(instance_name)
826            .expect("Entity tried to pathfind but the entity isn't in a valid world");
827
828        // obstruction check (the path we're executing isn't possible anymore)
829        let origin = executing_path.last_reached_node;
830        let cached_world = CachedWorld::new(world_lock, origin);
831        let mining_cache = MiningCache::new(if pathfinder.allow_mining {
832            Some(inventory.inventory_menu.clone())
833        } else {
834            None
835        });
836        let custom_state = custom_state.cloned().unwrap_or_default();
837        let custom_state_ref = custom_state.0.read();
838        let successors = |pos: RelBlockPos| {
839            call_successors_fn(
840                &cached_world,
841                &mining_cache,
842                &custom_state_ref,
843                successors_fn,
844                pos,
845            )
846        };
847
848        let Some(obstructed_index) = check_path_obstructed(
849            origin,
850            RelBlockPos::from_origin(origin, executing_path.last_reached_node),
851            &executing_path.path,
852            successors,
853        ) else {
854            continue;
855        };
856
857        drop(custom_state_ref);
858
859        warn!(
860            "path obstructed at index {obstructed_index} (starting at {:?})",
861            executing_path.last_reached_node,
862        );
863        debug!("obstructed path: {:?}", executing_path.path);
864        // if it's near the end, don't bother recalculating a patch, just truncate and
865        // mark it as partial
866        if obstructed_index + 5 > executing_path.path.len() {
867            debug!(
868                "obstruction is near the end of the path, truncating and marking path as partial"
869            );
870            executing_path.path.truncate(obstructed_index);
871            executing_path.is_path_partial = true;
872            continue;
873        }
874
875        let Some(successors_fn) = pathfinder.successors_fn else {
876            error!("got PatchExecutingPathEvent but the bot has no successors_fn");
877            continue;
878        };
879
880        let world_lock = instance_container
881            .get(instance_name)
882            .expect("Entity tried to pathfind but the entity isn't in a valid world");
883
884        // patch up to 20 nodes
885        let patch_end_index = cmp::min(obstructed_index + 20, executing_path.path.len() - 1);
886
887        patch_path(
888            obstructed_index..=patch_end_index,
889            &mut executing_path,
890            &mut pathfinder,
891            inventory,
892            entity,
893            successors_fn,
894            world_lock,
895            custom_state.clone(),
896        );
897    }
898}
899
900/// update the given [`ExecutingPath`] to recalculate the path of the nodes in
901/// the given index range.
902///
903/// You should avoid making the range too large, since the timeout for the A*
904/// calculation is very low. About 20 nodes is a good amount.
905#[allow(clippy::too_many_arguments)]
906fn patch_path(
907    patch_nodes: RangeInclusive<usize>,
908    executing_path: &mut ExecutingPath,
909    pathfinder: &mut Pathfinder,
910    inventory: &Inventory,
911    entity: Entity,
912    successors_fn: SuccessorsFn,
913    world_lock: Arc<RwLock<azalea_world::Instance>>,
914    custom_state: CustomPathfinderState,
915) {
916    let patch_start = if *patch_nodes.start() == 0 {
917        executing_path.last_reached_node
918    } else {
919        executing_path.path[*patch_nodes.start() - 1]
920            .movement
921            .target
922    };
923
924    let patch_end = executing_path.path[*patch_nodes.end()].movement.target;
925
926    // this doesn't override the main goal, it's just the goal for this A*
927    // calculation
928    let goal = Arc::new(BlockPosGoal(patch_end));
929
930    let goto_id_atomic = pathfinder.goto_id.clone();
931    let allow_mining = pathfinder.allow_mining;
932    let retry_on_no_path = pathfinder.retry_on_no_path;
933
934    let mining_cache = MiningCache::new(if allow_mining {
935        Some(inventory.inventory_menu.clone())
936    } else {
937        None
938    });
939
940    // the timeout is small enough that this doesn't need to be async
941    let path_found_event = calculate_path(CalculatePathOpts {
942        entity,
943        start: patch_start,
944        goal,
945        successors_fn,
946        world_lock,
947        goto_id_atomic,
948        allow_mining,
949        mining_cache,
950        retry_on_no_path,
951
952        custom_state,
953        min_timeout: PathfinderTimeout::Nodes(10_000),
954        max_timeout: PathfinderTimeout::Nodes(10_000),
955    });
956
957    // this is necessary in case we interrupted another ongoing path calculation
958    pathfinder.is_calculating = false;
959
960    debug!("obstruction patch: {path_found_event:?}");
961
962    let mut new_path = VecDeque::new();
963    if *patch_nodes.start() > 0 {
964        new_path.extend(
965            executing_path
966                .path
967                .iter()
968                .take(*patch_nodes.start())
969                .cloned(),
970        );
971    }
972
973    let mut is_patch_complete = false;
974    if let Some(path_found_event) = path_found_event {
975        if let Some(found_path_patch) = path_found_event.path
976            && !found_path_patch.is_empty()
977        {
978            new_path.extend(found_path_patch);
979
980            if !path_found_event.is_partial {
981                new_path.extend(executing_path.path.iter().skip(*patch_nodes.end()).cloned());
982                is_patch_complete = true;
983                debug!("the patch is not partial :)");
984            } else {
985                debug!("the patch is partial, throwing away rest of path :(");
986            }
987        }
988    } else {
989        // no path found, rip
990    }
991
992    executing_path.path = new_path;
993    if !is_patch_complete {
994        executing_path.is_path_partial = true;
995    }
996}
997
998pub fn recalculate_near_end_of_path(
999    mut query: Query<(Entity, &mut Pathfinder, &mut ExecutingPath)>,
1000    mut walk_events: EventWriter<StartWalkEvent>,
1001    mut goto_events: EventWriter<GotoEvent>,
1002    mut commands: Commands,
1003) {
1004    for (entity, mut pathfinder, mut executing_path) in &mut query {
1005        let Some(successors_fn) = pathfinder.successors_fn else {
1006            continue;
1007        };
1008
1009        // start recalculating if the path ends soon
1010        if (executing_path.path.len() == 50 || executing_path.path.len() < 5)
1011            && !pathfinder.is_calculating
1012            && executing_path.is_path_partial
1013        {
1014            match pathfinder.goal.as_ref().cloned() {
1015                Some(goal) => {
1016                    debug!("Recalculating path because it's empty or ends soon");
1017                    debug!(
1018                        "recalculate_near_end_of_path executing_path.is_path_partial: {}",
1019                        executing_path.is_path_partial
1020                    );
1021                    goto_events.write(GotoEvent {
1022                        entity,
1023                        goal,
1024                        successors_fn,
1025                        allow_mining: pathfinder.allow_mining,
1026                        retry_on_no_path: pathfinder.retry_on_no_path,
1027                        min_timeout: if executing_path.path.len() == 50 {
1028                            // we have quite some time until the node is reached, soooo we might as
1029                            // well burn some cpu cycles to get a good path
1030                            PathfinderTimeout::Time(Duration::from_secs(5))
1031                        } else {
1032                            PathfinderTimeout::Time(Duration::from_secs(1))
1033                        },
1034                        max_timeout: pathfinder.max_timeout.expect("max_timeout should be set"),
1035                    });
1036                    pathfinder.is_calculating = true;
1037
1038                    if executing_path.path.is_empty() {
1039                        if let Some(new_path) = executing_path.queued_path.take() {
1040                            executing_path.path = new_path;
1041                            if executing_path.path.is_empty() {
1042                                info!(
1043                                    "the path we just swapped to was empty, so reached end of path"
1044                                );
1045                                walk_events.write(StartWalkEvent {
1046                                    entity,
1047                                    direction: WalkDirection::None,
1048                                });
1049                                commands.entity(entity).remove::<ExecutingPath>();
1050                                break;
1051                            }
1052                        } else {
1053                            walk_events.write(StartWalkEvent {
1054                                entity,
1055                                direction: WalkDirection::None,
1056                            });
1057                            commands.entity(entity).remove::<ExecutingPath>();
1058                        }
1059                    }
1060                }
1061                _ => {
1062                    if executing_path.path.is_empty() {
1063                        // idk when this can happen but stop moving just in case
1064                        walk_events.write(StartWalkEvent {
1065                            entity,
1066                            direction: WalkDirection::None,
1067                        });
1068                    }
1069                }
1070            }
1071        }
1072    }
1073}
1074
1075#[allow(clippy::type_complexity)]
1076pub fn tick_execute_path(
1077    mut query: Query<(
1078        Entity,
1079        &mut ExecutingPath,
1080        &Position,
1081        &Physics,
1082        Option<&Mining>,
1083        &InstanceHolder,
1084        &Inventory,
1085    )>,
1086    mut look_at_events: EventWriter<LookAtEvent>,
1087    mut sprint_events: EventWriter<StartSprintEvent>,
1088    mut walk_events: EventWriter<StartWalkEvent>,
1089    mut jump_events: EventWriter<JumpEvent>,
1090    mut start_mining_events: EventWriter<StartMiningBlockEvent>,
1091    mut set_selected_hotbar_slot_events: EventWriter<SetSelectedHotbarSlotEvent>,
1092) {
1093    for (entity, executing_path, position, physics, mining, instance_holder, inventory_component) in
1094        &mut query
1095    {
1096        if let Some(edge) = executing_path.path.front() {
1097            let ctx = ExecuteCtx {
1098                entity,
1099                target: edge.movement.target,
1100                position: **position,
1101                start: executing_path.last_reached_node,
1102                physics,
1103                is_currently_mining: mining.is_some(),
1104                instance: instance_holder.instance.clone(),
1105                menu: inventory_component.inventory_menu.clone(),
1106
1107                look_at_events: &mut look_at_events,
1108                sprint_events: &mut sprint_events,
1109                walk_events: &mut walk_events,
1110                jump_events: &mut jump_events,
1111                start_mining_events: &mut start_mining_events,
1112                set_selected_hotbar_slot_events: &mut set_selected_hotbar_slot_events,
1113            };
1114            trace!(
1115                "executing move, position: {}, last_reached_node: {}",
1116                **position, executing_path.last_reached_node
1117            );
1118            (edge.movement.data.execute)(ctx);
1119        }
1120    }
1121}
1122
1123pub fn recalculate_if_has_goal_but_no_path(
1124    mut query: Query<(Entity, &mut Pathfinder), Without<ExecutingPath>>,
1125    mut goto_events: EventWriter<GotoEvent>,
1126) {
1127    for (entity, mut pathfinder) in &mut query {
1128        if pathfinder.goal.is_some()
1129            && !pathfinder.is_calculating
1130            && let Some(goal) = pathfinder.goal.as_ref().cloned()
1131        {
1132            debug!("Recalculating path because it has a goal but no ExecutingPath");
1133            goto_events.write(GotoEvent {
1134                entity,
1135                goal,
1136                successors_fn: pathfinder.successors_fn.unwrap(),
1137                allow_mining: pathfinder.allow_mining,
1138                retry_on_no_path: pathfinder.retry_on_no_path,
1139                min_timeout: pathfinder.min_timeout.expect("min_timeout should be set"),
1140                max_timeout: pathfinder.max_timeout.expect("max_timeout should be set"),
1141            });
1142            pathfinder.is_calculating = true;
1143        }
1144    }
1145}
1146
1147#[derive(Event)]
1148pub struct StopPathfindingEvent {
1149    pub entity: Entity,
1150    /// If false, then let the current movement finish before stopping. If true,
1151    /// then stop moving immediately. This might cause the bot to fall if it was
1152    /// in the middle of parkouring.
1153    pub force: bool,
1154}
1155
1156pub fn handle_stop_pathfinding_event(
1157    mut events: EventReader<StopPathfindingEvent>,
1158    mut query: Query<(&mut Pathfinder, &mut ExecutingPath)>,
1159    mut walk_events: EventWriter<StartWalkEvent>,
1160    mut commands: Commands,
1161) {
1162    for event in events.read() {
1163        // stop computing any path that's being computed
1164        commands.entity(event.entity).remove::<ComputePath>();
1165
1166        let Ok((mut pathfinder, mut executing_path)) = query.get_mut(event.entity) else {
1167            continue;
1168        };
1169        pathfinder.goal = None;
1170        if event.force {
1171            executing_path.path.clear();
1172            executing_path.queued_path = None;
1173        } else {
1174            // switch to an empty path as soon as it can
1175            executing_path.queued_path = Some(VecDeque::new());
1176            // make sure it doesn't recalculate
1177            executing_path.is_path_partial = false;
1178        }
1179
1180        if executing_path.path.is_empty() {
1181            walk_events.write(StartWalkEvent {
1182                entity: event.entity,
1183                direction: WalkDirection::None,
1184            });
1185            commands.entity(event.entity).remove::<ExecutingPath>();
1186        }
1187    }
1188}
1189
1190pub fn stop_pathfinding_on_instance_change(
1191    mut query: Query<(Entity, &mut ExecutingPath), Changed<InstanceName>>,
1192    mut stop_pathfinding_events: EventWriter<StopPathfindingEvent>,
1193) {
1194    for (entity, mut executing_path) in &mut query {
1195        if !executing_path.path.is_empty() {
1196            debug!("instance changed, clearing path");
1197            executing_path.path.clear();
1198            stop_pathfinding_events.write(StopPathfindingEvent {
1199                entity,
1200                force: true,
1201            });
1202        }
1203    }
1204}
1205
1206/// Checks whether the path has been obstructed, and returns Some(index) if it
1207/// has been. The index is of the first obstructed node.
1208pub fn check_path_obstructed<SuccessorsFn>(
1209    origin: BlockPos,
1210    mut current_position: RelBlockPos,
1211    path: &VecDeque<astar::Edge<BlockPos, moves::MoveData>>,
1212    successors_fn: SuccessorsFn,
1213) -> Option<usize>
1214where
1215    SuccessorsFn: Fn(RelBlockPos) -> Vec<astar::Edge<RelBlockPos, moves::MoveData>>,
1216{
1217    for (i, edge) in path.iter().enumerate() {
1218        let movement_target = RelBlockPos::from_origin(origin, edge.movement.target);
1219
1220        let mut found_edge = None;
1221        for candidate_edge in successors_fn(current_position) {
1222            if candidate_edge.movement.target == movement_target {
1223                found_edge = Some(candidate_edge);
1224                break;
1225            }
1226        }
1227
1228        current_position = movement_target;
1229        // if found_edge is None or the cost increased, then return the index
1230        if found_edge
1231            .map(|found_edge| found_edge.cost > edge.cost)
1232            .unwrap_or(true)
1233        {
1234            // if the node that we're currently executing was obstructed then it's often too
1235            // late to change the path, so it's usually better to just ignore this case :/
1236            if i == 0 {
1237                warn!("path obstructed at index 0, ignoring");
1238                continue;
1239            }
1240
1241            return Some(i);
1242        }
1243    }
1244
1245    None
1246}
1247
1248pub fn call_successors_fn(
1249    cached_world: &CachedWorld,
1250    mining_cache: &MiningCache,
1251    custom_state: &CustomPathfinderStateRef,
1252    successors_fn: SuccessorsFn,
1253    pos: RelBlockPos,
1254) -> Vec<astar::Edge<RelBlockPos, moves::MoveData>> {
1255    let mut edges = Vec::with_capacity(16);
1256    let mut ctx = PathfinderCtx {
1257        edges: &mut edges,
1258        world: cached_world,
1259        mining_cache,
1260        custom_state,
1261    };
1262    successors_fn(&mut ctx, pos);
1263    edges
1264}