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 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                // putting systems in the GameTick schedule makes them run every Minecraft tick
69                // (every 50 milliseconds).
70                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/// A component that makes this client able to pathfind.
102#[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/// A component that's present on clients that are actively following a
116/// pathfinder path.
117#[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/// Send this event to start pathfinding to the given goal.
127///
128/// Also see [`PathfinderClientExt::goto`].
129///
130/// This event is read by [`goto_listener`].
131#[derive(Event)]
132pub struct GotoEvent {
133    /// The local bot entity that will do the pathfinding and execute the path.
134    pub entity: Entity,
135    pub goal: Arc<dyn Goal>,
136    /// The function that's used for checking what moves are possible. Usually
137    /// `pathfinder::moves::default_move`
138    pub successors_fn: SuccessorsFn,
139
140    /// Whether the bot is allowed to break blocks while pathfinding.
141    pub allow_mining: bool,
142
143    /// The minimum amount of time that should pass before the A* pathfinder
144    /// function can return a timeout. It may take up to [`Self::max_timeout`]
145    /// if it can't immediately find a usable path.
146    ///
147    /// A good default value for this is
148    /// `PathfinderTimeout::Time(Duration::from_secs(1))`.
149    ///
150    /// Also see [`PathfinderTimeout::Nodes`]
151    pub min_timeout: PathfinderTimeout,
152    /// The absolute maximum amount of time that the pathfinder function can
153    /// take to find a path. If it takes this long, it means no usable path was
154    /// found (so it might be impossible).
155    ///
156    /// A good default value for this is
157    /// `PathfinderTimeout::Time(Duration::from_secs(5))`.
158    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    /// Pathfind to the given goal and wait until either the target is reached
191    /// or the pathfinding is canceled.
192    ///
193    /// ```
194    /// # use azalea::prelude::*;
195    /// # use azalea::{BlockPos, pathfinder::goals::BlockPosGoal};
196    /// # async fn example(bot: &Client) {
197    /// bot.goto(BlockPosGoal(BlockPos::new(0, 70, 0))).await;
198    /// # }
199    /// ```
200    async fn goto(&self, goal: impl Goal + 'static) {
201        self.start_goto(goal);
202        self.wait_until_goto_target_reached().await;
203    }
204
205    /// Start pathfinding to a given goal.
206    ///
207    /// ```
208    /// # use azalea::prelude::*;
209    /// # use azalea::{BlockPos, pathfinder::goals::BlockPosGoal};
210    /// # fn example(bot: &Client) {
211    /// bot.start_goto(BlockPosGoal(BlockPos::new(0, 70, 0)));
212    /// # }
213    /// ```
214    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    /// Same as [`start_goto`](Self::start_goto). but the bot won't break any
226    /// blocks while executing the path.
227    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    /// Waits forever until the bot no longer has a pathfinder goal.
246    async fn wait_until_goto_target_reached(&self) {
247        // we do this to make sure the event got handled before we start checking
248        // is_goto_target_reached
249        self.wait_one_update().await;
250
251        let mut tick_broadcaster = self.get_tick_broadcaster();
252        while !self.is_goto_target_reached() {
253            // check every tick
254            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            // we're already at the goal, nothing to do
297            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        // we store the goal so it can be recalculated later if necessary
305        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            // if we're currently pathfinding and got a goto event, start a little ahead
316            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    /// Also see [`GotoEvent::min_timeout`].
381    pub min_timeout: PathfinderTimeout,
382    pub max_timeout: PathfinderTimeout,
383}
384
385/// Calculate the [`PathFoundEvent`] for the given pathfinder options.
386///
387/// You usually want to just use [`PathfinderClientExt::goto`] or send a
388/// [`GotoEvent`] instead of calling this directly.
389///
390/// You are expected to immediately send the `PathFoundEvent` you received after
391/// calling this function. `None` will be returned if the pathfinding was
392/// interrupted by another path calculation.
393pub 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        // wait a bit so it's not a busy loop
427        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        // we must've done another goto while calculating this path, so throw it away
442        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    // replace the RelBlockPos types with BlockPos
451    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
469// poll the tasks and send the PathFoundEvent if they're done
470pub 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            // Task is complete, so remove task component from entity
482            commands.entity(entity).remove::<ComputePath>();
483        }
484    }
485}
486
487// set the path for the target entity when we get the PathFoundEvent
488pub 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                // combine the old and new paths if the first node of the new path is a
508                // successor of the last node of the old path
509                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                // set the queued path so we don't stop in the middle of a move
573                executing_path.queued_path = Some(VecDeque::new());
574            } else {
575                // wasn't executing a path, don't need to do anything
576            }
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        // don't timeout if we're mining
599        if let Some(mining) = mining {
600            // also make sure we're close enough to the block that's being mined
601            if mining.pos.distance_squared_to(&BlockPos::from(position)) < 6_i32.pow(2) {
602                // also reset the last_node_reached_at so we don't timeout after we finish
603                // mining
604                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            // try to fix the path without recalculating everything.
623            // (though, it'll still get fully recalculated by `recalculate_near_end_of_path`
624            // if the new path is too short)
625            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            // reset last_node_reached_at so we don't immediately try to patch again
635            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            // we check if the goal was reached *before* actually executing the movement so
654            // we don't unnecessarily execute a movement when it wasn't necessary
655
656            // see if we already reached any future nodes and can skip ahead
657            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                    // this is to make sure we don't fall off immediately after finishing the path
675                    physics.on_ground()
676                    && BlockPos::from(position) == movement.target
677                    // adding the delta like this isn't a perfect solution but it helps to make
678                    // sure we don't keep going if our delta is high
679                    && (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                        // run the function again since we just swapped
708                        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        // obstruction check (the path we're executing isn't possible anymore)
755        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 it's near the end, don't bother recalculating a patch, just truncate and
776            // mark it as partial
777            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            // patch up to 20 nodes
796            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
811/// update the given [`ExecutingPath`] to recalculate the path of the nodes in
812/// the given index range.
813///
814/// You should avoid making the range too large, since the timeout for the A*
815/// calculation is very low. About 20 nodes is a good amount.
816fn 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    // this doesn't override the main goal, it's just the goal for this A*
834    // calculation
835    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    // the timeout is small enough that this doesn't need to be async
847    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    // this is necessary in case we interrupted another ongoing path calculation
861    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        // no path found, rip
893    }
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        // start recalculating if the path ends soon
913        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                            // we have quite some time until the node is reached, soooo we might as
931                            // well burn some cpu cycles to get a good
932                            // path
933                            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                        // idk when this can happen but stop moving just in case
967                        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    /// If false, then let the current movement finish before stopping. If true,
1052    /// then stop moving immediately. This might cause the bot to fall if it was
1053    /// in the middle of parkouring.
1054    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        // stop computing any path that's being computed
1065        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            // switch to an empty path as soon as it can
1076            executing_path.queued_path = Some(VecDeque::new());
1077            // make sure it doesn't recalculate
1078            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
1107/// Checks whether the path has been obstructed, and returns Some(index) if it
1108/// has been. The index is of the first obstructed node.
1109pub 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        // you can uncomment this while debugging tests to get trace logs
1183        // simulation.app.add_plugins(bevy_log::LogPlugin {
1184        //     level: bevy_log::Level::TRACE,
1185        //     filter: "".to_string(),
1186        //     ..Default::default()
1187        // });
1188
1189        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                // this is the point where the bot might fall if it has too much momentum
1412                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}