dayzmake_core/navmesh/
islands.rs1use std::collections::BTreeMap;
5
6use crate::navmesh::detour::{NavMesh, decode_poly_ref, find_nearest_poly};
7
8const NULL_LINK: u32 = 0xffff_ffff;
10const FLAG_ISOLATED: u16 = 0x8000;
12const FLAG_DISABLED: u16 = 0x0002;
14const SEED_EXTENTS: [f32; 3] = [30.0, 30.0, 3.0];
16
17#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
19#[non_exhaustive]
20pub struct IslandReport {
21 pub reachable: usize,
23 pub isolated: usize,
25}
26
27pub fn filter_islands(mesh: &mut NavMesh, seed: [f32; 3]) -> Option<IslandReport> {
38 for (_, polys) in mesh.polys_mut() {
39 for p in polys {
40 p.flags &= !FLAG_ISOLATED;
41 }
42 }
43 let (start, _) = find_nearest_poly(
44 mesh,
45 seed,
46 SEED_EXTENTS,
47 0xffff,
48 FLAG_ISOLATED | FLAG_DISABLED,
49 )?;
50
51 let mut visited: BTreeMap<u32, Vec<bool>> = mesh
53 .tiles()
54 .map(|(r, t)| (decode_poly_ref(r).1, vec![false; t.polys.len()]))
55 .collect();
56 let mark = |visited: &mut BTreeMap<u32, Vec<bool>>, slot: u32, poly: usize| -> bool {
57 match visited.get_mut(&slot).and_then(|v| v.get_mut(poly)) {
58 Some(flag) if !*flag => {
59 *flag = true;
60 true
61 }
62 _ => false,
63 }
64 };
65 let mut reachable = 0_usize;
66 let mut stack = Vec::new();
67 {
68 let (_, slot, poly) = decode_poly_ref(start);
69 if let Ok(poly) = usize::try_from(poly)
70 && mark(&mut visited, slot, poly)
71 {
72 stack.push(start);
73 }
74 }
75 while let Some(r) = stack.pop() {
76 reachable += 1;
77 let Some((_, tile)) = mesh.tile_by_ref(r) else {
78 continue;
79 };
80 let (_, _, poly) = decode_poly_ref(r);
81 let Some(p) = usize::try_from(poly).ok().and_then(|i| tile.polys.get(i)) else {
82 continue;
83 };
84 let mut at = p.first_link;
85 let mut budget = tile.links.len();
87 while at != NULL_LINK && budget > 0 {
88 budget -= 1;
89 let Some(link) = usize::try_from(at).ok().and_then(|i| tile.links.get(i)) else {
90 break;
91 };
92 at = link.next;
93 if let Some((slot, _)) = mesh.tile_by_ref(link.reference) {
94 let (_, _, npoly) = decode_poly_ref(link.reference);
95 if let Ok(npoly) = usize::try_from(npoly)
96 && mark(&mut visited, slot, npoly)
97 {
98 stack.push(link.reference);
99 }
100 }
101 }
102 }
103
104 let mut isolated = 0_usize;
105 for (slot, polys) in mesh.polys_mut() {
106 let row = visited.get(&slot);
107 for (i, p) in polys.iter_mut().enumerate() {
108 if !row.and_then(|v| v.get(i)).copied().unwrap_or(false) {
109 p.flags |= FLAG_ISOLATED;
110 isolated += 1;
111 }
112 }
113 }
114 Some(IslandReport {
115 reachable,
116 isolated,
117 })
118}