use std::collections::BTreeMap;
use crate::navmesh::detour::{NavMesh, decode_poly_ref, find_nearest_poly};
const NULL_LINK: u32 = 0xffff_ffff;
const FLAG_ISOLATED: u16 = 0x8000;
const FLAG_DISABLED: u16 = 0x0002;
const SEED_EXTENTS: [f32; 3] = [30.0, 30.0, 3.0];
#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
#[non_exhaustive]
pub struct IslandReport {
pub reachable: usize,
pub isolated: usize,
}
pub fn filter_islands(mesh: &mut NavMesh, seed: [f32; 3]) -> Option<IslandReport> {
for (_, polys) in mesh.polys_mut() {
for p in polys {
p.flags &= !FLAG_ISOLATED;
}
}
let (start, _) = find_nearest_poly(
mesh,
seed,
SEED_EXTENTS,
0xffff,
FLAG_ISOLATED | FLAG_DISABLED,
)?;
let mut visited: BTreeMap<u32, Vec<bool>> = mesh
.tiles()
.map(|(r, t)| (decode_poly_ref(r).1, vec![false; t.polys.len()]))
.collect();
let mark = |visited: &mut BTreeMap<u32, Vec<bool>>, slot: u32, poly: usize| -> bool {
match visited.get_mut(&slot).and_then(|v| v.get_mut(poly)) {
Some(flag) if !*flag => {
*flag = true;
true
}
_ => false,
}
};
let mut reachable = 0_usize;
let mut stack = Vec::new();
{
let (_, slot, poly) = decode_poly_ref(start);
if let Ok(poly) = usize::try_from(poly)
&& mark(&mut visited, slot, poly)
{
stack.push(start);
}
}
while let Some(r) = stack.pop() {
reachable += 1;
let Some((_, tile)) = mesh.tile_by_ref(r) else {
continue;
};
let (_, _, poly) = decode_poly_ref(r);
let Some(p) = usize::try_from(poly).ok().and_then(|i| tile.polys.get(i)) else {
continue;
};
let mut at = p.first_link;
let mut budget = tile.links.len();
while at != NULL_LINK && budget > 0 {
budget -= 1;
let Some(link) = usize::try_from(at).ok().and_then(|i| tile.links.get(i)) else {
break;
};
at = link.next;
if let Some((slot, _)) = mesh.tile_by_ref(link.reference) {
let (_, _, npoly) = decode_poly_ref(link.reference);
if let Ok(npoly) = usize::try_from(npoly)
&& mark(&mut visited, slot, npoly)
{
stack.push(link.reference);
}
}
}
}
let mut isolated = 0_usize;
for (slot, polys) in mesh.polys_mut() {
let row = visited.get(&slot);
for (i, p) in polys.iter_mut().enumerate() {
if !row.and_then(|v| v.get(i)).copied().unwrap_or(false) {
p.flags |= FLAG_ISOLATED;
isolated += 1;
}
}
}
Some(IslandReport {
reachable,
isolated,
})
}