Skip to main content

dayzmake_core/navmesh/
build.rs

1//! Building one navmesh tile end to end (spec 4, 5, 7).
2//!
3//! [`tile_config`] derives the Recast configuration of a cell class, and [`build_tile`] runs every
4//! step of spec 5.4 on one tile input: terrain, objects, span filters, compact heightfield, area
5//! passes, regions, contours, polygon mesh, flags, the extra section and the Detour tile blob.
6//!
7//! The build raises no warnings: the counts it returns (stray part ids, obstacles) are for the
8//! caller to report.
9
10use 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/// What the door states of the tiles are (spec 5.1): which door parts start disabled.
35#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
36#[non_exhaustive]
37pub enum DoorPolicy {
38    /// Open doors (area 12) are disabled, closed doors (area 13) are not.
39    #[default]
40    Closed,
41    /// Closed doors (area 13) are disabled, open doors are not.
42    Open,
43    /// No door is disabled.
44    Enabled,
45}
46
47/// Options of a tile build.
48#[derive(Debug, Clone, PartialEq)]
49#[non_exhaustive]
50pub struct BuildOptions {
51    /// Build jump, climb and ladder links (spec 6).
52    pub links: bool,
53    /// The initial state of door parts.
54    pub doors: DoorPolicy,
55    /// Sea level in metres; `None` uses the world's `deepSeaHeight`.
56    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/// The Recast configuration derived from the world and a cell class (spec 4). Sizes in voxels
70/// unless noted.
71#[derive(Debug, Clone, Default, PartialEq)]
72#[non_exhaustive]
73pub struct TileConfig {
74    /// Cells across the tile (`tileSize`).
75    pub cells: i32,
76    /// Cell size in metres.
77    pub cs: f32,
78    /// Cell height in metres (0.1).
79    pub ch: f32,
80    /// `walkableHeight`.
81    pub walkable_height: i32,
82    /// Crouch height.
83    pub crouch_height: i32,
84    /// Prone height.
85    pub prone_height: i32,
86    /// `walkableClimb`.
87    pub walkable_climb: i32,
88    /// `walkableRadius`.
89    pub walkable_radius: i32,
90    /// Deep water depth.
91    pub deep_water: i32,
92    /// Sea level.
93    pub sea_level: i32,
94    /// Border size in cells.
95    pub border_size: i32,
96    /// Heightfield width and height: `cells + 2 * border_size`.
97    pub width: i32,
98    /// Padding in metres: `float(border_size) * cs`.
99    pub pad: f32,
100    /// Contour simplification error in cells.
101    pub max_simplification_error: f32,
102    /// Longest contour edge in cells (120).
103    pub max_edge_len: i32,
104    /// Vertical simplification error in voxels (8).
105    pub max_vertical_error: f32,
106    /// Default minimum region area.
107    pub min_region_area: i32,
108    /// Region merge area (400).
109    pub merge_region_area: i32,
110    /// Vertices per polygon (6).
111    pub nvp: usize,
112    /// Door dilation radius.
113    pub door_radius: i32,
114    /// Slope threshold: `cos(maxSlope)`.
115    pub slope_threshold: f32,
116}
117
118/// The configuration of tiles of `cell_class` (spec 4). All arithmetic is in `f32` as the spec
119/// writes it. A degenerate cell class (no cells) gives non-finite sizes, which [`build_tile`]
120/// rejects.
121#[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/// The result of building one tile.
161#[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    /// A tile blob.
169    #[non_exhaustive]
170    Built {
171        /// The Detour tile.
172        data: TileData,
173        /// Polygons whose part id was beyond the extras list (spec 12.3); they were ignored.
174        stray_part_ids: usize,
175        /// Tree obstacles stored in the tile.
176        obstacles: usize,
177    },
178    /// No walkable surface: no contours or no polygons.
179    Empty,
180}
181
182/// One entry of the tile extras list (spec 5.1).
183struct ExtraPart {
184    object_id: u64,
185    part_index: u32,
186    area: u8,
187    /// 0: the polygons of the part get the disabled flag.
188    state: u8,
189    polys: Vec<u32>,
190}
191
192/// The most spans one tile heightfield may hold (hostile input: stacked surfaces could otherwise
193/// need gigabytes). Past it the tile fails. A `Span` is 10 bytes, so this bounds the span data of a
194/// tile at 2^26 * 10 B = 640 MiB (before the slack of the column vectors); a field added to `Span`
195/// raises it.
196pub const MAX_SPANS: usize = 1 << 26;
197
198const SEA_FLOOR: f32 = -500.0;
199const NULL_AREA: u8 = 0;
200/// The terrain area: groups with it are skipped in step 3 (group 0 was rasterised in step 1).
201const TERRAIN_AREA: u32 = 1;
202const LADDER_AREA: u32 = 15;
203/// The hide part group (spec 5.4).
204const HIDE_AREA: u32 = 14;
205
206/// The low byte of an area id (the extras list stores the area "as a byte").
207fn low_byte(area: u32) -> u8 {
208    u8::try_from(area & 0xff).unwrap_or_default()
209}
210
211/// A part id as the 16-bit span field holds it: wrapping like C's `(unsigned short)counter++`
212/// (spec 5.4, part ids), so 65536 parts wrap to 0 instead of saturating.
213fn 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
221/// The extras list: all parts of all non-tree groups, and the part count of the last tree group.
222fn 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
248/// Rasterises the triangles of `verts` one by one in rasteriser order `(v0, v2, v1)`. With
249/// `slope` set, triangles that fail the slope test get area 0.
250fn 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
267/// The vertices of a part (server order); empty when the range is invalid.
268fn 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
275/// The triangles of a part in rasteriser order, as one flat vertex list.
276fn 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
285/// Spec 5.4 step 3: the objects of every group but the terrain. Returns the ladder groups, which
286/// the link stage uses.
287fn 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, &params, slope),
315            2 => {
316                params.mode = RasterMode::Water;
317                // Ruling R14: shallow water starts a step (walkableClimb) under the surface.
318                params.water_depth = cfg.walkable_climb;
319                raster_triangles(hf, &g.verts, &params, None);
320                params.area = 3;
321                params.water_depth = cfg.deep_water;
322                raster_triangles(hf, &g.verts, &params, None);
323            }
324            10 => {
325                if g.parts.is_empty() {
326                    params.mode = RasterMode::Tree;
327                    raster_triangles(hf, &g.verts, &params, 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), &params, 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, &params, 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), &params);
361                }
362            }
363            18 => raster_triangles(hf, &g.verts, &params, None),
364            _ => {}
365        }
366    }
367    ladders
368}
369
370/// The area table of spec 4: the default minimum region area, except for areas 10 and 12 to 14.
371pub(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
389/// Spec 5.4 step 6 (`postCompact`): sea box, dilations, tree obstacles, erosion, remap and roof.
390fn 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    // 6.1 The sea box.
399    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    // 6.2 Dilations: every area but the door and hide areas takes part.
406    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    // 6.3 Tree obstacles.
413    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    // 6.4 to 6.6.
420    erode(chf, cfg.walkable_radius).map_err(|e| error!("could not erode: {e}"))?;
421    remap_and_roof(chf);
422    Ok(found)
423}
424
425/// The poly flags of an area (spec 7.1).
426fn 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
440/// Spec 7.2: attaches polygons to parts, sets or clears the disabled flag and counts the stray part
441/// ids. Returns the stray count.
442fn 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
472/// Spec 7.2, ruling R17: the off-mesh polygons of the connections that belong to a hide part join the
473/// part's polygon list. `stored[i]` tells whether connection `i` is in the tile (Detour keeps those
474/// that start inside it, in order), and `ground` is the number of ground polygons that the off-mesh
475/// polygons follow. The lists stay ascending: the ground polygons come first.
476fn 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
489/// The extra section from the extras list (spec 7.2).
490fn 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
517/// Builds the Detour tile of one tile input (spec 5).
518///
519/// # Errors
520///
521/// Returns an error for an unknown cell class ("unknown cell class N"; the caller names the tile), an invalid
522/// grid, or a failure of one of the pipeline stages.
523pub 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/// [`build_tile`] with an explicit span budget (tests use a small one to prove the refusal without
532/// allocating the real limit).
533///
534/// # Errors
535///
536/// As [`build_tile`], plus "too many spans (N, limit L)" when the rasterised heightfield needs
537/// more than `span_limit` spans.
538#[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    // 5.1 setup.
556    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    // 5.4 step 1: terrain.
565    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    // Step 2: mode filter (it only runs for a border above 10).
576    mode_filter(&mut hf, cfg.border_size);
577    // Step 3: objects.
578    let ladders = rasterize_objects(&mut hf, input, &cfg, obstacles_on);
579    hf.check_span_budget()?;
580    // Step 4: span filters.
581    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    // Step 5: compact heightfield.
592    let mut chf = build_compact(cfg.prone_height, cfg.walkable_climb, &hf)
593        .map_err(|e| error!("could not build compact data: {e}"))?;
594    // Step 6: area passes.
595    let obstacles = post_compact(&mut chf, &cfg, pbmin, pbmax, tree_items, obstacles_on)?;
596    // Step 7: links.
597    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    // Step 8: distance field and regions.
608    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    // Step 9: contours.
617    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    // Step 10: polygon mesh.
629    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
638/// Spec 5.4 step 11 and 7: flags, extras and the Detour tile.
639fn 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    // The extra section comes after the scalars: which connections Detour keeps depends on them.
653    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(&params), pm.areas.len());
681    let extra = extra_section(extras, obstacles)?;
682    params.extra = &extra;
683    let data =
684        create_tile_data(&params).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    /// Ruling R17: the off-mesh polygon numbers follow the ground polygons in the order of the stored
708    /// connections; connections that Detour drops take no number and no part.
709    #[test]
710    fn off_mesh_polygons_join_their_hide_part() {
711        let mut extras = vec![extra(12), extra(14), extra(14)];
712        // The ground polygons 5 and 6 are already in part 1.
713        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        // Connection 1 is not stored, so the polygons are 10, (none), 11, 12, 13, 14.
719        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        // Part 9 does not exist: ignored, and its polygon (13) is still counted.
723        assert_eq!(extras[2].polys, [14]);
724        assert_eq!(extras[0].polys, Vec::<u32>::new());
725    }
726
727    /// Spec 5.4: part ids wrap like C's `(unsigned short)counter++`.
728    #[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}