Skip to main content

dayzmake_core/navmesh/
generate.rs

1//! The navmesh generator: plans the tiles of a run, fetches them (or reads them from a capture),
2//! builds them in parallel and assembles the mesh (spec 2.3, 8.4, 8.5).
3//!
4//! # Threads
5//!
6//! Three stages run inside one [`std::thread::scope`], joined by bounded channels:
7//!
8//! * **fetchers** (one per connection) claim the next plan index (a hand-back queue first, then a shared
9//!   counter), fetch the tile and send it to the builders (queue bound 64);
10//! * **builders** (`threads`, default cores - 1, at least 1) build the tiles and send the results to the
11//!   assembler (queue bound `builders * 4`);
12//! * the **assembler** is the calling thread. It keeps a reorder buffer keyed by plan index and applies
13//!   the results strictly in plan order, so the output is byte-identical for any `threads` and
14//!   `connections` (this deliberately differs from the completion order of the original, see the
15//!   spec's section 8.4).
16//!
17//! The graph is acyclic and the assembler only ever waits for the result channel, which it always
18//! drains into its reorder buffer. So every blocked `send` is eventually released: the assembler never
19//! waits for a send, the builders therefore never wait for it, and the fetchers wait only for builders.
20//! Each claimed plan index produces exactly one message (a tile, a skipped tile or an error), so the
21//! assembler's next-expected index is always eventually delivered. A fetcher whose connection died
22//! (a final network error) puts its claimed index back into the hand-back queue and stops; the other
23//! fetchers take it from there, and a fetcher with nothing left to claim waits while another one still has
24//! an index in flight. Only the last fetcher to stop reports what is left (handed-back and unclaimed
25//! indices) as fetch errors (small messages, so it ignores the window below).
26//!
27//! The reorder buffer is bounded by a claim window: a fetcher that has claimed index `i` waits (on a
28//! condition variable) while `i >= applied + window` before it fetches. The index the assembler waits
29//! for is always below that limit, so its holder never waits and the wait is released as soon as that
30//! tile is applied; a hung connection therefore stalls the run (until the receive timeout) but cannot
31//! make the buffer grow past the window. A failing checkpoint or capture write, and a panic of the
32//! assembler, set the stop flag and wake the waiting fetchers: they stop claiming, the channels close
33//! as the stages finish and the run ends with [`GenerateReport::stopped`] set. A panic while building a
34//! tile is caught and makes that tile fail; builders own the receiver of the fetch queue, so if every
35//! builder is gone the fetchers' sends fail and they return.
36
37use std::collections::{BTreeMap, VecDeque};
38use std::fs::File;
39use std::io;
40use std::panic::{AssertUnwindSafe, catch_unwind};
41use std::path::{Path, PathBuf};
42use std::sync::atomic::{AtomicBool, AtomicUsize, Ordering};
43use std::sync::mpsc::{Receiver, SyncSender, sync_channel};
44use std::sync::{Arc, Condvar, Mutex, PoisonError};
45use std::time::{Duration, Instant};
46
47use crate::error::ErrorExt;
48use crate::navmesh::build::{BuildOptions, TileOutcome, build_tile};
49use crate::navmesh::capture::{Capture, CaptureFile, CaptureWriter};
50use crate::navmesh::client::{Client, FetchError, Host, RetryPolicy};
51use crate::navmesh::detour::{NavMesh, NavMeshParams, NavMeshSet};
52use crate::navmesh::islands::{IslandReport, filter_islands};
53use crate::navmesh::wire::{TileInput, WorldBlock, WorldParams};
54use crate::warning::{Warning, WarningSink};
55
56/// Capacity of the fetch to build queue (spec 8.4).
57const FETCH_QUEUE: usize = 64;
58/// `maxPolys` of a fresh mesh (spec 8.1).
59const MAX_POLYS: i32 = 1 << 20;
60/// The largest plan: more tiles than any real map has.
61const MAX_PLAN: i64 = 1 << 22;
62/// The smallest claim window.
63const MIN_WINDOW: usize = 256;
64
65/// Where the tile geometry comes from.
66#[derive(Debug)]
67#[non_exhaustive]
68pub enum Source {
69    /// One or more data servers. Fetcher `k` uses host `k mod hosts` (spec 3.7); the world params come
70    /// from the first host.
71    Servers(Vec<Host>),
72    /// A capture (`.dzgeo`); tiles it lacks are skipped silently.
73    Capture(Capture),
74    /// A capture file that is indexed and read tile by tile (see [`CaptureFile`]); tiles it lacks, or that
75    /// the file was not asked to index (its range), are skipped silently. Memory is proportional to the
76    /// tiles of the range, not to the file. `record` must not name the file being read.
77    CaptureFile(CaptureFile),
78}
79
80/// The most builder threads or connections [`generate`] accepts; more is an error (each is an operating
81/// system thread, and the channels are sized by them).
82pub const MAX_WORKERS: usize = 256;
83
84/// Options of [`generate`].
85#[derive(Debug, Clone)]
86#[non_exhaustive]
87pub struct GenerateOptions {
88    /// The tile range `[x0, z0, x1, z1]` (inclusive, clamped, see [`plan_tiles`]); `None`: the whole
89    /// world, or for a capture the bounding box of its tiles.
90    pub range: Option<[i32; 4]>,
91    /// A mesh to continue from: its grid, tile size and origin are kept and new tiles replace the
92    /// tiles of their cell.
93    pub base: Option<NavMeshSet>,
94    /// Leave out the tiles that `base` already has (needs `base`).
95    pub skip_existing: bool,
96    /// Every `N` finished tiles (built, empty and failed) write the mesh atomically to the path. A
97    /// failing checkpoint stops fetching; the run still returns `Ok` with [`GenerateReport::stopped`]
98    /// set. `N` below 1 means 1.
99    pub checkpoint: Option<(usize, PathBuf)>,
100    /// Write a capture of the fetched tiles to this path. Tiles are recorded by the assembler in plan
101    /// order, so the capture is deterministic, and a crash loses the tiles that were fetched but not
102    /// yet applied. Queued tile inputs can be large (a frame may be up to 1 GiB) and there is no
103    /// aggregate byte budget: the memory of a run grows with the largest tiles in flight.
104    pub record: Option<PathBuf>,
105    /// The number of builder threads, at most [`MAX_WORKERS`]; `None`: the cores minus one, at least 1.
106    pub threads: Option<usize>,
107    /// The number of connections (fetcher threads), at most [`MAX_WORKERS`]; `None`: one per host (1 for a capture).
108    pub connections: Option<usize>,
109    /// The island filter seed; `None`: the world's `seedPosition`.
110    pub seed: Option<[f32; 3]>,
111    /// Run the island filter when the world asks for it (`filterIsolatedIslands`). On by default.
112    pub island_filter: bool,
113    /// Options of the tile build.
114    pub build: BuildOptions,
115    /// Connect and retry rules of the data server client.
116    pub retry: RetryPolicy,
117    /// Test hook: the size of the claim window instead of the computed one.
118    #[doc(hidden)]
119    pub window: Option<usize>,
120}
121
122impl Default for GenerateOptions {
123    fn default() -> Self {
124        Self {
125            range: None,
126            base: None,
127            skip_existing: false,
128            checkpoint: None,
129            record: None,
130            threads: None,
131            connections: None,
132            seed: None,
133            island_filter: true,
134            build: BuildOptions::default(),
135            retry: RetryPolicy::default(),
136            window: None,
137        }
138    }
139}
140
141/// How far a run has come; passed to the progress callback.
142#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
143#[non_exhaustive]
144pub struct Progress {
145    /// Tiles dealt with: built, empty, failed, skipped (not in the capture) and not fetched (fetch
146    /// errors). It reaches `total` when the run is complete.
147    pub done: usize,
148    /// Tiles planned.
149    pub total: usize,
150    /// Tiles built.
151    pub built: usize,
152    /// Tiles without walkable surface.
153    pub empty: usize,
154    /// Tiles that failed.
155    pub failed: usize,
156    /// Time since the run started.
157    pub elapsed: Duration,
158}
159
160/// The result of [`generate`].
161#[derive(Debug, Clone, Default)]
162#[non_exhaustive]
163pub struct GenerateReport {
164    /// The mesh. The caller writes it (see [`NavMeshSet::write_atomic`]).
165    pub set: NavMeshSet,
166    /// Tiles built.
167    pub built: usize,
168    /// Tiles without walkable surface (an existing tile of the cell was removed).
169    pub empty: usize,
170    /// Tiles that failed: `(x, z, message)`, in plan order.
171    pub failed: Vec<(i32, i32, String)>,
172    /// Tiles that could not be fetched (final network errors): `(x, z, message)`, in plan order. The
173    /// message does not name the tile.
174    pub fetch_errors: Vec<(i32, i32, String)>,
175    /// Tiles that had out-of-range door part ids (spec 12.3); the ids were ignored.
176    pub stray_tiles: usize,
177    /// The island filter result; `None` when it did not run or found no polygon near the seed.
178    pub islands: Option<IslandReport>,
179    /// Wall time of the run in seconds. Reported only; it is not part of the output.
180    pub seconds: f64,
181    /// Set when the run was stopped by a failing checkpoint or capture write: the message. The set
182    /// holds what was assembled until then and the island filter did not run. Callers should save
183    /// `set` and then report this as an error.
184    pub stopped: Option<String>,
185    /// The seed of the island filter: `GenerateOptions::seed`, else the world's seed position. Set also when
186    /// the filter did not run (a stopped run, or `island_filter` off).
187    pub seed: Option<[f32; 3]>,
188    /// Diagnostic: the largest number of finished tiles the reorder buffer held while waiting for an
189    /// earlier tile. It never exceeds [`GenerateReport::window`] (the final drain of unfetched tiles
190    /// after every connection failed is exempt).
191    pub peak_pending: usize,
192    /// Diagnostic: the claim window of the run, the number of plan indices a fetcher may be ahead of
193    /// the first tile not yet applied.
194    pub window: usize,
195}
196
197/// The tiles of the grid that `range` selects, as inclusive bounds `[x0, z0, x1, z1]`; `None` when
198/// nothing is left. Lower bounds below 0 become 0, an upper bound below 0 or beyond the grid becomes
199/// the last tile, and no range is the whole grid. [`plan_tiles`] and the index of a
200/// [`CaptureFile`](crate::navmesh::capture::CaptureFile) both use it, so a run and its capture cannot
201/// disagree about the range.
202pub(crate) fn clip_range(range: Option<[i32; 4]>, tiles_x: i32, tiles_z: i32) -> Option<[i32; 4]> {
203    let [rx0, rz0, rx1, rz1] = range.unwrap_or([0, 0, -1, -1]);
204    let last = |n: i32| n.saturating_sub(1);
205    let x1 = if rx1 < 0 {
206        last(tiles_x)
207    } else {
208        rx1.min(last(tiles_x))
209    };
210    let z1 = if rz1 < 0 {
211        last(tiles_z)
212    } else {
213        rz1.min(last(tiles_z))
214    };
215    let (x0, z0) = (rx0.max(0), rz0.max(0));
216    (x0 <= x1 && z0 <= z1).then_some([x0, z0, x1, z1])
217}
218
219/// The tiles of a run, in the order of spec 8.4.
220///
221/// The range is clamped to the grid: lower bounds to 0, an upper bound below 0 or beyond the grid to the
222/// last tile. The range is cut into square blocks of `blockSize` tiles starting at the range's
223/// own corner; blocks go row by row (z outer), and inside a block the tiles go row by row too.
224///
225/// # Errors
226///
227/// "empty tile range" when nothing is left of the range; "tile range too large (N tiles, limit
228/// 4194304)" above 2^22 tiles.
229pub fn plan_tiles(world: &WorldBlock, range: Option<[i32; 4]>) -> io::Result<Vec<(i32, i32)>> {
230    let Some([x0, z0, x1, z1]) = clip_range(range, world.tiles_x, world.tiles_z) else {
231        return Err(error!("empty tile range"));
232    };
233    let count = (i64::from(x1) - i64::from(x0) + 1) * (i64::from(z1) - i64::from(z0) + 1);
234    if count > MAX_PLAN {
235        return Err(error!(
236            "tile range too large ({count} tiles, limit {MAX_PLAN})"
237        ));
238    }
239    let count = usize::try_from(count).map_err(|_| error!("empty tile range"))?;
240    let block = world.block_size.max(1);
241    let step = usize::try_from(block).unwrap_or(1);
242    let mut plan = Vec::new();
243    plan.try_reserve_exact(count)
244        .map_err(|e| error!("cannot allocate the tile plan ({count} tiles): {e}"))?;
245    for bz in (z0..=z1).step_by(step) {
246        for bx in (x0..=x1).step_by(step) {
247            let ez = bz.saturating_add(block - 1).min(z1);
248            let ex = bx.saturating_add(block - 1).min(x1);
249            for z in bz..=ez {
250                for x in bx..=ex {
251                    plan.push((x, z));
252                }
253            }
254        }
255    }
256    Ok(plan)
257}
258
259/// Asks the data server at `host` for the world params (one attempt, no retry of the request).
260///
261/// # Errors
262///
263/// Fails when the server cannot be reached (the message says how to start the data server) or its
264/// answer is malformed.
265pub fn probe(host: &Host, policy: &RetryPolicy) -> io::Result<WorldParams> {
266    Client::connect(host, policy)?.world_params()
267}
268
269/// What a fetcher found for one plan index.
270enum Fetch {
271    Tile(TileInput),
272    /// The capture lacks the tile.
273    Skipped,
274    /// The payload was malformed.
275    Wire(String),
276    /// A final network error.
277    Net(String),
278}
279
280struct Fetched {
281    idx: usize,
282    what: Fetch,
283}
284
285/// What a builder made of one plan index.
286enum Outcome {
287    Tile(Box<TileOutcome>),
288    Skipped,
289    Failed(String),
290    Net(String),
291}
292
293struct Built {
294    idx: usize,
295    outcome: Outcome,
296    /// The fetched input, kept only when recording.
297    input: Option<TileInput>,
298}
299
300/// Where the fetchers get their tiles.
301enum FetchFrom<'a> {
302    Servers(&'a [Host]),
303    Capture(&'a Capture),
304    CaptureFile(&'a CaptureFile),
305}
306
307/// What the fetchers share.
308struct FetchShared<'a> {
309    plan: &'a [(i32, i32)],
310    next: &'a AtomicUsize,
311    stop: &'a AtomicBool,
312    alive: &'a AtomicUsize,
313    /// The number of fetchers.
314    connections: usize,
315    gate: &'a Gate,
316    window: usize,
317    world: &'a WorldParams,
318    from: FetchFrom<'a>,
319    policy: &'a RetryPolicy,
320}
321
322/// A tile handed back after its connection died.
323struct Handback {
324    /// The last error of the first connection that died on the tile (reported when the tile ends up failed).
325    why: String,
326    /// On how many connections that had been served before (so they were working) the tile has failed.
327    proven: u32,
328    /// On how many connections that had not been served yet (a refused or reset start looks the same as a
329    /// tile the server cannot answer) the tile has failed.
330    unproven: u32,
331}
332
333impl Handback {
334    /// The tile is reported as failed when the tile is the likely cause, not the connections: it failed
335    /// on two working connections, or on a working one and another one. Failures on connections that
336    /// were never served count only together with a working one, so a refused start loses no tile.
337    fn is_poison(&self) -> bool {
338        self.proven >= 2 || (self.proven >= 1 && self.unproven >= 1)
339    }
340}
341
342/// What the fetchers coordinate on, under one lock: how many plan indices the assembler has applied (the
343/// claim window), the hand-back queue and the number of indices in flight.
344#[derive(Default)]
345struct Work {
346    applied: usize,
347    /// Indices to fetch again on another connection.
348    retry: VecDeque<(usize, Handback)>,
349    /// Indices claimed and not yet delivered or handed back.
350    inflight: usize,
351}
352
353/// The claim window and the hand-back queue, with one condition variable for both: a waiting fetcher
354/// wakes when the assembler advances, when a tile is handed back, when an index is delivered and on stop.
355struct Gate {
356    work: Mutex<Work>,
357    changed: Condvar,
358}
359
360impl Gate {
361    fn new() -> Self {
362        Self {
363            work: Mutex::new(Work::default()),
364            changed: Condvar::new(),
365        }
366    }
367
368    fn set_applied(&self, n: usize) {
369        self.work
370            .lock()
371            .unwrap_or_else(PoisonError::into_inner)
372            .applied = n;
373        self.changed.notify_all();
374    }
375
376    /// Wakes the waiting fetchers (after `stop` was set).
377    fn wake(&self) {
378        // Taking the lock orders this after any fetcher's check of `stop`, so no wake-up is lost.
379        drop(self.work.lock().unwrap_or_else(PoisonError::into_inner));
380        self.changed.notify_all();
381    }
382
383    /// Claims the next index: a handed-back one first, then the next unclaimed one, which has to be inside
384    /// the claim window unless `windowed` is false (the last fetcher reporting what is left). Waits while
385    /// there is none: the next index is outside the window, or another fetcher still has one in flight
386    /// (its connection may die and hand it back). `None` when everything is delivered or the run was
387    /// stopped. The second value is set for a handed-back index.
388    ///
389    /// `prefer_fresh` takes a fresh index before a handed-back one when both are available: a connection
390    /// that has not delivered a tile yet should prove itself on a tile nobody failed before, or a late
391    /// starter would fail the tile of a connection that had worked.
392    ///
393    /// `before_wait` runs once, before the first wait: the caller closes its connection there, because
394    /// a server that serves one client at a time would otherwise keep serving the idle connection while
395    /// the connections that hold the tiles in flight wait for it.
396    fn claim(
397        &self,
398        shared: &FetchShared<'_>,
399        windowed: bool,
400        prefer_fresh: bool,
401        before_wait: &mut dyn FnMut(),
402    ) -> Option<(usize, Option<Handback>)> {
403        let mut work = self.work.lock().unwrap_or_else(PoisonError::into_inner);
404        let mut waited = Some(());
405        loop {
406            if shared.stop.load(Ordering::Relaxed) {
407                return None;
408            }
409            let next = shared.next.load(Ordering::Relaxed);
410            let fresh = next < shared.plan.len()
411                && (!windowed || next < work.applied.saturating_add(shared.window));
412            if !(prefer_fresh && fresh)
413                && let Some((idx, back)) = work.retry.pop_front()
414            {
415                work.inflight += 1;
416                return Some((idx, Some(back)));
417            }
418            if fresh {
419                shared.next.store(next + 1, Ordering::Relaxed);
420                work.inflight += 1;
421                return Some((next, None));
422            }
423            if next >= shared.plan.len() && work.inflight == 0 {
424                return None;
425            }
426            if waited.take().is_some() {
427                before_wait();
428            }
429            work = self
430                .changed
431                .wait(work)
432                .unwrap_or_else(PoisonError::into_inner);
433        }
434    }
435
436    /// An index was delivered (`back` is `None`) or its connection died (`Some`: it goes back to the
437    /// queue).
438    fn done(&self, idx: usize, back: Option<Handback>) {
439        let mut work = self.work.lock().unwrap_or_else(PoisonError::into_inner);
440        work.inflight = work.inflight.saturating_sub(1);
441        if let Some(back) = back {
442            work.retry.push_back((idx, back));
443        }
444        drop(work);
445        self.changed.notify_all();
446    }
447}
448
449/// Sets the stop flag and wakes the fetchers when the assembler's scope ends, also by a panic.
450struct StopOnDrop<'a> {
451    stop: &'a AtomicBool,
452    gate: &'a Gate,
453}
454
455impl Drop for StopOnDrop<'_> {
456    fn drop(&mut self) {
457        self.stop.store(true, Ordering::Relaxed);
458        self.gate.wake();
459    }
460}
461
462/// What `fetch_one` found.
463enum Got {
464    /// A result for the plan index (a tile, a skipped tile, or an error of the tile or the capture that
465    /// leaves the connection usable).
466    Done(Fetch),
467    /// The connection is dead (its retries are used up); the message is the last error.
468    Dead(String),
469}
470
471fn fetch_one(
472    shared: &FetchShared<'_>,
473    slot: usize,
474    client: &mut Option<Client>,
475    at: (i32, i32),
476) -> Got {
477    let (col, row) = at;
478    match &shared.from {
479        FetchFrom::Capture(capture) => Got::Done(
480            capture
481                .tile(col, row)
482                .map_or(Fetch::Skipped, |tile| Fetch::Tile(tile.clone())),
483        ),
484        FetchFrom::CaptureFile(file) => Got::Done(match file.tile(col, row) {
485            Ok(Some(tile)) => Fetch::Tile(tile),
486            Ok(None) => Fetch::Skipped,
487            // A malformed record fails the tile (it would fail again); anything else is a read error
488            // of the moment, so the tile is reported as not fetched and offered for a resume.
489            Err(e) if e.kind() == io::ErrorKind::InvalidData => Fetch::Wire(e.to_string()),
490            Err(e) => Fetch::Net(e.to_string()),
491        }),
492        FetchFrom::Servers(hosts) => {
493            if client.is_none() {
494                let Some(host) = hosts.get(slot % hosts.len().max(1)) else {
495                    return Got::Dead("no data server".to_owned());
496                };
497                // Not connected yet, so the retry loop of `tile` covers the first connect too.
498                *client = Some(Client::lazy(host, shared.policy));
499            }
500            let Some(conn) = client.as_mut() else {
501                return Got::Dead("not connected".to_owned());
502            };
503            match conn.tile(col, row, shared.world) {
504                Ok(tile) => Got::Done(Fetch::Tile(tile)),
505                Err(FetchError::Wire(e)) => Got::Done(Fetch::Wire(e.to_string())),
506                // A complete but wrong answer: the tile is at fault. The failed try closed the
507                // connection, the next request opens a fresh one, so nothing is out of sync.
508                Err(FetchError::Network(e)) if conn.last_failure_was_answer() => {
509                    Got::Done(Fetch::Net(e.to_string()))
510                }
511                Err(FetchError::Network(e)) => Got::Dead(e.to_string()),
512            }
513        }
514    }
515}
516
517/// Armed for the life of a fetcher. When the fetcher leaves any way but its normal end (a panic, or the
518/// assembler being gone), the run is stopped, the waiting fetchers are woken and the fetcher is no longer
519/// counted as alive, so nothing waits for a tile that will never come.
520struct FetcherExit<'a> {
521    shared: &'a FetchShared<'a>,
522    armed: bool,
523}
524
525impl Drop for FetcherExit<'_> {
526    fn drop(&mut self) {
527        if self.armed {
528            self.shared.stop.store(true, Ordering::Relaxed);
529            self.shared.gate.wake();
530            self.shared.alive.fetch_sub(1, Ordering::AcqRel);
531        }
532    }
533}
534
535/// Whether another fetcher uses the server of fetcher `slot` (fetcher `k` uses host `k mod hosts`).
536fn shares_host(shared: &FetchShared<'_>, slot: usize) -> bool {
537    match &shared.from {
538        FetchFrom::Servers(hosts) if !hosts.is_empty() => {
539            (0..shared.connections)
540                .filter(|k| k % hosts.len() == slot % hosts.len())
541                .count()
542                > 1
543        }
544        _ => false,
545    }
546}
547
548fn fetcher(shared: &FetchShared<'_>, slot: usize, tx: &SyncSender<Fetched>) {
549    let mut exit = FetcherExit {
550        shared,
551        armed: true,
552    };
553    let mut client: Option<Client> = None;
554    // This fetcher has been served by its server at least once: a failure of a connection of its then says
555    // something about the tile. It is kept when the connection is closed to wait or replaced, so a poison
556    // tile cannot take every connection down uncounted. Known limit: with three or more connections to a
557    // server that serves one client at a time, a reconnect that is reset can still count against an innocent
558    // tile; the result is a spurious fetch error for that tile (resumable), never a lost run.
559    let mut delivered = false;
560    let others_on_host = shares_host(shared, slot);
561    while let Some((idx, back)) = shared.gate.claim(shared, true, !delivered, &mut || {
562        // Only a fetcher that shares its server with others closes the connection before it waits:
563        // nobody else can be waiting for a server that only this fetcher uses.
564        if others_on_host {
565            client = None;
566        }
567    }) {
568        let Some(&at) = shared.plan.get(idx) else {
569            shared.gate.done(idx, None);
570            break;
571        };
572        let what = match fetch_one(shared, slot, &mut client, at) {
573            Got::Done(what) => what,
574            Got::Dead(message) => {
575                let (mut proven, mut unproven) =
576                    back.as_ref().map_or((0, 0), |b| (b.proven, b.unproven));
577                if delivered {
578                    proven += 1;
579                } else {
580                    unproven += 1;
581                }
582                let why = back.map_or(message, |b| b.why);
583                let hand = Handback {
584                    why,
585                    proven,
586                    unproven,
587                };
588                if !hand.is_poison() {
589                    // This connection is dead. The tile goes back for the live connections and
590                    // fails only when none is left (the last fetcher reports it below).
591                    shared.gate.done(idx, Some(hand));
592                    break;
593                }
594                let why = hand.why;
595                // The tile failed on another connection too: report it and carry on with a fresh
596                // connection of our own.
597                client = None;
598                Fetch::Net(why)
599            }
600        };
601        delivered |= matches!(what, Fetch::Tile(_) | Fetch::Skipped);
602        if tx.send(Fetched { idx, what }).is_err() {
603            return;
604        }
605        shared.gate.done(idx, None);
606    }
607    exit.armed = false;
608    // The last fetcher to stop reports every index that is left (handed back, or nobody claimed), so the
609    // run still ends. No other fetcher is alive, so nothing is in flight and `claim` does not wait.
610    if shared.alive.fetch_sub(1, Ordering::AcqRel) == 1 && !shared.stop.load(Ordering::Relaxed) {
611        while let Some((idx, back)) = shared.gate.claim(shared, false, false, &mut || {}) {
612            let message = back.map_or_else(
613                || "not fetched: every connection failed".to_owned(),
614                |b| b.why,
615            );
616            let sent = tx.send(Fetched {
617                idx,
618                what: Fetch::Net(message),
619            });
620            shared.gate.done(idx, None);
621            if sent.is_err() {
622                return;
623            }
624        }
625    }
626}
627
628/// Runs a tile build; a panic of the build (a bug on hostile geometry) fails the tile and nothing else.
629fn build_guarded(build: impl FnOnce() -> io::Result<TileOutcome>) -> Outcome {
630    match catch_unwind(AssertUnwindSafe(build)) {
631        Ok(Ok(outcome)) => Outcome::Tile(Box::new(outcome)),
632        Ok(Err(e)) => Outcome::Failed(e.to_string()),
633        Err(_) => Outcome::Failed("internal error: tile build panicked".to_owned()),
634    }
635}
636
637/// A builder. It owns a handle of the fetch queue's receiver: when the last builder is gone the
638/// receiver is dropped and the fetchers' sends fail instead of blocking.
639fn builder(
640    world: &WorldParams,
641    options: &GenerateOptions,
642    rx: &Mutex<Receiver<Fetched>>,
643    tx: &SyncSender<Built>,
644) {
645    let record = options.record.is_some();
646    loop {
647        // The lock is held only while waiting for the next tile.
648        let msg = rx.lock().unwrap_or_else(PoisonError::into_inner).recv();
649        let Ok(Fetched { idx, what }) = msg else {
650            return;
651        };
652        let (outcome, input) = match what {
653            Fetch::Tile(input) => {
654                let outcome = build_guarded(|| build_tile(world, &input, &options.build));
655                (outcome, record.then_some(input))
656            }
657            Fetch::Skipped => (Outcome::Skipped, None),
658            Fetch::Wire(m) => (Outcome::Failed(m), None),
659            Fetch::Net(m) => (Outcome::Net(m), None),
660        };
661        if tx
662            .send(Built {
663                idx,
664                outcome,
665                input,
666            })
667            .is_err()
668        {
669            return;
670        }
671    }
672}
673
674/// The assembler's state: the mesh and the report being made.
675struct Assembler<'a> {
676    mesh: NavMesh,
677    plan: &'a [(i32, i32)],
678    report: GenerateReport,
679    recorder: Option<CaptureWriter<File>>,
680    checkpoint: Option<(usize, &'a Path)>,
681    grid: (i32, i32),
682    stop: &'a AtomicBool,
683    gate: &'a Gate,
684    /// Tiles the capture lacks.
685    skipped: usize,
686    start: Instant,
687}
688
689impl Assembler<'_> {
690    fn finished(&self) -> usize {
691        self.report.built + self.report.empty + self.report.failed.len()
692    }
693
694    /// Stops the run: no further fetching, checkpoints or island filter. The first reason is kept.
695    fn halt(&mut self, reason: String) {
696        if self.report.stopped.is_none() {
697            self.report.stopped = Some(reason);
698        }
699        self.stop.store(true, Ordering::Relaxed);
700        self.gate.wake();
701    }
702
703    fn fail(&mut self, (x, z): (i32, i32), message: String, warnings: &mut dyn WarningSink) {
704        warnings.warn(Warning::new(
705            Some("navmesh-tile-failed"),
706            format!("tile ({x},{z}): {message}"),
707        ));
708        self.report.failed.push((x, z, message));
709    }
710
711    fn apply(&mut self, msg: Built, warnings: &mut dyn WarningSink) {
712        let Some(&at) = self.plan.get(msg.idx) else {
713            return;
714        };
715        let finished_before = self.finished();
716        if let (Some(w), Some(input)) = (self.recorder.as_mut(), msg.input.as_ref())
717            && let Err(e) = w.add(input)
718        {
719            self.halt(format!("cannot write the capture: {e}"));
720        }
721        match msg.outcome {
722            Outcome::Skipped => self.skipped += 1,
723            Outcome::Net(m) => self.report.fetch_errors.push((at.0, at.1, m)),
724            Outcome::Failed(m) => self.fail(at, m, warnings),
725            Outcome::Tile(outcome) => match *outcome {
726                TileOutcome::Empty => {
727                    self.mesh.remove_tile_at(at.0, at.1);
728                    self.report.empty += 1;
729                }
730                TileOutcome::Built {
731                    data,
732                    stray_part_ids,
733                    ..
734                } => match self.mesh.set_tile(data) {
735                    Ok(_) => {
736                        self.report.built += 1;
737                        if stray_part_ids > 0 {
738                            self.report.stray_tiles += 1;
739                            warnings.warn(Warning::new(
740                                Some("navmesh-stray-part"),
741                                format!(
742                                    "tile ({},{}): {stray_part_ids} polygons had out-of-range door part ids, which were ignored",
743                                    at.0, at.1
744                                ),
745                            ));
746                        }
747                    }
748                    Err(e) => self.fail(at, e.to_string(), warnings),
749                },
750            },
751        }
752        self.checkpoint_if_due(finished_before);
753    }
754
755    /// Writes the checkpoint when the tile just applied was the `N`th finished one.
756    fn checkpoint_if_due(&mut self, finished_before: usize) {
757        let Some((every, path)) = self.checkpoint else {
758            return;
759        };
760        let done = self.finished();
761        if self.report.stopped.is_some() || done == finished_before || !done.is_multiple_of(every) {
762            return;
763        }
764        let set = self.mesh.to_set(self.grid.0, self.grid.1);
765        if let Err(e) = set.write_atomic(path) {
766            self.halt(format!("checkpoint {}: {e}", path.display()));
767        }
768    }
769
770    fn progress(&self, progress: &mut dyn FnMut(&Progress)) {
771        progress(&Progress {
772            done: self.finished() + self.skipped + self.report.fetch_errors.len(),
773            total: self.plan.len(),
774            built: self.report.built,
775            empty: self.report.empty,
776            failed: self.report.failed.len(),
777            elapsed: self.start.elapsed(),
778        });
779    }
780}
781
782/// The bounding range of the tile coordinates of a capture.
783fn capture_range(capture: &Capture) -> Option<[i32; 4]> {
784    let tiles = capture.tiles();
785    let first = tiles.first()?;
786    let mut r = [first.x, first.z, first.x, first.z];
787    for t in tiles {
788        r = [r[0].min(t.x), r[1].min(t.z), r[2].max(t.x), r[3].max(t.z)];
789    }
790    Some(r)
791}
792
793/// Creates the target mesh (spec 2.3 step 3, 8.1) and its grid size.
794fn create_mesh(world: &WorldBlock, base: Option<&NavMeshSet>) -> io::Result<(NavMesh, (i32, i32))> {
795    if let Some(set) = base {
796        let p = &set.params;
797        let mismatch = p.tile_width.to_bits() != world.tile_width.to_bits()
798            || p.tile_height.to_bits() != world.tile_height.to_bits()
799            || p.orig.iter().any(|c| c.to_bits() & 0x7fff_ffff != 0)
800            || set.tiles_x != world.tiles_x
801            || set.tiles_z != world.tiles_z;
802        if mismatch {
803            return Err(error!(
804                "base navmesh does not match the world (base: {} x {} tiles of {} x {} m at {:?}; world: {} x {} tiles of {} x {} m at [0.0, 0.0, 0.0])",
805                set.tiles_x,
806                set.tiles_z,
807                p.tile_width,
808                p.tile_height,
809                p.orig,
810                world.tiles_x,
811                world.tiles_z,
812                world.tile_width,
813                world.tile_height
814            ));
815        }
816        return Ok((
817            NavMesh::from_set(set).prepend_error("cannot use the base mesh")?,
818            (set.tiles_x, set.tiles_z),
819        ));
820    }
821    let max_tiles = world
822        .tiles_x
823        .checked_mul(world.tiles_z)
824        .filter(|n| *n > 0)
825        .ok_or_else(|| error!("invalid tile grid {} x {}", world.tiles_x, world.tiles_z))?;
826    let params = NavMeshParams {
827        orig: [0.0; 3],
828        tile_width: world.tile_width,
829        tile_height: world.tile_height,
830        max_tiles,
831        max_polys: MAX_POLYS,
832    };
833    Ok((NavMesh::new(params)?, (world.tiles_x, world.tiles_z)))
834}
835
836/// Runs the fetchers and builders on scoped threads and applies their results in plan order on the
837/// calling thread (see the module docs).
838fn run_pipeline(
839    asm: &mut Assembler<'_>,
840    world: &WorldParams,
841    from: FetchFrom<'_>,
842    default_connections: usize,
843    options: &GenerateOptions,
844    progress: &mut dyn FnMut(&Progress),
845    warnings: &mut dyn WarningSink,
846) {
847    let builders = options
848        .threads
849        .unwrap_or_else(|| {
850            std::thread::available_parallelism().map_or(1, |n| n.get().saturating_sub(1))
851        })
852        .max(1);
853    let connections = options.connections.unwrap_or(default_connections).max(1);
854    let window = options
855        .window
856        .unwrap_or_else(|| {
857            MIN_WINDOW.max(
858                FETCH_QUEUE
859                    .saturating_add(builders.saturating_mul(5))
860                    .saturating_add(connections),
861            )
862        })
863        .max(1);
864    let (plan, stop, gate) = (asm.plan, asm.stop, asm.gate);
865    let next = AtomicUsize::new(0);
866    let alive = AtomicUsize::new(connections);
867    let shared = FetchShared {
868        plan,
869        next: &next,
870        stop,
871        alive: &alive,
872        connections,
873        gate,
874        window,
875        world,
876        from,
877        policy: &options.retry,
878    };
879    let (fetch_tx, fetch_rx) = sync_channel::<Fetched>(FETCH_QUEUE);
880    let (built_tx, built_rx) = sync_channel::<Built>(builders.saturating_mul(4));
881    let fetch_rx = Arc::new(Mutex::new(fetch_rx));
882    let mut peak = 0usize;
883    std::thread::scope(|scope| {
884        let _wake_on_exit = StopOnDrop { stop, gate };
885        for slot in 0..connections {
886            let tx = fetch_tx.clone();
887            let shared = &shared;
888            scope.spawn(move || fetcher(shared, slot, &tx));
889        }
890        drop(fetch_tx);
891        for _ in 0..builders {
892            let tx = built_tx.clone();
893            let rx = Arc::clone(&fetch_rx);
894            scope.spawn(move || builder(world, options, &rx, &tx));
895        }
896        drop(built_tx);
897        drop(fetch_rx);
898
899        // The assembler: results in plan order through a reorder buffer.
900        let mut pending: BTreeMap<usize, Built> = BTreeMap::new();
901        let mut expected = 0usize;
902        for msg in built_rx {
903            pending.insert(msg.idx, msg);
904            peak = peak.max(pending.len());
905            while let Some(done) = pending.remove(&expected) {
906                expected += 1;
907                asm.apply(done, warnings);
908                gate.set_applied(expected);
909                asm.progress(progress);
910            }
911        }
912    });
913    asm.report.peak_pending = peak;
914    asm.report.window = window;
915}
916
917/// Creates the capture file of `record` and writes its header.
918fn open_recorder(path: &Path, params: &WorldParams) -> io::Result<CaptureWriter<File>> {
919    let file = File::create(path).map_err(|e| error!("cannot create {}: {e}", path.display()))?;
920    CaptureWriter::new(file, params).prepend_error("cannot write the capture")
921}
922
923/// Refuses more than [`MAX_WORKERS`] builder threads or connections, before anything is allocated or spawned.
924fn check_worker_counts(options: &GenerateOptions, source: &Source) -> io::Result<()> {
925    if let Source::Servers(hosts) = source
926        && options.connections.is_none()
927        && hosts.len() > MAX_WORKERS
928    {
929        return Err(error!(
930            "hosts: at most {MAX_WORKERS} data servers (one connection each)"
931        ));
932    }
933    if options.threads.is_some_and(|n| n > MAX_WORKERS) {
934        return Err(error!("threads: at most {MAX_WORKERS} builder threads"));
935    }
936    if options.connections.is_some_and(|n| n > MAX_WORKERS) {
937        return Err(error!("connections: at most {MAX_WORKERS} connections"));
938    }
939    Ok(())
940}
941
942/// Whether two paths name the same existing file (by device and inode on Unix, by canonical path
943/// everywhere).
944fn same_file(a: &Path, b: &Path) -> bool {
945    #[cfg(unix)]
946    {
947        use std::os::unix::fs::MetadataExt;
948        if let (Ok(x), Ok(y)) = (std::fs::metadata(a), std::fs::metadata(b))
949            && x.dev() == y.dev()
950            && x.ino() == y.ino()
951        {
952            return true;
953        }
954    }
955    matches!((std::fs::canonicalize(a), std::fs::canonicalize(b)), (Ok(x), Ok(y)) if x == y)
956}
957
958/// The world params, the range, the fetch source and the default connection count of a source.
959fn open_source<'a>(
960    source: &'a Source,
961    options: &GenerateOptions,
962) -> io::Result<(WorldParams, Option<[i32; 4]>, FetchFrom<'a>, usize)> {
963    Ok(match source {
964        Source::Capture(c) => {
965            let range = options.range.or_else(|| capture_range(c));
966            (c.params().clone(), range, FetchFrom::Capture(c), 1)
967        }
968        Source::CaptureFile(c) => {
969            if let (Some(record), Some(read)) = (&options.record, c.path())
970                && same_file(record, read)
971            {
972                // Creating the recording would truncate the capture that is being read.
973                return Err(error!(
974                    "the recording {} is the capture being read; give another file",
975                    record.display()
976                ));
977            }
978            let range = options.range.or_else(|| c.bounds());
979            if !c.covers(range) {
980                // The tiles outside the indexed range would read as absent: a mesh without them and
981                // no error. The caller opened the capture for another range.
982                let fmt = |r: Option<[i32; 4]>| {
983                    r.map_or_else(
984                        || "no tiles".to_owned(),
985                        |[x0, z0, x1, z1]| format!("{x0},{z0},{x1},{z1}"),
986                    )
987                };
988                return Err(error!(
989                    "the capture was indexed for the range {} but the run asks for {}; open the capture with the range of the run",
990                    fmt(c.indexed_range()),
991                    fmt(range)
992                ));
993            }
994            (c.params().clone(), range, FetchFrom::CaptureFile(c), 1)
995        }
996        Source::Servers(hosts) => {
997            let first = hosts
998                .first()
999                .ok_or_else(|| error!("no data server given"))?;
1000            (
1001                probe(first, &options.retry)?,
1002                options.range,
1003                FetchFrom::Servers(hosts),
1004                hosts.len(),
1005            )
1006        }
1007    })
1008}
1009
1010/// Generates a navmesh from `source`.
1011///
1012/// The steps are those of the spec's section 2.3: world params, the target mesh (from `base` or a
1013/// fresh one), the tile plan, then fetchers, builders and the assembler (see the module docs), the
1014/// island filter, and the report. The mesh is in [`GenerateReport::set`]; the caller saves it. A
1015/// failing checkpoint or capture write stops the run but is not an `Err`: the report has
1016/// [`GenerateReport::stopped`], and the caller should save `set` and then fail. A failed tile does not stop the run: it is in [`GenerateReport::failed`] and raises the warning
1017/// `navmesh-tile-failed`. `progress` is called on the calling thread after each applied tile and once
1018/// at the end. The result does not depend on `threads` or `connections`. Memory: the queues between
1019/// fetchers, builders and the assembler are bounded in tiles, not in bytes; a tile input can be large (frames up
1020/// to 1 GiB) and there is no aggregate byte budget.
1021///
1022/// # Errors
1023///
1024/// "--skip-existing needs --base"; `threads` or `connections` above [`MAX_WORKERS`], or more than
1025/// [`MAX_WORKERS`] hosts without an explicit `connections` (the default is one connection per host); both
1026/// are checked before anything is allocated, spawned or connected; "empty tile range"; an unusable base or world grid; a world
1027/// params request that fails; "tile range too large"; a capture file that cannot be created.
1028#[expect(
1029    clippy::needless_pass_by_value,
1030    reason = "the API hands the source (a capture can be large) over to the run"
1031)]
1032pub fn generate(
1033    source: Source,
1034    options: &GenerateOptions,
1035    progress: &mut dyn FnMut(&Progress),
1036    warnings: &mut dyn WarningSink,
1037) -> io::Result<GenerateReport> {
1038    let start = Instant::now();
1039    check_worker_counts(options, &source)?;
1040    if options.skip_existing && options.base.is_none() {
1041        return Err(error!("--skip-existing needs --base"));
1042    }
1043    let (world_params, range, from, default_connections) = open_source(&source, options)?;
1044    let world = &world_params.world;
1045    let (mesh, grid) = create_mesh(world, options.base.as_ref())?;
1046    let mut plan = match range {
1047        Some(r) => plan_tiles(world, Some(r))?,
1048        None if matches!(source, Source::Capture(_) | Source::CaptureFile(_)) => {
1049            return Err(error!("empty tile range"));
1050        }
1051        None => plan_tiles(world, None)?,
1052    };
1053    if options.skip_existing {
1054        plan.retain(|&(x, z)| mesh.tile_at(x, z).is_none());
1055    }
1056    let recorder = match &options.record {
1057        Some(path) => Some(open_recorder(path, &world_params)?),
1058        None => None,
1059    };
1060
1061    let stop = AtomicBool::new(false);
1062    let gate = Gate::new();
1063    let mut asm = Assembler {
1064        mesh,
1065        plan: &plan,
1066        report: GenerateReport::default(),
1067        recorder,
1068        checkpoint: options
1069            .checkpoint
1070            .as_ref()
1071            .map(|(n, path)| ((*n).max(1), path.as_path())),
1072        grid,
1073        stop: &stop,
1074        gate: &gate,
1075        skipped: 0,
1076        start,
1077    };
1078    run_pipeline(
1079        &mut asm,
1080        &world_params,
1081        from,
1082        default_connections,
1083        options,
1084        progress,
1085        warnings,
1086    );
1087
1088    let skipped = asm.skipped;
1089    let mut report = std::mem::take(&mut asm.report);
1090    report.seed = Some(options.seed.unwrap_or(world.seed_position));
1091    let mut mesh = asm.mesh;
1092    if report.stopped.is_none() && options.island_filter && world.filter_isolated_islands {
1093        let seed = options.seed.unwrap_or(world.seed_position);
1094        report.islands = filter_islands(&mut mesh, seed);
1095        if report.islands.is_none() {
1096            warnings.warn(Warning::new(
1097                Some("navmesh-seed"),
1098                format!(
1099                    "island filter skipped: no polygon near the seed ({:.1} {:.1} {:.1})",
1100                    seed[0], seed[1], seed[2]
1101                ),
1102            ));
1103        }
1104    }
1105    report.set = mesh.into_set(grid.0, grid.1);
1106    report.seconds = start.elapsed().as_secs_f64();
1107    progress(&Progress {
1108        done: report.built
1109            + report.empty
1110            + report.failed.len()
1111            + skipped
1112            + report.fetch_errors.len(),
1113        total: plan.len(),
1114        built: report.built,
1115        empty: report.empty,
1116        failed: report.failed.len(),
1117        elapsed: start.elapsed(),
1118    });
1119    Ok(report)
1120}
1121
1122#[cfg(test)]
1123mod tests {
1124    use super::*;
1125
1126    /// A fetcher that panics must stop the run, wake the fetchers waiting for the window and stop
1127    /// counting as alive, or the run would hang (the assembler waits for the tile it claimed).
1128    #[test]
1129    fn a_panicking_fetcher_stops_the_run_and_wakes_the_waiters() {
1130        let world = WorldParams::default();
1131        let policy = RetryPolicy::default();
1132        let plan = [(0, 0), (1, 0)];
1133        let (next, stop, alive) = (
1134            AtomicUsize::new(0),
1135            AtomicBool::new(false),
1136            AtomicUsize::new(2),
1137        );
1138        let gate = Gate::new();
1139        let shared = FetchShared {
1140            plan: &plan,
1141            next: &next,
1142            stop: &stop,
1143            alive: &alive,
1144            connections: 1,
1145            gate: &gate,
1146            window: 1,
1147            world: &world,
1148            from: FetchFrom::Servers(&[]),
1149            policy: &policy,
1150        };
1151        let (ready_tx, ready_rx) = std::sync::mpsc::channel();
1152        std::thread::scope(|scope| {
1153            let waiter = scope.spawn(|| {
1154                // Index 0 is inside the window of 1; index 1 is outside it, so the second claim waits
1155                // until the run is stopped.
1156                assert_eq!(
1157                    gate.claim(&shared, true, false, &mut || {}).map(|c| c.0),
1158                    Some(0)
1159                );
1160                ready_tx.send(()).ok();
1161                gate.claim(&shared, true, false, &mut || {}).is_none()
1162            });
1163            ready_rx.recv().expect("waiter started");
1164            let panicked = catch_unwind(AssertUnwindSafe(|| {
1165                let _exit = FetcherExit {
1166                    shared: &shared,
1167                    armed: true,
1168                };
1169                std::panic::resume_unwind(Box::new("boom"))
1170            }));
1171            assert!(panicked.is_err());
1172            assert!(waiter.join().expect("waiter"), "the waiter was released");
1173        });
1174        assert!(stop.load(Ordering::Relaxed));
1175        assert_eq!(alive.load(Ordering::Relaxed), 1);
1176    }
1177
1178    #[test]
1179    fn a_fetcher_that_ends_normally_does_not_stop_the_run() {
1180        let world = WorldParams::default();
1181        let policy = RetryPolicy::default();
1182        let (next, stop, alive) = (
1183            AtomicUsize::new(0),
1184            AtomicBool::new(false),
1185            AtomicUsize::new(1),
1186        );
1187        let gate = Gate::new();
1188        let shared = FetchShared {
1189            plan: &[],
1190            next: &next,
1191            stop: &stop,
1192            alive: &alive,
1193            connections: 1,
1194            gate: &gate,
1195            window: 1,
1196            world: &world,
1197            from: FetchFrom::Servers(&[]),
1198            policy: &policy,
1199        };
1200        drop(FetcherExit {
1201            shared: &shared,
1202            armed: false,
1203        });
1204        assert!(!stop.load(Ordering::Relaxed));
1205        assert_eq!(alive.load(Ordering::Relaxed), 1);
1206    }
1207
1208    #[test]
1209    fn a_panicking_build_becomes_a_failed_tile() {
1210        // `resume_unwind` raises a panic without calling the panic hook: no noise, no global hook change.
1211        let outcome = build_guarded(|| std::panic::resume_unwind(Box::new("boom")));
1212        assert!(
1213            matches!(&outcome, Outcome::Failed(m) if m == "internal error: tile build panicked")
1214        );
1215        let outcome = build_guarded(|| Err(error!("bad tile")));
1216        assert!(matches!(&outcome, Outcome::Failed(m) if m == "bad tile"));
1217        let outcome = build_guarded(|| Ok(TileOutcome::Empty));
1218        assert!(matches!(&outcome, Outcome::Tile(t) if **t == TileOutcome::Empty));
1219    }
1220}