Demo-Derived Nav Mesh Generation: Automated Pipeline (navgen tool + bot_navtest)

[darkshade9]

Summary

The current nav mesh system has two options: manual editing (slow, requires expert human curation) and bot_navautogen (spawn-point flood-fill that only produces NODE_MOVE nodes — no ladders, water, jumps, drops, or crouch areas). This issue proposes a fully automated, zero-human-intervention pipeline to generate high-quality .nav files from existing MVD2 demo archives, validated by an automated in-engine bot test suite.

The key insight: demos don't just tell you where players stood — they tell you how players moved between positions. Every consecutive frame pair in a demo is a validated traversal edge. With thousands of demos available for popular maps, this is a dense, real-world-validated dataset for every node type the nav system supports.

---

Proposed Solution: Two-Component Pipeline

Component 1: Standalone Python Nav Generator (tools/navgen/navgen.py)

A standalone Python tool that:

1. Parses one or more .mvd2.gz demo files for a given map
2. Extracts per-player position traces with movement signals
3. Applies death-penalty weighting to penalize paths that led to environmental deaths
4. Clusters positions into nav nodes and infers node types from movement signals
5. Builds links directly from observed traversals (no DC_Reachability approximation needed)
6. Outputs a complete, ready-to-use .nav file with both nodes and links

Component 2: In-Engine Nav Test Mode (bot_navtest)

A new cvar bot_navtest 1 that puts q2proded into an automated navigation quality validation mode:

• Bots navigate between random goal nodes with combat/scoring disabled
• Collects per-node and per-link metrics (visits, fall deaths, stuck counts)
• Writes a <mapname>.navtest.json report with pass/fail assessment
• Flagged bad nodes/links feed back into the Python tool for iterative refinement

The Full Pipeline

demos/*.mvd2.gz  →  navgen.py  →  draft .nav
                                      ↓
                              q2proded bot_navtest
                                      ↓
                     PASS → ship .nav  |  FAIL → navgen.py prunes bad nodes → repeat

Convergence is guaranteed: each iteration only removes/penalizes failing edges. 3–5 iterations expected for a well-demo'd map.

---

MVD2 Data Available for Extraction

Reference: src/common/msg.c:1735 — MSG_WriteDeltaPlayerstate_Packet()

The MVD2 format records all player states per frame (not just the recording client). The following fields are available and sufficient for full node type classification:

Field	Encoding	Signal used for
pmove.origin[3]	int32_t 19.3 fixed-point ÷ 8 (inc/shared/shared.h:1127)	Position — foundation of everything
pmove.pm_type	byte enum (inc/shared/shared.h:1071)	PM_DEAD = death signal; PM_SPECTATOR = skip sample
viewoffset[3]	signed bytes	viewoffset[2] < 10 → crouching → NODE_CROUCH
rdflags	byte	RDF_UNDERWATER (inc/shared/shared.h:1309) → NODE_WATER
stats[STAT_HEALTH]	int16 (inc/shared/shared.h:1491)	Secondary death confirmation
Entity events	byte	EV_FALL, EV_FALLSHORT, EV_FALLFAR (inc/shared/shared.h:1706-1708) → fall death type

Velocity is not present in MVD2 (stripped by MSG_WriteDeltaPlayerstate_Packet as client-prediction-only data). It is fully recoverable via finite-differencing: derived_vz = (origin_z[t] - origin_z[t-1]) / frametime.

Coordinate decode: float world_units = int32_fixed_point / 8.0 (see inc/shared/shared.h:1613 — COORD2SHORT(x) = (int)((x)*8.0f)).

---

.nav Binary Format Reference

The Python tool must write exactly this format. Reference: src/action/botlib/botlib_nodes.c:2860 — BOTLIB_SaveNavCompressed().

File structure (after zlib compress/decompress):

[1 byte]  version = BOT_NAV_VERSION = 2  (src/action/botlib/botlib.h:6)
[4 bytes] uncompressed_buff_len (int)
[4 bytes] compressed_buff_len (int)
[N bytes] zlib-compressed payload:
  [2 bytes] numnodes (unsigned short)
  per node:
    [4 bytes]  area (int)            — always write for v2 (version > BOT_NAV_VERSION_1)
    [12 bytes] origin (3x float)     — world position
    [1 byte]   type (byte)           — nodetype_t value
    [2 bytes]  nodenum (short int)
    [1 byte]   inuse (qboolean = 1)
    [1 byte]   num_links (byte)
    per link (num_links times):
      [2 bytes] targetNode (short int)
      [1 byte]  targetNodeType (byte)
      [4 bytes] cost (float)         — Euclidean distance between node origins

Node type enum values (src/action/acesrc/acebot.h:76-105):

• NODE_MOVE = 1, NODE_JUMPPAD = 2, NODE_LADDER = 3, NODE_WATER = 4
• NODE_CROUCH = 5, NODE_BOXJUMP = 6, NODE_JUMP = 11
• NODE_STAND_DROP = 12, NODE_CROUCH_DROP = 13, NODE_UNSAFE_DROP = 14
• NODE_LADDER_UP = 15, NODE_LADDER_DOWN = 16
• NODE_SPAWNPOINT = 22 (include from map entity data)

Clustering constant: NODE_DENSITY = 96 units (src/action/acesrc/acebot.h:108). Max links per node: MAXLINKS = 32 (src/action/acesrc/acebot.h:117).

---

Implementation: Python Tool (tools/navgen/navgen.py)

Dependencies

• Python 3.10+
• numpy, scipy (spatial clustering via cKDTree)
• Standard library: struct, zlib, gzip, pathlib, json, multiprocessing

Stage 1 — MVD2 Parsing

The parser maintains a player_state[32] array and applies per-frame deltas for each player slot.

Key protocol pflags for player state delta decode (src/common/msg.c:1762-1818):

PPS_M_TYPE    = 0x0001   # pm_type changed
PPS_M_ORIGIN  = 0x0002   # origin XY changed
PPS_M_ORIGIN2 = 0x0004   # origin Z changed
PPS_VIEWOFFSET= 0x0008   # viewoffset changed
PPS_VIEWANGLES= 0x0010   # viewangles XY changed
PPS_VIEWANGLE2= 0x0020   # viewangle Z changed
PPS_RDFLAGS   = 0x0800   # rdflags changed
PPS_STATS     = 0x8000   # stats array changed
PPS_MOREBITS  = 0x4000   # extra flags byte follows
PPS_REMOVE    = 0x0200   # player slot removed

Origin decode: PPS_M_ORIGIN → read 2x int16 for XY; PPS_M_ORIGIN2 → read 1x int16 for Z. Convert: world = short_val / 8.0. Note: extended protocol (MSG_PS_EXTENSIONS_2) uses variable-length DeltaInt23 — detect from demo header protocol version.

File magic: 4 bytes b'MVD2' (little-endian 0x3256444D). Files are gzip-compressed — decompress with gzip.open() before parsing.

Stage 2 — Sample Gating: Spectator and State Filtering

This is the first and hardest gate applied to every frame of every player slot. Only samples where pm_type == PM_NORMAL are valid for nav generation. All other states must be discarded before any further processing.

# Exhaustive pm_type dispatch — no fallthrough
PM_NORMAL    → accept sample
PM_DEAD      → trigger death post-processing (see below), then discard
PM_GIB       → discard (ragdoll, no collision relevance)
PM_SPECTATOR → discard immediately — CRITICAL (see note)
PM_FREEZE    → discard (freeze-tag mode, artificial stillness)

Why PM_SPECTATOR is critical: Spectators in freeflight mode have no collision with the world. They pass through walls, floors, and ceilings, and can occupy any coordinate on the map including areas that are geometrically unreachable during normal play. Their position traces would inject invalid nodes into sealed rooms, inside brushes, and above the playable area. A single spectator flying across the map generates hundreds of poisoned samples. Hard-reject on first check, no exceptions.

Additionally: log a per-demo summary of discarded frame counts by state. If a demo is >60% PM_SPECTATOR frames it is likely a match-watching recording rather than a play recording — flag it and deprioritize or skip it entirely.

Death detection and penalty (applied when PM_DEAD is encountered):

• Check entity stream for EV_FALL/EV_FALLFAR in the same frame window → fall death
• rdflags & RDF_UNDERWATER sustained >90 frames immediately before PM_DEAD → drowning death
• Any other cause → combat death, no weight penalty applied

Environmental death penalty: walk back 90 frames in the run, multiply those samples' weight by 0.2.

Stage 3 — Strafe Jump Traversal Filtering

AQ2 expert players use circle-strafing and strafe-jump chaining to sustain speeds of 600+ units/sec — well above what a bot can produce (SPEED_RUN = 400, src/action/acesrc/acebot.h). Some routes are geometrically impossible at normal run speed and exist only because strafe momentum carries the player far enough to survive the crossing. Bots sent down these links will consistently fall short and die.

The filter is applied at link level, not node level. A node at the landing spot of a strafe-jump gap is still valid — bots may reach it via a different route. Only the specific high-speed traversal edge is excluded.

# Applied to each consecutive downsampled pair (A, B) before link vote is cast
BOT_MAX_XY_SPEED = 450  # units/sec
# Rationale: SPEED_RUN = 400; 450 allows for mild diagonal movement bonus
# without capturing the compounding velocity of strafe-jump chains.

def link_requires_advanced_movement(s_from, s_to, dt):
    dxy = sqrt((s_to.x - s_from.x)**2 + (s_to.y - s_from.y)**2)
    link_speed_xy = dxy / dt
    return link_speed_xy > BOT_MAX_XY_SPEED

if link_requires_advanced_movement(s_from, s_to, dt):
    # Node votes at both endpoints still accumulate normally
    # Link vote is NOT cast — this traversal does not count toward link threshold
    write_to_strafe_archive(s_from, s_to, map_name)  # preserve for future use
    continue

Natural consequence: If a gap is only crossable via strafe jump, every traversal of it exceeds the threshold. Zero normal-speed traversals → zero link votes → link is not emitted → bots never attempt it.

If a gap is crossable at both normal speed and strafe speed, normal-speed traversals still accumulate votes and the link is emitted. High-speed crossings of the same gap are simply not counted (they don't add or subtract).

Strafe trace archive: High-speed traversals are written to bots/nav/<mapname>.strafe_traces (binary, same compression pipeline as .nav). This file is not used by the current pipeline but is preserved for a future issue covering strafe-jump bot training, where these exact trajectories are the training dataset.

navtest as backstop: Any borderline link that passes the speed filter but bots still can't reliably traverse will accumulate link_failures above the 50% threshold in navtest and be pruned in the next iteration. The speed filter and navtest together provide two independent layers of protection against strafe-only routes ending up in production navs.

Stage 4 — Traversal Graph

Downsample each run to one sample per 96 units of path distance. Each consecutive downsampled pair (A, B) contributes (after passing Stage 3 gate):

• Votes for nodes at A.origin and B.origin
• A directed link vote A → B with weight = sample.weight

Cluster node votes using cKDTree with radius = 48 units. Emit a node only if sum(weights) >= 0.4 and at least 3 unique demo sources contributed.

Stage 5 — Node Type Classification

def classify_node(cluster_samples):
    underwater_ratio = mean(s.underwater for s in cluster_samples)
    crouch_ratio     = mean(s.viewoffset_z < 10 for s in cluster_samples)
    avg_vz           = mean(s.derived_vz for s in cluster_samples)
    dxy_avg          = mean(s.dxy for s in cluster_samples)

    if underwater_ratio > 0.6:              return NODE_WATER
    if crouch_ratio > 0.6:                  return NODE_CROUCH
    if avg_vz > 150 and dxy_avg < 40:       return NODE_LADDER_UP
    if avg_vz < -150 and dxy_avg < 40:      return NODE_LADDER_DOWN
    if avg_vz > 80:                         return NODE_JUMP
    return NODE_MOVE

Drop node types (NODE_STAND_DROP, NODE_CROUCH_DROP, NODE_UNSAFE_DROP) are assigned at link level based on dz of the traversal:

• dz < -30 and dz > -210 → NODE_STAND_DROP
• dz < -210 and dz > -224 → NODE_CROUCH_DROP
• dz < -224 and dz > -256 → NODE_UNSAFE_DROP

Reference fall thresholds from DC_Reachability() in src/action/botlib/botlib_nodes.c.

Stage 6 — Feedback Integration

When re-run with --feedback <mapname>.navtest.json:

• Load bad_nodes: remove by origin proximity match
• Load bad_links: remove those directed edges
• Re-cluster affected areas and regenerate the .nav

---

Implementation: bot_navtest In-Engine System

New files to create

• src/action/botlib/botlib_navtest.c — full navtest implementation

Files to modify

src/action/g_main.c ~line 521 — add alongside bot_navautogen:

cvar_t* bot_navtest;           // 0=off, 1=run nav quality test and write report
cvar_t* bot_navtest_duration;  // Test duration in seconds (default 300)
cvar_t* bot_navtest_bots;      // Number of bots to spawn for testing (default 8)

src/action/g_save.c ~line 743 — add cvar registrations alongside bot_navautogen:

bot_navtest          = gi.cvar("bot_navtest", "0", 0);
bot_navtest_duration = gi.cvar("bot_navtest_duration", "300", 0);
bot_navtest_bots     = gi.cvar("bot_navtest_bots", "8", 0);

src/action/g_local_q2pro.h ~line 1068 — add externs alongside use_mvd2:

extern cvar_t *bot_navtest;
extern cvar_t *bot_navtest_duration;
extern cvar_t *bot_navtest_bots;

src/action/botlib/botlib_ai.c ~line 897 — add navtest think branch alongside training branch:

if (bot_navtest->value) {
    BOTLIB_NavTest_Think(self);
}

src/action/botlib/botlib.h — add metrics struct and declarations:

typedef struct {
    int   node_visits[MAX_PNODES];
    int   node_deaths_fall[MAX_PNODES];
    int   node_deaths_drown[MAX_PNODES];
    int   node_stuck_count[MAX_PNODES];
    int   link_traversals[MAX_PNODES];
    int   link_failures[MAX_PNODES];
    int   total_bots_run;
    float test_start_time;
} navtest_metrics_t;
extern navtest_metrics_t navtest_metrics;

void BOTLIB_NavTest_Init(void);
void BOTLIB_NavTest_Think(edict_t *self);
void BOTLIB_NavTest_RecordDeath(edict_t *self, int mod);
void BOTLIB_NavTest_Finish(void);

src/action/g_combat.c ~line 743 — hook death recording where MOD_FALLING is already checked:

if (bot_navtest->value)
    BOTLIB_NavTest_RecordDeath(targ, mod);

botlib_navtest.c Behavior

BOTLIB_NavTest_Init() — On map load when bot_navtest->value:

• Zero all metrics, record test_start_time
• Spawn bot_navtest_bots->value bots
• Disable scoring and intermission; keep fall/drown/lava damage active (these are the signal)

BOTLIB_NavTest_Think(edict_t *self) — Modeled after BOTLIB_Think_Training() at src/action/botlib/botlib_ai.c:638:

• Zero self->enemy — no combat
• Pick a new random goal node when current goal is reached or stuck for >15s
• Record node_visits[goal_node]++ on arrival
• Record node_stuck_count[goal_node]++ and link_failures[current_node]++ on timeout
• Record link_traversals[current_node]++ on each successful node transition

BOTLIB_NavTest_Finish() — When level.time - test_start_time >= bot_navtest_duration->value:

• Evaluate pass/fail thresholds
• Write JSON to <gamedir>/bots/nav/<mapname>.navtest.json
• Print summary to server console

Pass/Fail Thresholds

#define NAVTEST_MIN_COVERAGE       0.85f  // 85%+ of nodes must be visited
#define NAVTEST_MAX_DEATH_RATE     0.5f   // Environmental deaths per bot per minute
#define NAVTEST_MAX_STUCK_RATE     1.0f   // Stuck events per bot per minute
#define NAVTEST_MAX_NODE_DEATH_PCT 0.30f  // Max 30% death rate at any single node
#define NAVTEST_MAX_LINK_FAIL_PCT  0.50f  // Max 50% failure rate on any single link
#define NAVTEST_MAX_UNREACHABLE    0.05f  // At most 5% of nodes never visited

JSON Output Format

{
  "map": "teamjungle",
  "passed": false,
  "coverage_ratio": 0.91,
  "death_rate_per_bot_min": 0.83,
  "stuck_rate_per_bot_min": 1.2,
  "bad_nodes": [142, 387, 501],
  "bad_links": [[142, 143], [501, 502]],
  "unreachable_nodes": [891, 1024],
  "test_duration_s": 300,
  "bot_count": 8,
  "total_node_visits": 14820,
  "total_environmental_deaths": 47
}

---

Automated Batch Runner

A shell or Python driver script tools/navgen/navgen_pipeline.sh <mapname> <demo_dir> orchestrates:

1. Run navgen.py on all demos for <mapname> → writes <mapname>.nav
2. Copy to baseaq/bots/nav/
3. Start q2proded with +map <mapname> +bot_navtest 1 +bot_navtest_duration 300
4. Wait for server exit, read <mapname>.navtest.json
5. If passed == true: done — nav is production-ready
6. If passed == false and iteration < 10: run navgen.py --feedback <mapname>.navtest.json → go to step 2
7. If not converged after 10 iterations: ship best result with logged warnings

---

What This Does Not Require

• No human node placement sessions
• No nav_edit usage
• No nav_autogen post-processing
• No BOTLIB_LinkAllNodesTogether() or DC_Reachability() — links come from observed traversals in demos
• No POI nodes (bots navigate all areas through random goal selection)

---

File Summary

Action	File	Relevant Lines
Create	tools/navgen/navgen.py	new
Create	tools/navgen/navgen_pipeline.sh	new
Create	src/action/botlib/botlib_navtest.c	new
Modify	src/action/g_main.c	~521 — cvar declarations
Modify	src/action/g_save.c	~743 — cvar registrations
Modify	src/action/g_local_q2pro.h	~1068 — extern declarations
Modify	src/action/botlib/botlib_ai.c	~897 — navtest think branch
Modify	src/action/botlib/botlib.h	add metrics struct + function decls
Modify	src/action/g_combat.c	~743 — hook BOTLIB_NavTest_RecordDeath()

Output files written by the tool (not committed to repo, generated per-run):

• bots/nav/<mapname>.nav — the generated nav mesh
• bots/nav/<mapname>.navtest.json — bot validation report
• bots/nav/<mapname>.strafe_traces — archived high-speed traversals for future strafe-jump training

Key Reference Files for Implementor

Purpose	File	Lines
MVD2 player state writer — parser blueprint	src/common/msg.c	1735–1860
.nav compressed save — Python must replicate	src/action/botlib/botlib_nodes.c	2860–2948
.nav load + version check logic	src/action/botlib/botlib_nodes.c	3009–3038
Node type enum + NODE_DENSITY + MAXLINKS	src/action/acesrc/acebot.h	73–117
Nav version constants	src/action/botlib/botlib.h	6–9
Coordinate encoding macros	inc/shared/shared.h	1610–1613
pmtype_t enum (PM_NORMAL, PM_DEAD, etc.)	inc/shared/shared.h	1071–1075
PMF_DUCKED, PMF_ON_GROUND flags	inc/shared/shared.h	1081–1083
RDF_UNDERWATER flag	inc/shared/shared.h	1309
STAT_HEALTH array index	inc/shared/shared.h	1491
EV_FALL, EV_FALLSHORT, EV_FALLFAR	inc/shared/shared.h	1706–1708
MOD_FALLING, MOD_LAVA, MOD_SLIME, MOD_WATER	src/action/g_local.h	1099–1104
Training mode think (model navtest after this)	src/action/botlib/botlib_ai.c	638–661
bot_navautogen cvar registration pattern	src/action/g_save.c	743
SPEED_RUN constant (bot max speed reference)	src/action/acesrc/acebot.h	200

[darkshade9]

Addendum: Two critical parsing constraints added to the spec above.

1. Spectator Hard-Rejection (Stage 2)

PM_SPECTATOR samples must be the first gate in the parser — before any other logic. Spectators in AQ2 freeflight mode have no world collision and can occupy coordinates inside brushes, above the playable area, or in sealed rooms. Their position traces would inject invalid nodes into geometrically unreachable areas.

The only valid state for nav sample collection is PM_NORMAL. All other states (PM_SPECTATOR, PM_GIB, PM_FREEZE) are hard-discarded. Additionally: demos where >60% of frames are PM_SPECTATOR are likely watch recordings rather than play recordings and should be flagged/skipped by the batch runner.

2. Strafe-Jump Link Filtering (Stage 3, new)

AQ2 expert players sustain 600+ units/sec through strafe-jump chaining. Some routes are impossible at normal bot run speed (400 units/sec). Including links that require advanced movement would result in bots falling to their deaths on those links, which would then pollute navtest metrics.

Filter: if a traversal's derived XY speed exceeds BOT_MAX_XY_SPEED = 450 units/sec, the link vote is not cast (though the node votes at both endpoints still accumulate — the positions are real, just reachable by other routes). High-speed traversals are archived to <mapname>.strafe_traces for a future strafe-jump bot training issue.

The navtest feedback loop serves as a backstop for any borderline links that pass the speed filter but bots still can't traverse reliably.