Skip to main content

dayzmake_core/navmesh/
islands.rs

1//! The island filter (spec 8.5): flags every polygon that cannot be reached from a seed position
2//! with the "isolated" bit `0x8000`.
3
4use std::collections::BTreeMap;
5
6use crate::navmesh::detour::{NavMesh, decode_poly_ref, find_nearest_poly};
7
8/// `DT_NULL_LINK`.
9const NULL_LINK: u32 = 0xffff_ffff;
10/// The polygon flag of the island filter.
11const FLAG_ISOLATED: u16 = 0x8000;
12/// The polygon flag of a disabled polygon (a closed door).
13const FLAG_DISABLED: u16 = 0x0002;
14/// The search box around the seed (`x`, `y`, `z` half extents).
15const SEED_EXTENTS: [f32; 3] = [30.0, 30.0, 3.0];
16
17/// What [`filter_islands`] found.
18#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
19#[non_exhaustive]
20pub struct IslandReport {
21    /// Polygons reachable from the seed.
22    pub reachable: usize,
23    /// Polygons flagged `0x8000`: every other polygon of every tile, off-mesh polygons included.
24    pub isolated: usize,
25}
26
27/// Runs the island filter on `mesh`.
28///
29/// Clears `0x8000` on every polygon, finds the polygon nearest to `seed` (search box
30/// `(30, 30, 3)`, include flags `0xffff`, exclude flags `0x8002`) and floods the mesh from it
31/// depth-first over every link, ignoring flags (so closed doors are traversed) and following
32/// one-way off-mesh links in their direction only. Every polygon not visited, off-mesh polygons
33/// included, gets `0x8000`.
34///
35/// Returns `None` when no polygon is found near the seed. The flags are cleared in that case
36/// too, and nothing is flagged.
37pub 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    // Visited polygons per tile slot. Marked when pushed, so each polygon is on the stack once.
52    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        // A hostile link list may loop: a chain cannot be longer than the link array.
86        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}