veloren_common/
path.rs

1use crate::{
2    astar::{Astar, PathResult},
3    resources::Time,
4    terrain::Block,
5    vol::{BaseVol, ReadVol},
6};
7use common_base::span;
8use fxhash::FxBuildHasher;
9#[cfg(feature = "rrt_pathfinding")]
10use hashbrown::HashMap;
11#[cfg(feature = "rrt_pathfinding")]
12use kiddo::{SquaredEuclidean, float::kdtree::KdTree, nearest_neighbour::NearestNeighbour}; /* For RRT paths (disabled for now) */
13use rand::{Rng, rng};
14#[cfg(feature = "rrt_pathfinding")]
15use rand::{
16    distributions::{Distribution, Uniform},
17    prelude::IteratorRandom,
18};
19#[cfg(feature = "rrt_pathfinding")]
20use std::f32::consts::PI;
21use std::{collections::VecDeque, iter::FromIterator};
22use vek::*;
23
24// Path
25
26#[derive(Clone, Debug)]
27pub struct Path<T> {
28    pub nodes: Vec<T>,
29}
30
31impl<T> Default for Path<T> {
32    fn default() -> Self {
33        Self {
34            nodes: Vec::default(),
35        }
36    }
37}
38
39impl<T> FromIterator<T> for Path<T> {
40    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
41        Self {
42            nodes: iter.into_iter().collect(),
43        }
44    }
45}
46
47impl<T> IntoIterator for Path<T> {
48    type IntoIter = std::vec::IntoIter<T>;
49    type Item = T;
50
51    fn into_iter(self) -> Self::IntoIter { self.nodes.into_iter() }
52}
53
54impl<T> Path<T> {
55    pub fn is_empty(&self) -> bool { self.nodes.is_empty() }
56
57    pub fn len(&self) -> usize { self.nodes.len() }
58
59    pub fn iter(&self) -> impl Iterator<Item = &T> { self.nodes.iter() }
60
61    pub fn start(&self) -> Option<&T> { self.nodes.first() }
62
63    pub fn end(&self) -> Option<&T> { self.nodes.last() }
64
65    pub fn nodes(&self) -> &[T] { &self.nodes }
66}
67
68// Route: A path that can be progressed along
69
70#[derive(Default, Clone, Debug)]
71pub struct Route {
72    path: Path<Vec3<i32>>,
73    next_idx: usize,
74}
75
76impl Route {
77    pub fn get_path(&self) -> &Path<Vec3<i32>> { &self.path }
78
79    pub fn next_idx(&self) -> usize { self.next_idx }
80}
81
82impl From<Path<Vec3<i32>>> for Route {
83    fn from(path: Path<Vec3<i32>>) -> Self { Self { path, next_idx: 0 } }
84}
85
86pub struct TraversalConfig {
87    /// The distance to a node at which node is considered visited.
88    pub node_tolerance: f32,
89    /// The slowdown factor when following corners.
90    /// 0.0 = no slowdown on corners, 1.0 = total slowdown on corners.
91    pub slow_factor: f32,
92    /// Whether the agent is currently on the ground.
93    pub on_ground: bool,
94    /// Whether the agent is currently in water.
95    pub in_liquid: bool,
96    /// The distance to the target below which it is considered reached.
97    pub min_tgt_dist: f32,
98    /// Whether the agent can climb.
99    pub can_climb: bool,
100    /// Whether the agent can fly.
101    pub can_fly: bool,
102    /// Whether the agent has vectored propulsion.
103    pub vectored_propulsion: bool,
104    /// Whether chunk containing target position is currently loaded
105    pub is_target_loaded: bool,
106}
107
108const DIAGONALS: [Vec2<i32>; 8] = [
109    Vec2::new(1, 0),
110    Vec2::new(1, 1),
111    Vec2::new(0, 1),
112    Vec2::new(-1, 1),
113    Vec2::new(-1, 0),
114    Vec2::new(-1, -1),
115    Vec2::new(0, -1),
116    Vec2::new(1, -1),
117];
118
119pub enum TraverseStop {
120    Done,
121    InvalidOutput,
122    InvalidPath,
123}
124
125impl Route {
126    pub fn path(&self) -> &Path<Vec3<i32>> { &self.path }
127
128    pub fn next(&self, i: usize) -> Option<Vec3<i32>> {
129        self.path.nodes.get(self.next_idx + i).copied()
130    }
131
132    pub fn is_finished(&self) -> bool { self.next(0).is_none() }
133
134    /// Handles moving along a path.
135    pub fn traverse<V>(
136        &mut self,
137        vol: &V,
138        pos: Vec3<f32>,
139        vel: Vec3<f32>,
140        traversal_cfg: &TraversalConfig,
141    ) -> Result<(Vec3<f32>, f32), TraverseStop>
142    where
143        V: BaseVol<Vox = Block> + ReadVol,
144    {
145        let (next0, next1, next_tgt, be_precise) = loop {
146            // If we've reached the end of the path, stop
147            let next0 = self.next(0).ok_or(TraverseStop::Done)?;
148            let next1 = self.next(1).unwrap_or(next0);
149
150            // Stop using obstructed paths
151            if !walkable(vol, next0, traversal_cfg.is_target_loaded)
152                || !walkable(vol, next1, traversal_cfg.is_target_loaded)
153            {
154                return Err(TraverseStop::InvalidPath);
155            }
156
157            // If, in any direction, there is a column of open air of several blocks
158            let open_space_nearby = DIAGONALS.iter().any(|pos| {
159                (-2..2).all(|z| {
160                    vol.get(next0 + Vec3::new(pos.x, pos.y, z))
161                        .map(|b| !b.is_solid())
162                        .unwrap_or(false)
163                })
164            });
165
166            // If, in any direction, there is a solid wall
167            let wall_nearby = DIAGONALS.iter().any(|pos| {
168                vol.get(next0 + Vec3::new(pos.x, pos.y, 1))
169                    .map(|b| b.is_solid())
170                    .unwrap_or(true)
171            });
172
173            // Unwalkable obstacles, such as walls or open space or stepping up blocks can
174            // affect path-finding
175            let be_precise =
176                open_space_nearby || wall_nearby || (pos.z - next0.z as f32).abs() > 1.0;
177
178            // If we're not being precise and the next next target is closer, go towards
179            // that instead.
180            if !be_precise
181                && next0.as_::<f32>().distance_squared(pos)
182                    > next1.as_::<f32>().distance_squared(pos)
183            {
184                self.next_idx += 1;
185                continue;
186            }
187
188            // Map position of node to middle of block
189            let next_tgt = next0.map(|e| e as f32) + Vec3::new(0.5, 0.5, 0.0);
190            let closest_tgt = next_tgt
191                .map2(pos, |tgt, pos| pos.clamped(tgt.floor(), tgt.ceil()))
192                .xy()
193                .with_z(next_tgt.z);
194            // Determine whether we're close enough to the next to to consider it completed
195            let dist_sqrd = pos.xy().distance_squared(closest_tgt.xy());
196            if dist_sqrd
197                < (traversal_cfg.node_tolerance
198                    * if be_precise {
199                        0.5
200                    } else if traversal_cfg.in_liquid {
201                        2.5
202                    } else {
203                        1.0
204                    })
205                .powi(2)
206                && ((-1.0..=2.25).contains(&(pos.z - closest_tgt.z))
207                    || (traversal_cfg.in_liquid
208                        && pos.z < closest_tgt.z + 0.8
209                        && pos.z > closest_tgt.z))
210            {
211                // Node completed, move on to the next one
212                self.next_idx += 1;
213            } else {
214                // The next node hasn't been reached yet, use it as a target
215                break (next0, next1, next_tgt, be_precise);
216            }
217        };
218
219        fn gradient(line: LineSegment2<f32>) -> f32 {
220            let r = (line.start.y - line.end.y) / (line.start.x - line.end.x);
221            if r.is_nan() { 100000.0 } else { r }
222        }
223
224        fn intersect(a: LineSegment2<f32>, b: LineSegment2<f32>) -> Option<Vec2<f32>> {
225            let ma = gradient(a);
226            let mb = gradient(b);
227
228            let ca = a.start.y - ma * a.start.x;
229            let cb = b.start.y - mb * b.start.x;
230
231            if (ma - mb).abs() < 0.0001 || (ca - cb).abs() < 0.0001 {
232                None
233            } else {
234                let x = (cb - ca) / (ma - mb);
235                let y = ma * x + ca;
236
237                Some(Vec2::new(x, y))
238            }
239        }
240
241        let line_segments = [
242            LineSegment3 {
243                start: self
244                    .next_idx
245                    .checked_sub(2)
246                    .and_then(|i| self.path().nodes().get(i))
247                    .unwrap_or(&next0)
248                    .as_()
249                    + 0.5,
250                end: self
251                    .next_idx
252                    .checked_sub(1)
253                    .and_then(|i| self.path().nodes().get(i))
254                    .unwrap_or(&next0)
255                    .as_()
256                    + 0.5,
257            },
258            LineSegment3 {
259                start: self
260                    .next_idx
261                    .checked_sub(1)
262                    .and_then(|i| self.path().nodes().get(i))
263                    .unwrap_or(&next0)
264                    .as_()
265                    + 0.5,
266                end: next0.as_() + 0.5,
267            },
268            LineSegment3 {
269                start: next0.as_() + 0.5,
270                end: next1.as_() + 0.5,
271            },
272        ];
273
274        if line_segments
275            .iter()
276            .map(|ls| {
277                if self.next_idx > 1 {
278                    ls.projected_point(pos).distance_squared(pos)
279                } else {
280                    LineSegment2 {
281                        start: ls.start.xy(),
282                        end: ls.end.xy(),
283                    }
284                    .projected_point(pos.xy())
285                    .distance_squared(pos.xy())
286                }
287            })
288            .reduce(|a, b| a.min(b))
289            .is_some_and(|d| {
290                d > if traversal_cfg.in_liquid {
291                    traversal_cfg.node_tolerance * 5.0
292                } else {
293                    traversal_cfg.node_tolerance * 2.0
294                }
295                .powi(2)
296            })
297        {
298            return Err(TraverseStop::InvalidPath);
299        }
300
301        // We don't always want to aim for the centre of block since this can create
302        // jerky zig-zag movement. This function attempts to find a position
303        // inside a target block's area that aligned nicely with our velocity.
304        // This has a twofold benefit:
305        //
306        // 1. Entities can move at any angle when
307        // running on a flat surface
308        //
309        // 2. We don't have to search diagonals when
310        // pathfinding - cartesian positions are enough since this code will
311        // make the entity move smoothly along them
312        let corners = [
313            Vec2::new(0, 0),
314            Vec2::new(1, 0),
315            Vec2::new(1, 1),
316            Vec2::new(0, 1),
317            Vec2::new(0, 0), // Repeated start
318        ];
319
320        let vel_line = LineSegment2 {
321            start: pos.xy(),
322            end: pos.xy() + vel.xy() * 100.0,
323        };
324
325        let align = |block_pos: Vec3<i32>, precision: f32| {
326            let lerp_block =
327                |x, precision| Lerp::lerp(x, block_pos.xy().map(|e| e as f32), precision);
328
329            (0..4)
330                .filter_map(|i| {
331                    let edge_line = LineSegment2 {
332                        start: lerp_block(
333                            (block_pos.xy() + corners[i]).map(|e| e as f32),
334                            precision,
335                        ),
336                        end: lerp_block(
337                            (block_pos.xy() + corners[i + 1]).map(|e| e as f32),
338                            precision,
339                        ),
340                    };
341                    intersect(vel_line, edge_line).filter(|intersect| {
342                        intersect
343                            .clamped(
344                                block_pos.xy().map(|e| e as f32),
345                                block_pos.xy().map(|e| e as f32 + 1.0),
346                            )
347                            .distance_squared(*intersect)
348                            < 0.001
349                    })
350                })
351                .min_by_key(|intersect: &Vec2<f32>| {
352                    (intersect.distance_squared(vel_line.end) * 1000.0) as i32
353                })
354                .unwrap_or_else(|| {
355                    (0..2)
356                        .flat_map(|i| (0..2).map(move |j| Vec2::new(i, j)))
357                        .map(|rpos| block_pos + rpos)
358                        .map(|block_pos| {
359                            let block_posf = block_pos.xy().map(|e| e as f32);
360                            let proj = vel_line.projected_point(block_posf);
361                            let clamped = lerp_block(
362                                proj.clamped(
363                                    block_pos.xy().map(|e| e as f32),
364                                    block_pos.xy().map(|e| e as f32),
365                                ),
366                                precision,
367                            );
368
369                            (proj.distance_squared(clamped), clamped)
370                        })
371                        .min_by_key(|(d2, _)| (d2 * 1000.0) as i32)
372                        .unwrap()
373                        .1
374                })
375        };
376
377        let bez = CubicBezier2 {
378            start: pos.xy(),
379            ctrl0: pos.xy() + vel.xy().try_normalized().unwrap_or_default() * 1.0,
380            ctrl1: align(next0, 1.0),
381            end: align(next1, 1.0),
382        };
383
384        // Use a cubic spline of the next few targets to come up with a sensible target
385        // position. We want to use a position that gives smooth movement but is
386        // also accurate enough to avoid the agent getting stuck under ledges or
387        // falling off walls.
388        let next_dir = bez
389            .evaluate_derivative(0.85)
390            .try_normalized()
391            .unwrap_or_default();
392        let straight_factor = next_dir
393            .dot(vel.xy().try_normalized().unwrap_or(next_dir))
394            .max(0.0)
395            .powi(2);
396
397        let bez = CubicBezier2 {
398            start: pos.xy(),
399            ctrl0: pos.xy() + vel.xy().try_normalized().unwrap_or_default() * 1.0,
400            ctrl1: align(
401                next0,
402                (1.0 - if (next0.z as f32 - pos.z).abs() < 0.25 && !be_precise {
403                    straight_factor
404                } else {
405                    0.0
406                })
407                .max(0.1),
408            ),
409            end: align(next1, 1.0),
410        };
411
412        let tgt2d = bez.evaluate(if (next0.z as f32 - pos.z).abs() < 0.25 {
413            0.25
414        } else {
415            0.5
416        });
417        let tgt = if be_precise {
418            next_tgt
419        } else {
420            Vec3::from(tgt2d) + Vec3::unit_z() * next_tgt.z
421        };
422
423        Some((
424            tgt - pos,
425            // Control the entity's speed to hopefully stop us falling off walls on sharp
426            // corners. This code is very imperfect: it does its best but it
427            // can still fail for particularly fast entities.
428            1.0 - (traversal_cfg.slow_factor * (1.0 - straight_factor)).min(0.9),
429        ))
430        .filter(|(bearing, _)| bearing.z < 2.1)
431        .ok_or(TraverseStop::InvalidOutput)
432    }
433}
434
435#[derive(Default, Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord)]
436/// How long the path we're trying to compute should be.
437pub enum PathLength {
438    #[default]
439    Small,
440    Medium,
441    Long,
442    Longest,
443}
444
445#[derive(Default, Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord)]
446pub enum PathState {
447    /// There is no path.
448    #[default]
449    None,
450    /// A non-complete path.
451    Exhausted,
452    /// In progress of computing a path.
453    Pending,
454    /// A complete path.
455    Path,
456}
457
458/// A self-contained system that attempts to chase a moving target, only
459/// performing pathfinding if necessary
460#[derive(Default, Clone, Debug)]
461pub struct Chaser {
462    last_search_tgt: Option<Vec3<f32>>,
463    /// `bool` indicates whether the Route is a complete route to the target
464    ///
465    /// `Vec3` is the target end pos
466    route: Option<(Route, bool, Vec3<f32>)>,
467    /// We use this hasher (FxHash) because:
468    /// (1) we don't care about DDOS attacks (We can use FxHash);
469    /// (2) we want this to be constant across compiles because of hot-reloading
470    /// (Ruling out AAHash);
471    ///
472    /// The Vec3 is the astar's start position.
473    astar: Option<(Astar<Node, FxBuildHasher>, Vec3<f32>)>,
474    flee_from: Option<Vec3<f32>>,
475    /// Whether to allow consideration of longer paths, npc will stand still
476    /// while doing this.
477    path_length: PathLength,
478
479    /// The current state of the path.
480    path_state: PathState,
481
482    /// The last time the `chase` method was called.
483    last_update_time: Option<Time>,
484
485    /// (position, requested walk dir)
486    recent_states: VecDeque<(Time, Vec3<f32>, Vec3<f32>)>,
487}
488
489impl Chaser {
490    fn stuck_check(
491        &mut self,
492        pos: Vec3<f32>,
493        bearing: Vec3<f32>,
494        speed: f32,
495        time: &Time,
496    ) -> (Vec3<f32>, f32, bool) {
497        /// The min amount of cached items.
498        const MIN_CACHED_STATES: usize = 3;
499        /// The max amount of cached items.
500        const MAX_CACHED_STATES: usize = 10;
501        /// Cache over 1 second.
502        const CACHED_TIME_SPAN: f64 = 1.0;
503        const TOLERANCE: f32 = 0.2;
504
505        // We pop the first until there is only one element which was over
506        // `CACHED_TIME_SPAN` seconds ago.
507        while self.recent_states.len() > MIN_CACHED_STATES
508            && self
509                .recent_states
510                .get(1)
511                .is_some_and(|(t, ..)| time.0 - t.0 > CACHED_TIME_SPAN)
512        {
513            self.recent_states.pop_front();
514        }
515
516        if self.recent_states.len() < MAX_CACHED_STATES {
517            self.recent_states.push_back((*time, pos, bearing * speed));
518
519            if self.recent_states.len() >= MIN_CACHED_STATES
520                && self
521                    .recent_states
522                    .front()
523                    .is_some_and(|(t, ..)| time.0 - t.0 > CACHED_TIME_SPAN)
524                && (bearing * speed).magnitude_squared() > 0.01
525            {
526                let average_pos = self
527                    .recent_states
528                    .iter()
529                    .map(|(_, pos, _)| *pos)
530                    .sum::<Vec3<f32>>()
531                    * (1.0 / self.recent_states.len() as f32);
532                let max_distance_sqr = self
533                    .recent_states
534                    .iter()
535                    .map(|(_, pos, _)| pos.distance_squared(average_pos))
536                    .reduce(|a, b| a.max(b));
537
538                let average_speed = self
539                    .recent_states
540                    .iter()
541                    .zip(self.recent_states.iter().skip(1).map(|(t, ..)| *t))
542                    .map(|((t0, _, bearing), t1)| {
543                        bearing.magnitude_squared() * (t1.0 - t0.0).powi(2) as f32
544                    })
545                    .sum::<f32>()
546                    * (1.0 / self.recent_states.len() as f32);
547
548                let is_stuck =
549                    max_distance_sqr.is_some_and(|d| d < (average_speed * TOLERANCE).powi(2));
550
551                let bearing = if is_stuck {
552                    match rng().random_range(0..100u32) {
553                        0..10 => -bearing,
554                        10..20 => Vec3::new(bearing.y, bearing.x, bearing.z),
555                        20..30 => Vec3::new(-bearing.y, bearing.x, bearing.z),
556                        30..50 => {
557                            if let Some((route, ..)) = &mut self.route {
558                                route.next_idx = route.next_idx.saturating_sub(1);
559                            }
560
561                            bearing
562                        },
563                        50..60 => {
564                            if let Some((route, ..)) = &mut self.route {
565                                route.next_idx = route.next_idx.saturating_sub(2);
566                            }
567
568                            bearing
569                        },
570                        _ => bearing,
571                    }
572                } else {
573                    bearing
574                };
575
576                return (bearing, speed, is_stuck);
577            }
578        }
579        (bearing, speed, false)
580    }
581
582    fn reset(&mut self) {
583        self.route = None;
584        self.astar = None;
585        self.last_search_tgt = None;
586        self.path_length = Default::default();
587        self.flee_from = None;
588    }
589
590    /// Returns bearing and speed
591    /// Bearing is a `Vec3<f32>` dictating the direction of movement
592    /// Speed is an f32 between 0.0 and 1.0
593    pub fn chase<V>(
594        &mut self,
595        vol: &V,
596        pos: Vec3<f32>,
597        vel: Vec3<f32>,
598        tgt: Vec3<f32>,
599        traversal_cfg: TraversalConfig,
600        time: &Time,
601    ) -> Option<(Vec3<f32>, f32, bool)>
602    where
603        V: BaseVol<Vox = Block> + ReadVol,
604    {
605        span!(_guard, "chase", "Chaser::chase");
606        self.last_update_time = Some(*time);
607        // If we're already close to the target then there's nothing to do
608        if ((pos - tgt) * Vec3::new(1.0, 1.0, 2.0)).magnitude_squared()
609            < traversal_cfg.min_tgt_dist.powi(2)
610        {
611            self.reset();
612            return None;
613        }
614
615        let d = tgt.distance_squared(pos);
616
617        // Check if the current route is no longer valid.
618        if let Some(end) = self.route.as_ref().map(|(_, _, end)| *end)
619            && self.flee_from.is_none()
620            && self.path_length < PathLength::Longest
621            && d < tgt.distance_squared(end)
622        {
623            self.path_length = Default::default();
624            self.route = None;
625        }
626
627        // If we're closer than the designated `flee_from` position, we ignore
628        // that.
629        if self.flee_from.is_some_and(|p| d < p.distance_squared(tgt)) {
630            self.route = None;
631            self.flee_from = None;
632            self.astar = None;
633            self.path_length = Default::default();
634        }
635
636        // Find a route if we don't have one.
637        if self.route.is_none() {
638            // Reset astar if last tgt is too far from tgt.
639            if self
640                .last_search_tgt
641                .is_some_and(|last_tgt| tgt.distance_squared(last_tgt) > 2.0)
642            {
643                self.astar = None;
644            }
645            match find_path(
646                &mut self.astar,
647                vol,
648                pos,
649                tgt,
650                &traversal_cfg,
651                self.path_length,
652                self.flee_from,
653            ) {
654                PathResult::Pending => {
655                    self.path_state = PathState::Pending;
656                },
657                PathResult::None(path) => {
658                    self.path_state = PathState::None;
659                    self.route = Some((Route { path, next_idx: 0 }, false, tgt));
660                },
661                PathResult::Exhausted(path) => {
662                    self.path_state = PathState::Exhausted;
663                    self.route = Some((Route { path, next_idx: 0 }, false, tgt));
664                },
665                PathResult::Path(path, _) => {
666                    self.flee_from = None;
667                    self.path_state = PathState::Path;
668                    self.path_length = Default::default();
669                    self.route = Some((Route { path, next_idx: 0 }, true, tgt));
670                },
671            }
672
673            self.last_search_tgt = Some(tgt);
674        }
675
676        if let Some((route, ..)) = &mut self.route {
677            let res = route.traverse(vol, pos, vel, &traversal_cfg);
678
679            // None either means we're done, or can't continue, either way we don't care
680            // about that route anymore.
681            if let Err(e) = &res {
682                self.route = None;
683                match e {
684                    TraverseStop::InvalidOutput => {
685                        return Some(self.stuck_check(
686                            pos,
687                            (tgt - pos).try_normalized().unwrap_or(Vec3::unit_x()),
688                            1.0,
689                            time,
690                        ));
691                    },
692                    TraverseStop::InvalidPath => {
693                        // If the path is invalid, blocks along the path have most likely changed,
694                        // so reset the astar.
695                        self.astar = None;
696                    },
697                    TraverseStop::Done => match self.path_state {
698                        PathState::None => {
699                            return Some(self.stuck_check(
700                                pos,
701                                (tgt - pos).try_normalized().unwrap_or_default(),
702                                1.0,
703                                time,
704                            ));
705                        },
706                        PathState::Exhausted => {
707                            // Upgrade path length if path is exhausted and we're at the same
708                            // position.
709                            if self.astar.as_ref().is_some_and(|(.., start)| {
710                                start.distance_squared(pos) < traversal_cfg.node_tolerance.powi(2)
711                            }) {
712                                match self.path_length {
713                                    PathLength::Small => {
714                                        self.path_length = PathLength::Medium;
715                                    },
716                                    PathLength::Medium => {
717                                        self.path_length = PathLength::Long;
718                                    },
719                                    PathLength::Long => {
720                                        self.path_length = PathLength::Longest;
721                                    },
722                                    PathLength::Longest => {
723                                        self.flee_from = Some(pos);
724                                        self.astar = None;
725                                    },
726                                }
727                            } else {
728                                self.astar = None;
729                            }
730                        },
731                        PathState::Pending | PathState::Path => {},
732                    },
733                }
734            }
735
736            let (bearing, speed) = res.ok()?;
737
738            return Some(self.stuck_check(pos, bearing, speed, time));
739        }
740
741        None
742    }
743
744    pub fn get_route(&self) -> Option<&Route> { self.route.as_ref().map(|(r, ..)| r) }
745
746    pub fn last_target(&self) -> Option<Vec3<f32>> { self.last_search_tgt }
747
748    pub fn state(&self) -> (PathLength, PathState) { (self.path_length, self.path_state) }
749
750    pub fn last_update_time(&self) -> Time {
751        self.last_update_time.unwrap_or(Time(f64::NEG_INFINITY))
752    }
753}
754
755fn walkable<V>(vol: &V, pos: Vec3<i32>, is_target_loaded: bool) -> bool
756where
757    V: BaseVol<Vox = Block> + ReadVol,
758{
759    let mut below_z = 1;
760    // We loop downwards
761    let below = loop {
762        if let Some(block) = vol.get(pos - Vec3::unit_z() * below_z).ok().copied() {
763            if block.is_solid() || block.is_liquid() {
764                break block;
765            }
766
767            below_z += 1;
768
769            if below_z > Block::MAX_HEIGHT.ceil() as i32 {
770                break Block::empty();
771            }
772        } else if is_target_loaded {
773            break Block::empty();
774        } else {
775            // If not loaded assume we can walk there.
776            break Block::new(crate::terrain::BlockKind::Misc, Default::default());
777        }
778    };
779
780    let a = vol.get(pos).ok().copied().unwrap_or_else(Block::empty);
781    let b = vol
782        .get(pos + Vec3::unit_z())
783        .ok()
784        .copied()
785        .unwrap_or_else(Block::empty);
786
787    let on_ground = (below_z == 1 && below.is_filled())
788        || below.get_sprite().is_some_and(|sprite| {
789            sprite
790                .solid_height()
791                .is_some_and(|h| ((below_z - 1) as f32) < h && h <= below_z as f32)
792        });
793    let in_liquid = a.is_liquid();
794    (on_ground || in_liquid) && !a.is_solid() && !b.is_solid()
795}
796
797#[derive(Copy, Clone, PartialEq, Eq, Hash, Debug)]
798pub struct Node {
799    pos: Vec3<i32>,
800    last_dir: Vec2<i32>,
801    last_dir_count: u32,
802}
803
804/// Attempt to search for a path to a target, returning the path (if one was
805/// found) and whether it is complete (reaches the target)
806///
807/// If `flee_from` is `Some` this will attempt to both walk away from that
808/// position and towards the target.
809fn find_path<V>(
810    astar: &mut Option<(Astar<Node, FxBuildHasher>, Vec3<f32>)>,
811    vol: &V,
812    startf: Vec3<f32>,
813    endf: Vec3<f32>,
814    traversal_cfg: &TraversalConfig,
815    path_length: PathLength,
816    flee_from: Option<Vec3<f32>>,
817) -> PathResult<Vec3<i32>>
818where
819    V: BaseVol<Vox = Block> + ReadVol,
820{
821    let is_walkable = |pos: &Vec3<i32>| walkable(vol, *pos, traversal_cfg.is_target_loaded);
822    let get_walkable_z = |pos| {
823        let mut z_incr = 0;
824        for _ in 0..32 {
825            let test_pos = pos + Vec3::unit_z() * z_incr;
826            if is_walkable(&test_pos) {
827                return Some(test_pos);
828            }
829            z_incr = -z_incr + i32::from(z_incr <= 0);
830        }
831        None
832    };
833
834    // Find walkable ground for start and end.
835    let (start, end) = match (
836        get_walkable_z(startf.map(|e| e.floor() as i32)),
837        get_walkable_z(endf.map(|e| e.floor() as i32)),
838    ) {
839        (Some(start), Some(end)) => (start, end),
840
841        // Special case for partially loaded path finding
842        (Some(start), None) if !traversal_cfg.is_target_loaded => {
843            (start, endf.map(|e| e.floor() as i32))
844        },
845
846        _ => return PathResult::None(Path::default()),
847    };
848
849    let heuristic = |node: &Node| {
850        let diff = end.as_::<f32>() - node.pos.as_::<f32>();
851        let d = diff.magnitude();
852
853        d - flee_from.map_or(0.0, |p| {
854            let ndiff = p - node.pos.as_::<f32>() - 0.5;
855            let nd = ndiff.magnitude();
856            nd.sqrt() * ((diff / d).dot(ndiff / nd) + 0.1).max(0.0) * 10.0
857        })
858    };
859    let transition = |a: Node, b: Node| {
860        1.0
861            // Discourage travelling in the same direction for too long: this encourages
862            // turns to be spread out along a path, more closely approximating a straight
863            // line toward the target.
864            + b.last_dir_count as f32 * 0.01
865            // Penalise jumping
866            + (b.pos.z - a.pos.z + 1).max(0) as f32 * 2.0
867    };
868    let neighbors = |node: &Node| {
869        let node = *node;
870        let pos = node.pos;
871        const DIRS: [Vec3<i32>; 9] = [
872            Vec3::new(0, 1, 0), // Forward
873            Vec3::new(0, 1, 1), // Forward upward
874            // Vec3::new(0, 1, -1),  // Forward downward
875            // Vec3::new(0, 1, -2),  // Forward downwardx2
876            Vec3::new(1, 0, 0), // Right
877            Vec3::new(1, 0, 1), // Right upward
878            // Vec3::new(1, 0, -1),  // Right downward
879            // Vec3::new(1, 0, -2),  // Right downwardx2
880            Vec3::new(0, -1, 0), // Backwards
881            Vec3::new(0, -1, 1), // Backward Upward
882            // Vec3::new(0, -1, -1), // Backward downward
883            // Vec3::new(0, -1, -2), // Backward downwardx2
884            Vec3::new(-1, 0, 0), // Left
885            Vec3::new(-1, 0, 1), // Left upward
886            // Vec3::new(-1, 0, -1), // Left downward
887            // Vec3::new(-1, 0, -2), // Left downwardx2
888            Vec3::new(0, 0, -1), // Downwards
889        ];
890
891        const JUMPS: [Vec3<i32>; 4] = [
892            Vec3::new(0, 1, 2),  // Forward Upwardx2
893            Vec3::new(1, 0, 2),  // Right Upwardx2
894            Vec3::new(0, -1, 2), // Backward Upwardx2
895            Vec3::new(-1, 0, 2), // Left Upwardx2
896        ];
897
898        /// The cost of falling a block.
899        const FALL_COST: f32 = 1.5;
900
901        let walkable = [
902            (is_walkable(&(pos + Vec3::new(1, 0, 0))), Vec3::new(1, 0, 0)),
903            (
904                is_walkable(&(pos + Vec3::new(-1, 0, 0))),
905                Vec3::new(-1, 0, 0),
906            ),
907            (is_walkable(&(pos + Vec3::new(0, 1, 0))), Vec3::new(0, 1, 0)),
908            (
909                is_walkable(&(pos + Vec3::new(0, -1, 0))),
910                Vec3::new(0, -1, 0),
911            ),
912        ];
913
914        // Discourage walking alog walls/edges.
915        let edge_cost = if path_length < PathLength::Medium {
916            walkable.iter().any(|(w, _)| !*w) as i32 as f32
917        } else {
918            0.0
919        };
920
921        // const DIAGONALS: [(Vec3<i32>, [usize; 2]); 8] = [
922        //     (Vec3::new(1, 1, 0), [0, 2]),
923        //     (Vec3::new(-1, 1, 0), [1, 2]),
924        //     (Vec3::new(1, -1, 0), [0, 3]),
925        //     (Vec3::new(-1, -1, 0), [1, 3]),
926        //     (Vec3::new(1, 1, 1), [0, 2]),
927        //     (Vec3::new(-1, 1, 1), [1, 2]),
928        //     (Vec3::new(1, -1, 1), [0, 3]),
929        //     (Vec3::new(-1, -1, 1), [1, 3]),
930        // ];
931
932        DIRS.iter()
933            .chain(
934                Some(JUMPS.iter())
935                    .filter(|_| {
936                        vol.get(pos - Vec3::unit_z())
937                            .map(|b| !b.is_liquid())
938                            .unwrap_or(traversal_cfg.is_target_loaded)
939                            || traversal_cfg.can_climb
940                            || traversal_cfg.can_fly
941                    })
942                    .into_iter()
943                    .flatten(),
944            )
945            .map(move |dir| (pos, dir))
946            .filter(move |(pos, dir)| {
947                (traversal_cfg.can_fly || is_walkable(pos) && is_walkable(&(*pos + **dir)))
948                    && ((dir.z < 1
949                        || vol
950                            .get(pos + Vec3::unit_z() * 2)
951                            .map(|b| !b.is_solid())
952                            .unwrap_or(traversal_cfg.is_target_loaded))
953                        && (dir.z < 2
954                            || vol
955                                .get(pos + Vec3::unit_z() * 3)
956                                .map(|b| !b.is_solid())
957                                .unwrap_or(traversal_cfg.is_target_loaded))
958                        && (dir.z >= 0
959                            || vol
960                                .get(pos + *dir + Vec3::unit_z() * 2)
961                                .map(|b| !b.is_solid())
962                                .unwrap_or(traversal_cfg.is_target_loaded)))
963            })
964            .map(move |(pos, dir)| {
965                let next_node = Node {
966                    pos: pos + dir,
967                    last_dir: dir.xy(),
968                    last_dir_count: if node.last_dir == dir.xy() {
969                        node.last_dir_count + 1
970                    } else {
971                        0
972                    },
973                };
974
975                (
976                    next_node,
977                    transition(node, next_node) + if dir.z == 0 { edge_cost } else { 0.0 },
978                )
979            })
980            // Falls
981            .chain(walkable.into_iter().filter_map(move |(w, dir)| {
982                let pos = pos + dir;
983                if w ||
984                    vol.get(pos).map(|b| b.is_solid()).unwrap_or(true) ||
985                    vol.get(pos + Vec3::unit_z()).map(|b| b.is_solid()).unwrap_or(true) {
986                    return None;
987                }
988
989                let down = (1..12).find(|i| is_walkable(&(pos - Vec3::unit_z() * *i)))?;
990
991                let next_node = Node {
992                    pos: pos - Vec3::unit_z() * down,
993                    last_dir: dir.xy(),
994                    last_dir_count: 0,
995                };
996
997                // Falling costs a lot.
998                Some((next_node, match down {
999                    1..=2 => {
1000                        transition(node, next_node)
1001                    }
1002                    _ => FALL_COST * (down - 2) as f32,
1003                }))
1004            }))
1005        // .chain(
1006        //     DIAGONALS
1007        //         .iter()
1008        //         .filter(move |(dir, [a, b])| {
1009        //             is_walkable(&(pos + *dir)) && walkable[*a] &&
1010        // walkable[*b]         })
1011        //         .map(move |(dir, _)| pos + *dir),
1012        // )
1013    };
1014
1015    let satisfied = |node: &Node| node.pos == end;
1016
1017    if astar
1018        .as_ref()
1019        .is_some_and(|(_, start)| start.distance_squared(startf) > 4.0)
1020    {
1021        *astar = None;
1022    }
1023    let max_iters = match path_length {
1024        PathLength::Small => 500,
1025        PathLength::Medium => 5000,
1026        PathLength::Long => 25_000,
1027        PathLength::Longest => 75_000,
1028    };
1029
1030    let (astar, _) = astar.get_or_insert_with(|| {
1031        (
1032            Astar::new(
1033                max_iters,
1034                Node {
1035                    pos: start,
1036                    last_dir: Vec2::zero(),
1037                    last_dir_count: 0,
1038                },
1039                FxBuildHasher::default(),
1040            ),
1041            startf,
1042        )
1043    });
1044
1045    astar.set_max_iters(max_iters);
1046
1047    let path_result = astar.poll(
1048        match path_length {
1049            PathLength::Small => 250,
1050            PathLength::Medium => 400,
1051            PathLength::Long => 500,
1052            PathLength::Longest => 750,
1053        },
1054        heuristic,
1055        neighbors,
1056        satisfied,
1057    );
1058
1059    path_result.map(|path| path.nodes.into_iter().map(|n| n.pos).collect())
1060}
1061// Enable when airbraking/sensible flight is a thing
1062#[cfg(feature = "rrt_pathfinding")]
1063fn find_air_path<V>(
1064    vol: &V,
1065    startf: Vec3<f32>,
1066    endf: Vec3<f32>,
1067    traversal_cfg: &TraversalConfig,
1068) -> (Option<Path<Vec3<i32>>>, bool)
1069where
1070    V: BaseVol<Vox = Block> + ReadVol,
1071{
1072    let radius = traversal_cfg.node_tolerance;
1073    let total_dist_sqrd = startf.distance_squared(endf);
1074    // First check if a straight line path works
1075    if vol
1076        .ray(startf + Vec3::unit_z(), endf + Vec3::unit_z())
1077        .until(Block::is_opaque)
1078        .cast()
1079        .0
1080        .powi(2)
1081        >= total_dist_sqrd
1082    {
1083        let path = vec![endf.map(|e| e.floor() as i32)];
1084        let connect = true;
1085        (Some(path.into_iter().collect()), connect)
1086    // Else use RRTs
1087    } else {
1088        let is_traversable = |start: &Vec3<f32>, end: &Vec3<f32>| {
1089            vol.ray(*start, *end)
1090                .until(Block::is_solid)
1091                .cast()
1092                .0
1093                .powi(2)
1094                > (*start).distance_squared(*end)
1095            //vol.get(*pos).ok().copied().unwrap_or_else(Block::empty).
1096            // is_fluid();
1097        };
1098        informed_rrt_connect(vol, startf, endf, is_traversable, radius)
1099    }
1100}
1101
1102/// Attempts to find a path from a start to the end using an informed
1103/// RRT-Connect algorithm. A point is sampled from a bounding spheroid
1104/// between the start and end. Two separate rapidly exploring random
1105/// trees extend toward the sampled point. Nodes are stored in k-d trees
1106/// for quicker nearest node calculations. Points are sampled until the
1107/// trees connect. A final path is then reconstructed from the nodes.
1108/// This pathfinding algorithm is more appropriate for 3D pathfinding
1109/// with wider gaps, such as flying through a forest than for terrain
1110/// with narrow gaps, such as navigating a maze.
1111/// Returns a path and whether that path is complete or not.
1112#[cfg(feature = "rrt_pathfinding")]
1113fn informed_rrt_connect<V>(
1114    vol: &V,
1115    startf: Vec3<f32>,
1116    endf: Vec3<f32>,
1117    is_valid_edge: impl Fn(&Vec3<f32>, &Vec3<f32>) -> bool,
1118    radius: f32,
1119) -> (Option<Path<Vec3<i32>>>, bool)
1120where
1121    V: BaseVol<Vox = Block> + ReadVol,
1122{
1123    const MAX_POINTS: usize = 7000;
1124    let mut path = Vec::new();
1125
1126    // Each tree has a vector of nodes
1127    let mut node_index1: usize = 0;
1128    let mut node_index2: usize = 0;
1129    let mut nodes1 = Vec::new();
1130    let mut nodes2 = Vec::new();
1131
1132    // The parents hashmap stores nodes and their parent nodes as pairs to
1133    // retrace the complete path once the two RRTs connect
1134    let mut parents1 = HashMap::new();
1135    let mut parents2 = HashMap::new();
1136
1137    // The path vector stores the path from the appropriate terminal to the
1138    // connecting node or vice versa
1139    let mut path1 = Vec::new();
1140    let mut path2 = Vec::new();
1141
1142    // K-d trees are used to find the closest nodes rapidly
1143    let mut kdtree1: KdTree<f32, usize, 3, 32, u32> = KdTree::with_capacity(MAX_POINTS);
1144    let mut kdtree2: KdTree<f32, usize, 3, 32, u32> = KdTree::with_capacity(MAX_POINTS);
1145
1146    // Add the start as the first node of the first k-d tree
1147    kdtree1.add(&[startf.x, startf.y, startf.z], node_index1);
1148    nodes1.push(startf);
1149    node_index1 += 1;
1150
1151    // Add the end as the first node of the second k-d tree
1152    kdtree2.add(&[endf.x, endf.y, endf.z], node_index2);
1153    nodes2.push(endf);
1154    node_index2 += 1;
1155
1156    let mut connection1_idx = 0;
1157    let mut connection2_idx = 0;
1158
1159    let mut connect = false;
1160
1161    // Scalar non-dimensional value that is proportional to the size of the
1162    // sample spheroid volume. This increases in value until a path is found.
1163    let mut search_parameter = 0.01;
1164
1165    // Maximum of MAX_POINTS iterations
1166    for _i in 0..MAX_POINTS {
1167        if connect {
1168            break;
1169        }
1170
1171        // Sample a point on the bounding spheroid
1172        let (sampled_point1, sampled_point2) = {
1173            let point = point_on_prolate_spheroid(startf, endf, search_parameter);
1174            (point, point)
1175        };
1176
1177        // Find the nearest nodes to the the sampled point
1178        let nearest_index1 = kdtree1
1179            .nearest_one::<SquaredEuclidean>(&[
1180                sampled_point1.x,
1181                sampled_point1.y,
1182                sampled_point1.z,
1183            ])
1184            .item;
1185        let nearest_index2 = kdtree2
1186            .nearest_one::<SquaredEuclidean>(&[
1187                sampled_point2.x,
1188                sampled_point2.y,
1189                sampled_point2.z,
1190            ])
1191            .item;
1192        let nearest1 = nodes1[nearest_index1];
1193        let nearest2 = nodes2[nearest_index2];
1194
1195        // Extend toward the sampled point from the nearest node of each tree
1196        let new_point1 = nearest1 + (sampled_point1 - nearest1).normalized().map(|a| a * radius);
1197        let new_point2 = nearest2 + (sampled_point2 - nearest2).normalized().map(|a| a * radius);
1198
1199        // Ensure the new nodes are valid/traversable
1200        if is_valid_edge(&nearest1, &new_point1) {
1201            kdtree1.add(&[new_point1.x, new_point1.y, new_point1.z], node_index1);
1202            nodes1.push(new_point1);
1203            parents1.insert(node_index1, nearest_index1);
1204            node_index1 += 1;
1205            // Check if the trees connect
1206            let NearestNeighbour {
1207                distance: check,
1208                item: index,
1209            } = kdtree2.nearest_one::<SquaredEuclidean>(&[
1210                new_point1.x,
1211                new_point1.y,
1212                new_point1.z,
1213            ]);
1214            if check < radius {
1215                let connection = nodes2[index];
1216                connection2_idx = index;
1217                nodes1.push(connection);
1218                connection1_idx = nodes1.len() - 1;
1219                parents1.insert(node_index1, node_index1 - 1);
1220                connect = true;
1221            }
1222        }
1223
1224        // Repeat the validity check for the second tree
1225        if is_valid_edge(&nearest2, &new_point2) {
1226            kdtree2.add(&[new_point2.x, new_point2.y, new_point1.z], node_index2);
1227            nodes2.push(new_point2);
1228            parents2.insert(node_index2, nearest_index2);
1229            node_index2 += 1;
1230            // Again check for a connection
1231            let NearestNeighbour {
1232                distance: check,
1233                item: index,
1234            } = kdtree1.nearest_one::<SquaredEuclidean>(&[
1235                new_point2.x,
1236                new_point2.y,
1237                new_point1.z,
1238            ]);
1239            if check < radius {
1240                let connection = nodes1[index];
1241                connection1_idx = index;
1242                nodes2.push(connection);
1243                connection2_idx = nodes2.len() - 1;
1244                parents2.insert(node_index2, node_index2 - 1);
1245                connect = true;
1246            }
1247        }
1248        // Increase the search parameter to widen the sample volume
1249        search_parameter += 0.02;
1250    }
1251
1252    if connect {
1253        // Construct paths from the connection node to the start and end
1254        let mut current_node_index1 = connection1_idx;
1255        while current_node_index1 > 0 {
1256            current_node_index1 = *parents1.get(&current_node_index1).unwrap_or(&0);
1257            path1.push(nodes1[current_node_index1].map(|e| e.floor() as i32));
1258        }
1259        let mut current_node_index2 = connection2_idx;
1260        while current_node_index2 > 0 {
1261            current_node_index2 = *parents2.get(&current_node_index2).unwrap_or(&0);
1262            path2.push(nodes2[current_node_index2].map(|e| e.floor() as i32));
1263        }
1264        // Join the two paths together in the proper order and remove duplicates
1265        path1.pop();
1266        path1.reverse();
1267        path.append(&mut path1);
1268        path.append(&mut path2);
1269        path.dedup();
1270    } else {
1271        // If the trees did not connect, construct a path from the start to
1272        // the closest node to the end
1273        let mut current_node_index1 = kdtree1
1274            .nearest_one::<SquaredEuclidean>(&[endf.x, endf.y, endf.z])
1275            .item;
1276        // Attempt to pick a node other than the start node
1277        for _i in 0..3 {
1278            if current_node_index1 == 0
1279                || nodes1[current_node_index1].distance_squared(startf) < 4.0
1280            {
1281                if let Some(index) = parents1.values().choose(&mut rng()) {
1282                    current_node_index1 = *index;
1283                } else {
1284                    break;
1285                }
1286            } else {
1287                break;
1288            }
1289        }
1290        path1.push(nodes1[current_node_index1].map(|e| e.floor() as i32));
1291        // Construct the path
1292        while current_node_index1 != 0 && nodes1[current_node_index1].distance_squared(startf) > 4.0
1293        {
1294            current_node_index1 = *parents1.get(&current_node_index1).unwrap_or(&0);
1295            path1.push(nodes1[current_node_index1].map(|e| e.floor() as i32));
1296        }
1297
1298        path1.reverse();
1299        path.append(&mut path1);
1300    }
1301    let mut new_path = Vec::new();
1302    let mut node = path[0];
1303    new_path.push(node);
1304    let mut node_idx = 0;
1305    let num_nodes = path.len();
1306    let end = path[num_nodes - 1];
1307    while node != end {
1308        let next_idx = if node_idx + 4 > num_nodes - 1 {
1309            num_nodes - 1
1310        } else {
1311            node_idx + 4
1312        };
1313        let next_node = path[next_idx];
1314        let start_pos = node.map(|e| e as f32 + 0.5);
1315        let end_pos = next_node.map(|e| e as f32 + 0.5);
1316        if vol
1317            .ray(start_pos, end_pos)
1318            .until(Block::is_solid)
1319            .cast()
1320            .0
1321            .powi(2)
1322            > (start_pos).distance_squared(end_pos)
1323        {
1324            node_idx = next_idx;
1325            new_path.push(next_node);
1326        } else {
1327            node_idx += 1;
1328        }
1329        node = path[node_idx];
1330    }
1331    path = new_path;
1332    (Some(path.into_iter().collect()), connect)
1333}
1334
1335/// Returns a random point within a radially symmetrical ellipsoid with given
1336/// foci and a `search parameter` to determine the size of the ellipse beyond
1337/// the foci. Technically the point is within a prolate spheroid translated and
1338/// rotated to the proper place in cartesian space.
1339/// The search_parameter is a float that relates to the length of the string for
1340/// a two dimensional ellipse or the size of the ellipse beyond the foci. In
1341/// this case that analogy still holds as the ellipse is radially symmetrical
1342/// along the axis between the foci. The value of the search parameter must be
1343/// greater than zero. In order to increase the sample area, the
1344/// search_parameter should be increased linearly as the search continues.
1345#[cfg(feature = "rrt_pathfinding")]
1346pub fn point_on_prolate_spheroid(
1347    focus1: Vec3<f32>,
1348    focus2: Vec3<f32>,
1349    search_parameter: f32,
1350) -> Vec3<f32> {
1351    let mut rng = rng();
1352    // Uniform distribution
1353    let range = Uniform::from(0.0..1.0);
1354
1355    // Midpoint is used as the local origin
1356    let midpoint = 0.5 * (focus1 + focus2);
1357    // Radius between the start and end of the path
1358    let radius: f32 = focus1.distance(focus2);
1359    // The linear eccentricity of an ellipse is the distance from the origin to a
1360    // focus A prolate spheroid is a half-ellipse rotated for a full revolution
1361    // which is why ellipse variables are used frequently in this function
1362    let linear_eccentricity: f32 = 0.5 * radius;
1363
1364    // For an ellipsoid, three variables determine the shape: a, b, and c.
1365    // These are the distance from the center/origin to the surface on the
1366    // x, y, and z axes, respectively.
1367    // For a prolate spheroid a and b are equal.
1368    // c is determined by adding the search parameter to the linear eccentricity.
1369    // As the search parameter increases the size of the spheroid increases
1370    let c: f32 = linear_eccentricity + search_parameter;
1371    // The width is calculated to prioritize increasing width over length of
1372    // the ellipsoid
1373    let a: f32 = (c.powi(2) - linear_eccentricity.powi(2)).powf(0.5);
1374    // The width should be the same in both the x and y directions
1375    let b: f32 = a;
1376
1377    // The parametric spherical equation for an ellipsoid measuring from the
1378    // center point is as follows:
1379    // x = a * cos(theta) * cos(lambda)
1380    // y = b * cos(theta) * sin(lambda)
1381    // z = c * sin(theta)
1382    //
1383    // where     -0.5 * PI <= theta <= 0.5 * PI
1384    // and       0.0 <= lambda < 2.0 * PI
1385    //
1386    // Select these two angles using the uniform distribution defined at the
1387    // beginning of the function from 0.0 to 1.0
1388    let rtheta: f32 = PI * range.sample(&mut rng) - 0.5 * PI;
1389    let lambda: f32 = 2.0 * PI * range.sample(&mut rng);
1390    // Select a point on the surface of the ellipsoid
1391    let point = Vec3::new(
1392        a * rtheta.cos() * lambda.cos(),
1393        b * rtheta.cos() * lambda.sin(),
1394        c * rtheta.sin(),
1395    );
1396    // NOTE: Theoretically we should sample a point within the spheroid
1397    // requiring selecting a point along the radius. In my tests selecting
1398    // a point *on the surface* of the spheroid results in sampling that is
1399    // "good enough". The following code is commented out to reduce expense.
1400    //let surface_point = Vec3::new(a * rtheta.cos() * lambda.cos(), b *
1401    // rtheta.cos() * lambda.sin(), c * rtheta.sin()); let magnitude =
1402    // surface_point.magnitude(); let direction = surface_point.normalized();
1403    //// Randomly select a point along the vector to the previously selected surface
1404    //// point using the uniform distribution
1405    //let point = magnitude * range.sample(&mut rng) * direction;
1406
1407    // Now that a point has been selected in local space, it must be rotated and
1408    // translated into global coordinates
1409    // NOTE: Don't rotate about the z axis as the point is already randomly
1410    // selected about the z axis
1411    //let dx = focus2.x - focus1.x;
1412    //let dy = focus2.y - focus1.y;
1413    let dz = focus2.z - focus1.z;
1414    // Phi and theta are the angles from the x axis in the x-y plane and from
1415    // the z axis, respectively. (As found in spherical coordinates)
1416    // These angles are used to rotate the random point in the spheroid about
1417    // the local origin
1418    //
1419    // Rotate about z axis by phi
1420    //let phi: f32 = if dx.abs() > 0.0 {
1421    //    (dy / dx).atan()
1422    //} else {
1423    //    0.5 * PI
1424    //};
1425    // This is unnecessary as rtheta is randomly selected between 0.0 and 2.0 * PI
1426    // let rot_z_mat = Mat3::new(phi.cos(), -1.0 * phi.sin(), 0.0, phi.sin(),
1427    // phi.cos(), 0.0, 0.0, 0.0, 1.0);
1428
1429    // Rotate about perpendicular vector in the xy plane by theta
1430    let theta: f32 = if radius > 0.0 {
1431        (dz / radius).acos()
1432    } else {
1433        0.0
1434    };
1435    // Vector from focus1 to focus2
1436    let r_vec = focus2 - focus1;
1437    // Perpendicular vector in xy plane
1438    let perp_vec = Vec3::new(-1.0 * r_vec.y, r_vec.x, 0.0).normalized();
1439    let l = perp_vec.x;
1440    let m = perp_vec.y;
1441    let n = perp_vec.z;
1442    // Rotation matrix for rotation about a vector
1443    let rot_2_mat = Mat3::new(
1444        l * l * (1.0 - theta.cos()),
1445        m * l * (1.0 - theta.cos()) - n * theta.sin(),
1446        n * l * (1.0 - theta.cos()) + m * theta.sin(),
1447        l * m * (1.0 - theta.cos()) + n * theta.sin(),
1448        m * m * (1.0 - theta.cos()) + theta.cos(),
1449        n * m * (1.0 - theta.cos()) - l * theta.sin(),
1450        l * n * (1.0 - theta.cos()) - m * theta.sin(),
1451        m * n * (1.0 - theta.cos()) + l * theta.sin(),
1452        n * n * (1.0 - theta.cos()) + theta.cos(),
1453    );
1454
1455    // Get the global coordinates of the point by rotating and adding the origin
1456    // rot_z_mat is unneeded due to the random rotation defined by lambda
1457    // let global_coords = midpoint + rot_2_mat * (rot_z_mat * point);
1458    midpoint + rot_2_mat * point
1459}