use std::io;
use super::dayz::{
areas::{dilate_area, extract_tree_obstacles, remap_and_roof},
filters::{filter_low_height_multi, mode_filter},
slope::walkable,
};
use super::detour::{
CreateParams, Obstacle, TileData, TileExtra, TilePart, TilePartPoly, create_tile_data,
stored_off_mesh,
};
use super::links::{Links, generate_links};
use super::num::{ceil_i32, i32_to_f32, trunc_i32};
use super::recast::{
compact::{CompactHeightfield, build_compact, erode, mark_box_area},
contour::{RC_CONTOUR_TESS_WALL_EDGES, build_contours},
filter::{filter_ledges, filter_low_hanging},
heightfield::Heightfield,
mesh::{PolyMesh, build_poly_mesh},
rasterize::{RasterMode, RasterParams, rasterize_part, rasterize_triangle},
region::{build_distance_field, build_regions},
};
use super::wire::{CellClass, TileGroup, TileInput, WorldParams};
#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
#[non_exhaustive]
pub enum DoorPolicy {
#[default]
Closed,
Open,
Enabled,
}
#[derive(Debug, Clone, PartialEq)]
#[non_exhaustive]
pub struct BuildOptions {
pub links: bool,
pub doors: DoorPolicy,
pub sea_level: Option<f32>,
}
impl Default for BuildOptions {
fn default() -> Self {
Self {
links: true,
doors: DoorPolicy::Closed,
sea_level: None,
}
}
}
#[derive(Debug, Clone, Default, PartialEq)]
#[non_exhaustive]
pub struct TileConfig {
pub cells: i32,
pub cs: f32,
pub ch: f32,
pub walkable_height: i32,
pub crouch_height: i32,
pub prone_height: i32,
pub walkable_climb: i32,
pub walkable_radius: i32,
pub deep_water: i32,
pub sea_level: i32,
pub border_size: i32,
pub width: i32,
pub pad: f32,
pub max_simplification_error: f32,
pub max_edge_len: i32,
pub max_vertical_error: f32,
pub min_region_area: i32,
pub merge_region_area: i32,
pub nvp: usize,
pub door_radius: i32,
pub slope_threshold: f32,
}
#[must_use]
pub fn tile_config(
world: &WorldParams,
cell_class: &CellClass,
options: &BuildOptions,
) -> TileConfig {
let b = &world.world;
let cs = cell_class.cell_size();
let walkable_radius = ceil_i32((b.diameter * 0.5_f32) / cs);
let border_size = 10.max(walkable_radius.saturating_sub(trunc_i32(-3.0_f32 / cs)));
let sea = options.sea_level.unwrap_or(b.deep_sea_height);
let min_region = trunc_i32((1.0_f32 / cs) * (1.0_f32 / cs));
TileConfig {
cells: cell_class.cells,
cs,
ch: 0.1,
walkable_height: ceil_i32(b.stand_height / 0.1_f32),
crouch_height: ceil_i32(b.crouch_height / 0.1_f32).saturating_sub(2),
prone_height: ceil_i32(b.prone_height / 0.1_f32).saturating_sub(2),
walkable_climb: ceil_i32(b.max_step_height / 0.1_f32),
walkable_radius,
deep_water: ceil_i32(b.deep_water_depth / 0.1_f32),
sea_level: ceil_i32(sea / 0.1_f32),
border_size,
width: cell_class
.cells
.saturating_add(border_size.saturating_mul(2)),
pad: i32_to_f32(border_size) * cs,
max_simplification_error: b.contour_max_error / cs,
max_edge_len: 120,
max_vertical_error: 8.0,
min_region_area: min_region,
merge_region_area: 400,
nvp: 6,
door_radius: trunc_i32(i32_to_f32(walkable_radius) * 0.8_f32),
slope_threshold: ((b.max_slope / 180.0_f32) * std::f32::consts::PI).cos(),
}
}
#[derive(Debug, Clone, PartialEq)]
#[non_exhaustive]
#[expect(
clippy::large_enum_variant,
reason = "the tile is returned by value; a box would only move it"
)]
pub enum TileOutcome {
#[non_exhaustive]
Built {
data: TileData,
stray_part_ids: usize,
obstacles: usize,
},
Empty,
}
struct ExtraPart {
object_id: u64,
part_index: u32,
area: u8,
state: u8,
polys: Vec<u32>,
}
pub const MAX_SPANS: usize = 1 << 26;
const SEA_FLOOR: f32 = -500.0;
const NULL_AREA: u8 = 0;
const TERRAIN_AREA: u32 = 1;
const LADDER_AREA: u32 = 15;
const HIDE_AREA: u32 = 14;
fn low_byte(area: u32) -> u8 {
u8::try_from(area & 0xff).unwrap_or_default()
}
fn part_id(counter: usize) -> u16 {
u16::try_from(counter & 0xffff).unwrap_or_default()
}
fn area_u8(area: u32) -> Option<u8> {
u8::try_from(area).ok().filter(|a| *a < 64)
}
fn extras_list(input: &TileInput, doors: DoorPolicy) -> (Vec<ExtraPart>, usize) {
let mut extras = Vec::new();
let mut tree_items = 0;
for g in &input.groups {
if g.area == 10 {
tree_items = g.parts.len();
continue;
}
let state = match doors {
DoorPolicy::Closed if g.area == 12 => 0,
DoorPolicy::Open if g.area == 13 => 0,
_ => 1,
};
for p in &g.parts {
extras.push(ExtraPart {
object_id: p.object_id,
part_index: p.part_index,
area: low_byte(g.area),
state,
polys: Vec::new(),
});
}
}
(extras, tree_items)
}
fn raster_triangles(
hf: &mut Heightfield,
verts: &[[f32; 3]],
params: &RasterParams,
slope: Option<f32>,
) {
for [v0, v1, v2] in verts.as_chunks::<3>().0.iter().copied() {
let mut p = *params;
if let Some(threshold) = slope
&& !walkable(threshold, v0, v1, v2)
{
p.area = NULL_AREA;
}
rasterize_triangle(hf, v0, v2, v1, &p);
}
}
fn part_verts(input: &TileInput, group: usize, part: usize) -> &[[f32; 3]] {
input
.part_vertex_range(group, part)
.and_then(|range| input.groups.get(group)?.verts.get(range))
.unwrap_or(&[])
}
fn part_triangles(input: &TileInput, group: usize, part: usize) -> Vec<[f32; 3]> {
let verts = part_verts(input, group, part);
let mut out = Vec::with_capacity(verts.len());
for [v0, v1, v2] in verts.as_chunks::<3>().0.iter().copied() {
out.extend([v0, v2, v1]);
}
out
}
fn rasterize_objects<'a>(
hf: &mut Heightfield,
input: &'a TileInput,
cfg: &TileConfig,
obstacles: bool,
) -> Vec<&'a TileGroup> {
let mut ladders = Vec::new();
let mut part_counter = 0_usize;
let slope = Some(cfg.slope_threshold);
for (gi, g) in input.groups.iter().enumerate() {
if g.area == TERRAIN_AREA {
continue;
}
if g.area == LADDER_AREA {
ladders.push(g);
continue;
}
let Some(area) = area_u8(g.area) else {
continue;
};
let mut params = RasterParams {
area,
walkable_climb: cfg.walkable_climb,
walkable_height: cfg.walkable_height,
..RasterParams::default()
};
match g.area {
6 | 7 | 8 | 9 | 11 => raster_triangles(hf, &g.verts, ¶ms, slope),
2 => {
params.mode = RasterMode::Water;
params.water_depth = cfg.walkable_climb;
raster_triangles(hf, &g.verts, ¶ms, None);
params.area = 3;
params.water_depth = cfg.deep_water;
raster_triangles(hf, &g.verts, ¶ms, None);
}
10 => {
if g.parts.is_empty() {
params.mode = RasterMode::Tree;
raster_triangles(hf, &g.verts, ¶ms, None);
continue;
}
for k in 0..g.parts.len() {
if obstacles {
params.mode = RasterMode::Tree;
params.sub_area = part_id(k);
} else {
params.mode = RasterMode::Add;
params.area = NULL_AREA;
params.sub_area = 0;
}
raster_triangles(hf, part_verts(input, gi, k), ¶ms, None);
}
}
12..=14 => {
params.mode = if g.area == 14 {
RasterMode::PaintOrAdd
} else {
RasterMode::PaintBelow
};
if g.area == 14 {
params.flag_merge_threshold = 1;
} else {
params.flag_merge_threshold = cfg.walkable_height;
}
if g.parts.is_empty() {
raster_triangles(hf, &g.verts, ¶ms, None);
continue;
}
for k in 0..g.parts.len() {
params.sub_area = part_id(part_counter);
part_counter = part_counter.saturating_add(1);
rasterize_part(hf, &part_triangles(input, gi, k), ¶ms);
}
}
18 => raster_triangles(hf, &g.verts, ¶ms, None),
_ => {}
}
}
ladders
}
pub(crate) fn min_region_table(cfg: &TileConfig) -> [i32; 64] {
let mut table = [cfg.min_region_area; 64];
for id in [10, 12, 13, 14] {
if let Some(e) = table.get_mut(id) {
*e = i32::MAX;
}
}
table
}
fn areas_flag(mask: &mut [bool; 64], ids: &[usize], value: bool) {
for &id in ids {
if let Some(m) = mask.get_mut(id) {
*m = value;
}
}
}
fn post_compact(
chf: &mut CompactHeightfield,
cfg: &TileConfig,
pbmin: [f32; 3],
pbmax: [f32; 3],
tree_items: usize,
obstacles: bool,
) -> io::Result<Vec<Obstacle>> {
mark_box_area(
chf,
[pbmin[0], SEA_FLOOR, pbmin[2]],
[pbmax[0], i32_to_f32(cfg.sea_level) * cfg.ch, pbmax[2]],
5,
);
let mut mask = [true; 64];
areas_flag(&mut mask, &[12, 13, 14], false);
dilate_area(chf, cfg.door_radius, 13, &mask);
dilate_area(chf, cfg.door_radius, 12, &mask);
dilate_area(chf, cfg.walkable_radius, 14, &mask);
dilate_area(chf, cfg.walkable_radius, 16, &mask);
let mut found = Vec::new();
if obstacles && tree_items > 0 {
let mut seeds = [false; 64];
areas_flag(&mut seeds, &[0, 10, 12, 13, 14], true);
found = extract_tree_obstacles(chf, 10, 1, tree_items, &seeds, 2.0, 3.0);
}
erode(chf, cfg.walkable_radius).map_err(|e| error!("could not erode: {e}"))?;
remap_and_roof(chf);
Ok(found)
}
fn area_flags(area: u8) -> u16 {
match area {
1 | 6 | 7 | 9 | 14 => 0x01,
2 | 4 => 0x11,
3 => 0x10,
5 => 0x20,
8 => 0x09,
12 | 13 => 0x05,
16 => 0x0400,
17 => 0x0800,
_ => 0,
}
}
fn attach_parts(
extras: &mut [ExtraPart],
sub_areas: &[u16],
areas: &[u8],
flags: &mut [u16],
) -> usize {
let mut stray = 0;
if extras.is_empty() {
return stray;
}
for (i, (&sub, &area)) in sub_areas.iter().zip(areas).enumerate() {
let Some(part) = extras.get_mut(usize::from(sub)) else {
stray += 1;
continue;
};
if part.area != area {
continue;
}
if let Some(f) = flags.get_mut(i) {
if part.state == 0 {
*f |= 0x2;
} else {
*f &= !0x2;
}
}
part.polys.push(u32::try_from(i).unwrap_or(u32::MAX));
}
stray
}
fn attach_off_mesh(extras: &mut [ExtraPart], links: &Links, stored: &[bool], ground: usize) {
let mut poly = ground;
for (part, &keep) in links.parts.iter().zip(stored) {
if !keep {
continue;
}
if let Some(part) = part.and_then(|p| extras.get_mut(usize::from(p))) {
part.polys.push(u32::try_from(poly).unwrap_or(u32::MAX));
}
poly += 1;
}
}
fn extra_section(extras: &[ExtraPart], obstacles: Vec<Obstacle>) -> io::Result<TileExtra> {
let mut extra = TileExtra::default();
for part in extras {
let first = if part.polys.is_empty() {
-1
} else {
i32::try_from(extra.part_polys.len()).map_err(|_| error!("too many part polygons"))?
};
extra.parts.push(TilePart {
object_id: part.object_id,
part_index: part.part_index,
first_poly: first,
});
let base = extra.part_polys.len();
for (k, poly) in part.polys.iter().enumerate() {
let next = if k + 1 < part.polys.len() {
i32::try_from(base + k + 1).map_err(|_| error!("too many part polygons"))?
} else {
-1
};
extra.part_polys.push(TilePartPoly { poly: *poly, next });
}
}
extra.obstacles = obstacles;
Ok(extra)
}
pub fn build_tile(
world: &WorldParams,
input: &TileInput,
options: &BuildOptions,
) -> io::Result<TileOutcome> {
build_tile_with_span_limit(world, input, options, MAX_SPANS)
}
#[doc(hidden)]
pub fn build_tile_with_span_limit(
world: &WorldParams,
input: &TileInput,
options: &BuildOptions,
span_limit: usize,
) -> io::Result<TileOutcome> {
let class = usize::try_from(input.cell_class)
.ok()
.and_then(|i| world.cell_classes.get(i))
.ok_or_else(|| error!("unknown cell class {}", input.cell_class))?;
let cfg = tile_config(world, class, options);
if cfg.cells <= 0 || !cfg.cs.is_finite() || cfg.cs <= 0.0 {
return Err(error!("cell class has {} cells of {} m", cfg.cells, cfg.cs));
}
let obstacles_on = world.world.obstacles;
let (mut extras, tree_items) = extras_list(input, options.doors);
let pad = cfg.pad;
let pbmin = [input.bmin[0] - pad, input.bmin[1], input.bmin[2] - pad];
let pbmax = [input.bmax[0] + pad, input.bmax[1], input.bmax[2] + pad];
let mut hf = Heightfield::new(cfg.width, cfg.width, pbmin, pbmax, cfg.cs, cfg.ch)
.map_err(|e| error!("could not create solid heightfield: {e}"))?;
hf.set_span_limit(span_limit);
if let Some(g) = input.groups.first()
&& let Some(area) = area_u8(g.area)
{
let p = RasterParams {
area,
..RasterParams::default()
};
raster_triangles(&mut hf, &g.verts, &p, Some(cfg.slope_threshold));
}
hf.check_span_budget()?;
mode_filter(&mut hf, cfg.border_size);
let ladders = rasterize_objects(&mut hf, input, &cfg, obstacles_on);
hf.check_span_budget()?;
filter_low_height_multi(
&mut hf,
[cfg.prone_height, cfg.crouch_height, cfg.walkable_height],
[0, 16, 17],
18,
);
filter_low_hanging(&mut hf, cfg.walkable_climb);
let mut skip = [false; 64];
areas_flag(&mut skip, &[0, 1], true);
filter_ledges(&mut hf, cfg.walkable_height, cfg.walkable_climb, &skip);
let mut chf = build_compact(cfg.prone_height, cfg.walkable_climb, &hf)
.map_err(|e| error!("could not build compact data: {e}"))?;
let obstacles = post_compact(&mut chf, &cfg, pbmin, pbmax, tree_items, obstacles_on)?;
let links = if options.links {
let hide: Vec<bool> = extras
.iter()
.map(|e| u32::from(e.area) == HIDE_AREA)
.collect();
generate_links(&mut chf, &hf, &ladders, &cfg, world, &hide)?
} else {
Links::default()
};
drop(hf);
build_distance_field(&mut chf).map_err(|e| error!("could not build distance field: {e}"))?;
build_regions(
&mut chf,
cfg.border_size,
&min_region_table(&cfg),
cfg.merge_region_area,
)
.map_err(|e| error!("could not build regions: {e}"))?;
let cset = build_contours(
&chf,
cfg.max_simplification_error,
cfg.max_vertical_error,
cfg.max_edge_len,
RC_CONTOUR_TESS_WALL_EDGES,
)
.map_err(|e| error!("could not create contours: {e}"))?;
if cset.contours.is_empty() {
return Ok(TileOutcome::Empty);
}
let pm = build_poly_mesh(&cset, cfg.nvp)
.map_err(|e| error!("could not triangulate contours: {e}"))?;
if pm.areas.is_empty() {
return Ok(TileOutcome::Empty);
}
finish_tile(world, input, &cfg, &pm, &mut extras, obstacles, &links)
}
fn finish_tile(
world: &WorldParams,
input: &TileInput,
cfg: &TileConfig,
pm: &PolyMesh,
extras: &mut [ExtraPart],
obstacles: Vec<Obstacle>,
links: &Links,
) -> io::Result<TileOutcome> {
let pad = cfg.pad;
let mut flags: Vec<u16> = pm.areas.iter().map(|a| area_flags(*a)).collect();
let stray = attach_parts(extras, &pm.sub_areas, &pm.areas, &mut flags);
let obstacle_count = obstacles.len();
let no_extra = TileExtra::default();
let mut params = CreateParams::new(
&pm.verts,
&pm.polys,
&flags,
&pm.areas,
cfg.nvp,
&links.off_mesh,
&no_extra,
);
params.tile_x = input.x;
params.tile_y = input.z;
params.bmin = [
(input.bmin[0] - pad) + pad,
input.bmin[1],
(input.bmin[2] - pad) + pad,
];
params.bmax = [
(input.bmax[0] + pad) - pad,
input.bmax[1] + i32_to_f32(cfg.prone_height) * 0.1_f32,
(input.bmax[2] + pad) - pad,
];
params.walkable_height = world.world.stand_height;
params.walkable_radius = world.world.diameter * 0.5_f32;
params.walkable_climb = world.world.max_step_height;
params.cs = cfg.cs;
params.ch = cfg.ch;
attach_off_mesh(extras, links, &stored_off_mesh(¶ms), pm.areas.len());
let extra = extra_section(extras, obstacles)?;
params.extra = &extra;
let data =
create_tile_data(¶ms).map_err(|e| error!("could not build Detour navmesh: {e}"))?;
Ok(TileOutcome::Built {
data,
stray_part_ids: stray,
obstacles: obstacle_count,
})
}
#[cfg(test)]
mod tests {
use super::{ExtraPart, Links, attach_off_mesh, part_id};
use crate::navmesh::detour::OffMeshInput;
fn extra(area: u8) -> ExtraPart {
ExtraPart {
object_id: 0,
part_index: 0,
area,
state: 1,
polys: Vec::new(),
}
}
#[test]
fn off_mesh_polygons_join_their_hide_part() {
let mut extras = vec![extra(12), extra(14), extra(14)];
extras[1].polys = vec![5, 6];
let links = Links {
off_mesh: vec![OffMeshInput::default(); 6],
parts: vec![Some(1), Some(2), None, Some(1), Some(9), Some(2)],
};
let stored = [true, false, true, true, true, true];
attach_off_mesh(&mut extras, &links, &stored, 10);
assert_eq!(extras[1].polys, [5, 6, 10, 12]);
assert_eq!(extras[2].polys, [14]);
assert_eq!(extras[0].polys, Vec::<u32>::new());
}
#[test]
fn part_ids_wrap_at_65536() {
assert_eq!(part_id(0), 0);
assert_eq!(part_id(65535), 65535);
assert_eq!(part_id(65536), 0);
assert_eq!(part_id(65537), 1);
}
}