use crate::navmesh::detour::Obstacle;
use crate::navmesh::num::{i32_to_f32, trunc_i32};
use crate::navmesh::recast::compact::{CompactHeightfield, chamfer};
fn flag(set: &[bool; 64], area: u8) -> bool {
set.get(usize::from(area)).copied().unwrap_or(false)
}
pub fn dilate_area(chf: &mut CompactHeightfield, radius: i32, target: u8, mask: &[bool; 64]) {
let n = chf.spans.len();
let mut dist: Vec<u8> = chf
.areas
.iter()
.map(|&a| if a == target { 0 } else { 255 })
.collect();
let mut label: Vec<(u8, u16)> = chf
.areas
.iter()
.zip(&chf.sub_areas)
.map(|(&a, &s)| (a, s))
.collect();
dist.resize(n, 255);
label.resize(n, (0, 0));
chamfer(chf, &mut dist, &mut label);
let limit = radius.wrapping_mul(2);
for i in 0..n {
let d = i32::from(dist.get(i).copied().unwrap_or(255));
let Some(&area) = chf.areas.get(i) else {
continue;
};
if flag(mask, area) && d <= limit {
if let Some(a) = chf.areas.get_mut(i) {
*a = target;
}
if let (Some(s), Some(&(_, sub))) = (chf.sub_areas.get_mut(i), label.get(i)) {
*s = sub;
}
}
}
}
#[derive(Clone, Copy, Default)]
struct TreeAcc {
count: i64,
sum_x: i64,
sum_y: i64,
sum_z: i64,
min_x: i32,
max_x: i32,
min_z: i32,
max_z: i32,
footprint: i32,
}
#[expect(
clippy::cast_precision_loss,
reason = "C int to float conversion of a cell index sum; rounds to nearest as in C"
)]
fn i64_to_f32(i: i64) -> f32 {
i as f32
}
fn part_min_dist(
chf: &CompactHeightfield,
dist: &[u8],
label: &[(u8, u16)],
tree_area: u8,
part_count: usize,
) -> Vec<u16> {
let (w, h) = (chf.width, chf.height);
let mut min_dist = vec![65535u16; part_count];
for y in 0..h {
for x in 0..w {
for i in chf.column_range(x, y) {
let Some(&(l_area, l_part)) = label.get(i) else {
continue;
};
if l_area != tree_area {
continue;
}
let own = u16::from(dist.get(i).copied().unwrap_or(255));
for dir in 0..4 {
let d = match chf.neighbor(x, y, i, dir) {
None => own,
Some((_, _, ni)) => {
if label.get(ni) == label.get(i) {
continue;
}
u16::from(dist.get(ni).copied().unwrap_or(255)).saturating_add(own)
}
};
if let Some(m) = min_dist.get_mut(usize::from(l_part)) {
*m = (*m).min(d);
}
}
}
}
}
min_dist
}
fn tree_records(chf: &CompactHeightfield, acc: &[TreeAcc]) -> Vec<Obstacle> {
let border = i32_to_f32(chf.border_size);
let cs = chf.cs;
let ch = chf.ch;
let mut out = Vec::new();
for a in acc {
if a.count == 0 {
continue;
}
let count = i64_to_f32(a.count);
let mut o = Obstacle::default();
o.pos[0] = (i64_to_f32(a.sum_x) / count + border + 0.5f32) * cs + chf.bmin[0];
o.pos[1] = (i64_to_f32(a.sum_y) / count + border + 0.5f32) * ch + chf.bmin[1];
o.pos[2] = (i64_to_f32(a.sum_z) / count + border + 0.5f32) * cs + chf.bmin[2];
o.radius = i32_to_f32(a.footprint) * cs * 0.5f32;
out.push(o);
}
out
}
pub fn extract_tree_obstacles(
chf: &mut CompactHeightfield,
tree_area: u8,
walkable_area: u8,
part_count: usize,
seed_areas: &[bool; 64],
clearance: f32,
max_footprint: f32,
) -> Vec<Obstacle> {
let part_count = part_count.min(65536);
let n = chf.spans.len();
let w = chf.width;
let h = chf.height;
let mut dist: Vec<u8> = chf
.areas
.iter()
.map(|&a| if flag(seed_areas, a) { 0 } else { 255 })
.collect();
let mut label: Vec<(u8, u16)> = chf
.areas
.iter()
.zip(&chf.sub_areas)
.map(|(&a, &s)| (a, s))
.collect();
dist.resize(n, 255);
label.resize(n, (0, 0));
chamfer(chf, &mut dist, &mut label);
let mut min_dist = part_min_dist(chf, &dist, &label, tree_area, part_count);
let thr = u16::try_from(trunc_i32((clearance + clearance) / chf.cs) & 0xffff).unwrap_or(0);
let mut acc = vec![TreeAcc::default(); part_count];
for y in 0..h {
for x in 0..w {
for i in chf.column_range(x, y) {
if chf.areas.get(i) != Some(&tree_area) {
continue;
}
let Some(&sub) = chf.sub_areas.get(i) else {
continue;
};
let p = usize::from(sub);
if p >= part_count || min_dist.get(p).is_none_or(|&m| thr >= m) {
continue;
}
let sy = chf.spans.get(i).map_or(0, |s| i64::from(s.y));
if let Some(a) = acc.get_mut(p) {
if a.count == 0 {
a.min_x = x;
a.max_x = x;
a.min_z = y;
a.max_z = y;
}
a.count += 1;
a.sum_x += i64::from(x);
a.sum_y += sy;
a.sum_z += i64::from(y);
a.min_x = a.min_x.min(x);
a.max_x = a.max_x.max(x);
a.min_z = a.min_z.min(y);
a.max_z = a.max_z.max(y);
}
}
}
}
let max_cells = trunc_i32(max_footprint / chf.cs);
for (p, a) in acc.iter_mut().enumerate() {
if a.count == 0 {
continue;
}
let mut size = a.max_z - a.min_z;
let wx = a.max_x - a.min_x;
if size < wx {
size = wx;
}
if max_cells < size + 1 {
if let Some(m) = min_dist.get_mut(p) {
*m = 0;
}
a.count = 0;
} else {
a.footprint = size + 1;
}
}
for i in 0..n {
if chf.areas.get(i) != Some(&tree_area) {
continue;
}
let p = label.get(i).map_or(usize::MAX, |l| usize::from(l.1));
let ok = p < part_count && min_dist.get(p).is_some_and(|&m| thr < m);
if let Some(a) = chf.areas.get_mut(i) {
*a = if ok { walkable_area } else { 0 };
}
if let Some(s) = chf.sub_areas.get_mut(i) {
*s = 0;
}
}
tree_records(chf, &acc)
}
pub fn remap_and_roof(chf: &mut CompactHeightfield) {
for a in &mut chf.areas {
match *a {
7 | 9 => *a = 1,
11 => *a = 8,
_ => {}
}
}
for z in 0..chf.height {
for x in 0..chf.width {
let range = chf.column_range(x, z);
if range.is_empty() {
continue;
}
let top = range.end - 1;
let h = chf.spans.get(top).map_or(0, |s| s.h);
if let Some(a) = chf.areas.get_mut(top)
&& *a == 8
&& h == 255
{
*a = 1;
}
}
}
}