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/// Vanilla `PathComputationType`.
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)]
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(&mut self, level: &dyn LevelReader, pos: BlockPos) -> PathType {
364        let key = PackedBlockPos::from(pos).as_raw();
365        let index = Self::index(key);
366        if self.positions[index] == key
367            && let Some(path_type) = self.path_types[index]
368        {
369            return path_type;
370        }
371
372        let path_type = WalkPathEvaluator::path_type_from_state(level, pos);
373        self.positions[index] = key;
374        self.path_types[index] = Some(path_type);
375        path_type
376    }
377
378    pub fn invalidate(&mut self, pos: BlockPos) {
379        let key = PackedBlockPos::from(pos).as_raw();
380        let index = Self::index(key);
381        if self.positions[index] == key {
382            self.path_types[index] = None;
383        }
384    }
385
386    const fn index(pos: i64) -> usize {
387        (fastutil_mix(pos as u64) as usize) & PATH_TYPE_CACHE_MASK
388    }
389}
390
391impl Default for PathTypeCache {
392    fn default() -> Self {
393        Self::new()
394    }
395}
396
397pub struct PathfindingContext<'a> {
398    level: &'a dyn LevelReader,
399    cache: Option<&'a mut PathTypeCache>,
400    mob_position: BlockPos,
401}
402
403impl<'a> PathfindingContext<'a> {
404    #[must_use]
405    pub const fn new(level: &'a dyn LevelReader, mob_position: BlockPos) -> Self {
406        Self {
407            level,
408            cache: None,
409            mob_position,
410        }
411    }
412
413    #[must_use]
414    pub fn with_cache(
415        level: &'a dyn LevelReader,
416        mob_position: BlockPos,
417        cache: &'a mut PathTypeCache,
418    ) -> Self {
419        Self {
420            level,
421            cache: Some(cache),
422            mob_position,
423        }
424    }
425
426    #[must_use]
427    pub fn get_path_type_from_state(&mut self, x: i32, y: i32, z: i32) -> PathType {
428        let pos = BlockPos::new(x, y, z);
429        match self.cache.as_deref_mut() {
430            Some(cache) => cache.get_or_compute(self.level, pos),
431            None => WalkPathEvaluator::path_type_from_state(self.level, pos),
432        }
433    }
434
435    #[must_use]
436    pub fn get_block_state(&self, pos: BlockPos) -> BlockStateId {
437        self.level.get_block_state(pos)
438    }
439
440    #[must_use]
441    pub const fn level(&self) -> &dyn LevelReader {
442        self.level
443    }
444
445    #[must_use]
446    pub const fn mob_position(&self) -> BlockPos {
447        self.mob_position
448    }
449}
450
451const fn fastutil_mix(value: u64) -> u64 {
452    let mixed = value.wrapping_mul(0x9E37_79B9_7F4A_7C15);
453    let mixed = mixed ^ (mixed >> 32);
454    mixed ^ (mixed >> 16)
455}
456
457#[cfg(test)]
458mod tests {
459    use steel_registry::{REGISTRY, init_vanilla_registry, vanilla_blocks};
460    use steel_utils::{BlockPos, BlockStateId};
461
462    use super::{
463        PATH_TYPE_CACHE_MASK, Path, PathType, PathTypeCache, PathTypeSet, PathfindingContext,
464        PathfindingMalus,
465    };
466    use crate::entity::ai::node::Node;
467    use crate::world::LevelReader;
468
469    struct SingleBlockLevel {
470        state: BlockStateId,
471    }
472
473    impl LevelReader for SingleBlockLevel {
474        fn get_block_state(&self, _pos: steel_utils::BlockPos) -> BlockStateId {
475            self.state
476        }
477
478        fn raw_brightness(&self, _pos: steel_utils::BlockPos, _sky_darkening: u8) -> u8 {
479            0
480        }
481
482        fn min_y(&self) -> i32 {
483            -64
484        }
485
486        fn height(&self) -> i32 {
487            384
488        }
489    }
490
491    #[test]
492    fn default_malus_matches_vanilla_path_types() {
493        assert_eq!(
494            PathType::Blocked.default_malus().to_bits(),
495            (-1.0_f32).to_bits()
496        );
497        assert_eq!(
498            PathType::Walkable.default_malus().to_bits(),
499            0.0_f32.to_bits()
500        );
501        assert_eq!(PathType::Water.default_malus().to_bits(), 8.0_f32.to_bits());
502        assert_eq!(PathType::Fire.default_malus().to_bits(), 16.0_f32.to_bits());
503        assert_eq!(
504            PathType::BigMobsCloseToDanger.default_malus().to_bits(),
505            4.0_f32.to_bits()
506        );
507    }
508
509    #[test]
510    fn malus_overrides_are_indexed_by_path_type() {
511        let mut malus = PathfindingMalus::new();
512        assert_eq!(malus.get(PathType::Fire).to_bits(), 16.0_f32.to_bits());
513
514        malus.set(PathType::Fire, -1.0);
515
516        assert_eq!(malus.get(PathType::Fire).to_bits(), (-1.0_f32).to_bits());
517        assert_eq!(malus.get(PathType::Water).to_bits(), 8.0_f32.to_bits());
518    }
519
520    #[test]
521    fn path_type_set_is_bit_indexed_by_vanilla_path_type_order() {
522        let mut set = PathTypeSet::new();
523        assert!(set.is_empty());
524        set.insert(PathType::Water);
525        set.insert(PathType::Fence);
526
527        assert_eq!(set.len(), 2);
528        assert!(set.contains(PathType::Water));
529        assert!(set.contains(PathType::Fence));
530        assert!(!set.contains(PathType::Open));
531        assert_eq!(
532            PathTypeSet::from_path_type(PathType::Rail).single(),
533            Some(PathType::Rail)
534        );
535        assert_eq!(
536            set.iter().collect::<Vec<_>>(),
537            vec![PathType::Fence, PathType::Water]
538        );
539    }
540
541    #[test]
542    fn path_type_cache_uses_vanilla_direct_mapped_size() {
543        assert_eq!(PATH_TYPE_CACHE_MASK, 4095);
544    }
545
546    #[test]
547    fn path_tracks_progress_and_target_distance() {
548        let mut path = Path::new(
549            vec![Node::new(0, 64, 0), Node::new(2, 64, 1)],
550            BlockPos::new(4, 64, 1),
551            false,
552        );
553
554        assert!(path.not_started());
555        assert!(!path.is_done());
556        assert_eq!(path.node_count(), 2);
557        assert_eq!(path.next_node_pos(), Some(BlockPos::new(0, 64, 0)));
558        assert_eq!(path.dist_to_target().to_bits(), 2.0_f32.to_bits());
559        assert!(!path.can_reach());
560
561        path.advance();
562
563        assert_eq!(
564            path.previous_node().map(Node::as_block_pos),
565            Some(BlockPos::new(0, 64, 0))
566        );
567        assert_eq!(path.next_node_pos(), Some(BlockPos::new(2, 64, 1)));
568    }
569
570    #[test]
571    fn path_same_as_compares_vanilla_node_identity() {
572        let left = Path::new(vec![Node::new(0, 64, 0)], BlockPos::new(1, 64, 0), false);
573        let mut right_node = Node::new(0, 64, 0);
574        right_node.cost_malus = 8.0;
575        let right = Path::new(vec![right_node], BlockPos::new(2, 64, 0), true);
576
577        assert!(left.same_as(&right));
578    }
579
580    #[test]
581    fn path_type_cache_invalidates_matching_position() {
582        init_vanilla_registry();
583
584        let level = SingleBlockLevel {
585            state: REGISTRY.blocks.get_default_state_id(&vanilla_blocks::AIR),
586        };
587        let pos = steel_utils::BlockPos::new(1, 64, 1);
588        let mut cache = PathTypeCache::new();
589
590        assert_eq!(cache.get_or_compute(&level, pos), PathType::Open);
591        cache.invalidate(pos);
592        assert_eq!(cache.get_or_compute(&level, pos), PathType::Open);
593    }
594
595    #[test]
596    fn pathfinding_context_uses_cache_when_supplied() {
597        init_vanilla_registry();
598
599        let level = SingleBlockLevel {
600            state: REGISTRY.blocks.get_default_state_id(&vanilla_blocks::AIR),
601        };
602        let mut cache = PathTypeCache::new();
603        let mut context = PathfindingContext::with_cache(
604            &level,
605            steel_utils::BlockPos::new(0, 64, 0),
606            &mut cache,
607        );
608
609        assert_eq!(context.get_path_type_from_state(0, 64, 0), PathType::Open);
610    }
611}
steel_core/entity/ai/path.rs

steel_core/entity/ai/
path.rs
