steel_core/entity/ai/
path.rs

1//! Path type, cache, and malus state used by vanilla mob pathfinding.
2
3use steel_utils::{BlockPos, BlockStateId, PackedBlockPos};
4
5use crate::entity::ai::node::Node;
6use crate::entity::ai::walk::WalkPathEvaluator;
7use crate::world::LevelReader;
8
9const PATH_TYPE_CACHE_SIZE: usize = 4096;
10const PATH_TYPE_CACHE_MASK: usize = PATH_TYPE_CACHE_SIZE - 1;
11
12/// Vanilla `PathType`.
13///
14/// Steel stores per-mob overrides in a fixed array keyed by this enum instead
15/// of Java's enum map. The observable path cost result is the same, while the
16/// hot path remains cache-local.
17#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
18#[repr(u8)]
19pub enum PathType {
20    Blocked,
21    Open,
22    Walkable,
23    WalkableDoor,
24    Trapdoor,
25    PowderSnow,
26    OnTopOfPowderSnow,
27    Fence,
28    Lava,
29    Water,
30    WaterBorder,
31    Rail,
32    UnpassableRail,
33    FireInNeighbor,
34    Fire,
35    DamagingInNeighbor,
36    Damaging,
37    DoorOpen,
38    DoorWoodClosed,
39    DoorIronClosed,
40    Breach,
41    Leaves,
42    StickyHoney,
43    Cocoa,
44    DamageCautious,
45    OnTopOfTrapdoor,
46    BigMobsCloseToDanger,
47}
48
49/// Which medium a path is being computed for.
50#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
51pub enum PathComputationType {
52    Land,
53    Water,
54    Air,
55}
56
57#[derive(Debug, Clone, PartialEq)]
58pub struct Path {
59    nodes: Vec<Node>,
60    next_node_index: usize,
61    target: BlockPos,
62    dist_to_target: f32,
63    reached: bool,
64}
65
66impl Path {
67    #[must_use]
68    pub fn new(nodes: Vec<Node>, target: BlockPos, reached: bool) -> Self {
69        let dist_to_target = nodes
70            .last()
71            .map_or(f32::MAX, |node| node.distance_manhattan_to_pos(target));
72        Self {
73            nodes,
74            next_node_index: 0,
75            target,
76            dist_to_target,
77            reached,
78        }
79    }
80
81    pub const fn advance(&mut self) {
82        self.next_node_index += 1;
83    }
84
85    #[must_use]
86    pub const fn not_started(&self) -> bool {
87        self.next_node_index == 0
88    }
89
90    #[must_use]
91    pub const fn is_done(&self) -> bool {
92        self.next_node_index >= self.nodes.len()
93    }
94
95    #[must_use]
96    pub fn end_node(&self) -> Option<&Node> {
97        self.nodes.last()
98    }
99
100    #[must_use]
101    pub fn node(&self, index: usize) -> Option<&Node> {
102        self.nodes.get(index)
103    }
104
105    pub fn truncate_nodes(&mut self, index: usize) {
106        if self.nodes.len() > index {
107            self.nodes.truncate(index);
108        }
109    }
110
111    pub fn replace_node(&mut self, index: usize, replace_with: Node) -> bool {
112        let Some(node) = self.nodes.get_mut(index) else {
113            return false;
114        };
115        *node = replace_with;
116        true
117    }
118
119    #[must_use]
120    pub const fn node_count(&self) -> usize {
121        self.nodes.len()
122    }
123
124    #[must_use]
125    pub const fn next_node_index(&self) -> usize {
126        self.next_node_index
127    }
128
129    pub const fn set_next_node_index(&mut self, next_node_index: usize) {
130        self.next_node_index = next_node_index;
131    }
132
133    #[must_use]
134    pub fn node_pos(&self, index: usize) -> Option<BlockPos> {
135        self.node(index).map(Node::as_block_pos)
136    }
137
138    #[must_use]
139    pub fn next_node_pos(&self) -> Option<BlockPos> {
140        self.node_pos(self.next_node_index)
141    }
142
143    #[must_use]
144    pub fn next_node(&self) -> Option<&Node> {
145        self.node(self.next_node_index)
146    }
147
148    #[must_use]
149    pub fn previous_node(&self) -> Option<&Node> {
150        self.next_node_index
151            .checked_sub(1)
152            .and_then(|index| self.node(index))
153    }
154
155    #[must_use]
156    pub fn same_as(&self, path: &Self) -> bool {
157        self.nodes.len() == path.nodes.len()
158            && self
159                .nodes
160                .iter()
161                .zip(path.nodes.iter())
162                .all(|(left, right)| left.hash() == right.hash())
163    }
164
165    #[must_use]
166    pub const fn can_reach(&self) -> bool {
167        self.reached
168    }
169
170    #[must_use]
171    pub const fn target(&self) -> BlockPos {
172        self.target
173    }
174
175    #[must_use]
176    pub const fn dist_to_target(&self) -> f32 {
177        self.dist_to_target
178    }
179
180    #[must_use]
181    pub fn nodes(&self) -> &[Node] {
182        &self.nodes
183    }
184}
185
186impl PathType {
187    pub const ALL: [Self; Self::COUNT] = [
188        Self::Blocked,
189        Self::Open,
190        Self::Walkable,
191        Self::WalkableDoor,
192        Self::Trapdoor,
193        Self::PowderSnow,
194        Self::OnTopOfPowderSnow,
195        Self::Fence,
196        Self::Lava,
197        Self::Water,
198        Self::WaterBorder,
199        Self::Rail,
200        Self::UnpassableRail,
201        Self::FireInNeighbor,
202        Self::Fire,
203        Self::DamagingInNeighbor,
204        Self::Damaging,
205        Self::DoorOpen,
206        Self::DoorWoodClosed,
207        Self::DoorIronClosed,
208        Self::Breach,
209        Self::Leaves,
210        Self::StickyHoney,
211        Self::Cocoa,
212        Self::DamageCautious,
213        Self::OnTopOfTrapdoor,
214        Self::BigMobsCloseToDanger,
215    ];
216    pub const COUNT: usize = 27;
217
218    #[must_use]
219    pub const fn index(self) -> usize {
220        self as usize
221    }
222
223    #[must_use]
224    #[expect(
225        clippy::match_same_arms,
226        reason = "one arm per vanilla PathType keeps the default table auditable"
227    )]
228    pub const fn default_malus(self) -> f32 {
229        match self {
230            Self::Blocked => -1.0,
231            Self::Open => 0.0,
232            Self::Walkable => 0.0,
233            Self::WalkableDoor => 0.0,
234            Self::Trapdoor => 0.0,
235            Self::PowderSnow => -1.0,
236            Self::OnTopOfPowderSnow => 0.0,
237            Self::Fence => -1.0,
238            Self::Lava => -1.0,
239            Self::Water => 8.0,
240            Self::WaterBorder => 8.0,
241            Self::Rail => 0.0,
242            Self::UnpassableRail => -1.0,
243            Self::FireInNeighbor => 8.0,
244            Self::Fire => 16.0,
245            Self::DamagingInNeighbor => 8.0,
246            Self::Damaging => -1.0,
247            Self::DoorOpen => 0.0,
248            Self::DoorWoodClosed => -1.0,
249            Self::DoorIronClosed => -1.0,
250            Self::Breach => 4.0,
251            Self::Leaves => -1.0,
252            Self::StickyHoney => 8.0,
253            Self::Cocoa => 0.0,
254            Self::DamageCautious => 0.0,
255            Self::OnTopOfTrapdoor => 0.0,
256            Self::BigMobsCloseToDanger => 4.0,
257        }
258    }
259}
260
261#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
262pub struct PathTypeSet {
263    bits: u32,
264}
265
266impl PathTypeSet {
267    #[must_use]
268    pub const fn new() -> Self {
269        Self { bits: 0 }
270    }
271
272    #[must_use]
273    pub const fn from_path_type(path_type: PathType) -> Self {
274        Self {
275            bits: Self::bit(path_type),
276        }
277    }
278
279    pub const fn insert(&mut self, path_type: PathType) {
280        self.bits |= Self::bit(path_type);
281    }
282
283    #[must_use]
284    pub const fn contains(self, path_type: PathType) -> bool {
285        self.bits & Self::bit(path_type) != 0
286    }
287
288    #[must_use]
289    pub const fn len(self) -> u32 {
290        self.bits.count_ones()
291    }
292
293    #[must_use]
294    pub const fn is_empty(self) -> bool {
295        self.bits == 0
296    }
297
298    #[must_use]
299    pub const fn single(self) -> Option<PathType> {
300        if self.bits.is_power_of_two() {
301            Some(PathType::ALL[self.bits.trailing_zeros() as usize])
302        } else {
303            None
304        }
305    }
306
307    pub fn iter(self) -> impl Iterator<Item = PathType> {
308        PathType::ALL
309            .into_iter()
310            .filter(move |path_type| self.contains(*path_type))
311    }
312
313    const fn bit(path_type: PathType) -> u32 {
314        1 << path_type.index()
315    }
316}
317
318#[derive(Debug, Clone)]
319pub struct PathfindingMalus {
320    overrides: [Option<f32>; PathType::COUNT],
321}
322
323impl PathfindingMalus {
324    #[must_use]
325    pub const fn new() -> Self {
326        Self {
327            overrides: [None; PathType::COUNT],
328        }
329    }
330
331    #[must_use]
332    pub fn get(&self, path_type: PathType) -> f32 {
333        self.overrides[path_type.index()].unwrap_or_else(|| path_type.default_malus())
334    }
335
336    pub const fn set(&mut self, path_type: PathType, malus: f32) {
337        self.overrides[path_type.index()] = Some(malus);
338    }
339}
340
341impl Default for PathfindingMalus {
342    fn default() -> Self {
343        Self::new()
344    }
345}
346
347#[derive(Debug, Clone, PartialEq, Eq)]
348pub struct PathTypeCache {
349    positions: Box<[i64]>,
350    path_types: Box<[Option<PathType>]>,
351}
352
353impl PathTypeCache {
354    #[must_use]
355    pub fn new() -> Self {
356        Self {
357            positions: vec![0; PATH_TYPE_CACHE_SIZE].into_boxed_slice(),
358            path_types: vec![None; PATH_TYPE_CACHE_SIZE].into_boxed_slice(),
359        }
360    }
361
362    #[must_use]
363    pub fn get_or_compute(
364        &mut self,
365        level: &(impl LevelReader + ?Sized),
366        pos: BlockPos,
367    ) -> PathType {
368        let key = PackedBlockPos::from(pos).as_raw();
369        let index = Self::index(key);
370        if self.positions[index] == key
371            && let Some(path_type) = self.path_types[index]
372        {
373            return path_type;
374        }
375
376        let path_type = WalkPathEvaluator::path_type_from_state(level, pos);
377        self.positions[index] = key;
378        self.path_types[index] = Some(path_type);
379        path_type
380    }
381
382    pub fn invalidate(&mut self, pos: BlockPos) {
383        let key = PackedBlockPos::from(pos).as_raw();
384        let index = Self::index(key);
385        if self.positions[index] == key {
386            self.path_types[index] = None;
387        }
388    }
389
390    const fn index(pos: i64) -> usize {
391        (fastutil_mix(pos as u64) as usize) & PATH_TYPE_CACHE_MASK
392    }
393}
394
395impl Default for PathTypeCache {
396    fn default() -> Self {
397        Self::new()
398    }
399}
400
401pub struct PathfindingContext<'a> {
402    level: &'a dyn LevelReader,
403    cache: Option<&'a mut PathTypeCache>,
404    mob_position: BlockPos,
405}
406
407impl<'a> PathfindingContext<'a> {
408    #[must_use]
409    pub const fn new(level: &'a dyn LevelReader, mob_position: BlockPos) -> Self {
410        Self {
411            level,
412            cache: None,
413            mob_position,
414        }
415    }
416
417    #[must_use]
418    pub fn with_cache(
419        level: &'a dyn LevelReader,
420        mob_position: BlockPos,
421        cache: &'a mut PathTypeCache,
422    ) -> Self {
423        Self {
424            level,
425            cache: Some(cache),
426            mob_position,
427        }
428    }
429
430    #[must_use]
431    pub fn get_path_type_from_state(&mut self, x: i32, y: i32, z: i32) -> PathType {
432        let pos = BlockPos::new(x, y, z);
433        match self.cache.as_deref_mut() {
434            Some(cache) => cache.get_or_compute(self.level, pos),
435            None => WalkPathEvaluator::path_type_from_state(self.level, pos),
436        }
437    }
438
439    #[must_use]
440    pub fn get_block_state(&self, pos: BlockPos) -> BlockStateId {
441        self.level.get_block_state(pos)
442    }
443
444    #[must_use]
445    pub const fn level(&self) -> &dyn LevelReader {
446        self.level
447    }
448
449    #[must_use]
450    pub const fn mob_position(&self) -> BlockPos {
451        self.mob_position
452    }
453}
454
455const fn fastutil_mix(value: u64) -> u64 {
456    let mixed = value.wrapping_mul(0x9E37_79B9_7F4A_7C15);
457    let mixed = mixed ^ (mixed >> 32);
458    mixed ^ (mixed >> 16)
459}
460
461#[cfg(test)]
462mod tests {
463    use steel_registry::{REGISTRY, init_vanilla_registry, vanilla_blocks};
464    use steel_utils::{BlockPos, BlockStateId};
465    use steel_worldgen::density_functions::overworld::OverworldNoiseSettings;
466
467    use super::{
468        PATH_TYPE_CACHE_MASK, Path, PathType, PathTypeCache, PathTypeSet, PathfindingContext,
469        PathfindingMalus,
470    };
471    use crate::entity::ai::node::Node;
472    use crate::world::LevelReader;
473
474    struct SingleBlockLevel {
475        state: BlockStateId,
476    }
477
478    impl LevelReader for SingleBlockLevel {
479        fn get_block_state(&self, _pos: steel_utils::BlockPos) -> BlockStateId {
480            self.state
481        }
482
483        fn raw_brightness(&self, _pos: steel_utils::BlockPos, _sky_darkening: u8) -> u8 {
484            0
485        }
486
487        fn min_y(&self) -> i32 {
488            OverworldNoiseSettings::MIN_Y
489        }
490
491        fn height(&self) -> i32 {
492            OverworldNoiseSettings::HEIGHT
493        }
494
495        fn sea_level(&self) -> i32 {
496            OverworldNoiseSettings::SEA_LEVEL
497        }
498    }
499
500    #[test]
501    fn default_malus_matches_vanilla_path_types() {
502        assert_eq!(
503            PathType::Blocked.default_malus().to_bits(),
504            (-1.0_f32).to_bits()
505        );
506        assert_eq!(
507            PathType::Walkable.default_malus().to_bits(),
508            0.0_f32.to_bits()
509        );
510        assert_eq!(PathType::Water.default_malus().to_bits(), 8.0_f32.to_bits());
511        assert_eq!(PathType::Fire.default_malus().to_bits(), 16.0_f32.to_bits());
512        assert_eq!(
513            PathType::BigMobsCloseToDanger.default_malus().to_bits(),
514            4.0_f32.to_bits()
515        );
516    }
517
518    #[test]
519    fn malus_overrides_are_indexed_by_path_type() {
520        let mut malus = PathfindingMalus::new();
521        assert_eq!(malus.get(PathType::Fire).to_bits(), 16.0_f32.to_bits());
522
523        malus.set(PathType::Fire, -1.0);
524
525        assert_eq!(malus.get(PathType::Fire).to_bits(), (-1.0_f32).to_bits());
526        assert_eq!(malus.get(PathType::Water).to_bits(), 8.0_f32.to_bits());
527    }
528
529    #[test]
530    fn path_type_set_is_bit_indexed_by_vanilla_path_type_order() {
531        let mut set = PathTypeSet::new();
532        assert!(set.is_empty());
533        set.insert(PathType::Water);
534        set.insert(PathType::Fence);
535
536        assert_eq!(set.len(), 2);
537        assert!(set.contains(PathType::Water));
538        assert!(set.contains(PathType::Fence));
539        assert!(!set.contains(PathType::Open));
540        assert_eq!(
541            PathTypeSet::from_path_type(PathType::Rail).single(),
542            Some(PathType::Rail)
543        );
544        assert_eq!(
545            set.iter().collect::<Vec<_>>(),
546            vec![PathType::Fence, PathType::Water]
547        );
548    }
549
550    #[test]
551    fn path_type_cache_uses_vanilla_direct_mapped_size() {
552        assert_eq!(PATH_TYPE_CACHE_MASK, 4095);
553    }
554
555    #[test]
556    fn path_tracks_progress_and_target_distance() {
557        let mut path = Path::new(
558            vec![Node::new(0, 64, 0), Node::new(2, 64, 1)],
559            BlockPos::new(4, 64, 1),
560            false,
561        );
562
563        assert!(path.not_started());
564        assert!(!path.is_done());
565        assert_eq!(path.node_count(), 2);
566        assert_eq!(path.next_node_pos(), Some(BlockPos::new(0, 64, 0)));
567        assert_eq!(path.dist_to_target().to_bits(), 2.0_f32.to_bits());
568        assert!(!path.can_reach());
569
570        path.advance();
571
572        assert_eq!(
573            path.previous_node().map(Node::as_block_pos),
574            Some(BlockPos::new(0, 64, 0))
575        );
576        assert_eq!(path.next_node_pos(), Some(BlockPos::new(2, 64, 1)));
577    }
578
579    #[test]
580    fn path_same_as_compares_vanilla_node_identity() {
581        let left = Path::new(vec![Node::new(0, 64, 0)], BlockPos::new(1, 64, 0), false);
582        let mut right_node = Node::new(0, 64, 0);
583        right_node.cost_malus = 8.0;
584        let right = Path::new(vec![right_node], BlockPos::new(2, 64, 0), true);
585
586        assert!(left.same_as(&right));
587    }
588
589    #[test]
590    fn path_type_cache_invalidates_matching_position() {
591        init_vanilla_registry();
592
593        let level = SingleBlockLevel {
594            state: REGISTRY.blocks.get_default_state_id(&vanilla_blocks::AIR),
595        };
596        let pos = steel_utils::BlockPos::new(1, 64, 1);
597        let mut cache = PathTypeCache::new();
598
599        assert_eq!(cache.get_or_compute(&level, pos), PathType::Open);
600        cache.invalidate(pos);
601        assert_eq!(cache.get_or_compute(&level, pos), PathType::Open);
602    }
603
604    #[test]
605    fn pathfinding_context_uses_cache_when_supplied() {
606        init_vanilla_registry();
607
608        let level = SingleBlockLevel {
609            state: REGISTRY.blocks.get_default_state_id(&vanilla_blocks::AIR),
610        };
611        let mut cache = PathTypeCache::new();
612        let mut context = PathfindingContext::with_cache(
613            &level,
614            steel_utils::BlockPos::new(0, 64, 0),
615            &mut cache,
616        );
617
618        assert_eq!(context.get_path_type_from_state(0, 64, 0), PathType::Open);
619    }
620}
steel_core/entity/ai/path.rs

steel_core/entity/ai/
path.rs
