1use std::io;
11
12use super::dayz::{
13 areas::{dilate_area, extract_tree_obstacles, remap_and_roof},
14 filters::{filter_low_height_multi, mode_filter},
15 slope::walkable,
16};
17use super::detour::{
18 CreateParams, Obstacle, TileData, TileExtra, TilePart, TilePartPoly, create_tile_data,
19 stored_off_mesh,
20};
21use super::links::{Links, generate_links};
22use super::num::{ceil_i32, i32_to_f32, trunc_i32};
23use super::recast::{
24 compact::{CompactHeightfield, build_compact, erode, mark_box_area},
25 contour::{RC_CONTOUR_TESS_WALL_EDGES, build_contours},
26 filter::{filter_ledges, filter_low_hanging},
27 heightfield::Heightfield,
28 mesh::{PolyMesh, build_poly_mesh},
29 rasterize::{RasterMode, RasterParams, rasterize_part, rasterize_triangle},
30 region::{build_distance_field, build_regions},
31};
32use super::wire::{CellClass, TileGroup, TileInput, WorldParams};
33
34#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
36#[non_exhaustive]
37pub enum DoorPolicy {
38 #[default]
40 Closed,
41 Open,
43 Enabled,
45}
46
47#[derive(Debug, Clone, PartialEq)]
49#[non_exhaustive]
50pub struct BuildOptions {
51 pub links: bool,
53 pub doors: DoorPolicy,
55 pub sea_level: Option<f32>,
57}
58
59impl Default for BuildOptions {
60 fn default() -> Self {
61 Self {
62 links: true,
63 doors: DoorPolicy::Closed,
64 sea_level: None,
65 }
66 }
67}
68
69#[derive(Debug, Clone, Default, PartialEq)]
72#[non_exhaustive]
73pub struct TileConfig {
74 pub cells: i32,
76 pub cs: f32,
78 pub ch: f32,
80 pub walkable_height: i32,
82 pub crouch_height: i32,
84 pub prone_height: i32,
86 pub walkable_climb: i32,
88 pub walkable_radius: i32,
90 pub deep_water: i32,
92 pub sea_level: i32,
94 pub border_size: i32,
96 pub width: i32,
98 pub pad: f32,
100 pub max_simplification_error: f32,
102 pub max_edge_len: i32,
104 pub max_vertical_error: f32,
106 pub min_region_area: i32,
108 pub merge_region_area: i32,
110 pub nvp: usize,
112 pub door_radius: i32,
114 pub slope_threshold: f32,
116}
117
118#[must_use]
122pub fn tile_config(
123 world: &WorldParams,
124 cell_class: &CellClass,
125 options: &BuildOptions,
126) -> TileConfig {
127 let b = &world.world;
128 let cs = cell_class.cell_size();
129 let walkable_radius = ceil_i32((b.diameter * 0.5_f32) / cs);
130 let border_size = 10.max(walkable_radius.saturating_sub(trunc_i32(-3.0_f32 / cs)));
131 let sea = options.sea_level.unwrap_or(b.deep_sea_height);
132 let min_region = trunc_i32((1.0_f32 / cs) * (1.0_f32 / cs));
133 TileConfig {
134 cells: cell_class.cells,
135 cs,
136 ch: 0.1,
137 walkable_height: ceil_i32(b.stand_height / 0.1_f32),
138 crouch_height: ceil_i32(b.crouch_height / 0.1_f32).saturating_sub(2),
139 prone_height: ceil_i32(b.prone_height / 0.1_f32).saturating_sub(2),
140 walkable_climb: ceil_i32(b.max_step_height / 0.1_f32),
141 walkable_radius,
142 deep_water: ceil_i32(b.deep_water_depth / 0.1_f32),
143 sea_level: ceil_i32(sea / 0.1_f32),
144 border_size,
145 width: cell_class
146 .cells
147 .saturating_add(border_size.saturating_mul(2)),
148 pad: i32_to_f32(border_size) * cs,
149 max_simplification_error: b.contour_max_error / cs,
150 max_edge_len: 120,
151 max_vertical_error: 8.0,
152 min_region_area: min_region,
153 merge_region_area: 400,
154 nvp: 6,
155 door_radius: trunc_i32(i32_to_f32(walkable_radius) * 0.8_f32),
156 slope_threshold: ((b.max_slope / 180.0_f32) * std::f32::consts::PI).cos(),
157 }
158}
159
160#[derive(Debug, Clone, PartialEq)]
162#[non_exhaustive]
163#[expect(
164 clippy::large_enum_variant,
165 reason = "the tile is returned by value; a box would only move it"
166)]
167pub enum TileOutcome {
168 #[non_exhaustive]
170 Built {
171 data: TileData,
173 stray_part_ids: usize,
175 obstacles: usize,
177 },
178 Empty,
180}
181
182struct ExtraPart {
184 object_id: u64,
185 part_index: u32,
186 area: u8,
187 state: u8,
189 polys: Vec<u32>,
190}
191
192pub const MAX_SPANS: usize = 1 << 26;
197
198const SEA_FLOOR: f32 = -500.0;
199const NULL_AREA: u8 = 0;
200const TERRAIN_AREA: u32 = 1;
202const LADDER_AREA: u32 = 15;
203const HIDE_AREA: u32 = 14;
205
206fn low_byte(area: u32) -> u8 {
208 u8::try_from(area & 0xff).unwrap_or_default()
209}
210
211fn part_id(counter: usize) -> u16 {
214 u16::try_from(counter & 0xffff).unwrap_or_default()
215}
216
217fn area_u8(area: u32) -> Option<u8> {
218 u8::try_from(area).ok().filter(|a| *a < 64)
219}
220
221fn extras_list(input: &TileInput, doors: DoorPolicy) -> (Vec<ExtraPart>, usize) {
223 let mut extras = Vec::new();
224 let mut tree_items = 0;
225 for g in &input.groups {
226 if g.area == 10 {
227 tree_items = g.parts.len();
228 continue;
229 }
230 let state = match doors {
231 DoorPolicy::Closed if g.area == 12 => 0,
232 DoorPolicy::Open if g.area == 13 => 0,
233 _ => 1,
234 };
235 for p in &g.parts {
236 extras.push(ExtraPart {
237 object_id: p.object_id,
238 part_index: p.part_index,
239 area: low_byte(g.area),
240 state,
241 polys: Vec::new(),
242 });
243 }
244 }
245 (extras, tree_items)
246}
247
248fn raster_triangles(
251 hf: &mut Heightfield,
252 verts: &[[f32; 3]],
253 params: &RasterParams,
254 slope: Option<f32>,
255) {
256 for [v0, v1, v2] in verts.as_chunks::<3>().0.iter().copied() {
257 let mut p = *params;
258 if let Some(threshold) = slope
259 && !walkable(threshold, v0, v1, v2)
260 {
261 p.area = NULL_AREA;
262 }
263 rasterize_triangle(hf, v0, v2, v1, &p);
264 }
265}
266
267fn part_verts(input: &TileInput, group: usize, part: usize) -> &[[f32; 3]] {
269 input
270 .part_vertex_range(group, part)
271 .and_then(|range| input.groups.get(group)?.verts.get(range))
272 .unwrap_or(&[])
273}
274
275fn part_triangles(input: &TileInput, group: usize, part: usize) -> Vec<[f32; 3]> {
277 let verts = part_verts(input, group, part);
278 let mut out = Vec::with_capacity(verts.len());
279 for [v0, v1, v2] in verts.as_chunks::<3>().0.iter().copied() {
280 out.extend([v0, v2, v1]);
281 }
282 out
283}
284
285fn rasterize_objects<'a>(
288 hf: &mut Heightfield,
289 input: &'a TileInput,
290 cfg: &TileConfig,
291 obstacles: bool,
292) -> Vec<&'a TileGroup> {
293 let mut ladders = Vec::new();
294 let mut part_counter = 0_usize;
295 let slope = Some(cfg.slope_threshold);
296 for (gi, g) in input.groups.iter().enumerate() {
297 if g.area == TERRAIN_AREA {
298 continue;
299 }
300 if g.area == LADDER_AREA {
301 ladders.push(g);
302 continue;
303 }
304 let Some(area) = area_u8(g.area) else {
305 continue;
306 };
307 let mut params = RasterParams {
308 area,
309 walkable_climb: cfg.walkable_climb,
310 walkable_height: cfg.walkable_height,
311 ..RasterParams::default()
312 };
313 match g.area {
314 6 | 7 | 8 | 9 | 11 => raster_triangles(hf, &g.verts, ¶ms, slope),
315 2 => {
316 params.mode = RasterMode::Water;
317 params.water_depth = cfg.walkable_climb;
319 raster_triangles(hf, &g.verts, ¶ms, None);
320 params.area = 3;
321 params.water_depth = cfg.deep_water;
322 raster_triangles(hf, &g.verts, ¶ms, None);
323 }
324 10 => {
325 if g.parts.is_empty() {
326 params.mode = RasterMode::Tree;
327 raster_triangles(hf, &g.verts, ¶ms, None);
328 continue;
329 }
330 for k in 0..g.parts.len() {
331 if obstacles {
332 params.mode = RasterMode::Tree;
333 params.sub_area = part_id(k);
334 } else {
335 params.mode = RasterMode::Add;
336 params.area = NULL_AREA;
337 params.sub_area = 0;
338 }
339 raster_triangles(hf, part_verts(input, gi, k), ¶ms, None);
340 }
341 }
342 12..=14 => {
343 params.mode = if g.area == 14 {
344 RasterMode::PaintOrAdd
345 } else {
346 RasterMode::PaintBelow
347 };
348 if g.area == 14 {
349 params.flag_merge_threshold = 1;
350 } else {
351 params.flag_merge_threshold = cfg.walkable_height;
352 }
353 if g.parts.is_empty() {
354 raster_triangles(hf, &g.verts, ¶ms, None);
355 continue;
356 }
357 for k in 0..g.parts.len() {
358 params.sub_area = part_id(part_counter);
359 part_counter = part_counter.saturating_add(1);
360 rasterize_part(hf, &part_triangles(input, gi, k), ¶ms);
361 }
362 }
363 18 => raster_triangles(hf, &g.verts, ¶ms, None),
364 _ => {}
365 }
366 }
367 ladders
368}
369
370pub(crate) fn min_region_table(cfg: &TileConfig) -> [i32; 64] {
372 let mut table = [cfg.min_region_area; 64];
373 for id in [10, 12, 13, 14] {
374 if let Some(e) = table.get_mut(id) {
375 *e = i32::MAX;
376 }
377 }
378 table
379}
380
381fn areas_flag(mask: &mut [bool; 64], ids: &[usize], value: bool) {
382 for &id in ids {
383 if let Some(m) = mask.get_mut(id) {
384 *m = value;
385 }
386 }
387}
388
389fn post_compact(
391 chf: &mut CompactHeightfield,
392 cfg: &TileConfig,
393 pbmin: [f32; 3],
394 pbmax: [f32; 3],
395 tree_items: usize,
396 obstacles: bool,
397) -> io::Result<Vec<Obstacle>> {
398 mark_box_area(
400 chf,
401 [pbmin[0], SEA_FLOOR, pbmin[2]],
402 [pbmax[0], i32_to_f32(cfg.sea_level) * cfg.ch, pbmax[2]],
403 5,
404 );
405 let mut mask = [true; 64];
407 areas_flag(&mut mask, &[12, 13, 14], false);
408 dilate_area(chf, cfg.door_radius, 13, &mask);
409 dilate_area(chf, cfg.door_radius, 12, &mask);
410 dilate_area(chf, cfg.walkable_radius, 14, &mask);
411 dilate_area(chf, cfg.walkable_radius, 16, &mask);
412 let mut found = Vec::new();
414 if obstacles && tree_items > 0 {
415 let mut seeds = [false; 64];
416 areas_flag(&mut seeds, &[0, 10, 12, 13, 14], true);
417 found = extract_tree_obstacles(chf, 10, 1, tree_items, &seeds, 2.0, 3.0);
418 }
419 erode(chf, cfg.walkable_radius).map_err(|e| error!("could not erode: {e}"))?;
421 remap_and_roof(chf);
422 Ok(found)
423}
424
425fn area_flags(area: u8) -> u16 {
427 match area {
428 1 | 6 | 7 | 9 | 14 => 0x01,
429 2 | 4 => 0x11,
430 3 => 0x10,
431 5 => 0x20,
432 8 => 0x09,
433 12 | 13 => 0x05,
434 16 => 0x0400,
435 17 => 0x0800,
436 _ => 0,
437 }
438}
439
440fn attach_parts(
443 extras: &mut [ExtraPart],
444 sub_areas: &[u16],
445 areas: &[u8],
446 flags: &mut [u16],
447) -> usize {
448 let mut stray = 0;
449 if extras.is_empty() {
450 return stray;
451 }
452 for (i, (&sub, &area)) in sub_areas.iter().zip(areas).enumerate() {
453 let Some(part) = extras.get_mut(usize::from(sub)) else {
454 stray += 1;
455 continue;
456 };
457 if part.area != area {
458 continue;
459 }
460 if let Some(f) = flags.get_mut(i) {
461 if part.state == 0 {
462 *f |= 0x2;
463 } else {
464 *f &= !0x2;
465 }
466 }
467 part.polys.push(u32::try_from(i).unwrap_or(u32::MAX));
468 }
469 stray
470}
471
472fn attach_off_mesh(extras: &mut [ExtraPart], links: &Links, stored: &[bool], ground: usize) {
477 let mut poly = ground;
478 for (part, &keep) in links.parts.iter().zip(stored) {
479 if !keep {
480 continue;
481 }
482 if let Some(part) = part.and_then(|p| extras.get_mut(usize::from(p))) {
483 part.polys.push(u32::try_from(poly).unwrap_or(u32::MAX));
484 }
485 poly += 1;
486 }
487}
488
489fn extra_section(extras: &[ExtraPart], obstacles: Vec<Obstacle>) -> io::Result<TileExtra> {
491 let mut extra = TileExtra::default();
492 for part in extras {
493 let first = if part.polys.is_empty() {
494 -1
495 } else {
496 i32::try_from(extra.part_polys.len()).map_err(|_| error!("too many part polygons"))?
497 };
498 extra.parts.push(TilePart {
499 object_id: part.object_id,
500 part_index: part.part_index,
501 first_poly: first,
502 });
503 let base = extra.part_polys.len();
504 for (k, poly) in part.polys.iter().enumerate() {
505 let next = if k + 1 < part.polys.len() {
506 i32::try_from(base + k + 1).map_err(|_| error!("too many part polygons"))?
507 } else {
508 -1
509 };
510 extra.part_polys.push(TilePartPoly { poly: *poly, next });
511 }
512 }
513 extra.obstacles = obstacles;
514 Ok(extra)
515}
516
517pub fn build_tile(
524 world: &WorldParams,
525 input: &TileInput,
526 options: &BuildOptions,
527) -> io::Result<TileOutcome> {
528 build_tile_with_span_limit(world, input, options, MAX_SPANS)
529}
530
531#[doc(hidden)]
539pub fn build_tile_with_span_limit(
540 world: &WorldParams,
541 input: &TileInput,
542 options: &BuildOptions,
543 span_limit: usize,
544) -> io::Result<TileOutcome> {
545 let class = usize::try_from(input.cell_class)
546 .ok()
547 .and_then(|i| world.cell_classes.get(i))
548 .ok_or_else(|| error!("unknown cell class {}", input.cell_class))?;
549 let cfg = tile_config(world, class, options);
550 if cfg.cells <= 0 || !cfg.cs.is_finite() || cfg.cs <= 0.0 {
551 return Err(error!("cell class has {} cells of {} m", cfg.cells, cfg.cs));
552 }
553 let obstacles_on = world.world.obstacles;
554
555 let (mut extras, tree_items) = extras_list(input, options.doors);
557 let pad = cfg.pad;
558 let pbmin = [input.bmin[0] - pad, input.bmin[1], input.bmin[2] - pad];
559 let pbmax = [input.bmax[0] + pad, input.bmax[1], input.bmax[2] + pad];
560 let mut hf = Heightfield::new(cfg.width, cfg.width, pbmin, pbmax, cfg.cs, cfg.ch)
561 .map_err(|e| error!("could not create solid heightfield: {e}"))?;
562 hf.set_span_limit(span_limit);
563
564 if let Some(g) = input.groups.first()
566 && let Some(area) = area_u8(g.area)
567 {
568 let p = RasterParams {
569 area,
570 ..RasterParams::default()
571 };
572 raster_triangles(&mut hf, &g.verts, &p, Some(cfg.slope_threshold));
573 }
574 hf.check_span_budget()?;
575 mode_filter(&mut hf, cfg.border_size);
577 let ladders = rasterize_objects(&mut hf, input, &cfg, obstacles_on);
579 hf.check_span_budget()?;
580 filter_low_height_multi(
582 &mut hf,
583 [cfg.prone_height, cfg.crouch_height, cfg.walkable_height],
584 [0, 16, 17],
585 18,
586 );
587 filter_low_hanging(&mut hf, cfg.walkable_climb);
588 let mut skip = [false; 64];
589 areas_flag(&mut skip, &[0, 1], true);
590 filter_ledges(&mut hf, cfg.walkable_height, cfg.walkable_climb, &skip);
591 let mut chf = build_compact(cfg.prone_height, cfg.walkable_climb, &hf)
593 .map_err(|e| error!("could not build compact data: {e}"))?;
594 let obstacles = post_compact(&mut chf, &cfg, pbmin, pbmax, tree_items, obstacles_on)?;
596 let links = if options.links {
598 let hide: Vec<bool> = extras
599 .iter()
600 .map(|e| u32::from(e.area) == HIDE_AREA)
601 .collect();
602 generate_links(&mut chf, &hf, &ladders, &cfg, world, &hide)?
603 } else {
604 Links::default()
605 };
606 drop(hf);
607 build_distance_field(&mut chf).map_err(|e| error!("could not build distance field: {e}"))?;
609 build_regions(
610 &mut chf,
611 cfg.border_size,
612 &min_region_table(&cfg),
613 cfg.merge_region_area,
614 )
615 .map_err(|e| error!("could not build regions: {e}"))?;
616 let cset = build_contours(
618 &chf,
619 cfg.max_simplification_error,
620 cfg.max_vertical_error,
621 cfg.max_edge_len,
622 RC_CONTOUR_TESS_WALL_EDGES,
623 )
624 .map_err(|e| error!("could not create contours: {e}"))?;
625 if cset.contours.is_empty() {
626 return Ok(TileOutcome::Empty);
627 }
628 let pm = build_poly_mesh(&cset, cfg.nvp)
630 .map_err(|e| error!("could not triangulate contours: {e}"))?;
631 if pm.areas.is_empty() {
632 return Ok(TileOutcome::Empty);
633 }
634
635 finish_tile(world, input, &cfg, &pm, &mut extras, obstacles, &links)
636}
637
638fn finish_tile(
640 world: &WorldParams,
641 input: &TileInput,
642 cfg: &TileConfig,
643 pm: &PolyMesh,
644 extras: &mut [ExtraPart],
645 obstacles: Vec<Obstacle>,
646 links: &Links,
647) -> io::Result<TileOutcome> {
648 let pad = cfg.pad;
649 let mut flags: Vec<u16> = pm.areas.iter().map(|a| area_flags(*a)).collect();
650 let stray = attach_parts(extras, &pm.sub_areas, &pm.areas, &mut flags);
651 let obstacle_count = obstacles.len();
652 let no_extra = TileExtra::default();
654 let mut params = CreateParams::new(
655 &pm.verts,
656 &pm.polys,
657 &flags,
658 &pm.areas,
659 cfg.nvp,
660 &links.off_mesh,
661 &no_extra,
662 );
663 params.tile_x = input.x;
664 params.tile_y = input.z;
665 params.bmin = [
666 (input.bmin[0] - pad) + pad,
667 input.bmin[1],
668 (input.bmin[2] - pad) + pad,
669 ];
670 params.bmax = [
671 (input.bmax[0] + pad) - pad,
672 input.bmax[1] + i32_to_f32(cfg.prone_height) * 0.1_f32,
673 (input.bmax[2] + pad) - pad,
674 ];
675 params.walkable_height = world.world.stand_height;
676 params.walkable_radius = world.world.diameter * 0.5_f32;
677 params.walkable_climb = world.world.max_step_height;
678 params.cs = cfg.cs;
679 params.ch = cfg.ch;
680 attach_off_mesh(extras, links, &stored_off_mesh(¶ms), pm.areas.len());
681 let extra = extra_section(extras, obstacles)?;
682 params.extra = &extra;
683 let data =
684 create_tile_data(¶ms).map_err(|e| error!("could not build Detour navmesh: {e}"))?;
685 Ok(TileOutcome::Built {
686 data,
687 stray_part_ids: stray,
688 obstacles: obstacle_count,
689 })
690}
691
692#[cfg(test)]
693mod tests {
694 use super::{ExtraPart, Links, attach_off_mesh, part_id};
695 use crate::navmesh::detour::OffMeshInput;
696
697 fn extra(area: u8) -> ExtraPart {
698 ExtraPart {
699 object_id: 0,
700 part_index: 0,
701 area,
702 state: 1,
703 polys: Vec::new(),
704 }
705 }
706
707 #[test]
710 fn off_mesh_polygons_join_their_hide_part() {
711 let mut extras = vec![extra(12), extra(14), extra(14)];
712 extras[1].polys = vec![5, 6];
714 let links = Links {
715 off_mesh: vec![OffMeshInput::default(); 6],
716 parts: vec![Some(1), Some(2), None, Some(1), Some(9), Some(2)],
717 };
718 let stored = [true, false, true, true, true, true];
720 attach_off_mesh(&mut extras, &links, &stored, 10);
721 assert_eq!(extras[1].polys, [5, 6, 10, 12]);
722 assert_eq!(extras[2].polys, [14]);
724 assert_eq!(extras[0].polys, Vec::<u32>::new());
725 }
726
727 #[test]
729 fn part_ids_wrap_at_65536() {
730 assert_eq!(part_id(0), 0);
731 assert_eq!(part_id(65535), 65535);
732 assert_eq!(part_id(65536), 0);
733 assert_eq!(part_id(65537), 1);
734 }
735}