1use super::*;
2
3#[derive(Debug, Clone)]
4pub struct WalkNodeEvaluator {
5 settings: MobPathSettings,
6 nodes: NodeStore,
7}
8
9#[derive(Debug, Clone, Copy, PartialEq)]
10pub struct AcceptedNodeRequest {
11 pub pos: BlockPos,
12 pub jump_size: i32,
13 pub node_height: f64,
14 pub travel_direction: Direction,
15 pub current_path_type: PathType,
16}
17
18#[derive(Debug, Clone, Copy, PartialEq, Eq)]
19pub struct WalkNeighbors {
20 nodes: [Option<i32>; 8],
21 len: usize,
22}
23
24impl WalkNeighbors {
25 #[must_use]
26 pub const fn new() -> Self {
27 Self {
28 nodes: [None; 8],
29 len: 0,
30 }
31 }
32
33 #[must_use]
34 pub const fn len(&self) -> usize {
35 self.len
36 }
37
38 #[must_use]
39 pub const fn is_empty(&self) -> bool {
40 self.len == 0
41 }
42
43 pub fn iter(&self) -> impl Iterator<Item = i32> + '_ {
44 self.nodes[..self.len].iter().copied().flatten()
45 }
46
47 const fn push(&mut self, node: i32) {
48 self.nodes[self.len] = Some(node);
49 self.len += 1;
50 }
51}
52
53impl Default for WalkNeighbors {
54 fn default() -> Self {
55 Self::new()
56 }
57}
58
59const VANILLA_HORIZONTAL_DIRECTIONS: [Direction; 4] = [
60 Direction::North,
61 Direction::East,
62 Direction::South,
63 Direction::West,
64];
65
66impl WalkNodeEvaluator {
67 #[must_use]
68 pub fn new(settings: MobPathSettings) -> Self {
69 Self {
70 settings,
71 nodes: NodeStore::new(),
72 }
73 }
74
75 #[must_use]
76 pub const fn settings(&self) -> &MobPathSettings {
77 &self.settings
78 }
79
80 pub fn clear_nodes(&mut self) {
81 self.nodes.clear();
82 }
83
84 #[must_use]
85 pub fn node(&self, hash: i32) -> Option<&Node> {
86 self.nodes.get(hash)
87 }
88
89 pub(crate) fn node_mut(&mut self, hash: i32) -> Option<&mut Node> {
90 self.nodes.get_mut(hash)
91 }
92
93 pub(crate) const fn nodes_mut(&mut self) -> &mut NodeStore {
94 &mut self.nodes
95 }
96
97 pub(crate) fn reset_search_state(&mut self) {
98 self.nodes.reset_search_state();
99 }
100
101 #[must_use]
102 pub fn get_start(&mut self, context: &mut PathfindingContext<'_>) -> i32 {
103 let position = self.settings.mob_position_vec();
104 let mut start_y = self.settings.mob_position().y();
105 let mut reusable_pos = BlockPos::containing(position.x, f64::from(start_y), position.z);
106 let mut block_state = context.get_block_state(reusable_pos);
107
108 if self
109 .settings
110 .can_stand_on_fluid(block_state.get_fluid_state())
111 {
112 while self
113 .settings
114 .can_stand_on_fluid(block_state.get_fluid_state())
115 {
116 start_y += 1;
117 reusable_pos = BlockPos::containing(position.x, f64::from(start_y), position.z);
118 block_state = context.get_block_state(reusable_pos);
119 }
120 start_y -= 1;
121 } else if self.settings.can_float() && self.settings.in_water() {
122 while block_state.get_fluid_state().is_water() {
123 start_y += 1;
124 reusable_pos = BlockPos::containing(position.x, f64::from(start_y), position.z);
125 block_state = context.get_block_state(reusable_pos);
126 }
127 start_y -= 1;
128 } else if self.settings.on_ground() {
129 start_y = fast_floor(position.y + 0.5);
130 } else {
131 reusable_pos = BlockPos::containing(position.x, position.y + 1.0, position.z);
132
133 while reusable_pos.y() > context.level().min_y() {
134 start_y = reusable_pos.y();
135 reusable_pos = reusable_pos.below();
136 let below_block_state = context.get_block_state(reusable_pos);
137 if !below_block_state.is_air()
138 && !below_block_state.is_pathfindable(PathComputationType::Land)
139 {
140 break;
141 }
142 }
143 }
144
145 let start_pos = self.settings.mob_position();
146 let centered_start = BlockPos::new(start_pos.x(), start_y, start_pos.z());
147 if !self.can_start_at(context, centered_start)
148 && let Some(corner) = self.first_startable_corner(context, start_y)
149 {
150 return self.get_start_node(context, corner);
151 }
152
153 self.get_start_node(context, centered_start)
154 }
155
156 #[must_use]
157 pub fn get_neighbors(
158 &mut self,
159 context: &mut PathfindingContext<'_>,
160 collision: &mut impl WalkNodeCollision,
161 pos_hash: i32,
162 ) -> WalkNeighbors {
163 let Some(pos) = self.node(pos_hash) else {
164 return WalkNeighbors::new();
165 };
166 let pos_x = pos.x;
167 let pos_y = pos.y;
168 let pos_z = pos.z;
169 let pos_cost_malus = pos.cost_malus;
170 let pos_block = BlockPos::new(pos_x, pos_y, pos_z);
171
172 let path_type_above = self.get_path_type_of_mob(context, pos_x, pos_y + 1, pos_z);
173 let current_path_type = self.get_path_type_of_mob(context, pos_x, pos_y, pos_z);
174 let jump_size = if self.settings.pathfinding_malus(path_type_above) >= 0.0
175 && current_path_type != PathType::StickyHoney
176 {
177 fast_floor(f64::from(self.settings.max_up_step()).max(1.0))
178 } else {
179 0
180 };
181 let pos_height = self.get_floor_level(context, pos_block);
182
183 let mut neighbors = WalkNeighbors::new();
184 let mut reusable_neighbors = [None; 4];
185 for (index, direction) in VANILLA_HORIZONTAL_DIRECTIONS.iter().copied().enumerate() {
186 let (step_x, _, step_z) = direction.offset();
187 let node = self.find_accepted_node(
188 context,
189 collision,
190 AcceptedNodeRequest {
191 pos: BlockPos::new(pos_x + step_x, pos_y, pos_z + step_z),
192 jump_size,
193 node_height: pos_height,
194 travel_direction: direction,
195 current_path_type,
196 },
197 );
198 reusable_neighbors[index] = node;
199 if self.is_neighbor_valid(node, pos_cost_malus)
200 && let Some(node) = node
201 {
202 neighbors.push(node);
203 }
204 }
205
206 for (index, direction) in VANILLA_HORIZONTAL_DIRECTIONS.iter().copied().enumerate() {
207 let second_index = clockwise_direction_index(index);
208 let second_direction = VANILLA_HORIZONTAL_DIRECTIONS[second_index];
209 if !self.is_diagonal_corner_valid(
210 pos_y,
211 reusable_neighbors[index],
212 reusable_neighbors[second_index],
213 ) {
214 continue;
215 }
216
217 let (step_x, _, step_z) = direction.offset();
218 let (second_step_x, _, second_step_z) = second_direction.offset();
219 let node = self.find_accepted_node(
220 context,
221 collision,
222 AcceptedNodeRequest {
223 pos: BlockPos::new(
224 pos_x + step_x + second_step_x,
225 pos_y,
226 pos_z + step_z + second_step_z,
227 ),
228 jump_size,
229 node_height: pos_height,
230 travel_direction: direction,
231 current_path_type,
232 },
233 );
234 if self.is_diagonal_node_valid(node)
235 && let Some(node) = node
236 {
237 neighbors.push(node);
238 }
239 }
240
241 neighbors
242 }
243
244 #[must_use]
245 pub fn get_floor_level(&self, context: &PathfindingContext<'_>, pos: BlockPos) -> f64 {
246 if self.settings.can_float() && context.get_block_state(pos).get_fluid_state().is_water() {
247 return f64::from(pos.y()) + 0.5;
248 }
249
250 Self::floor_level(context.level(), pos)
251 }
252
253 #[must_use]
254 pub fn floor_level(level: &dyn LevelReader, pos: BlockPos) -> f64 {
255 let target = pos.offset(0, -1, 0);
256 let state = level.get_block_state(target);
257 let behavior = BLOCK_BEHAVIORS.get_behavior(state.get_block());
258 let shape =
259 behavior.get_collision_shape(state, level, target, BlockCollisionContext::empty());
260 f64::from(target.y())
261 + if shape.is_empty() {
262 0.0
263 } else {
264 shape.max(Axis::Y)
265 }
266 }
267
268 #[must_use]
269 pub fn get_path_type_of_mob(
270 &self,
271 context: &mut PathfindingContext<'_>,
272 x: i32,
273 y: i32,
274 z: i32,
275 ) -> PathType {
276 let block_types = self.get_path_type_within_mob_bb(context, x, y, z);
277 if let Some(path_type) = block_types.single() {
278 return path_type;
279 }
280
281 if block_types.contains(PathType::Fence) {
282 return PathType::Fence;
283 }
284
285 if block_types.contains(PathType::UnpassableRail) {
286 return PathType::UnpassableRail;
287 }
288
289 let mut highest_malus_path_type = PathType::Blocked;
290 let mut highest_malus = self.settings.pathfinding_malus(highest_malus_path_type);
291 for path_type in block_types.iter() {
292 let malus = self.settings.pathfinding_malus(path_type);
293 if malus < 0.0 {
294 return path_type;
295 }
296 if malus >= highest_malus {
297 highest_malus = malus;
298 highest_malus_path_type = path_type;
299 }
300 }
301
302 let current_node_path_type = WalkPathEvaluator::path_type(context, x, y, z);
303 if self.settings.entity_width() > 1 {
304 let current_is_cheaper =
305 self.settings.pathfinding_malus(current_node_path_type) < highest_malus;
306 let cap_due_to_cheap_node = current_is_cheaper
307 && self
308 .settings
309 .pathfinding_malus(PathType::BigMobsCloseToDanger)
310 < highest_malus;
311 if cap_due_to_cheap_node {
312 PathType::BigMobsCloseToDanger
313 } else {
314 highest_malus_path_type
315 }
316 } else if current_node_path_type == PathType::Open
317 && highest_malus_path_type != PathType::Open
318 && highest_malus == 0.0
319 {
320 PathType::Open
321 } else {
322 highest_malus_path_type
323 }
324 }
325
326 pub fn find_accepted_node(
327 &mut self,
328 context: &mut PathfindingContext<'_>,
329 collision: &mut impl WalkNodeCollision,
330 request: AcceptedNodeRequest,
331 ) -> Option<i32> {
332 let x = request.pos.x();
333 let y = request.pos.y();
334 let z = request.pos.z();
335 let max_y_target = self.get_floor_level(context, request.pos);
336 if max_y_target - request.node_height > self.mob_jump_height() {
337 return None;
338 }
339
340 let path_type = self.get_path_type_of_mob(context, x, y, z);
341 let path_cost = self.settings.pathfinding_malus(path_type);
342 let mut best = if path_cost >= 0.0 {
343 Some(self.get_node_and_update_cost_to_max(x, y, z, path_type, path_cost))
344 } else {
345 None
346 };
347
348 if let Some(best_hash) = best {
349 let needs_collision_check =
350 does_block_have_partial_collision(request.current_path_type)
351 && self
352 .node(best_hash)
353 .is_some_and(|node| node.cost_malus >= 0.0);
354 if needs_collision_check && !self.can_reach_without_collision(collision, best_hash) {
355 best = None;
356 }
357 }
358
359 if path_type == PathType::Walkable {
360 return best;
361 }
362
363 let needs_jump = best.is_none_or(|best_hash| {
364 self.node(best_hash)
365 .is_none_or(|node| node.cost_malus < 0.0)
366 });
367 if needs_jump
368 && request.jump_size > 0
369 && (path_type != PathType::Fence || self.settings.can_walk_over_fences())
370 && path_type != PathType::UnpassableRail
371 && path_type != PathType::Trapdoor
372 && path_type != PathType::PowderSnow
373 {
374 return self.try_jump_on(context, collision, request);
375 }
376
377 if path_type == PathType::Water && !self.settings.can_float() {
378 return self.try_find_first_non_water_below(context, x, y, z, best);
379 }
380
381 if path_type == PathType::Open {
382 return Some(self.try_find_first_ground_node_below(context, x, y, z));
383 }
384
385 if does_block_have_partial_collision(path_type) && best.is_none() {
386 return Some(self.get_closed_node(x, y, z, path_type));
387 }
388
389 best
390 }
391
392 #[must_use]
393 pub fn get_path_type_within_mob_bb(
394 &self,
395 context: &mut PathfindingContext<'_>,
396 x: i32,
397 y: i32,
398 z: i32,
399 ) -> PathTypeSet {
400 let mut block_types = PathTypeSet::new();
401 let mut mob_on_rail = None;
402
403 for dx in 0..self.settings.entity_width() {
404 for dy in 0..self.settings.entity_height() {
405 for dz in 0..self.settings.entity_depth() {
406 let mut block_type =
407 WalkPathEvaluator::path_type(context, x + dx, y + dy, z + dz);
408 block_type =
409 self.adjust_path_type_for_mob(context, block_type, &mut mob_on_rail);
410 block_types.insert(block_type);
411 }
412 }
413 }
414
415 block_types
416 }
417
418 fn adjust_path_type_for_mob(
419 &self,
420 context: &mut PathfindingContext<'_>,
421 block_type: PathType,
422 mob_on_rail: &mut Option<bool>,
423 ) -> PathType {
424 if block_type == PathType::DoorWoodClosed
425 && self.settings.can_open_doors()
426 && self.settings.can_pass_doors()
427 {
428 return PathType::WalkableDoor;
429 }
430
431 if block_type == PathType::DoorOpen && !self.settings.can_pass_doors() {
432 return PathType::Blocked;
433 }
434
435 if block_type != PathType::Rail {
436 return block_type;
437 }
438
439 if mob_on_rail.is_none() {
440 let mob_position = self.settings.mob_position();
441 *mob_on_rail = Some(
442 WalkPathEvaluator::path_type(
443 context,
444 mob_position.x(),
445 mob_position.y(),
446 mob_position.z(),
447 ) == PathType::Rail
448 || WalkPathEvaluator::path_type(
449 context,
450 mob_position.x(),
451 mob_position.y() - 1,
452 mob_position.z(),
453 ) == PathType::Rail,
454 );
455 }
456
457 if matches!(mob_on_rail, Some(true)) {
458 PathType::Rail
459 } else {
460 PathType::UnpassableRail
461 }
462 }
463
464 fn first_startable_corner(
465 &self,
466 context: &mut PathfindingContext<'_>,
467 start_y: i32,
468 ) -> Option<BlockPos> {
469 let bounding_box = self.settings.bounding_box();
470 [
471 BlockPos::containing(
472 bounding_box.min_x(),
473 f64::from(start_y),
474 bounding_box.min_z(),
475 ),
476 BlockPos::containing(
477 bounding_box.min_x(),
478 f64::from(start_y),
479 bounding_box.max_z(),
480 ),
481 BlockPos::containing(
482 bounding_box.max_x(),
483 f64::from(start_y),
484 bounding_box.min_z(),
485 ),
486 BlockPos::containing(
487 bounding_box.max_x(),
488 f64::from(start_y),
489 bounding_box.max_z(),
490 ),
491 ]
492 .into_iter()
493 .find(|pos| self.can_start_at(context, *pos))
494 }
495
496 fn get_start_node(&mut self, context: &mut PathfindingContext<'_>, pos: BlockPos) -> i32 {
497 let path_type = self.get_path_type_of_mob(context, pos.x(), pos.y(), pos.z());
498 let cost_malus = self.settings.pathfinding_malus(path_type);
499 let node = self.nodes.get_node(pos.x(), pos.y(), pos.z());
500 node.path_type = path_type;
501 node.cost_malus = cost_malus;
502 node.hash()
503 }
504
505 fn can_start_at(&self, context: &mut PathfindingContext<'_>, pos: BlockPos) -> bool {
506 let path_type = self.get_path_type_of_mob(context, pos.x(), pos.y(), pos.z());
507 path_type != PathType::Open && self.settings.pathfinding_malus(path_type) >= 0.0
508 }
509
510 fn is_neighbor_valid(&self, node: Option<i32>, current_cost_malus: f32) -> bool {
511 let Some(node) = node.and_then(|hash| self.node(hash)) else {
512 return false;
513 };
514
515 !node.closed && (node.cost_malus >= 0.0 || current_cost_malus < 0.0)
516 }
517
518 fn is_diagonal_corner_valid(
519 &self,
520 current_y: i32,
521 first: Option<i32>,
522 second: Option<i32>,
523 ) -> bool {
524 let Some(first) = first.and_then(|hash| self.node(hash)) else {
525 return false;
526 };
527 let Some(second) = second.and_then(|hash| self.node(hash)) else {
528 return false;
529 };
530
531 if first.y > current_y || second.y > current_y {
532 return false;
533 }
534 if first.path_type == PathType::WalkableDoor || second.path_type == PathType::WalkableDoor {
535 return false;
536 }
537 if self.settings.bounding_box().width() > 1.0
538 && (first.cost_malus > 0.0 || second.cost_malus > 0.0)
539 {
540 return false;
541 }
542
543 let can_pass_between_fence_posts = first.path_type == PathType::Fence
544 && second.path_type == PathType::Fence
545 && self.settings.bounding_box().width() < 0.5;
546 (first.y < current_y || first.cost_malus >= 0.0 || can_pass_between_fence_posts)
547 && (second.y < current_y || second.cost_malus >= 0.0 || can_pass_between_fence_posts)
548 }
549
550 fn is_diagonal_node_valid(&self, node: Option<i32>) -> bool {
551 let Some(node) = node.and_then(|hash| self.node(hash)) else {
552 return false;
553 };
554
555 !node.closed && node.path_type != PathType::WalkableDoor && node.cost_malus >= 0.0
556 }
557
558 fn try_jump_on(
559 &mut self,
560 context: &mut PathfindingContext<'_>,
561 collision: &mut impl WalkNodeCollision,
562 request: AcceptedNodeRequest,
563 ) -> Option<i32> {
564 let x = request.pos.x();
565 let y = request.pos.y();
566 let z = request.pos.z();
567 let node_above = self.find_accepted_node(
568 context,
569 collision,
570 AcceptedNodeRequest {
571 pos: request.pos.offset(0, 1, 0),
572 jump_size: request.jump_size - 1,
573 ..request
574 },
575 )?;
576
577 if self.settings.bounding_box().width() >= 1.0 {
578 return Some(node_above);
579 }
580
581 let node = self.node(node_above)?;
582 if node.path_type != PathType::Open && node.path_type != PathType::Walkable {
583 return Some(node_above);
584 }
585
586 let (step_x, _, step_z) = request.travel_direction.offset();
587 let center_x = f64::from(x - step_x) + 0.5;
588 let center_z = f64::from(z - step_z) + 0.5;
589 let half_width = self.settings.bounding_box().width() / 2.0;
590 let min_y = self.get_floor_level(
591 context,
592 BlockPos::new(fast_floor(center_x), y + 1, fast_floor(center_z)),
593 ) + 0.001;
594 let max_y = self.get_floor_level(context, BlockPos::new(node.x, node.y, node.z))
595 + self.settings.bounding_box().height()
596 - 0.002;
597 let collision_box = WorldAabb::new(
598 center_x - half_width,
599 min_y,
600 center_z - half_width,
601 center_x + half_width,
602 max_y,
603 center_z + half_width,
604 );
605
606 if collision.has_collision(collision_box) {
607 None
608 } else {
609 Some(node_above)
610 }
611 }
612
613 fn try_find_first_non_water_below(
614 &mut self,
615 context: &mut PathfindingContext<'_>,
616 x: i32,
617 mut y: i32,
618 z: i32,
619 mut best: Option<i32>,
620 ) -> Option<i32> {
621 y -= 1;
622
623 while y > context.level().min_y() {
624 let path_type = self.get_path_type_of_mob(context, x, y, z);
625 if path_type != PathType::Water {
626 return best;
627 }
628
629 let path_cost = self.settings.pathfinding_malus(path_type);
630 best = Some(self.get_node_and_update_cost_to_max(x, y, z, path_type, path_cost));
631 y -= 1;
632 }
633
634 best
635 }
636
637 fn try_find_first_ground_node_below(
638 &mut self,
639 context: &mut PathfindingContext<'_>,
640 x: i32,
641 y: i32,
642 z: i32,
643 ) -> i32 {
644 for current_y in (context.level().min_y()..y).rev() {
645 if y - current_y > self.settings.max_fall_distance() {
646 return self.get_blocked_node(x, current_y, z);
647 }
648
649 let path_type = self.get_path_type_of_mob(context, x, current_y, z);
650 let path_cost = self.settings.pathfinding_malus(path_type);
651 if path_type != PathType::Open {
652 if path_cost >= 0.0 {
653 return self
654 .get_node_and_update_cost_to_max(x, current_y, z, path_type, path_cost);
655 }
656
657 return self.get_blocked_node(x, current_y, z);
658 }
659 }
660
661 self.get_blocked_node(x, y, z)
662 }
663
664 fn can_reach_without_collision(
665 &self,
666 collision: &mut impl WalkNodeCollision,
667 target: i32,
668 ) -> bool {
669 let Some(node) = self.node(target) else {
670 return false;
671 };
672 let mut bounding_box = self.settings.bounding_box();
673 let delta = glam::DVec3::new(
674 f64::from(node.x) - self.settings.mob_position_vec().x + bounding_box.width() / 2.0,
675 f64::from(node.y) - self.settings.mob_position_vec().y + bounding_box.height() / 2.0,
676 f64::from(node.z) - self.settings.mob_position_vec().z + bounding_box.depth() / 2.0,
677 );
678 let steps = (delta.length() / bounding_box.size()).ceil() as i32;
679 if steps <= 0 {
680 return true;
681 }
682 let step_delta = delta / f64::from(steps);
683
684 for _ in 1..=steps {
685 bounding_box = bounding_box.translate(step_delta);
686 if collision.has_collision(bounding_box) {
687 return false;
688 }
689 }
690
691 true
692 }
693
694 fn mob_jump_height(&self) -> f64 {
695 f64::from(self.settings.max_up_step()).max(1.125)
696 }
697
698 fn get_node_and_update_cost_to_max(
699 &mut self,
700 x: i32,
701 y: i32,
702 z: i32,
703 path_type: PathType,
704 cost: f32,
705 ) -> i32 {
706 let node = self.nodes.get_node(x, y, z);
707 node.path_type = path_type;
708 node.cost_malus = node.cost_malus.max(cost);
709 node.hash()
710 }
711
712 fn get_blocked_node(&mut self, x: i32, y: i32, z: i32) -> i32 {
713 let node = self.nodes.get_node(x, y, z);
714 node.path_type = PathType::Blocked;
715 node.cost_malus = -1.0;
716 node.hash()
717 }
718
719 fn get_closed_node(&mut self, x: i32, y: i32, z: i32, path_type: PathType) -> i32 {
720 let node = self.nodes.get_node(x, y, z);
721 node.closed = true;
722 node.path_type = path_type;
723 node.cost_malus = path_type.default_malus();
724 node.hash()
725 }
726}
727
728const fn clockwise_direction_index(index: usize) -> usize {
729 (index + 1) % VANILLA_HORIZONTAL_DIRECTIONS.len()
730}