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}; use 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#[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#[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 pub node_tolerance: f32,
89 pub slow_factor: f32,
92 pub on_ground: bool,
94 pub in_liquid: bool,
96 pub min_tgt_dist: f32,
98 pub can_climb: bool,
100 pub can_fly: bool,
102 pub vectored_propulsion: bool,
104 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 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 let next0 = self.next(0).ok_or(TraverseStop::Done)?;
148 let next1 = self.next(1).unwrap_or(next0);
149
150 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 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 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 let be_precise =
176 open_space_nearby || wall_nearby || (pos.z - next0.z as f32).abs() > 1.0;
177
178 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 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 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 self.next_idx += 1;
213 } else {
214 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 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), ];
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 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 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)]
436pub 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 #[default]
449 None,
450 Exhausted,
452 Pending,
454 Path,
456}
457
458#[derive(Default, Clone, Debug)]
461pub struct Chaser {
462 last_search_tgt: Option<Vec3<f32>>,
463 route: Option<(Route, bool, Vec3<f32>)>,
467 astar: Option<(Astar<Node, FxBuildHasher>, Vec3<f32>)>,
474 flee_from: Option<Vec3<f32>>,
475 path_length: PathLength,
478
479 path_state: PathState,
481
482 last_update_time: Option<Time>,
484
485 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 const MIN_CACHED_STATES: usize = 3;
499 const MAX_CACHED_STATES: usize = 10;
501 const CACHED_TIME_SPAN: f64 = 1.0;
503 const TOLERANCE: f32 = 0.2;
504
505 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 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 ((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 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 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 if self.route.is_none() {
638 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 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 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 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 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 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
804fn 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 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 (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 + b.last_dir_count as f32 * 0.01
865 + (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), Vec3::new(0, 1, 1), Vec3::new(1, 0, 0), Vec3::new(1, 0, 1), Vec3::new(0, -1, 0), Vec3::new(0, -1, 1), Vec3::new(-1, 0, 0), Vec3::new(-1, 0, 1), Vec3::new(0, 0, -1), ];
890
891 const JUMPS: [Vec3<i32>; 4] = [
892 Vec3::new(0, 1, 2), Vec3::new(1, 0, 2), Vec3::new(0, -1, 2), Vec3::new(-1, 0, 2), ];
897
898 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 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 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 .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 Some((next_node, match down {
999 1..=2 => {
1000 transition(node, next_node)
1001 }
1002 _ => FALL_COST * (down - 2) as f32,
1003 }))
1004 }))
1005 };
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#[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 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 {
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 };
1098 informed_rrt_connect(vol, startf, endf, is_traversable, radius)
1099 }
1100}
1101
1102#[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 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 let mut parents1 = HashMap::new();
1135 let mut parents2 = HashMap::new();
1136
1137 let mut path1 = Vec::new();
1140 let mut path2 = Vec::new();
1141
1142 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 kdtree1.add(&[startf.x, startf.y, startf.z], node_index1);
1148 nodes1.push(startf);
1149 node_index1 += 1;
1150
1151 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 let mut search_parameter = 0.01;
1164
1165 for _i in 0..MAX_POINTS {
1167 if connect {
1168 break;
1169 }
1170
1171 let (sampled_point1, sampled_point2) = {
1173 let point = point_on_prolate_spheroid(startf, endf, search_parameter);
1174 (point, point)
1175 };
1176
1177 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 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 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 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 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 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 search_parameter += 0.02;
1250 }
1251
1252 if connect {
1253 let mut current_node_index1 = connection1_idx;
1255 while current_node_index1 > 0 {
1256 current_node_index1 = *parents1.get(¤t_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(¤t_node_index2).unwrap_or(&0);
1262 path2.push(nodes2[current_node_index2].map(|e| e.floor() as i32));
1263 }
1264 path1.pop();
1266 path1.reverse();
1267 path.append(&mut path1);
1268 path.append(&mut path2);
1269 path.dedup();
1270 } else {
1271 let mut current_node_index1 = kdtree1
1274 .nearest_one::<SquaredEuclidean>(&[endf.x, endf.y, endf.z])
1275 .item;
1276 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 while current_node_index1 != 0 && nodes1[current_node_index1].distance_squared(startf) > 4.0
1293 {
1294 current_node_index1 = *parents1.get(¤t_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#[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 let range = Uniform::from(0.0..1.0);
1354
1355 let midpoint = 0.5 * (focus1 + focus2);
1357 let radius: f32 = focus1.distance(focus2);
1359 let linear_eccentricity: f32 = 0.5 * radius;
1363
1364 let c: f32 = linear_eccentricity + search_parameter;
1371 let a: f32 = (c.powi(2) - linear_eccentricity.powi(2)).powf(0.5);
1374 let b: f32 = a;
1376
1377 let rtheta: f32 = PI * range.sample(&mut rng) - 0.5 * PI;
1389 let lambda: f32 = 2.0 * PI * range.sample(&mut rng);
1390 let point = Vec3::new(
1392 a * rtheta.cos() * lambda.cos(),
1393 b * rtheta.cos() * lambda.sin(),
1394 c * rtheta.sin(),
1395 );
1396 let dz = focus2.z - focus1.z;
1414 let theta: f32 = if radius > 0.0 {
1431 (dz / radius).acos()
1432 } else {
1433 0.0
1434 };
1435 let r_vec = focus2 - focus1;
1437 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 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 midpoint + rot_2_mat * point
1459}