0257d6c6dc
Squashed from work: - docs: button shader annotations — widgets/button.rs complete + splash demo buttons - tweaker: the Shader tab shows the pinned widget's ANIMATOR STATES as little posed swatches under the well — one per tr - widgets: the glass stops reading draw_pass.time, so glass apps idle again - render, sim, platform: what a strategy round needs underneath - draw, platform: overlays now composite above content that uses draw_depth - asset: mp4 sample index for range-streaming, chat tools, import profiles - platform: native file and save dialogs, in-house on all three desktops - sim: a per-unit decision hook — one commandable unit can think for itself, before the kit steers - makepad_ai is deleted — every backend is a hub pipe, the agent seam lives with its consumers (aicore §14, decided 2026 - libs: the zero-warning sweep — stitch casts say what they mean, xatlas keeps upstream's surface quietly - zero-warning sweep, round two — the first full-workspace pass - zero-warning sweep, round three — the model lanes and the deep examples - zero-warning sweep, round four — the last stragglers
4987 lines
210 KiB
Rust
4987 lines
210 KiB
Rust
//! Walking an imported level: real-triangle collision plus an autonomous
|
||
//! first-person walker.
|
||
//!
|
||
//! Imported Doom/Quake/Duke maps are one big static mesh. The renderer's
|
||
//! prop collider (`voxel_collider_boxes`) is a low-res box decomposition
|
||
//! built for props — for a 20 000-triangle level it collapses to a few
|
||
//! dozen boxes, and a walker standing on a box top stands in mid-air. So
|
||
//! this module probes the LEVEL'S OWN TRIANGLES through [`MeshRaycaster`]:
|
||
//! the floor under your feet is the triangle you are actually standing on.
|
||
//!
|
||
//! Nothing here touches `Cx`, the renderer or the asset crates: a level is
|
||
//! positions + indices, and a walk step is geometry. That keeps it usable
|
||
//! by the VJ's map slot AND by the game sandbox's NPCs, and unit-testable
|
||
//! against synthetic triangle soups.
|
||
|
||
use crate::ao::MeshRaycaster;
|
||
use makepad_draw::*;
|
||
|
||
/// Which axis the source considers "up". Imported packs are Y-up (the
|
||
/// importer converts), but a raw Quake/Build mesh is Z-up and would walk on
|
||
/// the walls if taken at face value.
|
||
#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
|
||
pub enum UpAxis {
|
||
#[default]
|
||
Y,
|
||
Z,
|
||
}
|
||
|
||
/// What a floor triangle IS, for walkers that care. Doom's damaging
|
||
/// sectors and Quake's lava/slime brushes are floors you can stand on and
|
||
/// should not: the tour keeps to clean ground while it has the choice.
|
||
#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
|
||
pub enum SurfaceKind {
|
||
#[default]
|
||
Floor,
|
||
/// Damaging ground (nukage, lava, slime): walkable, avoided.
|
||
Hazard,
|
||
/// Water and other non-damaging liquid: crossed without complaint.
|
||
Liquid,
|
||
}
|
||
|
||
/// A level's collision geometry: its triangles, indexed for fast probes.
|
||
pub struct LevelCollision {
|
||
caster: MeshRaycaster,
|
||
min: Vec3f,
|
||
max: Vec3f,
|
||
/// Per-triangle surface kind, when the source could classify them
|
||
/// (importer `hazard_N` nodes, or a material-name heuristic). Empty
|
||
/// means "everything is plain floor".
|
||
kinds: Vec<SurfaceKind>,
|
||
}
|
||
|
||
/// A downward probe result.
|
||
#[derive(Clone, Copy, Debug, PartialEq)]
|
||
pub struct FloorHit {
|
||
/// Height of the surface (world Y).
|
||
pub y: f32,
|
||
/// How steep it is: 1 = flat floor, 0 = vertical wall.
|
||
pub flatness: f32,
|
||
/// What the surface is — the walker avoids standing on hazards.
|
||
pub kind: SurfaceKind,
|
||
}
|
||
|
||
impl LevelCollision {
|
||
/// From a packed vertex stream (`stride` floats per vertex, position
|
||
/// first — the engine's `MODEL_VERTEX_FLOATS` layout) plus indices.
|
||
pub fn from_packed(
|
||
vertices: &[f32],
|
||
stride: usize,
|
||
indices: &[u32],
|
||
up: UpAxis,
|
||
) -> Option<LevelCollision> {
|
||
if stride < 3 || vertices.len() < stride || indices.len() < 3 {
|
||
return None;
|
||
}
|
||
let positions: Vec<Vec3f> = vertices
|
||
.chunks_exact(stride)
|
||
.map(|v| match up {
|
||
UpAxis::Y => vec3f(v[0], v[1], v[2]),
|
||
// Z-up → Y-up, keeping the handedness the renderer expects.
|
||
UpAxis::Z => vec3f(v[0], v[2], -v[1]),
|
||
})
|
||
.collect();
|
||
Some(Self::from_positions(positions, indices.to_vec()))
|
||
}
|
||
|
||
pub fn from_positions(positions: Vec<Vec3f>, indices: Vec<u32>) -> LevelCollision {
|
||
let mut min = vec3f(f32::MAX, f32::MAX, f32::MAX);
|
||
let mut max = vec3f(f32::MIN, f32::MIN, f32::MIN);
|
||
for p in &positions {
|
||
min.x = min.x.min(p.x);
|
||
min.y = min.y.min(p.y);
|
||
min.z = min.z.min(p.z);
|
||
max.x = max.x.max(p.x);
|
||
max.y = max.y.max(p.y);
|
||
max.z = max.z.max(p.z);
|
||
}
|
||
// A hair of padding so probes starting exactly on the boundary
|
||
// (the scan starts at the ceiling) are not clipped away.
|
||
let pad = vec3f(0.01, 0.01, 0.01);
|
||
LevelCollision {
|
||
caster: MeshRaycaster::new(positions, indices, min - pad, max + pad),
|
||
min,
|
||
max,
|
||
kinds: Vec::new(),
|
||
}
|
||
}
|
||
|
||
/// Attach per-triangle surface kinds (one entry per triangle, in index
|
||
/// order). Sources: the importer's `hazard_N` nodes, or a flat/material
|
||
/// name heuristic. Without them every floor is plain [`SurfaceKind::Floor`].
|
||
pub fn with_kinds(mut self, kinds: Vec<SurfaceKind>) -> LevelCollision {
|
||
if kinds.len() == self.caster.tri_count() {
|
||
self.kinds = kinds;
|
||
}
|
||
self
|
||
}
|
||
|
||
pub fn kind_of(&self, tri: u32) -> SurfaceKind {
|
||
self.kinds.get(tri as usize).copied().unwrap_or_default()
|
||
}
|
||
|
||
/// True when any surface kinds are known (the tour can then avoid
|
||
/// hazards; otherwise it treats every floor alike).
|
||
pub fn has_kinds(&self) -> bool {
|
||
!self.kinds.is_empty()
|
||
}
|
||
|
||
pub fn bounds(&self) -> (Vec3f, Vec3f) {
|
||
(self.min, self.max)
|
||
}
|
||
|
||
pub fn triangles(&self) -> usize {
|
||
self.caster.tri_count()
|
||
}
|
||
|
||
/// Nearest surface below `from`, within `max_drop`. `from` should be
|
||
/// the probe START (feet plus the step-up allowance), so a walker can
|
||
/// find ledges above its feet as well as the ground below them.
|
||
pub fn floor_below(&self, from: Vec3f, max_drop: f32) -> Option<FloorHit> {
|
||
let (t, tri) = self.caster.nearest_hit(from, vec3f(0.0, -1.0, 0.0), max_drop)?;
|
||
let (a, b, c) = self.caster.triangle(tri);
|
||
// Winding is not trustworthy in imported maps; flatness is the
|
||
// magnitude of the normal's up component.
|
||
let (e1, e2) = (b - a, c - a);
|
||
let n = vec3f(
|
||
e1.y * e2.z - e1.z * e2.y,
|
||
e1.z * e2.x - e1.x * e2.z,
|
||
e1.x * e2.y - e1.y * e2.x,
|
||
);
|
||
let len = (n.x * n.x + n.y * n.y + n.z * n.z).sqrt().max(1e-9);
|
||
Some(FloorHit {
|
||
y: from.y - t,
|
||
flatness: (n.y / len).abs(),
|
||
kind: self.kind_of(tri),
|
||
})
|
||
}
|
||
|
||
/// Nearest surface above `from`, within `max_rise` (a ceiling proves an
|
||
/// interior; the outside of a map has open sky above it).
|
||
pub fn ceiling_above(&self, from: Vec3f, max_rise: f32) -> Option<f32> {
|
||
let (t, _) = self.caster.nearest_hit(from, vec3f(0.0, 1.0, 0.0), max_rise)?;
|
||
Some(from.y + t)
|
||
}
|
||
|
||
/// Does the level's own geometry cut the straight line from `from` to
|
||
/// `to`? A line of sight, a shot, a thrown thing: anything that travels
|
||
/// point to point through a streamed map has to ask THIS, because the
|
||
/// map's triangles are not bodies in the sim — a body-only ray cast
|
||
/// passes clean through every wall of the level.
|
||
pub fn segment_blocked(&self, from: Vec3f, to: Vec3f) -> bool {
|
||
let delta = to - from;
|
||
let dist = (delta.x * delta.x + delta.y * delta.y + delta.z * delta.z).sqrt();
|
||
if dist < 1e-6 {
|
||
return false;
|
||
}
|
||
self.caster.any_hit(from, delta * (1.0 / dist), dist)
|
||
}
|
||
|
||
/// Nearest surface along `dir` (unit length) from `from`, within
|
||
/// `max`: `(distance, unit normal)`, the normal flipped to face back
|
||
/// along the ray — winding is not trustworthy in imported maps, and a
|
||
/// suspension spring wants the push-back direction, not the authored
|
||
/// one.
|
||
pub fn ray_hit(&self, from: Vec3f, dir: Vec3f, max: f32) -> Option<(f32, Vec3f)> {
|
||
let (t, tri) = self.caster.nearest_hit(from, dir, max)?;
|
||
let (a, b, c) = self.caster.triangle(tri);
|
||
let (e1, e2) = (b - a, c - a);
|
||
let mut n = vec3f(
|
||
e1.y * e2.z - e1.z * e2.y,
|
||
e1.z * e2.x - e1.x * e2.z,
|
||
e1.x * e2.y - e1.y * e2.x,
|
||
);
|
||
let len = (n.x * n.x + n.y * n.y + n.z * n.z).sqrt();
|
||
n = if len > 1.0e-9 { n * (1.0 / len) } else { dir * -1.0 };
|
||
if n.x * dir.x + n.y * dir.y + n.z * dir.z > 0.0 {
|
||
n = n * -1.0;
|
||
}
|
||
Some((t, n))
|
||
}
|
||
|
||
/// The floor a body near `(x, near_y, z)` belongs on.
|
||
///
|
||
/// Indoors a single probe from far above lands on the CEILING (the
|
||
/// map_actors lesson), so this walks every surface in the column from
|
||
/// the sky down, keeps the ones with at least `head_room` of space
|
||
/// above them (a floor you could stand on), and returns the standable
|
||
/// floor of the room containing `near_y` — else the nearest one. A body
|
||
/// spawned inside a raised slab is lifted onto it; one spawned in the
|
||
/// air belongs to the floor below it. `None` = no floor in this column
|
||
/// (outside the map).
|
||
pub fn ground_under(&self, x: f32, z: f32, near_y: f32, head_room: f32) -> Option<f32> {
|
||
let mut surfaces: Vec<f32> = Vec::new();
|
||
let mut probe = near_y + 200.0;
|
||
for _ in 0..24 {
|
||
let Some(hit) = self.floor_below(vec3f(x, probe, z), 500.0) else { break };
|
||
surfaces.push(hit.y);
|
||
probe = hit.y - 0.02;
|
||
}
|
||
// Standable floors: enough room between this surface and the one
|
||
// above it (the topmost surface has the sky).
|
||
let mut floors: Vec<(f32, f32)> = Vec::new(); // (floor, space above)
|
||
for (i, &y) in surfaces.iter().enumerate() {
|
||
let space = if i == 0 { f32::INFINITY } else { surfaces[i - 1] - y };
|
||
if space >= head_room {
|
||
floors.push((y, space));
|
||
}
|
||
}
|
||
// The room containing near_y wins outright; else nearest floor.
|
||
floors
|
||
.iter()
|
||
.find(|(y, space)| near_y >= *y && near_y < *y + *space)
|
||
.or_else(|| {
|
||
floors.iter().min_by(|a, b| {
|
||
(a.0 - near_y)
|
||
.abs()
|
||
.partial_cmp(&(b.0 - near_y).abs())
|
||
.unwrap_or(std::cmp::Ordering::Equal)
|
||
})
|
||
})
|
||
.map(|(y, _)| *y)
|
||
}
|
||
|
||
/// The room around `at`: `(headroom, span)` — floor-to-ceiling height
|
||
/// over the floor `at` belongs to, and the narrowest straight
|
||
/// horizontal line through the spot at door height (eight directions,
|
||
/// opposite pairs summed). `None` when there is no ceiling: open
|
||
/// ground, where anything fits.
|
||
pub fn room_at(&self, at: Vec3f) -> Option<(f32, f32)> {
|
||
let floor = self.ground_under(at.x, at.z, at.y, 1.0)?;
|
||
let ceiling = self.ceiling_above(vec3f(at.x, floor + 0.05, at.z), 60.0)?;
|
||
let probe = vec3f(at.x, floor + 1.0, at.z);
|
||
let reach = 30.0;
|
||
let mut dist = [reach; 8];
|
||
for (i, d) in dist.iter_mut().enumerate() {
|
||
let a = std::f32::consts::TAU * i as f32 / 8.0;
|
||
if let Some((t, _)) = self.ray_hit(probe, vec3f(a.sin(), 0.0, -a.cos()), reach) {
|
||
*d = t;
|
||
}
|
||
}
|
||
let span = (0..4)
|
||
.map(|i| dist[i] + dist[i + 4])
|
||
.fold(f32::INFINITY, f32::min);
|
||
Some((ceiling - floor, span))
|
||
}
|
||
|
||
/// Are any of these horizontal moves cut by the level? Each pair is a
|
||
/// start/end ground point of one tracked point of a body's footprint
|
||
/// (a wheeled body sweeps its corners and edge midpoints through here).
|
||
/// Rays run at each `height` above `base` — the HIGHER of the two floor
|
||
/// heights, the same rule as [`Self::path_blocked`], so climbing a
|
||
/// step's own riser never reads as a wall.
|
||
pub fn moves_blocked(&self, moves: &[(Vec3f, Vec3f)], base: f32, heights: &[f32]) -> bool {
|
||
for (from, to) in moves {
|
||
let delta = vec3f(to.x - from.x, 0.0, to.z - from.z);
|
||
let dist = (delta.x * delta.x + delta.z * delta.z).sqrt();
|
||
if dist < 1.0e-6 {
|
||
continue;
|
||
}
|
||
let dir = vec3f(delta.x / dist, 0.0, delta.z / dist);
|
||
for &h in heights {
|
||
let origin = vec3f(from.x, base + h, from.z);
|
||
// Barely past the move itself: a fatter margin re-blocked
|
||
// the move AWAY from a wall the body was already against,
|
||
// which is how a car got welded to the plaster it hit.
|
||
if self.caster.any_hit(origin, dir, dist + 0.02) {
|
||
return true;
|
||
}
|
||
}
|
||
}
|
||
false
|
||
}
|
||
|
||
/// Is the straight walk from `from` to `to` (both FEET positions)
|
||
/// obstructed? The body is approximated by rays at knee and chest
|
||
/// height, plus the same pair offset by ±`radius` sideways, so a
|
||
/// doorway narrower than the body reads as blocked.
|
||
///
|
||
/// The rays are measured above the HIGHER of the two floors. Probing a
|
||
/// rising step this lifts them into the destination's frame, so a
|
||
/// staircase's own next treads (and any thin riser lip an importer
|
||
/// leaves poking above them) never read as walls — the rays are cast
|
||
/// `dist + radius` long, and on a flight steeper than the knee height
|
||
/// per body-radius a start-relative knee ray slams into the tread AFTER
|
||
/// the destination, which is how a perfectly legal staircase used to
|
||
/// have no graph edges at all. A genuine wall is taller than knee
|
||
/// height above EITHER floor and still blocks; flat walks and drops
|
||
/// (probed from the upper floor) are unchanged.
|
||
pub fn path_blocked(
|
||
&self,
|
||
from: Vec3f,
|
||
to: Vec3f,
|
||
radius: f32,
|
||
step_up: f32,
|
||
height: f32,
|
||
) -> bool {
|
||
let delta = vec3f(to.x - from.x, 0.0, to.z - from.z);
|
||
let dist = (delta.x * delta.x + delta.z * delta.z).sqrt();
|
||
if dist < 1e-6 {
|
||
return false;
|
||
}
|
||
let dir = vec3f(delta.x / dist, 0.0, delta.z / dist);
|
||
let side = vec3f(-dir.z, 0.0, dir.x);
|
||
let base = from.y.max(to.y);
|
||
// Knee starts above the step-up allowance: a ledge you can climb is
|
||
// not a wall, exactly as the step logic assumes.
|
||
let heights = [knee_height(step_up, height), height * 0.85];
|
||
let lanes = [-radius, 0.0, radius];
|
||
for h in heights {
|
||
for l in lanes {
|
||
let origin = vec3f(from.x + side.x * l, base + h, from.z + side.z * l);
|
||
if self.caster.any_hit(origin, dir, dist + radius) {
|
||
return true;
|
||
}
|
||
}
|
||
}
|
||
false
|
||
}
|
||
|
||
/// Is there at least `clear` of empty space all round the body? The
|
||
/// walker keeps this much between its eye and any wall so the camera's
|
||
/// near plane never pokes through geometry.
|
||
///
|
||
/// The lowest ray sits at the SAME knee height [`path_blocked`] probes
|
||
/// with. The two must agree: any gap between them is a band of wall
|
||
/// tops the walk probe offers and the landing check refuses — the body
|
||
/// walks up to the ledge and then refuses to stand, forever (the E1M1
|
||
/// courtyard rim bug).
|
||
pub fn clearance_ok(&self, feet: Vec3f, clear: f32, step_up: f32, height: f32) -> bool {
|
||
if clear <= 0.0 {
|
||
return true;
|
||
}
|
||
let heights = [knee_height(step_up, height), height * 0.55, height * 0.95];
|
||
for h in heights {
|
||
let origin = vec3f(feet.x, feet.y + h, feet.z);
|
||
for i in 0..8 {
|
||
let a = std::f32::consts::TAU * i as f32 / 8.0;
|
||
if self.caster.any_hit(origin, vec3f(a.sin(), 0.0, -a.cos()), clear) {
|
||
return false;
|
||
}
|
||
}
|
||
}
|
||
true
|
||
}
|
||
|
||
/// Free walking distance along `dir` from `feet`, stopping at a wall,
|
||
/// a step too tall, or the edge of the floor. Marched in body-radius
|
||
/// steps: this is the "how open is this heading" probe.
|
||
pub fn free_run(&self, feet: Vec3f, yaw: f32, cfg: &WalkerConfig) -> f32 {
|
||
let dir = yaw_forward(yaw);
|
||
let step = (cfg.radius * 1.5).max(0.05);
|
||
let mut at = feet;
|
||
let mut travelled = 0.0;
|
||
while travelled < cfg.probe_ahead {
|
||
let want = vec3f(at.x + dir.x * step, at.y, at.z + dir.z * step);
|
||
if self.path_blocked(at, want, cfg.radius, cfg.step_up, cfg.height) {
|
||
break;
|
||
}
|
||
let Some(floor) = self.floor_below(
|
||
vec3f(want.x, want.y + cfg.step_up, want.z),
|
||
cfg.step_up + cfg.fall_limit,
|
||
) else {
|
||
break; // void ahead
|
||
};
|
||
if floor.y - at.y > cfg.step_up + STEP_EPS || at.y - floor.y > cfg.fall_limit {
|
||
break;
|
||
}
|
||
at = vec3f(want.x, floor.y, want.z);
|
||
travelled += step;
|
||
}
|
||
travelled
|
||
}
|
||
|
||
/// How much of the free run along `yaw` crosses hazardous floor
|
||
/// (nukage, lava, slime). Zero when the way is clean — the heading
|
||
/// picker subtracts this so a safe bridge always beats a shortcut
|
||
/// through the ooze.
|
||
pub fn hazard_run(&self, feet: Vec3f, yaw: f32, cfg: &WalkerConfig) -> f32 {
|
||
let dir = yaw_forward(yaw);
|
||
let step = (cfg.radius * 1.5).max(0.05);
|
||
let mut at = feet;
|
||
let (mut travelled, mut bad) = (0.0, 0.0);
|
||
while travelled < cfg.probe_ahead {
|
||
let want = vec3f(at.x + dir.x * step, at.y, at.z + dir.z * step);
|
||
if self.path_blocked(at, want, cfg.radius, cfg.step_up, cfg.height) {
|
||
break;
|
||
}
|
||
let Some(floor) =
|
||
self.floor_below(vec3f(want.x, want.y + cfg.step_up, want.z), cfg.step_up + cfg.fall_limit)
|
||
else {
|
||
break;
|
||
};
|
||
if floor.y - at.y > cfg.step_up + STEP_EPS || at.y - floor.y > cfg.fall_limit {
|
||
break;
|
||
}
|
||
if floor.kind == SurfaceKind::Hazard {
|
||
bad += step;
|
||
}
|
||
at = vec3f(want.x, floor.y, want.z);
|
||
travelled += step;
|
||
}
|
||
bad
|
||
}
|
||
|
||
/// A standable spot INSIDE the level: floor under the feet, a ceiling
|
||
/// over the head, and room to stand. Scans a coarse grid and prefers
|
||
/// the most open interior spot nearest the middle of the map.
|
||
///
|
||
/// This is the fallback for maps whose catalog manifest carries no
|
||
/// `player_start` anchor — today, every classic map.
|
||
pub fn interior_start(&self, cfg: &WalkerConfig) -> Option<Vec3f> {
|
||
let (min, max) = self.bounds();
|
||
let steps = 24;
|
||
let mut best: Option<(f32, Vec3f)> = None;
|
||
for iz in 0..=steps {
|
||
for ix in 0..=steps {
|
||
let x = min.x + (max.x - min.x) * ix as f32 / steps as f32;
|
||
let z = min.z + (max.z - min.z) * iz as f32 / steps as f32;
|
||
for (floor, kind) in self.surfaces_in_column(x, z, cfg) {
|
||
if kind == SurfaceKind::Hazard {
|
||
continue; // never spawn the tour in the nukage
|
||
}
|
||
let feet = vec3f(x, floor, z);
|
||
// Room to stand AND somewhere to walk.
|
||
let open: f32 = (0..4)
|
||
.map(|q| {
|
||
self.free_run(feet, q as f32 * std::f32::consts::FRAC_PI_2, cfg)
|
||
})
|
||
.sum();
|
||
if open < cfg.radius * 4.0 {
|
||
continue;
|
||
}
|
||
if best.is_none_or(|(cur, _)| open > cur) {
|
||
best = Some((open, feet));
|
||
}
|
||
}
|
||
}
|
||
}
|
||
best.map(|(_, p)| p)
|
||
}
|
||
|
||
/// Floors in the column at `(x, z)` that a body fits on with a ceiling
|
||
/// above it — i.e. interior floors, never the outside of the roof.
|
||
fn surfaces_in_column(&self, x: f32, z: f32, cfg: &WalkerConfig) -> Vec<(f32, SurfaceKind)> {
|
||
let (min, max) = self.bounds();
|
||
// (height, kind, has a ceiling over it)
|
||
let mut raw: Vec<(f32, SurfaceKind, bool)> = Vec::new();
|
||
let mut y = max.y + 0.05;
|
||
// March down through every surface in this column.
|
||
for _ in 0..32 {
|
||
let Some(hit) = self.floor_below(vec3f(x, y, z), y - min.y + 0.1) else {
|
||
break;
|
||
};
|
||
if hit.flatness >= 0.5 {
|
||
let roofed = self
|
||
.ceiling_above(vec3f(x, hit.y + 0.02, z), MAX_HEADROOM)
|
||
.is_some_and(|c| c - hit.y >= cfg.height);
|
||
raw.push((hit.y, hit.kind, roofed));
|
||
}
|
||
y = hit.y - 1e-3;
|
||
if y < min.y - 0.05 {
|
||
break;
|
||
}
|
||
}
|
||
// Surfaces come off the march top-down. A ceiling over the head
|
||
// proves we are indoors and the surface is a floor. Open sky above
|
||
// means one of two things — the OUTSIDE OF A ROOF, or genuine open
|
||
// ground — and what tells them apart is whether the column holds
|
||
// another surface underneath: a roof always has its room below it,
|
||
// a courtyard has nothing. (The old rule was "open sky counts only
|
||
// in the lower half of the map", which threw away every outdoor
|
||
// yard on a hill and cut classic maps into disconnected wings.)
|
||
raw.iter()
|
||
.enumerate()
|
||
.filter(|(i, (y, _, roofed))| {
|
||
*roofed || *i + 1 == raw.len() || *y < (min.y + max.y) * 0.5
|
||
})
|
||
.map(|(_, (y, kind, _))| (*y, *kind))
|
||
.collect()
|
||
}
|
||
}
|
||
|
||
/// How far above the head a ceiling may be and still prove "indoors".
|
||
const MAX_HEADROOM: f32 = 8.0;
|
||
|
||
// ---------------------------------------------------------------------------
|
||
// Surface kinds out of a GLB
|
||
// ---------------------------------------------------------------------------
|
||
|
||
/// Classify every triangle of a level GLB as floor, hazard or liquid.
|
||
///
|
||
/// The importer's contract is a `hazard_N` node carrying
|
||
/// `extras {kind:"hazard", damage, flat, liquid}`; older files (every
|
||
/// classic map published before that lane) carry only the source engine's
|
||
/// flat/material name, so the name heuristic stays as a fallback.
|
||
///
|
||
/// Triangles are counted in EXACTLY the order [`crate::StaticModel`] packs
|
||
/// them — nodes in file order, primitives in mesh order, geometry under an
|
||
/// animated node left out. `expect_tris` is that model's triangle count and
|
||
/// the contract check: a walk that does not reproduce it has drifted from
|
||
/// the loader, and `None` (every floor plain) is the honest answer, never a
|
||
/// mislabelled map.
|
||
pub fn surface_kinds_from_glb(bytes: &[u8], expect_tris: usize) -> Option<Vec<SurfaceKind>> {
|
||
use crate::skin::{JsonParser, Val};
|
||
if bytes.len() < 12 || &bytes[0..4] != b"glTF" {
|
||
return None;
|
||
}
|
||
let mut json_chunk: Option<&[u8]> = None;
|
||
let mut at = 12;
|
||
while at + 8 <= bytes.len() {
|
||
let len = u32::from_le_bytes(bytes[at..at + 4].try_into().ok()?) as usize;
|
||
if &bytes[at + 4..at + 8] == b"JSON" {
|
||
json_chunk = bytes.get(at + 8..at + 8 + len);
|
||
}
|
||
at += 8 + len + (4 - len % 4) % 4;
|
||
}
|
||
let json = JsonParser::parse(json_chunk?).ok()?;
|
||
let nodes = json.get("nodes").map(|n| n.arr()).unwrap_or(&[]);
|
||
if nodes.is_empty() {
|
||
return None;
|
||
}
|
||
let mut parents: Vec<Option<usize>> = vec![None; nodes.len()];
|
||
for (p, n) in nodes.iter().enumerate() {
|
||
if let Some(children) = n.get("children") {
|
||
for c in children.arr() {
|
||
if let Some(ci) = c.usize() {
|
||
if ci < parents.len() {
|
||
parents[ci] = Some(p);
|
||
}
|
||
}
|
||
}
|
||
}
|
||
}
|
||
// A node the loader turns into a moving part (`extras.states` naming at
|
||
// least two states) takes its geometry OUT of the static stream.
|
||
let animated: Vec<bool> = nodes
|
||
.iter()
|
||
.map(|n| {
|
||
n.get("extras")
|
||
.and_then(|e| e.get("states"))
|
||
.map(|s| s.arr().iter().filter(|v| v.str().is_some()).count() >= 2)
|
||
.unwrap_or(false)
|
||
&& n.get("name").and_then(Val::str).is_some()
|
||
})
|
||
.collect();
|
||
let has_animations = json.get("animations").map(|a| !a.arr().is_empty()).unwrap_or(false);
|
||
// Geometry under a SKY node is the sky's, not the level's — the loader
|
||
// takes it out of the static stream (`StaticModel::sky`), so a walk that
|
||
// counts it can never reproduce the model's triangle count, and the
|
||
// whole classification is discarded as drift. Every classic map with an
|
||
// open-air area publishes one of these, which is exactly the set of maps
|
||
// that also has a nukage pool to mark.
|
||
let sky: Vec<bool> = nodes
|
||
.iter()
|
||
.map(|n| {
|
||
let Some(extras) = n.get("extras") else { return false };
|
||
let marked = extras.get("kind").and_then(Val::str) == Some("sky")
|
||
|| n.get("name").and_then(Val::str) == Some("sky");
|
||
// Same contract as the loader: a sky node without a projection
|
||
// it understands stays ordinary geometry.
|
||
marked && extras.get("projection").and_then(Val::str).is_some()
|
||
})
|
||
.collect();
|
||
let owned_by_sky = |mut i: usize| -> bool {
|
||
for _ in 0..64 {
|
||
if sky[i] {
|
||
return true;
|
||
}
|
||
match parents[i] {
|
||
Some(p) => i = p,
|
||
None => break,
|
||
}
|
||
}
|
||
false
|
||
};
|
||
// The node's kind is its own, or the nearest ancestor's that has one:
|
||
// classic importers group a whole nukage sector under one node.
|
||
let kind_of_node = |mut i: usize| -> Option<SurfaceKind> {
|
||
for _ in 0..64 {
|
||
if let Some(k) = node_surface_kind(&nodes[i]) {
|
||
return Some(k);
|
||
}
|
||
match parents[i] {
|
||
Some(p) => i = p,
|
||
None => break,
|
||
}
|
||
}
|
||
None
|
||
};
|
||
let owned_by_part = |mut i: usize| -> bool {
|
||
for _ in 0..64 {
|
||
if animated[i] {
|
||
return true;
|
||
}
|
||
match parents[i] {
|
||
Some(p) => i = p,
|
||
None => break,
|
||
}
|
||
}
|
||
false
|
||
};
|
||
// Two passes: with the anim-part skip (what a level with doors packs)
|
||
// and without (what every file predating that lane packs). The one whose
|
||
// triangle count matches the loaded model is the one to trust.
|
||
let attempts: &[bool] = if has_animations { &[true, false] } else { &[false] };
|
||
for &skip_parts in attempts {
|
||
let mut kinds: Vec<SurfaceKind> = Vec::with_capacity(expect_tris);
|
||
for (ni, n) in nodes.iter().enumerate() {
|
||
let Some(mesh_index) = n.get("mesh").and_then(Val::usize) else { continue };
|
||
if skip_parts && owned_by_part(ni) {
|
||
continue;
|
||
}
|
||
if owned_by_sky(ni) {
|
||
continue;
|
||
}
|
||
let node_kind = kind_of_node(ni);
|
||
let Some(mesh) = json.get("meshes").and_then(|m| m.idx(mesh_index)) else { continue };
|
||
for prim in mesh.get("primitives").map(|p| p.arr()).unwrap_or(&[]) {
|
||
let tris = prim_triangle_count(&json, prim);
|
||
if tris == 0 {
|
||
continue;
|
||
}
|
||
let kind = node_kind
|
||
.or_else(|| prim_material_kind(&json, prim))
|
||
.unwrap_or_default();
|
||
kinds.resize(kinds.len() + tris, kind);
|
||
}
|
||
}
|
||
if kinds.len() == expect_tris && kinds.iter().any(|k| *k != SurfaceKind::Floor) {
|
||
return Some(kinds);
|
||
}
|
||
if skip_parts == has_animations && has_animations {
|
||
continue; // try the no-skip walk
|
||
}
|
||
break;
|
||
}
|
||
None
|
||
}
|
||
|
||
/// A node's own declared surface, from the importer's `hazard_N` contract
|
||
/// (`extras {kind, damage, liquid, flat}`) or, failing that, its name.
|
||
fn node_surface_kind(node: &crate::skin::Val) -> Option<SurfaceKind> {
|
||
use crate::skin::Val;
|
||
if let Some(extras) = node.get("extras") {
|
||
let declared = extras.get("kind").and_then(Val::str).unwrap_or("");
|
||
let damage = extras.get("damage").and_then(Val::f64).unwrap_or(0.0);
|
||
let liquid = matches!(extras.get("liquid"), Some(Val::Bool(true)))
|
||
|| extras.get("liquid").and_then(Val::f64).unwrap_or(0.0) > 0.0;
|
||
if declared.eq_ignore_ascii_case("hazard") {
|
||
// A declared hazard with no damage that calls itself a liquid is
|
||
// just water: crossed, not avoided.
|
||
return Some(if damage <= 0.0 && liquid {
|
||
SurfaceKind::Liquid
|
||
} else {
|
||
SurfaceKind::Hazard
|
||
});
|
||
}
|
||
if damage > 0.0 {
|
||
return Some(SurfaceKind::Hazard);
|
||
}
|
||
if let Some(flat) = extras.get("flat").and_then(Val::str) {
|
||
if let Some(k) = surface_kind_from_name(flat) {
|
||
return Some(k);
|
||
}
|
||
}
|
||
if liquid {
|
||
return Some(SurfaceKind::Liquid);
|
||
}
|
||
}
|
||
node.get("name").and_then(Val::str).and_then(surface_kind_from_name)
|
||
}
|
||
|
||
/// The material's name as a last resort — a Doom import names its material
|
||
/// after the flat, which is how every map published before the `hazard_N`
|
||
/// contract can still be classified.
|
||
fn prim_material_kind(json: &crate::skin::Val, prim: &crate::skin::Val) -> Option<SurfaceKind> {
|
||
use crate::skin::Val;
|
||
let mi = prim.get("material").and_then(Val::usize)?;
|
||
let mat = json.get("materials").and_then(|m| m.idx(mi))?;
|
||
if let Some(k) = mat
|
||
.get("extras")
|
||
.and_then(|e| e.get("flat"))
|
||
.and_then(Val::str)
|
||
.and_then(surface_kind_from_name)
|
||
{
|
||
return Some(k);
|
||
}
|
||
mat.get("name").and_then(Val::str).and_then(surface_kind_from_name)
|
||
}
|
||
|
||
/// Flat/texture names the classic engines use for ground that hurts, and
|
||
/// for ground that is merely wet. Matched case-insensitively anywhere in the
|
||
/// name, because importers prefix and suffix freely (`doom.NUKAGE1.001`).
|
||
fn surface_kind_from_name(name: &str) -> Option<SurfaceKind> {
|
||
let n = name.to_ascii_lowercase();
|
||
// Water first: `fwater` contains neither, but `*water` in Quake and
|
||
// `water` anywhere must not be read as a hazard by a later rule.
|
||
const HAZARD: [&str; 7] = ["nukage", "slime", "lava", "blood", "acid", "sludge", "hazard"];
|
||
const LIQUID: [&str; 3] = ["water", "wtr", "swamp"];
|
||
if HAZARD.iter().any(|h| n.contains(h)) {
|
||
return Some(SurfaceKind::Hazard);
|
||
}
|
||
if LIQUID.iter().any(|l| n.contains(l)) {
|
||
return Some(SurfaceKind::Liquid);
|
||
}
|
||
None
|
||
}
|
||
|
||
/// Triangles a primitive contributes: its index count, or its vertex count
|
||
/// when it is drawn unindexed. Only TRIANGLES mode (4, the glTF default)
|
||
/// reaches the static stream.
|
||
fn prim_triangle_count(json: &crate::skin::Val, prim: &crate::skin::Val) -> usize {
|
||
use crate::skin::Val;
|
||
let count = match prim.get("indices").and_then(Val::usize) {
|
||
Some(acc) => json
|
||
.get("accessors")
|
||
.and_then(|a| a.idx(acc))
|
||
.and_then(|a| a.get("count"))
|
||
.and_then(Val::usize)
|
||
.unwrap_or(0),
|
||
None => prim
|
||
.get("attributes")
|
||
.and_then(|a| a.get("POSITION"))
|
||
.and_then(Val::usize)
|
||
.and_then(|acc| json.get("accessors").and_then(|a| a.idx(acc)))
|
||
.and_then(|a| a.get("count"))
|
||
.and_then(Val::usize)
|
||
.unwrap_or(0),
|
||
};
|
||
count / 3
|
||
}
|
||
|
||
// ---------------------------------------------------------------------------
|
||
// Navigation grid
|
||
// ---------------------------------------------------------------------------
|
||
|
||
/// Smallest xz cell the nav grid uses: ONE BODY per cell, i.e. two radii.
|
||
///
|
||
/// This used to be the bare number 0.5 — a Doom body's width at the Doom
|
||
/// importer's metres-per-map-unit. A map published at a different scale (a
|
||
/// Quake 1 level is 1/32, twice Doom's 1/64) then got a lattice half the
|
||
/// width of the body walking it: several sample points across one body, so
|
||
/// every ledge and jamb cut the grid into slivers, the room watershed read
|
||
/// the whole map as corridor, and the string-pull had a mandatory waypoint
|
||
/// every metre. The cell has to be the body's, or the graph is not a graph
|
||
/// of where THIS body can walk.
|
||
fn nav_cell_min(cfg: &WalkerConfig) -> f32 {
|
||
// 0.5 is the finest lattice worth probing (a Doom body's width, and the
|
||
// old fixed value); a WIDER body only ever makes it coarser.
|
||
(cfg.radius * 2.0).max(0.5)
|
||
}
|
||
/// Above this many columns the cell grows instead: a 500-unit outdoor map
|
||
/// must not turn into a hundred million probes.
|
||
const NAV_MAX_COLUMNS: usize = 40_000;
|
||
/// Hard ceiling on the growth above (a cell this big is no longer nav).
|
||
const NAV_CELL_MAX: f32 = 4.0;
|
||
/// Classic integer grid costs: a diagonal is √2 orthogonals.
|
||
const NAV_STEP_COST: u32 = 10;
|
||
const NAV_DIAG_COST: u32 = 14;
|
||
/// Entering hazardous ground costs twenty ordinary cells, so a bridge is
|
||
/// taken whenever a bridge exists and the ooze is still crossable when it
|
||
/// is the only way through.
|
||
const NAV_HAZARD_COST: u32 = 200;
|
||
/// Unreached cell marker in the flood's distance array.
|
||
const NAV_UNREACHED: u32 = u32::MAX;
|
||
|
||
/// One standable spot: a floor point at a column centre, on one of the
|
||
/// floors stacked in that column.
|
||
#[derive(Clone, Copy, Debug, PartialEq)]
|
||
pub struct NavCell {
|
||
/// Feet position — the column centre at this floor's height.
|
||
pub pos: Vec3f,
|
||
pub kind: SurfaceKind,
|
||
/// `ix + iz * nx` — which xz column this floor belongs to.
|
||
pub column: u32,
|
||
/// The door part that gates this cell, when one does. The walker asks
|
||
/// the host to open it before walking in.
|
||
pub door: Option<u16>,
|
||
/// Teleporter pad: stepping on this cell moves the body to
|
||
/// `NavGrid::teleport_target`.
|
||
pub teleport: Option<u16>,
|
||
/// This cell is in a pocket the ordinary step cannot leave — a sunken
|
||
/// nukage pool, a lift well — and its way out was linked with the
|
||
/// generous escape step. The body is allowed the same stretch while it
|
||
/// stands here, or it would refuse the edge the graph is routing it
|
||
/// along and grind along the rim instead.
|
||
pub escape: bool,
|
||
}
|
||
|
||
/// A level's walkable cells and how they connect: built ONCE per level from
|
||
/// [`LevelCollision`], then used to plan real routes.
|
||
///
|
||
/// The old walker scored twelve headings from where it stood, which makes a
|
||
/// corridor a local optimum: the longest free run is always the way it just
|
||
/// came, so it paced between two staircases forever. A graph over the whole
|
||
/// map replaces "which way looks open" with "which part of the map have I
|
||
/// not seen yet, and how do I get there".
|
||
///
|
||
/// Columns are a regular xz lattice; a column holds EVERY floor stacked in
|
||
/// it (a room over a room is two cells), which is what makes multi-storey
|
||
/// maps work. Edges are 8-neighbour, refused through walls by the same
|
||
/// knee/chest probe the walker's own step uses.
|
||
pub struct NavGrid {
|
||
cell: f32,
|
||
/// World position of column (0, 0)'s centre in x/z.
|
||
origin_x: f32,
|
||
origin_z: f32,
|
||
nx: usize,
|
||
nz: usize,
|
||
cells: Vec<NavCell>,
|
||
/// CSR over columns: column `c` owns `cells[col_start[c]..col_start[c+1]]`.
|
||
col_start: Vec<u32>,
|
||
edge_start: Vec<u32>,
|
||
edge_to: Vec<u32>,
|
||
edge_cost: Vec<u32>,
|
||
/// Which connected piece of the map each cell belongs to, and how big
|
||
/// each piece is. A classic map whose doors are still baked into the
|
||
/// static mesh is a dozen sealed rooms, and the tour has to know that.
|
||
component: Vec<u32>,
|
||
comp_size: Vec<usize>,
|
||
/// Teleporter destinations: `(feet, yaw)`, indexed by `NavCell::teleport`.
|
||
teleports: Vec<(Vec3f, f32)>,
|
||
refused: NavRefusals,
|
||
}
|
||
|
||
/// Why neighbouring cells did NOT become edges. A map the walker cannot
|
||
/// leave shows up here before it shows up on screen.
|
||
#[derive(Clone, Copy, Debug, Default, PartialEq)]
|
||
pub struct NavRefusals {
|
||
/// Rise over the step limit.
|
||
pub too_tall: usize,
|
||
/// The smallest rise that was still refused — on a Doom map this should
|
||
/// read well over 0.375, and a value AT 0.375 means the step rule is
|
||
/// off by a float.
|
||
pub smallest_refused_rise: f32,
|
||
/// Drop past the fall limit.
|
||
pub too_deep: usize,
|
||
/// A wall between the two centres.
|
||
pub walled: usize,
|
||
/// Edges the escape pass added to un-trap a pocket.
|
||
pub escapes: usize,
|
||
}
|
||
|
||
/// A planned leg: where the tour is going and the cells it walks through.
|
||
#[derive(Clone, Debug, PartialEq)]
|
||
pub struct NavPlan {
|
||
pub goal: u32,
|
||
/// Cells from the one AFTER the start up to and including the goal.
|
||
pub path: Vec<u32>,
|
||
/// How much of the map the plan could see from the start.
|
||
pub reachable: usize,
|
||
/// Visit count of the LEAST-trodden reachable cell. Once this rises
|
||
/// above one, everything the walker can reach has been seen and the
|
||
/// tour should cut somewhere else.
|
||
pub frontier: f32,
|
||
}
|
||
|
||
impl NavGrid {
|
||
/// Probe the level into a walkable-cell graph. Thousands of short rays:
|
||
/// this belongs on the loader thread, never in a frame.
|
||
pub fn build(level: &LevelCollision, cfg: &WalkerConfig) -> NavGrid {
|
||
let (min, max) = level.bounds();
|
||
let span_x = (max.x - min.x).max(0.001);
|
||
let span_z = (max.z - min.z).max(0.001);
|
||
let mut cell = nav_cell_min(cfg);
|
||
let (mut nx, mut nz);
|
||
loop {
|
||
nx = ((span_x / cell).ceil() as usize).max(1);
|
||
nz = ((span_z / cell).ceil() as usize).max(1);
|
||
if nx * nz <= NAV_MAX_COLUMNS || cell >= NAV_CELL_MAX {
|
||
break;
|
||
}
|
||
cell *= 1.25;
|
||
}
|
||
// Columns are CENTRES, half a cell in from the bounds. A lattice
|
||
// that starts exactly on `min` puts its first column inside the
|
||
// boundary wall, where a zero-length clearance ray reports "clear"
|
||
// and a cell appears in the masonry.
|
||
let (origin_x, origin_z) = (min.x + cell * 0.5, min.z + cell * 0.5);
|
||
let columns = nx * nz;
|
||
let mut cells: Vec<NavCell> = Vec::new();
|
||
let mut col_start: Vec<u32> = Vec::with_capacity(columns + 1);
|
||
for iz in 0..nz {
|
||
for ix in 0..nx {
|
||
col_start.push(cells.len() as u32);
|
||
let x = origin_x + ix as f32 * cell;
|
||
let z = origin_z + iz as f32 * cell;
|
||
for (y, kind) in level.surfaces_in_column(x, z, cfg) {
|
||
let feet = vec3f(x, y, z);
|
||
// The cell exists only if the BODY fits standing here:
|
||
// a capsule of the walker's radius, its full height.
|
||
if !level.clearance_ok(feet, cfg.radius, cfg.step_up, cfg.height) {
|
||
continue;
|
||
}
|
||
cells.push(NavCell {
|
||
pos: feet,
|
||
kind,
|
||
column: (ix + iz * nx) as u32,
|
||
door: None,
|
||
teleport: None,
|
||
escape: false,
|
||
});
|
||
}
|
||
}
|
||
}
|
||
col_start.push(cells.len() as u32);
|
||
let mut grid = NavGrid {
|
||
cell,
|
||
origin_x,
|
||
origin_z,
|
||
nx,
|
||
nz,
|
||
cells,
|
||
col_start,
|
||
edge_start: Vec::new(),
|
||
edge_to: Vec::new(),
|
||
edge_cost: Vec::new(),
|
||
component: Vec::new(),
|
||
comp_size: Vec::new(),
|
||
teleports: Vec::new(),
|
||
refused: NavRefusals { smallest_refused_rise: f32::MAX, ..NavRefusals::default() },
|
||
};
|
||
grid.link(level, cfg);
|
||
grid.label_components();
|
||
grid.link_escapes(level, cfg);
|
||
grid
|
||
}
|
||
|
||
/// Second linking pass: every cell in a pocket that is NOT the biggest
|
||
/// piece of the map gets its refused neighbours retried with the
|
||
/// generous escape step.
|
||
///
|
||
/// A Doom nukage pool sits 24 map units below its rim, which is exactly
|
||
/// the step limit — and a float baked through the importer lands either
|
||
/// side of it. One pool that reads a hair too tall is a walker who can
|
||
/// never leave the goo. The rule stays Doom's everywhere the map is
|
||
/// already connected; it only relaxes where the alternative is a trap.
|
||
fn link_escapes(&mut self, level: &LevelCollision, cfg: &WalkerConfig) {
|
||
const ORTHO: [(i32, i32); 4] = [(1, 0), (-1, 0), (0, 1), (0, -1)];
|
||
// Two rounds, so a pool that escapes into a ledge that was itself
|
||
// trapped ends up connected to the map rather than to another trap.
|
||
for _ in 0..2 {
|
||
let Some(core) = self.best_start() else { return };
|
||
// Which cells can REACH the core. Connectivity here is directed:
|
||
// you fall into a nukage pool through a one-way drop, so the
|
||
// pool is "reachable" from the map while being a prison. Only
|
||
// the reverse flood tells the two apart.
|
||
let out = self.can_reach(core);
|
||
let mut added: Vec<(u32, u32, u32)> = Vec::new();
|
||
for a in 0..self.cells.len() {
|
||
if out[a] {
|
||
continue;
|
||
}
|
||
let (ix, iz) = self.column_xz(self.cells[a].column);
|
||
for (dx, dz) in ORTHO {
|
||
let Some(col) = self.column_index(ix as i32 + dx, iz as i32 + dz) else {
|
||
continue;
|
||
};
|
||
for b in self.column_cells(col) {
|
||
if !out[b] {
|
||
continue; // no use escaping into another prison
|
||
}
|
||
let dy = self.cells[b].pos.y - self.cells[a].pos.y;
|
||
let reach = cfg.step_up + STEP_EPS + hazard_escape_step(cfg.step_up);
|
||
if dy <= cfg.step_up + STEP_EPS || dy > reach {
|
||
continue; // already linked, or genuinely a cliff
|
||
}
|
||
// The knee ray starts just above the step the body
|
||
// is allowed to climb. Probing an ESCAPE step with
|
||
// the ordinary knee height hits the riser of the
|
||
// very step it is asking about, and every way out
|
||
// of the pool reads as a wall.
|
||
if level.path_blocked(
|
||
self.cells[a].pos,
|
||
self.cells[b].pos,
|
||
cfg.radius,
|
||
(cfg.step_up + hazard_escape_step(cfg.step_up)).min(cfg.height * 0.8),
|
||
cfg.height,
|
||
) {
|
||
continue;
|
||
}
|
||
added.push((a as u32, b as u32, NAV_STEP_COST * 3));
|
||
}
|
||
}
|
||
}
|
||
if added.is_empty() {
|
||
return;
|
||
}
|
||
self.refused.escapes += added.len();
|
||
for (a, b, cost) in added {
|
||
self.cells[a as usize].escape = true;
|
||
self.push_edge(a, b, cost);
|
||
}
|
||
self.label_components();
|
||
}
|
||
}
|
||
|
||
/// Cells from which `target` can be walked to — a flood over the
|
||
/// REVERSED edges. The answer to "is this a place you can leave".
|
||
pub fn can_reach(&self, target: u32) -> Vec<bool> {
|
||
let n = self.cells.len();
|
||
let mut rev_head: Vec<u32> = vec![u32::MAX; n];
|
||
let mut rev_next: Vec<u32> = vec![u32::MAX; self.edge_to.len()];
|
||
let mut rev_from: Vec<u32> = vec![0; self.edge_to.len()];
|
||
for a in 0..n {
|
||
let (s, e) = (self.edge_start[a] as usize, self.edge_start[a + 1] as usize);
|
||
for k in s..e {
|
||
let b = self.edge_to[k] as usize;
|
||
rev_from[k] = a as u32;
|
||
rev_next[k] = rev_head[b];
|
||
rev_head[b] = k as u32;
|
||
}
|
||
}
|
||
let mut seen = vec![false; n];
|
||
if (target as usize) < n {
|
||
seen[target as usize] = true;
|
||
}
|
||
let mut stack = vec![target];
|
||
while let Some(b) = stack.pop() {
|
||
let mut k = rev_head[b as usize];
|
||
while k != u32::MAX {
|
||
let a = rev_from[k as usize] as usize;
|
||
if !seen[a] {
|
||
seen[a] = true;
|
||
stack.push(a as u32);
|
||
}
|
||
k = rev_next[k as usize];
|
||
}
|
||
}
|
||
seen
|
||
}
|
||
|
||
/// What the build refused, and why — the numbers that answer "why can
|
||
/// the walker not get out of there".
|
||
pub fn refusals(&self) -> NavRefusals {
|
||
self.refused
|
||
}
|
||
|
||
/// Flood-fill the graph into connected pieces, largest first in
|
||
/// `comp_size`'s value order (ids are assignment order, not rank).
|
||
fn label_components(&mut self) {
|
||
let n = self.cells.len();
|
||
self.component = vec![u32::MAX; n];
|
||
self.comp_size = Vec::new();
|
||
let mut stack: Vec<u32> = Vec::new();
|
||
for seed in 0..n {
|
||
if self.component[seed] != u32::MAX {
|
||
continue;
|
||
}
|
||
let id = self.comp_size.len() as u32;
|
||
let mut size = 0usize;
|
||
self.component[seed] = id;
|
||
stack.push(seed as u32);
|
||
while let Some(a) = stack.pop() {
|
||
size += 1;
|
||
let (s, e) = (
|
||
self.edge_start[a as usize] as usize,
|
||
self.edge_start[a as usize + 1] as usize,
|
||
);
|
||
for k in s..e {
|
||
let b = self.edge_to[k] as usize;
|
||
if self.component[b] == u32::MAX {
|
||
self.component[b] = id;
|
||
stack.push(b as u32);
|
||
}
|
||
}
|
||
}
|
||
self.comp_size.push(size);
|
||
}
|
||
}
|
||
|
||
/// Which connected piece `i` belongs to.
|
||
pub fn component_of(&self, i: u32) -> Option<u32> {
|
||
self.component.get(i as usize).copied().filter(|c| *c != u32::MAX)
|
||
}
|
||
|
||
/// Sizes of every connected piece, biggest first — the honest picture
|
||
/// of how cut up a map is.
|
||
pub fn component_sizes(&self) -> Vec<usize> {
|
||
let mut sizes = self.comp_size.clone();
|
||
sizes.sort_unstable_by(|a, b| b.cmp(a));
|
||
sizes
|
||
}
|
||
|
||
/// Teleporters, as `(pad min, pad max, destination feet, destination
|
||
/// yaw)`. A pad's cells get a ONE-WAY edge to the destination cell, so
|
||
/// the planner routes through a teleporter exactly as Doom's player
|
||
/// does, and the walker cuts to the far side when it steps on one.
|
||
pub fn mark_teleports(&mut self, pads: &[(Vec3f, Vec3f, Vec3f, f32)]) {
|
||
for (min, max, dst, yaw) in pads {
|
||
if self.teleports.len() > u16::MAX as usize {
|
||
break;
|
||
}
|
||
let Some(target) = self.cell_at(*dst) else { continue };
|
||
let id = self.teleports.len() as u16;
|
||
self.teleports.push((*dst, *yaw));
|
||
let pad = self.cell * 0.5;
|
||
let mut sources: Vec<u32> = Vec::new();
|
||
for (i, c) in self.cells.iter_mut().enumerate() {
|
||
if c.pos.x < min.x - pad || c.pos.x > max.x + pad {
|
||
continue;
|
||
}
|
||
if c.pos.z < min.z - pad || c.pos.z > max.z + pad {
|
||
continue;
|
||
}
|
||
if c.pos.y < min.y - 1.0 || c.pos.y > max.y + 1.0 {
|
||
continue;
|
||
}
|
||
c.teleport = Some(id);
|
||
sources.push(i as u32);
|
||
}
|
||
for s in sources {
|
||
self.push_edge(s, target, NAV_STEP_COST);
|
||
}
|
||
}
|
||
self.label_components();
|
||
}
|
||
|
||
/// Append one directed edge after the graph is built. CSR is rebuilt
|
||
/// for the tail only: teleporters are a handful, not a hot path.
|
||
fn push_edge(&mut self, from: u32, to: u32, cost: u32) {
|
||
let at = self.edge_start[from as usize + 1] as usize;
|
||
self.edge_to.insert(at, to);
|
||
self.edge_cost.insert(at, cost);
|
||
for s in self.edge_start.iter_mut().skip(from as usize + 1) {
|
||
*s += 1;
|
||
}
|
||
}
|
||
|
||
/// A teleporter's destination.
|
||
pub fn teleport_target(&self, id: u16) -> Option<(Vec3f, f32)> {
|
||
self.teleports.get(id as usize).copied()
|
||
}
|
||
|
||
/// Orthogonal edges first (one wall probe each), then diagonals, which
|
||
/// are allowed only where BOTH flanking orthogonals are — a body cannot
|
||
/// squeeze through the corner between two walls.
|
||
fn link(&mut self, level: &LevelCollision, cfg: &WalkerConfig) {
|
||
let n = self.cells.len();
|
||
let mut refused = NavRefusals { smallest_refused_rise: f32::MAX, ..Default::default() };
|
||
let mut adj: Vec<Vec<(u32, u32)>> = vec![Vec::new(); n];
|
||
const ORTHO: [(i32, i32); 4] = [(1, 0), (-1, 0), (0, 1), (0, -1)];
|
||
const DIAG: [(i32, i32); 4] = [(1, 1), (1, -1), (-1, 1), (-1, -1)];
|
||
for a in 0..n {
|
||
let (ix, iz) = self.column_xz(self.cells[a].column);
|
||
for (dx, dz) in ORTHO {
|
||
let (jx, jz) = (ix as i32 + dx, iz as i32 + dz);
|
||
let Some(col) = self.column_index(jx, jz) else { continue };
|
||
// One wall probe serves every floor in the neighbour column
|
||
// only if they share the walk height, so probe per candidate.
|
||
for b in self.column_cells(col) {
|
||
match self.step_cost(level, cfg, a, b, NAV_STEP_COST) {
|
||
StepVerdict::Ok(cost) => adj[a].push((b as u32, cost)),
|
||
StepVerdict::TooTall(rise) => {
|
||
refused.too_tall += 1;
|
||
refused.smallest_refused_rise =
|
||
refused.smallest_refused_rise.min(rise);
|
||
}
|
||
StepVerdict::TooDeep => refused.too_deep += 1,
|
||
StepVerdict::Walled => refused.walled += 1,
|
||
}
|
||
}
|
||
}
|
||
}
|
||
// A diagonal needs its two flanking orthogonal moves to exist, from
|
||
// the SAME cell — that is the standard no-corner-cutting rule.
|
||
for a in 0..n {
|
||
let (ix, iz) = self.column_xz(self.cells[a].column);
|
||
for (dx, dz) in DIAG {
|
||
let Some(col) = self.column_index(ix as i32 + dx, iz as i32 + dz) else { continue };
|
||
let flank_x = self.column_index(ix as i32 + dx, iz as i32);
|
||
let flank_z = self.column_index(ix as i32, iz as i32 + dz);
|
||
let has = |col: Option<usize>| match col {
|
||
Some(c) => adj[a].iter().any(|(b, _)| {
|
||
self.cells[*b as usize].column == c as u32
|
||
}),
|
||
None => false,
|
||
};
|
||
if !has(flank_x) || !has(flank_z) {
|
||
continue;
|
||
}
|
||
for b in self.column_cells(col) {
|
||
if let StepVerdict::Ok(cost) = self.step_cost(level, cfg, a, b, NAV_DIAG_COST) {
|
||
adj[a].push((b as u32, cost));
|
||
}
|
||
}
|
||
}
|
||
}
|
||
self.edge_start = Vec::with_capacity(n + 1);
|
||
for list in &adj {
|
||
self.edge_start.push(self.edge_to.len() as u32);
|
||
for (b, cost) in list {
|
||
self.edge_to.push(*b);
|
||
self.edge_cost.push(*cost);
|
||
}
|
||
}
|
||
self.edge_start.push(self.edge_to.len() as u32);
|
||
self.refused = refused;
|
||
}
|
||
|
||
/// Cost of stepping a → b, or `None` when the body cannot make it:
|
||
/// a rise over the step-up allowance, a drop past the fall limit, or a
|
||
/// wall between the two centres. A drop between those two is ONE-WAY —
|
||
/// you can walk off a ledge you cannot climb back up.
|
||
fn step_cost(
|
||
&self,
|
||
level: &LevelCollision,
|
||
cfg: &WalkerConfig,
|
||
a: usize,
|
||
b: usize,
|
||
base: u32,
|
||
) -> StepVerdict {
|
||
let (pa, pb) = (self.cells[a].pos, self.cells[b].pos);
|
||
let dy = pb.y - pa.y;
|
||
// Same inclusive step rule the body uses, and the same extra reach
|
||
// out of a hazard: a nukage pit whose rim is exactly one step tall
|
||
// must be a place you can leave.
|
||
let reach = cfg.step_up
|
||
+ STEP_EPS
|
||
+ if self.cells[a].kind == SurfaceKind::Hazard { hazard_escape_step(cfg.step_up) } else { 0.0 };
|
||
if dy > reach {
|
||
return StepVerdict::TooTall(dy);
|
||
}
|
||
if -dy > cfg.fall_limit {
|
||
return StepVerdict::TooDeep;
|
||
}
|
||
if level.path_blocked(pa, pb, cfg.radius, cfg.step_up, cfg.height) {
|
||
return StepVerdict::Walled;
|
||
}
|
||
let hazard = if self.cells[b].kind == SurfaceKind::Hazard { NAV_HAZARD_COST } else { 0 };
|
||
// A drop is walkable but not free: prefer the stairs.
|
||
let fall = if dy < -cfg.step_up { base } else { 0 };
|
||
StepVerdict::Ok(base + hazard + fall)
|
||
}
|
||
|
||
fn column_xz(&self, column: u32) -> (usize, usize) {
|
||
let c = column as usize;
|
||
(c % self.nx, c / self.nx)
|
||
}
|
||
|
||
fn column_index(&self, ix: i32, iz: i32) -> Option<usize> {
|
||
if ix < 0 || iz < 0 || ix as usize >= self.nx || iz as usize >= self.nz {
|
||
return None;
|
||
}
|
||
Some(ix as usize + iz as usize * self.nx)
|
||
}
|
||
|
||
fn column_cells(&self, column: usize) -> std::ops::Range<usize> {
|
||
let (s, e) = (self.col_start[column] as usize, self.col_start[column + 1] as usize);
|
||
s..e
|
||
}
|
||
|
||
pub fn cell_size(&self) -> f32 {
|
||
self.cell
|
||
}
|
||
|
||
pub fn dims(&self) -> (usize, usize) {
|
||
(self.nx, self.nz)
|
||
}
|
||
|
||
/// World x/z of column `(0, 0)`'s CENTRE. A consumer that wants to lay
|
||
/// its own lattice over this one (a strategy map played on a streamed
|
||
/// level) needs the origin as well as the pitch.
|
||
pub fn origin_xz(&self) -> (f32, f32) {
|
||
(self.origin_x, self.origin_z)
|
||
}
|
||
|
||
pub fn len(&self) -> usize {
|
||
self.cells.len()
|
||
}
|
||
|
||
pub fn is_empty(&self) -> bool {
|
||
self.cells.is_empty()
|
||
}
|
||
|
||
pub fn edge_count(&self) -> usize {
|
||
self.edge_to.len()
|
||
}
|
||
|
||
pub fn cell(&self, i: u32) -> Option<&NavCell> {
|
||
self.cells.get(i as usize)
|
||
}
|
||
|
||
/// Every outgoing edge of `i`, as `(neighbour, cost)`.
|
||
pub fn edges(&self, i: u32) -> impl Iterator<Item = (u32, u32)> + '_ {
|
||
let (s, e) = (self.edge_start[i as usize] as usize, self.edge_start[i as usize + 1] as usize);
|
||
(s..e).map(move |k| (self.edge_to[k], self.edge_cost[k]))
|
||
}
|
||
|
||
/// The cell a body at `p` is standing in: same column (or a neighbouring
|
||
/// one, since a cell centre is up to half a cell away), the floor whose
|
||
/// height is nearest the feet.
|
||
pub fn cell_at(&self, p: Vec3f) -> Option<u32> {
|
||
let fx = ((p.x - self.origin_x) / self.cell).round();
|
||
let fz = ((p.z - self.origin_z) / self.cell).round();
|
||
if !fx.is_finite() || !fz.is_finite() {
|
||
return None;
|
||
}
|
||
let (cx, cz) = (fx as i32, fz as i32);
|
||
let mut best: Option<(f32, u32)> = None;
|
||
for dz in -1..=1 {
|
||
for dx in -1..=1 {
|
||
let Some(col) = self.column_index(cx + dx, cz + dz) else { continue };
|
||
for i in self.column_cells(col) {
|
||
let c = &self.cells[i];
|
||
let dy = (c.pos.y - p.y).abs();
|
||
// A floor more than a step out of reach is a different
|
||
// storey, not the one under these feet.
|
||
if dy > 1.0 + self.cell {
|
||
continue;
|
||
}
|
||
let dxz = (c.pos.x - p.x).abs().max((c.pos.z - p.z).abs());
|
||
let score = dy * 4.0 + dxz;
|
||
if best.is_none_or(|(cur, _)| score < cur) {
|
||
best = Some((score, i as u32));
|
||
}
|
||
}
|
||
}
|
||
}
|
||
best.map(|(_, i)| i)
|
||
}
|
||
|
||
/// Mark the cells a door part's footprint covers, by index into `doors`.
|
||
/// Cells under a door are walkable — the walker opens it on approach —
|
||
/// so the door must NOT also be part of the collision mesh.
|
||
pub fn mark_doors(&mut self, doors: &[(Vec3f, Vec3f)]) {
|
||
for (d, (min, max)) in doors.iter().enumerate() {
|
||
if d > u16::MAX as usize {
|
||
break;
|
||
}
|
||
let pad = self.cell * 0.5;
|
||
for c in self.cells.iter_mut() {
|
||
if c.pos.x < min.x - pad || c.pos.x > max.x + pad {
|
||
continue;
|
||
}
|
||
if c.pos.z < min.z - pad || c.pos.z > max.z + pad {
|
||
continue;
|
||
}
|
||
// The door's own storey: its box starts at that floor.
|
||
if c.pos.y < min.y - 1.0 || c.pos.y > max.y + 1.0 {
|
||
continue;
|
||
}
|
||
c.door = Some(d as u16);
|
||
}
|
||
}
|
||
}
|
||
|
||
/// Dijkstra from `from` over every edge not in `blocked`, filling
|
||
/// `dist`/`parent` (both resized to the cell count). Returns how many
|
||
/// cells were reached, `from` included.
|
||
pub fn flood(
|
||
&self,
|
||
from: u32,
|
||
blocked: &std::collections::HashSet<u64>,
|
||
dist: &mut Vec<u32>,
|
||
parent: &mut Vec<u32>,
|
||
) -> usize {
|
||
use std::cmp::Reverse;
|
||
use std::collections::BinaryHeap;
|
||
dist.clear();
|
||
dist.resize(self.cells.len(), NAV_UNREACHED);
|
||
parent.clear();
|
||
parent.resize(self.cells.len(), NAV_UNREACHED);
|
||
if from as usize >= self.cells.len() {
|
||
return 0;
|
||
}
|
||
dist[from as usize] = 0;
|
||
let mut heap: BinaryHeap<Reverse<(u32, u32)>> = BinaryHeap::new();
|
||
heap.push(Reverse((0, from)));
|
||
let mut reached = 0;
|
||
while let Some(Reverse((d, a))) = heap.pop() {
|
||
if d > dist[a as usize] {
|
||
continue;
|
||
}
|
||
reached += 1;
|
||
for (b, cost) in self.edges(a) {
|
||
if blocked.contains(&edge_key(a, b)) {
|
||
continue;
|
||
}
|
||
let nd = d + cost;
|
||
if nd < dist[b as usize] {
|
||
dist[b as usize] = nd;
|
||
parent[b as usize] = a;
|
||
heap.push(Reverse((nd, b)));
|
||
}
|
||
}
|
||
}
|
||
reached
|
||
}
|
||
|
||
/// Where to drop the tour: the cell nearest the middle of the LARGEST
|
||
/// connected component, never on hazardous ground.
|
||
///
|
||
/// This replaces the old open-space heuristic outright. That one scored
|
||
/// a 24×24 lattice by how far it could walk in four directions, which
|
||
/// happily picked a wide sealed courtyard the walker could never leave;
|
||
/// "the biggest piece of the map that is actually one piece" cannot.
|
||
pub fn best_start(&self) -> Option<u32> {
|
||
let best_comp = (0..self.comp_size.len() as u32)
|
||
.max_by_key(|c| self.comp_size[*c as usize])?;
|
||
self.middle_of(best_comp)
|
||
}
|
||
|
||
/// The cell nearest the middle of one connected piece, never on
|
||
/// hazardous ground.
|
||
pub fn middle_of(&self, comp: u32) -> Option<u32> {
|
||
let (mut cx, mut cz, mut count) = (0.0f32, 0.0f32, 0.0f32);
|
||
for (i, c) in self.component.iter().enumerate() {
|
||
if *c == comp {
|
||
cx += self.cells[i].pos.x;
|
||
cz += self.cells[i].pos.z;
|
||
count += 1.0;
|
||
}
|
||
}
|
||
if count == 0.0 {
|
||
return None;
|
||
}
|
||
let (cx, cz) = (cx / count, cz / count);
|
||
let mut best: Option<(f32, u32)> = None;
|
||
for (i, c) in self.component.iter().enumerate() {
|
||
if *c != comp || self.cells[i].kind == SurfaceKind::Hazard {
|
||
continue;
|
||
}
|
||
let p = self.cells[i].pos;
|
||
let d = (p.x - cx) * (p.x - cx) + (p.z - cz) * (p.z - cz);
|
||
if best.is_none_or(|(cur, _)| d < cur) {
|
||
best = Some((d, i as u32));
|
||
}
|
||
}
|
||
best.map(|(_, i)| i)
|
||
}
|
||
|
||
/// Somewhere else to continue the tour when the region round the walker
|
||
/// has been seen: the middle of the biggest piece of the map whose cells
|
||
/// are least trodden. Deterministic — `visits` and the sizes decide.
|
||
pub fn next_region(&self, from: u32, visits: &[f32]) -> Option<u32> {
|
||
let here = self.component_of(from);
|
||
let mut best: Option<(f32, usize, u32)> = None;
|
||
for comp in 0..self.comp_size.len() as u32 {
|
||
if Some(comp) == here || self.comp_size[comp as usize] < 4 {
|
||
continue;
|
||
}
|
||
let (mut sum, mut n) = (0.0f32, 0.0f32);
|
||
for (i, c) in self.component.iter().enumerate() {
|
||
if *c == comp {
|
||
sum += visits.get(i).copied().unwrap_or(0.0);
|
||
n += 1.0;
|
||
}
|
||
}
|
||
let mean = if n > 0.0 { sum / n } else { 0.0 };
|
||
let size = self.comp_size[comp as usize];
|
||
// Least trodden first, biggest first among equals.
|
||
let better = match best {
|
||
None => true,
|
||
Some((bm, bs, _)) => mean < bm - 1e-6 || ((mean - bm).abs() <= 1e-6 && size > bs),
|
||
};
|
||
if better {
|
||
best = Some((mean, size, comp));
|
||
}
|
||
}
|
||
best.and_then(|(_, _, comp)| self.middle_of(comp))
|
||
}
|
||
|
||
/// How much of the map is reachable from `i` (a spawn sanity check).
|
||
pub fn reachable_from(&self, i: u32) -> usize {
|
||
let (mut dist, mut parent) = (Vec::new(), Vec::new());
|
||
self.flood(i, &std::collections::HashSet::new(), &mut dist, &mut parent)
|
||
}
|
||
|
||
/// Waypoints from (but excluding) the flood's start to `goal`.
|
||
pub fn path_to(&self, goal: u32, parent: &[u32]) -> Vec<u32> {
|
||
let mut out = Vec::new();
|
||
let mut at = goal;
|
||
// Bounded by the cell count: a parent chain cannot be longer.
|
||
for _ in 0..=self.cells.len() {
|
||
out.push(at);
|
||
let p = *parent.get(at as usize).unwrap_or(&NAV_UNREACHED);
|
||
if p == NAV_UNREACHED {
|
||
break;
|
||
}
|
||
at = p;
|
||
}
|
||
out.reverse();
|
||
// The first entry is the start cell itself.
|
||
if !out.is_empty() {
|
||
out.remove(0);
|
||
}
|
||
out
|
||
}
|
||
|
||
/// Pick the next leg: the least-visited cell the tour can reach,
|
||
/// nearest first, with a minimum leg length so it does not spend the
|
||
/// evening shuffling one cell at a time along the frontier.
|
||
///
|
||
/// `jitter` (0..1) breaks ties deterministically from the walker's seed.
|
||
pub fn explore(
|
||
&self,
|
||
from: u32,
|
||
visits: &[f32],
|
||
blocked: &std::collections::HashSet<u64>,
|
||
jitter: f32,
|
||
dist: &mut Vec<u32>,
|
||
parent: &mut Vec<u32>,
|
||
) -> Option<NavPlan> {
|
||
let reachable = self.flood(from, blocked, dist, parent);
|
||
// One visit is worth forty cells of walking: an unseen room across
|
||
// the map beats trodden ground next door, which is the whole point.
|
||
const VISIT_PENALTY: f32 = 400.0;
|
||
/// Shorter legs than this are not worth replanning for.
|
||
const MIN_LEG: u32 = 100;
|
||
let mut best: Option<(f32, u32)> = None;
|
||
let mut best_near: Option<(f32, u32)> = None;
|
||
let mut frontier = f32::MAX;
|
||
for i in 0..self.cells.len() {
|
||
let d = dist[i];
|
||
if d == NAV_UNREACHED || i as u32 == from {
|
||
continue;
|
||
}
|
||
if self.cells[i].kind == SurfaceKind::Hazard {
|
||
continue; // never park the tour in the ooze
|
||
}
|
||
frontier = frontier.min(visits.get(i).copied().unwrap_or(0.0));
|
||
let score = d as f32
|
||
+ visits.get(i).copied().unwrap_or(0.0) * VISIT_PENALTY
|
||
+ jitter * 30.0 * ((i % 7) as f32 / 7.0);
|
||
if best_near.is_none_or(|(cur, _)| score < cur) {
|
||
best_near = Some((score, i as u32));
|
||
}
|
||
if d >= MIN_LEG && best.is_none_or(|(cur, _)| score < cur) {
|
||
best = Some((score, i as u32));
|
||
}
|
||
}
|
||
let (_, goal) = best.or(best_near)?;
|
||
Some(NavPlan {
|
||
goal,
|
||
path: self.path_to(goal, parent),
|
||
reachable,
|
||
frontier: if frontier == f32::MAX { 0.0 } else { frontier },
|
||
})
|
||
}
|
||
}
|
||
|
||
/// What happened to one candidate step of the body.
|
||
#[derive(Clone, Copy, Debug, PartialEq)]
|
||
pub enum StepRefusal {
|
||
Ok { rise: f32 },
|
||
/// The knee/chest probe found geometry between here and there.
|
||
Walled,
|
||
/// No floor at all under the destination.
|
||
NoFloor,
|
||
TooTall { rise: f32, reach: f32 },
|
||
Pit { drop: f32 },
|
||
/// The landing is closer than a body radius to a wall.
|
||
NoClearance { rise: f32 },
|
||
}
|
||
|
||
/// Why one neighbour did or did not become an edge.
|
||
enum StepVerdict {
|
||
Ok(u32),
|
||
/// Rise, in world units — the number that says whether the step rule is
|
||
/// off by a float or the wall is genuinely too tall.
|
||
TooTall(f32),
|
||
TooDeep,
|
||
Walled,
|
||
}
|
||
|
||
/// Undirected-safe key for one DIRECTED edge (a→b is invalidated on its own:
|
||
/// a ledge you fell off may still be walkable the other way).
|
||
fn edge_key(a: u32, b: u32) -> u64 {
|
||
(a as u64) << 32 | b as u64
|
||
}
|
||
|
||
/// What the tour is doing right now, for the trace log.
|
||
#[derive(Clone, Copy, Debug, Default, PartialEq)]
|
||
pub struct NavStats {
|
||
pub cells: usize,
|
||
pub reachable: usize,
|
||
pub at: Option<u32>,
|
||
pub goal: Option<u32>,
|
||
pub path_left: usize,
|
||
/// Cells stood in at least once since the level loaded.
|
||
pub distinct: usize,
|
||
/// Reachable cells the tour has never stood in (or has forgotten).
|
||
pub unseen: usize,
|
||
/// Visit count of the least-trodden reachable cell.
|
||
pub frontier: f32,
|
||
pub replans: u64,
|
||
pub invalidated: usize,
|
||
/// Teleporter jumps + exhausted-region cuts so far.
|
||
pub cuts: u64,
|
||
}
|
||
|
||
/// Which game's head-bob the camera imitates. Constants are the originals
|
||
/// where the source is public; amplitudes are a fraction of eye height so
|
||
/// they survive each importer's unit conversion.
|
||
#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
|
||
pub enum BobStyle {
|
||
/// Doom `P_CalcHeight` (p_user.c): `bob = (momx² + momy²) >> 2` capped
|
||
/// at `MAXBOB` (16 units), applied as `bob/2 · sin(angle)` with
|
||
/// `angle = FINEANGLES/20 · leveltime` — one cycle per 20 tics, 1.75 Hz
|
||
/// at 35 tics/s. Peak 8 of 41 view-height units.
|
||
#[default]
|
||
Doom,
|
||
/// Build engine (Duke 3D): `bobcounter` advances with horizontal speed
|
||
/// and drives the view offset — quicker and deeper than Doom, with the
|
||
/// engine's lateral sway. Matched by feel; the fixed-point constants
|
||
/// are not transcribed.
|
||
Duke,
|
||
/// Quake `V_CalcBob` (view.c): `cl_bobcycle 0.6`, `cl_bobup 0.5`,
|
||
/// `cl_bob 0.02` × speed, shaped `0.3 + 0.7·sin`, clamped +4/−7 units;
|
||
/// plus `cl_rollangle 2.0` roll as the view swings.
|
||
Quake,
|
||
None,
|
||
}
|
||
|
||
impl BobStyle {
|
||
/// Family from a catalog alias/namespace (`doom/doom/worlds/…`,
|
||
/// `duke/duke3d/…`, `quake/id1/…`). Unknown sources keep Doom's.
|
||
pub fn from_source(text: &str) -> BobStyle {
|
||
let t = text.to_ascii_lowercase();
|
||
if t.contains("duke") || t.contains("build") {
|
||
BobStyle::Duke
|
||
} else if t.contains("quake") || t.contains("q3") || t.contains("q2") {
|
||
BobStyle::Quake
|
||
} else {
|
||
BobStyle::Doom
|
||
}
|
||
}
|
||
|
||
fn frequency(self) -> f32 {
|
||
match self {
|
||
BobStyle::Doom => 35.0 / 20.0,
|
||
BobStyle::Duke => 2.2,
|
||
BobStyle::Quake => 1.0 / 0.6,
|
||
BobStyle::None => 0.0,
|
||
}
|
||
}
|
||
|
||
/// Peak vertical travel as a fraction of eye height.
|
||
///
|
||
/// Doom's MAXBOB/2 is 8 map units — a quarter of a metre, which reads
|
||
/// as seasickness on a big screen at 60 fps rather than as walking.
|
||
/// These are the originals' CADENCE at a comfortable magnitude: about
|
||
/// 3 cm at walk speed for Doom/Build, 2 cm for Quake (`cl_bob 0.02` ×
|
||
/// speed lands there too).
|
||
fn amplitude(self) -> f32 {
|
||
match self {
|
||
BobStyle::Doom => 0.024,
|
||
BobStyle::Duke => 0.030,
|
||
BobStyle::Quake => 0.016,
|
||
BobStyle::None => 0.0,
|
||
}
|
||
}
|
||
|
||
fn sway(self) -> f32 {
|
||
match self {
|
||
BobStyle::Duke => 0.012,
|
||
_ => 0.0,
|
||
}
|
||
}
|
||
|
||
fn roll(self) -> f32 {
|
||
match self {
|
||
BobStyle::Quake => 2.0f32.to_radians(),
|
||
_ => 0.0,
|
||
}
|
||
}
|
||
|
||
fn wave(self, phase: f32) -> f32 {
|
||
let p = phase.rem_euclid(1.0);
|
||
match self {
|
||
BobStyle::Quake => {
|
||
const BOB_UP: f32 = 0.5;
|
||
let cycle = if p < BOB_UP {
|
||
std::f32::consts::PI * p / BOB_UP
|
||
} else {
|
||
std::f32::consts::PI + std::f32::consts::PI * (p - BOB_UP) / (1.0 - BOB_UP)
|
||
};
|
||
0.3 + 0.7 * cycle.sin()
|
||
}
|
||
BobStyle::None => 0.0,
|
||
_ => (p * std::f32::consts::TAU).sin(),
|
||
}
|
||
}
|
||
}
|
||
|
||
/// Body + gait, in world units. Defaults are the classic-importer scale
|
||
/// (Doom map units / 64): a 41-unit view height is 0.64, a 24-unit step is
|
||
/// 0.375.
|
||
#[derive(Clone, Copy, Debug)]
|
||
pub struct WalkerConfig {
|
||
pub eye_height: f32,
|
||
/// Body radius — the originals all use 16 map units (0.25 here). The
|
||
/// walker never ends a step with a wall closer than this, which is
|
||
/// also what keeps the camera's near plane out of the geometry.
|
||
pub radius: f32,
|
||
pub height: f32,
|
||
pub speed: f32,
|
||
pub turn_rate: f32,
|
||
/// Ledge the walker steps straight onto, the way the originals do
|
||
/// (Doom 24 map units = 0.375, Quake 18 = 0.28).
|
||
pub step_up: f32,
|
||
/// Deepest drop it will walk off. Beyond this it turns away rather
|
||
/// than diving into a pit; a void (no floor at all) always refuses.
|
||
pub fall_limit: f32,
|
||
/// Downward acceleration while falling, world units/s². Doom's
|
||
/// GRAVITY is 1 map unit per tic² = 19.1 u/s² at 35 tics; Quake's is
|
||
/// 800 Quake units/s² ≈ 12.5 here.
|
||
pub gravity: f32,
|
||
pub probe_ahead: f32,
|
||
pub repick_secs: f32,
|
||
pub bob: BobStyle,
|
||
}
|
||
|
||
impl Default for WalkerConfig {
|
||
fn default() -> Self {
|
||
Self {
|
||
eye_height: 0.64,
|
||
radius: 0.25,
|
||
height: 0.85,
|
||
speed: 1.6,
|
||
turn_rate: 1.6,
|
||
step_up: 0.375,
|
||
fall_limit: 2.5,
|
||
gravity: 19.1,
|
||
probe_ahead: 6.0,
|
||
repick_secs: 4.0,
|
||
bob: BobStyle::Doom,
|
||
}
|
||
}
|
||
}
|
||
|
||
impl WalkerConfig {
|
||
/// The body/gait each engine gives its player, at the classic
|
||
/// importer's ORIGINAL metres per map unit (1/64).
|
||
///
|
||
/// These are ratios of an engine's own constants, not the map's units:
|
||
/// an importer is free to publish at whatever scale suits its source
|
||
/// (Quake 1 is 1/32, twice this), and every such map DECLARES its step
|
||
/// height. Use [`Self::with_declared`] to land the body in the units of
|
||
/// the map it is about to walk — a preset alone is a guess.
|
||
pub fn for_style(bob: BobStyle) -> WalkerConfig {
|
||
let base = WalkerConfig { bob, ..WalkerConfig::default() };
|
||
match bob {
|
||
// Doom: radius 16, height 56, view 41, step 24, gravity 1/tic².
|
||
BobStyle::Doom | BobStyle::None => base,
|
||
// Quake: radius 16, height 56, view 22 above the feet of a
|
||
// 56-tall box, step 18, gravity 800 u/s².
|
||
BobStyle::Quake => WalkerConfig {
|
||
eye_height: 0.66,
|
||
step_up: 0.28,
|
||
gravity: 12.5,
|
||
speed: 1.9,
|
||
..base
|
||
},
|
||
// Build (Duke): comparable body, brisker walk.
|
||
BobStyle::Duke => WalkerConfig {
|
||
eye_height: 0.62,
|
||
step_up: 0.34,
|
||
gravity: 16.0,
|
||
speed: 1.8,
|
||
..base
|
||
},
|
||
}
|
||
}
|
||
|
||
/// Put the preset body into the units of the map it is about to walk,
|
||
/// from the facts the importer DECLARED about that map.
|
||
///
|
||
/// Every classic converter publishes its engine's step height and eye
|
||
/// height as anchors, in the GLB's own metres — `step_height` /
|
||
/// `eye_height` (`world_nav.rs`). A preset says "18 units"; the map says
|
||
/// what a unit is worth. Doom's 24 at 1/64 is 0.375 and matches the
|
||
/// preset; Quake 1's 18 at **1/32** is 0.5625, exactly twice the 18-at-
|
||
/// 1/64 the Quake preset carries (Quake II and III publish at 1/64, so
|
||
/// the preset was written for those and silently halved the body on
|
||
/// every Quake 1 map).
|
||
///
|
||
/// A halved body is not a smaller walker, it is a broken one: it cannot
|
||
/// climb the map's own stairs, its nav lattice is finer than its own
|
||
/// width, and the graph it plans on stops being a graph of where it can
|
||
/// go. So the declared step sets the SCALE and the whole body travels
|
||
/// with it — radius, height, eye, step, fall limit, walking speed, and
|
||
/// gravity (length/s², so once as well). Angles and durations do not
|
||
/// scale, and neither does the bob (already a fraction of eye height).
|
||
///
|
||
/// Declaring nothing (Build states no step height) keeps the preset.
|
||
pub fn with_declared(mut self, step_height: Option<f32>, eye_height: Option<f32>) -> Self {
|
||
let scale = step_height
|
||
.filter(|s| s.is_finite() && *s > 1.0e-4)
|
||
.map(|s| s / self.step_up.max(1.0e-4))
|
||
// A map whose step is 30× the preset's is not a scale, it is a
|
||
// bad sidecar: keep the body we know rather than invent one.
|
||
.filter(|k| (0.1..=10.0).contains(k) && (*k - 1.0).abs() > 0.02);
|
||
if let Some(k) = scale {
|
||
self.radius *= k;
|
||
self.height *= k;
|
||
self.step_up *= k;
|
||
self.eye_height *= k;
|
||
self.fall_limit *= k;
|
||
self.speed *= k;
|
||
self.gravity *= k;
|
||
self.probe_ahead *= k;
|
||
}
|
||
// The eye is declared outright, so it needs no scaling guess — and
|
||
// `PlayerNav` already reads the same anchor to turn the authored
|
||
// `player_start` eye into feet. The two must agree or the walker
|
||
// spawns at one height and looks from another.
|
||
if let Some(e) = eye_height.filter(|e| e.is_finite() && *e > 0.05) {
|
||
self.eye_height = e;
|
||
}
|
||
self
|
||
}
|
||
|
||
/// Radius of the circle a body traces when it walks and turns as hard
|
||
/// as it can — walking speed over turn rate.
|
||
pub fn turn_radius(&self) -> f32 {
|
||
self.speed / self.turn_rate.max(0.01)
|
||
}
|
||
}
|
||
|
||
/// Camera pose produced by one walker tick.
|
||
#[derive(Clone, Copy, Debug, PartialEq)]
|
||
pub struct CameraPose {
|
||
pub eye: Vec3f,
|
||
pub yaw: f32,
|
||
pub roll: f32,
|
||
}
|
||
|
||
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
|
||
pub enum WalkerEvent {
|
||
Stepped,
|
||
/// The way ahead was solid: the walker turned instead of clipping.
|
||
Blocked,
|
||
/// Nothing under the feet at all — a bad start. The host can respawn.
|
||
Stranded,
|
||
}
|
||
|
||
/// Directions tried when picking a new heading (whole turn, evenly spaced).
|
||
const PROBE_DIRS: usize = 12;
|
||
/// How far down a landing spot is looked for while falling.
|
||
const MAX_FALL_SEARCH: f32 = 40.0;
|
||
/// A drop smaller than this is standing on the floor, not falling.
|
||
const LAND_EPS: f32 = 0.02;
|
||
/// Doom's step rule is `step <= 24` map units — INCLUSIVE. At the classic
|
||
/// importer's 1/64 scale that is exactly 0.375, and a sector floor baked
|
||
/// through a float pipeline lands on 0.3750001 as often as on 0.375. A rim
|
||
/// that is exactly one step tall must never read as a wall, or a walker in
|
||
/// the nukage is walled into it.
|
||
const STEP_EPS: f32 = 0.02;
|
||
/// The ONE knee-probe height above a floor, shared by
|
||
/// [`LevelCollision::path_blocked`] (the walk probe — the graph's and the
|
||
/// body's "is that a wall?") and [`LevelCollision::clearance_ok`] (the
|
||
/// landing check — "can the body stand here?"). It sits safely above a
|
||
/// maximal legal step — float noise and the thin riser lip classic
|
||
/// importers leave on step edges included — so a climbable ledge is never
|
||
/// a wall, while anything meaningfully taller than a step still is. For
|
||
/// the Doom body (step 0.375, height 0.85) this is ≈ 0.446.
|
||
///
|
||
/// The two probes MUST use the same height: any gap between them is a
|
||
/// band of wall tops one probe offers and the other refuses forever.
|
||
pub(crate) fn knee_height(step_up: f32, height: f32) -> f32 {
|
||
step_up + (height - step_up) * 0.15
|
||
}
|
||
/// Standing in something that hurts — or in any pocket of floor the normal
|
||
/// step cannot leave — the way OUT is worth a bigger stretch than an
|
||
/// ordinary step: about 38 map units instead of 24. Being stuck in the goo
|
||
/// is worse than a walker who once climbs a step Doom would not have.
|
||
///
|
||
/// A RATIO of the body's own step, not a length: the same 38-vs-24 stretch
|
||
/// has to mean the same thing on a map published at half the metres per map
|
||
/// unit. (`0.375 · 0.6133` is Doom's 0.23 to the last float.)
|
||
const HAZARD_ESCAPE_RATIO: f32 = 0.23 / 0.375;
|
||
|
||
pub(crate) fn hazard_escape_step(step_up: f32) -> f32 {
|
||
step_up * HAZARD_ESCAPE_RATIO
|
||
}
|
||
/// Ticks between forward look-ahead probes (60 Hz → five per second).
|
||
const LOOKAHEAD_TICKS: u32 = 12;
|
||
/// Time constant of the eased turn (a corner takes about this long).
|
||
const TURN_EASE_SECS: f32 = 0.35;
|
||
/// How far the camera's yaw trails the body's heading.
|
||
const CAM_LAG_SECS: f32 = 0.12;
|
||
/// Acceleration/deceleration time.
|
||
const SPEED_EASE_SECS: f32 = 0.30;
|
||
/// Spring rate of the eye's catch-up after a step up (~0.25 s settle).
|
||
const VIEW_CATCHUP_RATE: f32 = 11.0;
|
||
|
||
pub fn yaw_forward(yaw: f32) -> Vec3f {
|
||
// The renderer's camera convention: yaw 0 looks down -Z.
|
||
vec3f(yaw.sin(), 0.0, -yaw.cos())
|
||
}
|
||
|
||
fn wrap_pi(a: f32) -> f32 {
|
||
let tau = std::f32::consts::TAU;
|
||
let mut a = a % tau;
|
||
if a > std::f32::consts::PI {
|
||
a -= tau;
|
||
} else if a < -std::f32::consts::PI {
|
||
a += tau;
|
||
}
|
||
a
|
||
}
|
||
|
||
/// Deterministic xorshift64* — a level tour must repeat exactly.
|
||
#[derive(Clone, Copy, Debug)]
|
||
struct Rng(u64);
|
||
|
||
impl Rng {
|
||
fn new(seed: u64) -> Rng {
|
||
// Mix first: a bare `seed | 1` maps 42 and 43 onto the same state.
|
||
Rng(seed.wrapping_mul(0x9e37_79b9_7f4a_7c15) ^ 0xd1b5_4a32_d192_ed03 | 1)
|
||
}
|
||
|
||
fn unit(&mut self) -> f32 {
|
||
let mut x = self.0;
|
||
x ^= x >> 12;
|
||
x ^= x << 25;
|
||
x ^= x >> 27;
|
||
self.0 = x;
|
||
((x.wrapping_mul(0x2545_f491_4f6c_dd1d)) >> 40) as f32 / 16_777_216.0
|
||
}
|
||
}
|
||
|
||
/// An autonomous first-person walker: stays on real floors, slides along
|
||
/// walls, turns away from voids and dead ends, and never ends a tick inside
|
||
/// geometry. Deterministic from its seed.
|
||
pub struct LevelWalker {
|
||
pos: Vec3f,
|
||
yaw: f32,
|
||
target_yaw: f32,
|
||
cfg: WalkerConfig,
|
||
rng: Rng,
|
||
since_pick: f32,
|
||
bob_phase: f32,
|
||
gait: f32,
|
||
turn_rate: f32,
|
||
stuck_ticks: u32,
|
||
/// Falling state: the originals drop you off a ledge instead of
|
||
/// snapping you to the floor below.
|
||
airborne: bool,
|
||
vel_y: f32,
|
||
/// How far the EYE is currently below its nominal height because the
|
||
/// body just stepped up. Doom keeps `viewheight` separate from the
|
||
/// mobj's z for exactly this: the body snaps onto the tread, the view
|
||
/// catches up over ~0.25 s, and stairs read as a smooth rise instead
|
||
/// of a series of jumps.
|
||
view_offset: f32,
|
||
view_vel: f32,
|
||
/// Eased walking speed, so starts, stops and corners do not snap.
|
||
speed_now: f32,
|
||
/// Camera yaw, lagging the body's heading slightly.
|
||
cam_yaw: f32,
|
||
probe_countdown: u32,
|
||
/// Distance to the point the route is steering at, when there is one.
|
||
/// The tick's speed limit reads it: a body may not walk faster than its
|
||
/// own turn can steer toward what it is aiming at.
|
||
aim_dist: Option<f32>,
|
||
/// Stand still this tick (waiting for a door to open).
|
||
hold: bool,
|
||
/// The cell under the feet is in a pocket the graph had to link with
|
||
/// the escape step: the body gets the same reach while it stands there.
|
||
escape_step: bool,
|
||
// ---- player_nav seam ------------------------------------------------
|
||
/// An outside planner owns the route: the built-in least-visited tour
|
||
/// stops choosing goals, and everything BELOW the heading — eased turn,
|
||
/// step, gravity, wall-slide, bob, door wait, teleport, relocate/flash —
|
||
/// keeps working exactly as it does for the built-in tour.
|
||
external: bool,
|
||
/// Route handed in before the first tick (the nav state does not exist
|
||
/// until a grid has been seen).
|
||
ext_route: Option<Vec<u32>>,
|
||
/// Heading to hold when the route is empty — a look-around pan.
|
||
ext_yaw: Option<f32>,
|
||
/// Door the planner wants opened, when it drives that itself.
|
||
ext_door: Option<u16>,
|
||
// player_nav: stand in place while the route is empty (a look-around
|
||
// pan turns the body without walking it into a wall).
|
||
ext_hold: bool,
|
||
// player_nav: walk-speed scale the planner sets for the slight
|
||
// slow-down at doors and glances. 1.0 = the config's full speed.
|
||
ext_speed: f32,
|
||
/// Exploration state, created the first time a nav grid is handed in.
|
||
nav: Option<NavState>,
|
||
}
|
||
|
||
/// Everything the tour remembers about where it has been. Kept in the
|
||
/// walker (not the grid) so two walkers can explore one shared map.
|
||
struct NavState {
|
||
/// Per-cell visit count, decayed slowly so a map is eventually re-toured.
|
||
visits: Vec<f32>,
|
||
/// Cells stood in and not yet forgotten. Unlike `visits` this does not
|
||
/// decay every tick, so "have I seen everything I can reach" is a
|
||
/// question with a stable answer; a cell whose visit count has faded
|
||
/// away is forgotten with it.
|
||
seen: Vec<bool>,
|
||
/// Reachable cells never stood in, as of the last plan.
|
||
unseen: usize,
|
||
dist: Vec<u32>,
|
||
parent: Vec<u32>,
|
||
/// Directed edges the walker proved it cannot actually make.
|
||
blocked: std::collections::HashSet<u64>,
|
||
/// Remaining waypoints, in order.
|
||
path: std::collections::VecDeque<u32>,
|
||
goal: Option<u32>,
|
||
at: Option<u32>,
|
||
reachable: usize,
|
||
distinct: usize,
|
||
replans: u64,
|
||
since_plan: f32,
|
||
since_decay: f32,
|
||
/// Seconds since the walker last made real ground toward its waypoint.
|
||
since_progress: f32,
|
||
/// Closest the body has come to the current waypoint. Displacement on
|
||
/// its own is not progress: a walker jiggling along a wall covers
|
||
/// metres a second and arrives nowhere.
|
||
best_gap: f32,
|
||
/// Ticks spent unable to move at all.
|
||
blocked_ticks: u32,
|
||
/// Which way it is currently trying to slide past an obstruction.
|
||
slide: f32,
|
||
/// Door the host should open, and how long we have waited for it.
|
||
want_door: Option<u16>,
|
||
door_wait: f32,
|
||
open_doors: Vec<u16>,
|
||
/// Goals handed out this session, newest last (bounded, for the trace).
|
||
goal_log: Vec<u32>,
|
||
/// Least-visited reachable cell as of the last plan.
|
||
frontier: f32,
|
||
/// The host owes the picture a cut-flash (Doom's teleport white-out).
|
||
flash: bool,
|
||
cuts: u64,
|
||
since_cut: f32,
|
||
/// Unbroken seconds spent standing in something that hurts.
|
||
hazard_secs: f32,
|
||
}
|
||
|
||
/// No progress for this long means the plan is a lie: drop the edge and
|
||
/// re-plan rather than grinding into a wall the probe said was open.
|
||
const NAV_STUCK_SECS: f32 = 3.0;
|
||
/// Ground covered under which "no progress" is declared.
|
||
const NAV_PROGRESS_EPS: f32 = 0.25;
|
||
/// A leg is re-planned at least this often, so a changed world (a door that
|
||
/// opened, an edge that was invalidated) is noticed.
|
||
const NAV_REPLAN_SECS: f32 = 12.0;
|
||
/// Visit counts fade by this factor every `NAV_DECAY_SECS`.
|
||
const NAV_DECAY: f32 = 0.6;
|
||
const NAV_DECAY_SECS: f32 = 30.0;
|
||
/// How long the tour waits at a closed door before walking on regardless.
|
||
const NAV_DOOR_WAIT: f32 = 1.5;
|
||
/// How far ahead the tour looks for a door to open.
|
||
const NAV_DOOR_LOOKAHEAD: usize = 3;
|
||
/// Newest goals kept for the trace log.
|
||
const NAV_GOAL_LOG: usize = 64;
|
||
/// A tour that has not moved for this long is not going to: cut elsewhere.
|
||
/// (A classic map still bakes its doors into the static mesh, so a route
|
||
/// can genuinely end at a wall that Doom would have opened.)
|
||
const NAV_CUT_AFTER_SECS: f32 = 10.0;
|
||
/// Minimum gap between cuts, so a bad corner cannot strobe the picture.
|
||
const NAV_CUT_COOLDOWN: f32 = 6.0;
|
||
/// Longest the tour may stand in a hazard before it is cut out of it.
|
||
const NAV_HAZARD_ESCAPE_SECS: f32 = 6.0;
|
||
|
||
impl NavState {
|
||
fn new(cells: usize) -> NavState {
|
||
NavState {
|
||
visits: vec![0.0; cells],
|
||
seen: vec![false; cells],
|
||
unseen: cells,
|
||
dist: Vec::new(),
|
||
parent: Vec::new(),
|
||
blocked: std::collections::HashSet::new(),
|
||
path: std::collections::VecDeque::new(),
|
||
goal: None,
|
||
at: None,
|
||
reachable: 0,
|
||
distinct: 0,
|
||
replans: 0,
|
||
since_plan: f32::MAX,
|
||
since_decay: 0.0,
|
||
since_progress: 0.0,
|
||
best_gap: f32::MAX,
|
||
blocked_ticks: 0,
|
||
slide: 0.0,
|
||
want_door: None,
|
||
door_wait: 0.0,
|
||
open_doors: Vec::new(),
|
||
goal_log: Vec::new(),
|
||
frontier: 0.0,
|
||
flash: false,
|
||
cuts: 0,
|
||
since_cut: NAV_CUT_COOLDOWN,
|
||
hazard_secs: 0.0,
|
||
}
|
||
}
|
||
}
|
||
|
||
impl LevelWalker {
|
||
pub fn new(start: Vec3f, yaw: f32, cfg: WalkerConfig, seed: u64) -> LevelWalker {
|
||
LevelWalker {
|
||
pos: start,
|
||
yaw,
|
||
target_yaw: yaw,
|
||
cfg,
|
||
rng: Rng::new(seed),
|
||
since_pick: 0.0,
|
||
bob_phase: 0.0,
|
||
gait: 0.0,
|
||
turn_rate: 0.0,
|
||
stuck_ticks: 0,
|
||
airborne: false,
|
||
vel_y: 0.0,
|
||
view_offset: 0.0,
|
||
view_vel: 0.0,
|
||
speed_now: 0.0,
|
||
cam_yaw: yaw,
|
||
probe_countdown: 0,
|
||
aim_dist: None,
|
||
hold: false,
|
||
escape_step: false,
|
||
external: false,
|
||
ext_route: None,
|
||
ext_yaw: None,
|
||
ext_door: None,
|
||
ext_hold: false,
|
||
ext_speed: 1.0,
|
||
nav: None,
|
||
}
|
||
}
|
||
|
||
/// The door the tour wants opened before it walks on, if any. The host
|
||
/// answers with `Renderer::set_model_state(level, "door_N", "open", …)`
|
||
/// and then calls [`Self::set_door_open`].
|
||
pub fn wanted_door(&self) -> Option<u16> {
|
||
self.nav.as_ref().and_then(|n| n.want_door)
|
||
}
|
||
|
||
/// Tell the walker a door part is now passable (or shut again).
|
||
pub fn set_door_open(&mut self, door: u16, open: bool) {
|
||
let Some(nav) = self.nav.as_mut() else { return };
|
||
let held = nav.open_doors.iter().position(|d| *d == door);
|
||
match (open, held) {
|
||
(true, None) => nav.open_doors.push(door),
|
||
(false, Some(i)) => {
|
||
nav.open_doors.remove(i);
|
||
}
|
||
_ => {}
|
||
}
|
||
if open && nav.want_door == Some(door) {
|
||
nav.want_door = None;
|
||
nav.door_wait = 0.0;
|
||
}
|
||
}
|
||
|
||
/// What the exploration is doing — the numbers `VJ_WALKER_TRACE` logs.
|
||
pub fn nav_stats(&self) -> NavStats {
|
||
match &self.nav {
|
||
Some(n) => NavStats {
|
||
cells: n.visits.len(),
|
||
reachable: n.reachable,
|
||
at: n.at,
|
||
goal: n.goal,
|
||
path_left: n.path.len(),
|
||
distinct: n.distinct,
|
||
unseen: n.unseen,
|
||
frontier: n.frontier,
|
||
replans: n.replans,
|
||
invalidated: n.blocked.len(),
|
||
cuts: n.cuts,
|
||
},
|
||
None => NavStats::default(),
|
||
}
|
||
}
|
||
|
||
/// The goals handed out so far, newest last (bounded).
|
||
pub fn nav_goal_log(&self) -> &[u32] {
|
||
self.nav.as_ref().map(|n| n.goal_log.as_slice()).unwrap_or(&[])
|
||
}
|
||
|
||
// ---- player_nav seam ----------------------------------------------------
|
||
// A planner that thinks in ROOMS lives outside this module and drives the
|
||
// body through these four calls. Note when routing: a DIAGONAL step out of
|
||
// a rim corner is refused by the landing clearance check (`StepRefusal::
|
||
// NoClearance`) even where the grid offers the edge — orthogonal exits out
|
||
// of a sunken area are the reliable ones, so prefer them.
|
||
|
||
/// Hand the route over. While this is on, the built-in least-visited
|
||
/// tour stops picking goals and cutting to other regions; locomotion,
|
||
/// waypoint following, the stuck watchdog, doors, teleporters and the
|
||
/// cut flash all keep working.
|
||
pub fn set_external_planner(&mut self, on: bool) {
|
||
self.external = on;
|
||
}
|
||
|
||
pub fn has_external_planner(&self) -> bool {
|
||
self.external
|
||
}
|
||
|
||
/// Replace the waypoint queue with `route` (nav-grid cell ids, in order).
|
||
/// Taken verbatim: the walker consumes waypoints as it reaches them and
|
||
/// stops steering when the queue empties.
|
||
pub fn set_route(&mut self, route: Vec<u32>) {
|
||
match self.nav.as_mut() {
|
||
Some(nav) => {
|
||
nav.path = route.into();
|
||
nav.goal = nav.path.back().copied();
|
||
nav.best_gap = f32::MAX;
|
||
nav.since_progress = 0.0;
|
||
nav.blocked_ticks = 0;
|
||
// A fresh route is a fresh plan, so the "try the other way
|
||
// round the obstruction" offset goes with the old one. The
|
||
// built-in tour cleared it on its own replan; an EXTERNAL
|
||
// planner never runs that branch, so once a watchdog set
|
||
// the offset the body steered 34° off every bearing it was
|
||
// given, for the rest of the level. That crab is a body
|
||
// that cannot converge on any waypoint — it circles one
|
||
// forever, which is the tour that looks demented.
|
||
nav.slide = 0.0;
|
||
}
|
||
None => self.ext_route = Some(route),
|
||
}
|
||
}
|
||
|
||
/// What is left of the route.
|
||
pub fn route(&self) -> Vec<u32> {
|
||
self.nav.as_ref().map(|n| n.path.iter().copied().collect()).unwrap_or_default()
|
||
}
|
||
|
||
/// Hold this heading while the route is empty (a look-around pan).
|
||
/// `None` lets the body keep the heading it has.
|
||
pub fn set_target_yaw(&mut self, yaw: Option<f32>) {
|
||
self.ext_yaw = yaw;
|
||
if let Some(y) = yaw {
|
||
if self.nav.as_ref().is_none_or(|n| n.path.is_empty()) {
|
||
self.target_yaw = wrap_pi(y);
|
||
}
|
||
}
|
||
}
|
||
|
||
// player_nav: stand still while the route is empty — the look-around
|
||
// pan turns the body in place instead of walking it forward. Has no
|
||
// effect while a route is being followed (a door wait still holds).
|
||
pub fn set_hold(&mut self, hold: bool) {
|
||
self.ext_hold = hold;
|
||
}
|
||
|
||
// player_nav: walk-speed scale (the slight slow-down through doorways
|
||
// and during glances); clamped to 0..1, 1 = the config's full speed.
|
||
pub fn set_speed_scale(&mut self, scale: f32) {
|
||
self.ext_speed = scale.clamp(0.0, 1.0);
|
||
}
|
||
|
||
/// Ask the host to open a door (what `wanted_door` will report until
|
||
/// `set_door_open` clears it). The built-in look-ahead does this by
|
||
/// itself for the built-in tour.
|
||
pub fn request_door(&mut self, door: Option<u16>) {
|
||
self.ext_door = door;
|
||
if let Some(nav) = self.nav.as_mut() {
|
||
nav.want_door = door.filter(|d| !nav.open_doors.contains(d));
|
||
}
|
||
}
|
||
|
||
/// Put the body somewhere else instantly — a teleporter, or a cut to
|
||
/// another wing of a map the tour cannot walk to. Physics and the eye
|
||
/// spring are reset so the arrival is a CUT, not a fall.
|
||
pub fn relocate(&mut self, feet: Vec3f, yaw: f32) {
|
||
self.pos = feet;
|
||
self.yaw = wrap_pi(yaw);
|
||
self.target_yaw = self.yaw;
|
||
self.cam_yaw = self.yaw;
|
||
self.vel_y = 0.0;
|
||
self.airborne = false;
|
||
self.view_offset = 0.0;
|
||
self.view_vel = 0.0;
|
||
self.speed_now = 0.0;
|
||
self.gait = 0.0;
|
||
self.stuck_ticks = 0;
|
||
self.hold = false;
|
||
if let Some(n) = self.nav.as_mut() {
|
||
n.path.clear();
|
||
n.goal = None;
|
||
n.at = None;
|
||
n.since_plan = f32::MAX;
|
||
n.since_progress = 0.0;
|
||
n.best_gap = f32::MAX;
|
||
n.blocked_ticks = 0;
|
||
n.slide = 0.0;
|
||
n.since_cut = 0.0;
|
||
n.cuts += 1;
|
||
n.flash = true;
|
||
}
|
||
}
|
||
|
||
/// True once per cut: the host paints Doom's white teleport flash.
|
||
pub fn take_flash(&mut self) -> bool {
|
||
match self.nav.as_mut() {
|
||
Some(n) => std::mem::replace(&mut n.flash, false),
|
||
None => false,
|
||
}
|
||
}
|
||
|
||
/// How many cuts (teleporters + exhausted-region jumps) so far.
|
||
pub fn cut_count(&self) -> u64 {
|
||
self.nav.as_ref().map(|n| n.cuts).unwrap_or(0)
|
||
}
|
||
|
||
/// True while the walker is falling (no floor under its feet).
|
||
pub fn is_airborne(&self) -> bool {
|
||
self.airborne
|
||
}
|
||
|
||
pub fn feet(&self) -> Vec3f {
|
||
self.pos
|
||
}
|
||
|
||
pub fn yaw(&self) -> f32 {
|
||
self.yaw
|
||
}
|
||
|
||
pub fn config(&self) -> &WalkerConfig {
|
||
&self.cfg
|
||
}
|
||
|
||
/// Camera for this tick: eye height above the feet plus the engine's
|
||
/// head bob (speed-proportional, zero standing still), and its roll.
|
||
pub fn camera(&self) -> CameraPose {
|
||
let cfg = &self.cfg;
|
||
// Doom's bob is momentum-SQUARED, so it fades away quickly as the
|
||
// walker slows and is zero at rest.
|
||
let effort = self.gait * self.gait;
|
||
let lift = cfg.bob.wave(self.bob_phase) * cfg.bob.amplitude() * cfg.eye_height * effort;
|
||
let sway = cfg.bob.sway()
|
||
* cfg.eye_height
|
||
* effort
|
||
* (self.bob_phase * std::f32::consts::PI).sin();
|
||
let right = vec3f(self.cam_yaw.cos(), 0.0, self.cam_yaw.sin());
|
||
CameraPose {
|
||
eye: vec3f(
|
||
self.pos.x + right.x * sway,
|
||
self.pos.y + cfg.eye_height + lift - self.view_offset,
|
||
self.pos.z + right.z * sway,
|
||
),
|
||
yaw: self.cam_yaw,
|
||
roll: (self.turn_rate / cfg.turn_rate.max(0.01)).clamp(-1.0, 1.0) * cfg.bob.roll(),
|
||
}
|
||
}
|
||
|
||
/// One fixed step against the level's triangles, wandering by local
|
||
/// probes alone. Use [`Self::tick_in`] to tour a whole map.
|
||
pub fn tick(&mut self, dt: f32, level: &LevelCollision) -> WalkerEvent {
|
||
self.tick_in(dt, level, None)
|
||
}
|
||
|
||
/// One fixed step. With a [`NavGrid`] the heading comes from a planned
|
||
/// route through the map's least-visited ground; without one it falls
|
||
/// back to scoring the twelve directions from where it stands.
|
||
pub fn tick_in(
|
||
&mut self,
|
||
dt: f32,
|
||
level: &LevelCollision,
|
||
nav: Option<&NavGrid>,
|
||
) -> WalkerEvent {
|
||
let dt = dt.clamp(0.0, 0.1);
|
||
let nav = nav.filter(|g| !g.is_empty());
|
||
if let Some(grid) = nav {
|
||
self.nav_steer(dt, grid);
|
||
}
|
||
self.since_pick += dt;
|
||
self.probe_countdown = self.probe_countdown.saturating_sub(1);
|
||
// Everything that raises the BODY within this tick is instant (a
|
||
// step onto a tread, or the ground snap when a slope rises under
|
||
// the feet). The eye must absorb all of it, so the reference is
|
||
// taken here, before either can happen.
|
||
let body_before = self.pos.y;
|
||
// Eased turn: the rate ramps down as the heading is reached, so a
|
||
// corner is a curve rather than a snap. Still rate-limited by the
|
||
// engine's turn speed (~90°/s).
|
||
let delta = wrap_pi(self.target_yaw - self.yaw);
|
||
let rate = (delta / TURN_EASE_SECS).clamp(-self.cfg.turn_rate, self.cfg.turn_rate);
|
||
let turn = (rate * dt).clamp(-delta.abs(), delta.abs());
|
||
self.yaw = wrap_pi(self.yaw + turn);
|
||
self.turn_rate = if dt > 0.0 { turn / dt } else { 0.0 };
|
||
// The camera trails the body's heading a little.
|
||
let cam_delta = wrap_pi(self.yaw - self.cam_yaw);
|
||
self.cam_yaw = wrap_pi(self.cam_yaw + cam_delta * (dt / CAM_LAG_SECS).min(1.0));
|
||
let facing_target = delta.abs() < 0.6;
|
||
|
||
// Where the ground is right now. A walker with nothing at all
|
||
// beneath it does not move: better a stopped tour than a camera
|
||
// drifting through the void.
|
||
let ground = self.ground_below(self.pos, level);
|
||
let Some(ground) = ground else {
|
||
self.stuck_ticks += 1;
|
||
return WalkerEvent::Stranded;
|
||
};
|
||
|
||
// Falling: the originals do not snap you down a ledge, they drop
|
||
// you (Doom GRAVITY, Quake sv_gravity). Horizontal motion carries
|
||
// on mid-air, and the landing dips the view like `deltaviewheight`.
|
||
if self.airborne || self.pos.y - ground.y > LAND_EPS {
|
||
self.airborne = true;
|
||
self.vel_y -= self.cfg.gravity * dt;
|
||
self.pos.y += self.vel_y * dt;
|
||
if self.pos.y <= ground.y {
|
||
self.pos.y = ground.y;
|
||
// Doom's landing sets `deltaviewheight` — a VELOCITY, not
|
||
// a height: the view sinks over the next few tics and
|
||
// springs back. Adding the dip to the offset directly is
|
||
// what makes a landing snap.
|
||
self.view_vel += (-self.vel_y * 0.35).min(1.6);
|
||
self.vel_y = 0.0;
|
||
self.airborne = false;
|
||
}
|
||
} else {
|
||
self.pos.y = ground.y;
|
||
self.vel_y = 0.0;
|
||
}
|
||
|
||
// Accelerate/decelerate over ~0.3 s instead of stepping at full
|
||
// speed from a standstill.
|
||
// player_nav: `ext_speed` is 1.0 unless an external planner asks
|
||
// for the slight door/glance slow-down, so the built-in tours are
|
||
// unchanged by the multiply.
|
||
let want_speed = match (self.hold, facing_target) {
|
||
(true, _) => 0.0,
|
||
(false, true) => self.cfg.speed * self.ext_speed,
|
||
(false, false) => self.cfg.speed * 0.25 * self.ext_speed,
|
||
};
|
||
// A body walking `v` and turning at `w` traces a circle of radius
|
||
// `v / w`. If what it is steering at lies INSIDE that circle it can
|
||
// never turn toward it — it orbits, at full turn rate, until
|
||
// something else rescues it. So the turn sets the speed: never walk
|
||
// faster than `turn_rate · distance to the aim point`. That is the
|
||
// slow-into-the-corner a person does, and it is a HARD requirement,
|
||
// not a comfort: without it the tour circles a waypoint forever
|
||
// wherever the route bends tighter than the body can turn. Doom's
|
||
// 1 m circle sits well inside its string-pulled waypoints and never
|
||
// meets the cap; a map published at twice the metres per map unit
|
||
// walks twice as fast and meets it at every corner.
|
||
let want_speed = match self.aim_dist {
|
||
Some(d) => want_speed.min(self.cfg.turn_rate * d),
|
||
None => want_speed,
|
||
};
|
||
self.speed_now += (want_speed - self.speed_now) * (dt / SPEED_EASE_SECS).min(1.0);
|
||
let step = self.speed_now * dt;
|
||
let dir = yaw_forward(self.yaw);
|
||
let mut moved = false;
|
||
// The body walks THROUGH its turns, at the quarter speed decided
|
||
// just above. It used to stand still for every heading change wider
|
||
// than `facing_target` — and that dead stop was the whole jitter:
|
||
// an eight-neighbour route turns 45° at a corner, 45° is wider than
|
||
// the gate, so the walker stopped, spun, took a step, stopped again.
|
||
// Worse, it was self-feeding: standing still is no progress, no
|
||
// progress trips the planner's watchdog, a dropped leg makes the
|
||
// next one CELL-BY-CELL, and a cell-by-cell leg turns at every
|
||
// single cell. Stepping while turning is safe on its own — every
|
||
// candidate step still goes through `try_move`, which refuses to
|
||
// enter geometry — and a person walks the curve rather than pausing
|
||
// to aim.
|
||
for delta in [
|
||
vec3f(dir.x * step, 0.0, dir.z * step),
|
||
vec3f(dir.x * step, 0.0, 0.0),
|
||
vec3f(0.0, 0.0, dir.z * step),
|
||
] {
|
||
if delta.x == 0.0 && delta.z == 0.0 {
|
||
continue;
|
||
}
|
||
if let Some(landed) = self.try_move(delta, level) {
|
||
self.pos.x = landed.x;
|
||
self.pos.z = landed.z;
|
||
// Step UP (or level) instantly, as the originals do.
|
||
// A lower floor is NOT snapped to: the walker is now
|
||
// unsupported and next tick's gravity drops it.
|
||
if !self.airborne && landed.y >= self.pos.y - LAND_EPS {
|
||
self.pos.y = landed.y;
|
||
}
|
||
moved = true;
|
||
break;
|
||
}
|
||
}
|
||
// A body step UP is instant and collision-correct; the EYE is not
|
||
// moved with it — `view_offset` holds it back and the spring below
|
||
// eases it up (Doom's `deltaviewheight`).
|
||
let climbed = self.pos.y - body_before;
|
||
if climbed > LAND_EPS {
|
||
self.view_offset = (self.view_offset + climbed).min(self.cfg.eye_height * 0.8);
|
||
}
|
||
// Critically damped catch-up, ~0.25 s.
|
||
let w = VIEW_CATCHUP_RATE;
|
||
self.view_vel += (-w * w * self.view_offset - 2.0 * w * self.view_vel) * dt;
|
||
self.view_offset += self.view_vel * dt;
|
||
|
||
let target_gait = if moved && !self.airborne {
|
||
(self.speed_now / self.cfg.speed.max(0.01)).clamp(0.0, 1.0)
|
||
} else {
|
||
0.0
|
||
};
|
||
self.gait += (target_gait - self.gait) * (dt * 4.0).min(1.0);
|
||
self.bob_phase = (self.bob_phase + self.cfg.bob.frequency() * self.gait * dt).fract();
|
||
if moved {
|
||
self.stuck_ticks = 0;
|
||
if let Some(n) = self.nav.as_mut() {
|
||
n.blocked_ticks = 0;
|
||
} else {
|
||
// Turn EARLY: a heading with less than two body widths of
|
||
// floor left is already a dead end as far as the camera is
|
||
// concerned.
|
||
if self.probe_countdown == 0 {
|
||
self.probe_countdown = LOOKAHEAD_TICKS;
|
||
if level.free_run(self.pos, self.yaw, &self.cfg) < self.cfg.radius * 2.0 {
|
||
self.pick_heading(level);
|
||
}
|
||
}
|
||
if self.since_pick >= self.cfg.repick_secs {
|
||
self.pick_heading(level);
|
||
}
|
||
}
|
||
return WalkerEvent::Stepped;
|
||
}
|
||
if facing_target && !self.airborne {
|
||
self.stuck_ticks += 1;
|
||
// With a route, a refused step is evidence about ONE edge — the
|
||
// planner deals with it (see `nav_steer`). Re-scoring headings
|
||
// here would fight the plan.
|
||
match self.nav.as_mut() {
|
||
Some(n) => n.blocked_ticks += 1,
|
||
None => self.pick_heading(level),
|
||
}
|
||
if self.stuck_ticks > 240 {
|
||
return WalkerEvent::Stranded;
|
||
}
|
||
return WalkerEvent::Blocked;
|
||
}
|
||
WalkerEvent::Stepped
|
||
}
|
||
|
||
/// Route the tour: keep track of where it is, plan a new leg when the
|
||
/// old one is done (or has been proven wrong), and aim the heading at
|
||
/// the next waypoint. Everything else — turning, stepping, gravity,
|
||
/// wall-slide — is the ordinary tick.
|
||
fn nav_steer(&mut self, dt: f32, grid: &NavGrid) {
|
||
if self.nav.as_ref().is_none_or(|n| n.visits.len() != grid.len()) {
|
||
self.nav = Some(NavState::new(grid.len()));
|
||
// A route handed in before the first grid was seen.
|
||
if let Some(route) = self.ext_route.take() {
|
||
self.set_route(route);
|
||
}
|
||
}
|
||
let external = self.external;
|
||
let feet = self.pos;
|
||
let cell_size = grid.cell_size();
|
||
// Drawn every tick, not only when a plan happens: the borrow of
|
||
// `self.nav` below covers the whole routine, and a tie-break that
|
||
// advances on a fixed schedule is still deterministic.
|
||
let jitter = self.rng.unit();
|
||
let nav = self.nav.as_mut().expect("just created");
|
||
nav.since_plan += dt;
|
||
nav.since_decay += dt;
|
||
nav.since_progress += dt;
|
||
nav.since_cut += dt;
|
||
// Visit counts fade, so a map toured for ten minutes is toured
|
||
// again rather than settling into one loop through the leftovers.
|
||
if nav.since_decay >= NAV_DECAY_SECS {
|
||
nav.since_decay = 0.0;
|
||
for v in nav.visits.iter_mut() {
|
||
*v *= NAV_DECAY;
|
||
}
|
||
}
|
||
// Where are we? A body between storeys (mid-fall) may be nowhere.
|
||
let here = grid.cell_at(feet);
|
||
let in_hazard = here
|
||
.and_then(|c| grid.cell(c))
|
||
.is_some_and(|c| c.kind == SurfaceKind::Hazard);
|
||
self.escape_step = here.and_then(|c| grid.cell(c)).is_some_and(|c| c.escape);
|
||
nav.hazard_secs = if in_hazard { nav.hazard_secs + dt } else { 0.0 };
|
||
if let Some(c) = here {
|
||
if nav.at != Some(c) {
|
||
nav.at = Some(c);
|
||
let v = &mut nav.visits[c as usize];
|
||
if *v <= 0.0 {
|
||
nav.distinct += 1;
|
||
}
|
||
*v += 1.0;
|
||
nav.seen[c as usize] = true;
|
||
// Reaching a new cell IS progress, however slowly.
|
||
nav.since_progress = 0.0;
|
||
nav.best_gap = f32::MAX;
|
||
nav.blocked_ticks = 0;
|
||
}
|
||
}
|
||
// Consume waypoints already walked through. Matching the CELL alone
|
||
// is not enough: a body that clips the corner of a waypoint without
|
||
// landing in it leaves that waypoint in the queue, and the next aim
|
||
// turns it round to go back for it — the ping-pong the plan exists
|
||
// to prevent.
|
||
while let Some(w) = nav.path.front().copied() {
|
||
let reached = Some(w) == here
|
||
|| grid.cell(w).is_some_and(|c| {
|
||
let (dx, dz) = (c.pos.x - feet.x, c.pos.z - feet.z);
|
||
(dx * dx + dz * dz).sqrt() < cell_size * 0.5
|
||
&& (c.pos.y - feet.y).abs() < self.cfg.step_up + 0.1
|
||
});
|
||
if !reached {
|
||
break;
|
||
}
|
||
// A waypoint walked PAST counts as walked THROUGH: without this
|
||
// the cell stays "unseen", is picked as a goal again, is passed
|
||
// again, and the tour circles one spot forever.
|
||
let w = w as usize;
|
||
if !nav.seen[w] {
|
||
nav.seen[w] = true;
|
||
if nav.visits[w] <= 0.0 {
|
||
nav.distinct += 1;
|
||
}
|
||
nav.visits[w] += 1.0;
|
||
}
|
||
nav.path.pop_front();
|
||
nav.best_gap = f32::MAX;
|
||
}
|
||
// Progress is measured against the WAYPOINT, not against the last
|
||
// position: a body sliding back and forth along a wall covers metres
|
||
// a second and gets no nearer to anything.
|
||
match nav.path.front().and_then(|w| grid.cell(*w)) {
|
||
Some(c) => {
|
||
let (dx, dz) = (c.pos.x - feet.x, c.pos.z - feet.z);
|
||
let gap = (dx * dx + dz * dz).sqrt();
|
||
if gap + NAV_PROGRESS_EPS < nav.best_gap {
|
||
nav.best_gap = gap;
|
||
nav.since_progress = 0.0;
|
||
}
|
||
}
|
||
None => nav.since_progress = 0.0,
|
||
}
|
||
let give_up = nav.since_progress >= NAV_STUCK_SECS || nav.blocked_ticks > 40;
|
||
if give_up {
|
||
// The edge we were trying to take does not exist in practice.
|
||
if let (Some(a), Some(b)) = (nav.at, nav.path.front().copied()) {
|
||
nav.blocked.insert(edge_key(a, b));
|
||
}
|
||
nav.path.clear();
|
||
nav.goal = None;
|
||
nav.since_progress = 0.0;
|
||
nav.blocked_ticks = 0;
|
||
// Slide the other way next time this happens.
|
||
nav.slide = if nav.slide >= 0.0 { -0.6 } else { 0.6 };
|
||
}
|
||
let need_plan = !external && (nav.path.is_empty() || nav.since_plan >= NAV_REPLAN_SECS);
|
||
if need_plan {
|
||
nav.since_plan = 0.0;
|
||
let start = here.or(nav.at);
|
||
if let Some(start) = start {
|
||
let (mut dist, mut parent) = (
|
||
std::mem::take(&mut nav.dist),
|
||
std::mem::take(&mut nav.parent),
|
||
);
|
||
let plan = grid.explore(
|
||
start,
|
||
&nav.visits,
|
||
&nav.blocked,
|
||
jitter,
|
||
&mut dist,
|
||
&mut parent,
|
||
);
|
||
nav.dist = dist;
|
||
nav.parent = parent;
|
||
match plan {
|
||
Some(plan) => {
|
||
nav.reachable = plan.reachable;
|
||
nav.frontier = plan.frontier;
|
||
// How much of what it can reach it has not seen —
|
||
// the honest "is there anything left here" test,
|
||
// and one the visit decay cannot blur.
|
||
nav.unseen = (0..nav.seen.len())
|
||
.filter(|i| {
|
||
nav.dist.get(*i).copied().unwrap_or(NAV_UNREACHED) != NAV_UNREACHED
|
||
&& !nav.seen[*i]
|
||
&& grid.cell(*i as u32).is_some_and(|c| {
|
||
c.kind != SurfaceKind::Hazard
|
||
})
|
||
})
|
||
.count();
|
||
nav.goal = Some(plan.goal);
|
||
nav.path = plan.path.into();
|
||
nav.replans += 1;
|
||
nav.goal_log.push(plan.goal);
|
||
if nav.goal_log.len() > NAV_GOAL_LOG {
|
||
nav.goal_log.remove(0);
|
||
}
|
||
nav.slide = 0.0;
|
||
}
|
||
None => {
|
||
// Nothing reachable at all: forget the invalidated
|
||
// edges rather than paralysing the tour forever.
|
||
nav.blocked.clear();
|
||
nav.goal = None;
|
||
}
|
||
}
|
||
}
|
||
}
|
||
// Stepping onto a teleport pad IS the edge: cut to the far side the
|
||
// way Doom does, white flash and all.
|
||
let pad = here.and_then(|c| grid.cell(c)).and_then(|c| c.teleport);
|
||
// Nothing new within reach (or a route that has gone nowhere for ten
|
||
// seconds — a classic map still bakes its doors into the walls):
|
||
// cut to another wing rather than pacing a room it has memorised.
|
||
// Paddling in the nukage for this long means the way out is not
|
||
// one the graph can see: cut, rather than stand in it dying.
|
||
// With an outside planner, WHERE to go next is not this module's
|
||
// business — only a hazard it is drowning in still forces a cut.
|
||
let exhausted = match external {
|
||
true => nav.hazard_secs >= NAV_HAZARD_ESCAPE_SECS,
|
||
false => {
|
||
nav.unseen == 0
|
||
|| nav.since_progress >= NAV_CUT_AFTER_SECS
|
||
|| nav.hazard_secs >= NAV_HAZARD_ESCAPE_SECS
|
||
}
|
||
};
|
||
let elsewhere = (exhausted && nav.since_cut >= NAV_CUT_COOLDOWN)
|
||
.then(|| nav.at.and_then(|a| grid.next_region(a, &nav.visits)))
|
||
.flatten();
|
||
if let Some(dst) = pad.and_then(|t| grid.teleport_target(t)) {
|
||
self.relocate(dst.0, dst.1);
|
||
return;
|
||
}
|
||
if let Some(cell) = elsewhere.and_then(|c| grid.cell(c)) {
|
||
// Forget the region being left behind, so coming back to it in
|
||
// ten minutes is a tour again and not an instant bounce out.
|
||
for i in 0..nav.seen.len() {
|
||
if nav.dist.get(i).copied().unwrap_or(NAV_UNREACHED) != NAV_UNREACHED {
|
||
nav.seen[i] = false;
|
||
}
|
||
}
|
||
let (pos, yaw) = (cell.pos, self.yaw);
|
||
self.relocate(pos, yaw);
|
||
return;
|
||
}
|
||
// A door on the near stretch of the route is opened before we get
|
||
// there; the tour pauses briefly if it is still shut.
|
||
let ext_door = self.ext_door;
|
||
let nav = self.nav.as_mut().expect("still there");
|
||
nav.want_door = match external {
|
||
// The planner says which door; the built-in tour finds it itself.
|
||
true => ext_door.filter(|d| !nav.open_doors.contains(d)),
|
||
false => nav
|
||
.path
|
||
.iter()
|
||
.take(NAV_DOOR_LOOKAHEAD)
|
||
.filter_map(|w| grid.cell(*w).and_then(|c| c.door))
|
||
.find(|d| !nav.open_doors.contains(d)),
|
||
};
|
||
let waiting = match nav.want_door {
|
||
Some(_) => {
|
||
nav.door_wait += dt;
|
||
nav.door_wait < NAV_DOOR_WAIT
|
||
}
|
||
None => {
|
||
nav.door_wait = 0.0;
|
||
false
|
||
}
|
||
};
|
||
// Aim at the next waypoint. Waypoints are cell centres, so the
|
||
// heading is simply the bearing to the next one, plus the slide
|
||
// offset that walks the body along a wall it snagged on.
|
||
//
|
||
// The aim NEVER jumps a waypoint the queue still holds: a route is
|
||
// a proven chain of cells and the straight line to a later one may
|
||
// go through a wall. What keeps a close waypoint reachable is the
|
||
// speed cap below, not skipping it.
|
||
let mut aim = None;
|
||
for w in nav.path.iter() {
|
||
let Some(c) = grid.cell(*w) else { continue };
|
||
let (dx, dz) = (c.pos.x - feet.x, c.pos.z - feet.z);
|
||
if (dx * dx + dz * dz).sqrt() < cell_size * 0.35 {
|
||
continue; // standing on it already
|
||
}
|
||
aim = Some((dx, dz));
|
||
break;
|
||
}
|
||
// How far the thing being steered at is — the tick's speed limit.
|
||
// A body walking `v` while turning at `w` traces a circle of radius
|
||
// `v/w`; steering at anything INSIDE that circle is a circle round
|
||
// it, never a path to it, and the body orbits at full turn rate
|
||
// until something else rescues it. That orbit is the tour a viewer
|
||
// calls demented, and it is what a corner does to a walker whose
|
||
// route bends tighter than its own turning circle.
|
||
self.aim_dist = aim.map(|(dx, dz)| (dx * dx + dz * dz).sqrt());
|
||
let slide = nav.slide;
|
||
match aim {
|
||
// yaw 0 looks down -Z (see `yaw_forward`).
|
||
Some((dx, dz)) => self.target_yaw = wrap_pi(dx.atan2(-dz) + slide),
|
||
// Route done: hold whatever heading the planner asked for.
|
||
None => {
|
||
if let Some(y) = self.ext_yaw {
|
||
self.target_yaw = wrap_pi(y);
|
||
}
|
||
}
|
||
}
|
||
// A closed door stops the tour where it stands rather than letting
|
||
// it grind into the leaf. player_nav: an external planner may also
|
||
// hold the body for its look-around pan (route empty, turning only).
|
||
self.hold = waiting
|
||
|| (external && self.ext_hold && self.nav.as_ref().is_none_or(|n| n.path.is_empty()));
|
||
}
|
||
|
||
/// The floor under `p`: a step up is allowed, and the search reaches
|
||
/// far enough down to find the landing spot of a fall.
|
||
fn ground_below(&self, p: Vec3f, level: &LevelCollision) -> Option<FloorHit> {
|
||
self.ground_below_up(p, level, 0.0)
|
||
}
|
||
|
||
/// The probe has to START above the tallest tread it may find, or a
|
||
/// ledge exactly `step_up` up is missed by the ray that was supposed to
|
||
/// find it — which is how a rim of exactly 24 map units became a wall.
|
||
fn ground_below_up(&self, p: Vec3f, level: &LevelCollision, extra: f32) -> Option<FloorHit> {
|
||
let up = self.cfg.step_up + STEP_EPS + extra;
|
||
let from = vec3f(p.x, p.y + up, p.z);
|
||
let reach = up + self.cfg.fall_limit.max(MAX_FALL_SEARCH);
|
||
let hit = level.floor_below(from, reach)?;
|
||
(hit.flatness >= 0.5).then_some(hit)
|
||
}
|
||
|
||
/// Why one candidate step was refused — the diagnostic behind
|
||
/// "it will not climb that ledge".
|
||
pub fn step_refusal(&self, level: &LevelCollision, delta: Vec3f) -> StepRefusal {
|
||
let want = vec3f(self.pos.x + delta.x, self.pos.y, self.pos.z + delta.z);
|
||
let standing_in = self
|
||
.ground_below(self.pos, level)
|
||
.map(|f| f.kind)
|
||
.unwrap_or_default();
|
||
let escape = match standing_in == SurfaceKind::Hazard || self.escape_step {
|
||
true => hazard_escape_step(self.cfg.step_up),
|
||
false => 0.0,
|
||
};
|
||
let step = (self.cfg.step_up + escape).min(self.cfg.height * 0.8);
|
||
if level.path_blocked(self.pos, want, self.cfg.radius, step, self.cfg.height) {
|
||
return StepRefusal::Walled;
|
||
}
|
||
let Some(floor) = self.ground_below_up(want, level, escape) else {
|
||
return StepRefusal::NoFloor;
|
||
};
|
||
let rise = floor.y - self.pos.y;
|
||
let reach = self.cfg.step_up + STEP_EPS + escape;
|
||
if rise > reach {
|
||
return StepRefusal::TooTall { rise, reach };
|
||
}
|
||
if !self.airborne && -rise > self.cfg.fall_limit {
|
||
return StepRefusal::Pit { drop: -rise };
|
||
}
|
||
// The landing check gets the SAME step allowance as the walk probe
|
||
// (escape stretch included): the two must never disagree about a
|
||
// ledge, or the body is offered a step it refuses forever.
|
||
let stand = vec3f(want.x, floor.y.max(self.pos.y), want.z);
|
||
if !level.clearance_ok(stand, self.cfg.radius, step, self.cfg.height) {
|
||
return StepRefusal::NoClearance { rise };
|
||
}
|
||
StepRefusal::Ok { rise }
|
||
}
|
||
|
||
/// Apply a horizontal step if the body fits, the walls stay a body
|
||
/// radius away, and there is floor within the step/drop budget.
|
||
///
|
||
/// A step UP happens instantly, the way the originals do it. A step
|
||
/// DOWN does NOT snap: the walker simply becomes unsupported and
|
||
/// gravity drops it, so ledges are fallen off rather than teleported
|
||
/// down. A drop deeper than `fall_limit` is refused outright — that is
|
||
/// a pit, and the tour turns away from it.
|
||
fn try_move(&self, delta: Vec3f, level: &LevelCollision) -> Option<Vec3f> {
|
||
let want = vec3f(self.pos.x + delta.x, self.pos.y, self.pos.z + delta.z);
|
||
// Standing in the ooze — or anywhere the graph had to link with the
|
||
// generous escape step — the rim is always climbable.
|
||
let standing_in = self
|
||
.ground_below(self.pos, level)
|
||
.map(|f| f.kind)
|
||
.unwrap_or_default();
|
||
let escape = match standing_in == SurfaceKind::Hazard || self.escape_step {
|
||
true => hazard_escape_step(self.cfg.step_up),
|
||
false => 0.0,
|
||
};
|
||
// The knee ray must start above the tallest step this body may take,
|
||
// or climbing out of a pool is refused by the riser of the very step
|
||
// being asked about.
|
||
let step = (self.cfg.step_up + escape).min(self.cfg.height * 0.8);
|
||
if level.path_blocked(self.pos, want, self.cfg.radius, step, self.cfg.height) {
|
||
return None;
|
||
}
|
||
let floor = self.ground_below_up(want, level, escape)?;
|
||
let reach = self.cfg.step_up + STEP_EPS + escape;
|
||
if floor.y - self.pos.y > reach {
|
||
return None; // too tall to step onto
|
||
}
|
||
if !self.airborne && self.pos.y - floor.y > self.cfg.fall_limit {
|
||
return None; // a pit, not a step
|
||
}
|
||
// Keep the camera's near plane clear of the walls: the body never
|
||
// ends a step with geometry inside its radius. Same step allowance
|
||
// as the walk probe above — the two must never disagree.
|
||
let stand = vec3f(want.x, floor.y.max(self.pos.y), want.z);
|
||
if !level.clearance_ok(stand, self.cfg.radius, step, self.cfg.height) {
|
||
return None;
|
||
}
|
||
Some(vec3f(want.x, floor.y, want.z))
|
||
}
|
||
|
||
/// Turn toward the most open direction; ties and a small preference
|
||
/// jitter come from the seed, so the wander repeats exactly.
|
||
fn pick_heading(&mut self, level: &LevelCollision) {
|
||
self.since_pick = 0.0;
|
||
let mut best = (f32::MIN, self.yaw);
|
||
for i in 0..PROBE_DIRS {
|
||
let yaw = wrap_pi(self.yaw + std::f32::consts::TAU * i as f32 / PROBE_DIRS as f32);
|
||
let open = level.free_run(self.pos, yaw, &self.cfg);
|
||
let ahead = 1.0 - wrap_pi(yaw - self.yaw).abs() / std::f32::consts::PI;
|
||
// Nukage, lava and slime are floors the tour would rather not
|
||
// stand in: a hazardous run scores far below a clean one, so
|
||
// the bridge wins whenever there is a bridge.
|
||
let hazard = if level.has_kinds() {
|
||
level.hazard_run(self.pos, yaw, &self.cfg)
|
||
} else {
|
||
0.0
|
||
};
|
||
// The forward bias has to outweigh ordinary differences in
|
||
// open distance, or the walker ping-pongs along a corridor:
|
||
// the way it just came is always the longest free run.
|
||
let score = open - hazard * 4.0 + ahead * 2.5 + self.rng.unit() * 0.5;
|
||
if score > best.0 {
|
||
best = (score, yaw);
|
||
}
|
||
}
|
||
self.target_yaw = best.1;
|
||
}
|
||
}
|
||
|
||
#[cfg(test)]
|
||
mod tests {
|
||
use super::*;
|
||
|
||
/// Append a quad (two triangles) to a triangle soup.
|
||
fn quad(pos: &mut Vec<Vec3f>, idx: &mut Vec<u32>, a: Vec3f, b: Vec3f, c: Vec3f, d: Vec3f) {
|
||
let n = pos.len() as u32;
|
||
pos.extend_from_slice(&[a, b, c, d]);
|
||
idx.extend_from_slice(&[n, n + 1, n + 2, n, n + 2, n + 3]);
|
||
}
|
||
|
||
/// A horizontal slab top at `y` spanning the given x/z range.
|
||
fn floor(pos: &mut Vec<Vec3f>, idx: &mut Vec<u32>, x0: f32, x1: f32, z0: f32, z1: f32, y: f32) {
|
||
quad(
|
||
pos,
|
||
idx,
|
||
vec3f(x0, y, z0),
|
||
vec3f(x1, y, z0),
|
||
vec3f(x1, y, z1),
|
||
vec3f(x0, y, z1),
|
||
);
|
||
}
|
||
|
||
/// A vertical wall spanning x0..x1 at `z`, from y0 to y1.
|
||
fn wall_z(pos: &mut Vec<Vec3f>, idx: &mut Vec<u32>, x0: f32, x1: f32, z: f32, y0: f32, y1: f32) {
|
||
quad(
|
||
pos,
|
||
idx,
|
||
vec3f(x0, y0, z),
|
||
vec3f(x1, y0, z),
|
||
vec3f(x1, y1, z),
|
||
vec3f(x0, y1, z),
|
||
);
|
||
}
|
||
|
||
/// A vertical wall spanning z0..z1 at `x`, from y0 to y1.
|
||
fn wall_x(pos: &mut Vec<Vec3f>, idx: &mut Vec<u32>, z0: f32, z1: f32, x: f32, y0: f32, y1: f32) {
|
||
quad(
|
||
pos,
|
||
idx,
|
||
vec3f(x, y0, z0),
|
||
vec3f(x, y0, z1),
|
||
vec3f(x, y1, z1),
|
||
vec3f(x, y1, z0),
|
||
);
|
||
}
|
||
|
||
/// A roofed corridor along -Z: floor at 0, ceiling at 2, side walls,
|
||
/// and an end wall at z = -10. Open end at z = +1.
|
||
fn corridor() -> LevelCollision {
|
||
let (mut p, mut i) = (Vec::new(), Vec::new());
|
||
floor(&mut p, &mut i, -1.0, 1.0, -10.0, 1.0, 0.0);
|
||
floor(&mut p, &mut i, -1.0, 1.0, -10.0, 1.0, 2.0); // ceiling
|
||
wall_x(&mut p, &mut i, -10.0, 1.0, -1.0, 0.0, 2.0);
|
||
wall_x(&mut p, &mut i, -10.0, 1.0, 1.0, 0.0, 2.0);
|
||
wall_z(&mut p, &mut i, -1.0, 1.0, -10.0, 0.0, 2.0);
|
||
LevelCollision::from_positions(p, i)
|
||
}
|
||
|
||
fn cfg() -> WalkerConfig {
|
||
WalkerConfig {
|
||
radius: 0.2,
|
||
height: 0.8,
|
||
eye_height: 0.6,
|
||
speed: 1.5,
|
||
turn_rate: 6.0,
|
||
step_up: 0.3,
|
||
probe_ahead: 8.0,
|
||
..WalkerConfig::default()
|
||
}
|
||
}
|
||
|
||
#[test]
|
||
fn floor_probe_finds_the_real_triangle_under_the_feet() {
|
||
let level = corridor();
|
||
assert_eq!(level.triangles(), 10);
|
||
let hit = level.floor_below(vec3f(0.0, 1.0, 0.0), 4.0).unwrap();
|
||
assert!((hit.y - 0.0).abs() < 1e-4, "stands on the floor slab: {hit:?}");
|
||
assert!(hit.flatness > 0.99, "a floor is flat: {hit:?}");
|
||
// The ceiling is found looking up, which is what proves "indoors".
|
||
assert_eq!(level.ceiling_above(vec3f(0.0, 0.1, 0.0), 8.0), Some(2.0));
|
||
// Outside the corridor there is no floor at all.
|
||
assert!(level.floor_below(vec3f(5.0, 1.0, 0.0), 4.0).is_none());
|
||
}
|
||
|
||
#[test]
|
||
fn walls_block_and_open_space_does_not() {
|
||
let level = corridor();
|
||
let cfg = cfg();
|
||
let from = vec3f(0.0, 0.0, 0.0);
|
||
assert!(
|
||
!level.path_blocked(from, vec3f(0.0, 0.0, -1.0), cfg.radius, cfg.step_up, cfg.height),
|
||
"the corridor is open ahead"
|
||
);
|
||
assert!(
|
||
level.path_blocked(from, vec3f(2.0, 0.0, 0.0), cfg.radius, cfg.step_up, cfg.height),
|
||
"the side wall is solid"
|
||
);
|
||
// Free run stops at the end wall, not before and not through it.
|
||
let run = level.free_run(from, 0.0, &cfg);
|
||
assert!(run > 8.0 && run < 10.5, "ran {run} down a 10-unit corridor");
|
||
}
|
||
|
||
#[test]
|
||
fn walker_stays_on_the_floor_and_never_enters_a_wall() {
|
||
let level = corridor();
|
||
let cfg = WalkerConfig { repick_secs: 1.0e6, ..cfg() };
|
||
let start = level.interior_start(&cfg).expect("a corridor is walkable");
|
||
assert!((start.y - 0.0).abs() < 1e-3, "starts on the floor: {start:?}");
|
||
let mut w = LevelWalker::new(start, 0.0, cfg, 7);
|
||
let mut turned_back = false;
|
||
let mut min_z = f32::MAX;
|
||
for _ in 0..1800 {
|
||
let ev = w.tick(1.0 / 60.0, &level);
|
||
assert_ne!(ev, WalkerEvent::Stranded, "a corridor is not a void");
|
||
let feet = w.feet();
|
||
// ON the floor — the mid-air bug this module exists to kill.
|
||
assert!((feet.y - 0.0).abs() < 1e-3, "left the floor: {feet:?}");
|
||
// The body radius is kept clear of every wall, which is also
|
||
// what keeps the camera's near plane out of the geometry.
|
||
let clear = cfg.radius - 1e-3;
|
||
assert!(
|
||
feet.x > -1.0 + clear && feet.x < 1.0 - clear,
|
||
"camera too close to a side wall: {feet:?}"
|
||
);
|
||
assert!(feet.z > -10.0 + clear, "too close to the end wall: {feet:?}");
|
||
min_z = min_z.min(feet.z);
|
||
// It turns AWAY before it ever touches the dead end.
|
||
turned_back |= w.yaw().abs() > 2.0;
|
||
}
|
||
assert!(min_z < -5.0, "should get down the corridor, min_z={min_z}");
|
||
assert!(turned_back, "the dead end turns the walker around");
|
||
}
|
||
|
||
#[test]
|
||
fn climbs_a_staircase_and_stands_on_each_tread() {
|
||
let cfg = cfg();
|
||
let (mut p, mut i) = (Vec::new(), Vec::new());
|
||
// Four 0.25-high treads (each within step_up 0.3) going -Z.
|
||
floor(&mut p, &mut i, -1.0, 1.0, -1.0, 2.0, 0.0);
|
||
for n in 0..4 {
|
||
let y = 0.25 * (n + 1) as f32;
|
||
let z0 = -1.0 - n as f32;
|
||
floor(&mut p, &mut i, -1.0, 1.0, z0 - 1.0, z0, y);
|
||
}
|
||
floor(&mut p, &mut i, -1.0, 1.0, -8.0, 2.0, 4.0); // ceiling
|
||
wall_x(&mut p, &mut i, -8.0, 2.0, -1.0, 0.0, 4.0);
|
||
wall_x(&mut p, &mut i, -8.0, 2.0, 1.0, 0.0, 4.0);
|
||
let level = LevelCollision::from_positions(p, i);
|
||
let mut w = LevelWalker::new(vec3f(0.0, 0.0, 1.5), 0.0, WalkerConfig { repick_secs: 1.0e6, ..cfg }, 3);
|
||
let mut top = 0.0f32;
|
||
for _ in 0..900 {
|
||
w.tick(1.0 / 60.0, &level);
|
||
let feet = w.feet();
|
||
top = top.max(feet.y);
|
||
// Always exactly on a tread, never between them.
|
||
// Grounded, the feet are exactly on a tread; mid-fall (coming
|
||
// back DOWN the stairs) they are legitimately between them.
|
||
if !w.is_airborne() {
|
||
let tread = (feet.y / 0.25).round() * 0.25;
|
||
assert!((feet.y - tread).abs() < 1e-3, "not on a tread: {feet:?}");
|
||
}
|
||
}
|
||
assert!(top >= 0.75, "climbed the stairs, reached {top}");
|
||
}
|
||
|
||
#[test]
|
||
fn stairs_rise_smoothly_even_though_the_body_snaps() {
|
||
// Five treads. The BODY steps instantly (Doom sets z), the EYE
|
||
// must not: no visible jump bigger than a couple of centimetres.
|
||
let cfg = WalkerConfig { repick_secs: 1.0e6, ..cfg() };
|
||
let (mut p, mut i) = (Vec::new(), Vec::new());
|
||
floor(&mut p, &mut i, -1.0, 1.0, -1.0, 2.0, 0.0);
|
||
for n in 0..5 {
|
||
let y = 0.25 * (n + 1) as f32;
|
||
let z0 = -1.0 - n as f32;
|
||
floor(&mut p, &mut i, -1.0, 1.0, z0 - 1.0, z0, y);
|
||
}
|
||
floor(&mut p, &mut i, -1.0, 1.0, -9.0, 2.0, 6.0);
|
||
wall_x(&mut p, &mut i, -9.0, 2.0, -1.0, 0.0, 6.0);
|
||
wall_x(&mut p, &mut i, -9.0, 2.0, 1.0, 0.0, 6.0);
|
||
let level = LevelCollision::from_positions(p, i);
|
||
let mut w = LevelWalker::new(vec3f(0.0, 0.0, 1.5), 0.0, cfg, 3);
|
||
let mut prev_eye = w.camera().eye.y;
|
||
let (mut body_jumps, mut worst_grounded, mut worst_any) = (0, 0.0f32, 0.0f32);
|
||
let mut prev_body = w.feet().y;
|
||
// The HIGHEST tread reached, not where the wander happened to stop:
|
||
// the walker walks through its turns, so the tail of a free wander
|
||
// is wherever it was going next, and the subject here is the eye.
|
||
let mut top = w.feet().y;
|
||
for _ in 0..900 {
|
||
w.tick(1.0 / 60.0, &level);
|
||
let body = w.feet().y;
|
||
top = top.max(body);
|
||
let eye = w.camera().eye.y;
|
||
if body - prev_body > 0.1 {
|
||
body_jumps += 1; // the body DOES snap up a tread
|
||
}
|
||
let jump = (eye - prev_eye).abs();
|
||
worst_any = worst_any.max(jump);
|
||
// While the feet are on the ground — climbing or walking — the
|
||
// eye may only ease. Falling back DOWN the stairs it follows
|
||
// the body at gravity's pace, which is not a snap.
|
||
if !w.is_airborne() {
|
||
worst_grounded = worst_grounded.max(jump);
|
||
}
|
||
prev_body = body;
|
||
prev_eye = eye;
|
||
}
|
||
assert!(body_jumps >= 3, "the body climbed treads: {body_jumps}");
|
||
// ~0.3 s to absorb a 0.25-unit tread is about 3 cm of eye travel
|
||
// per tick at 60 Hz — smooth, and the same catch-up Doom gives
|
||
// `viewheight`. The BODY's 0.25 jump never reaches the camera.
|
||
assert!(
|
||
worst_grounded < 0.03,
|
||
"climbing must ease the view, not snap: worst {worst_grounded} per tick"
|
||
);
|
||
// Even falling, the eye never moves faster than free fall over one
|
||
// tread (√(2·g·0.25) ≈ 3.1 u/s ≈ 0.052 per tick).
|
||
assert!(worst_any < 0.06, "eye outran gravity: {worst_any} per tick");
|
||
assert!(top >= 0.75, "climbed the stairs, reached {top}");
|
||
}
|
||
|
||
#[test]
|
||
fn head_bob_stays_within_a_few_centimetres() {
|
||
// "Sickeningly big" was 25 cm — Doom's raw MAXBOB/2 in map units.
|
||
// At the importer's scale one world unit is about two metres, so
|
||
// the peak has to stay near 0.015 units.
|
||
let level = corridor();
|
||
for style in [BobStyle::Doom, BobStyle::Duke, BobStyle::Quake] {
|
||
let cfg = WalkerConfig { bob: style, repick_secs: 1.0e6, ..cfg() };
|
||
let mut w = LevelWalker::new(vec3f(0.0, 0.0, 0.5), 0.0, cfg, 3);
|
||
let mut peak = 0.0f32;
|
||
for i in 0..600 {
|
||
w.tick(1.0 / 60.0, &level);
|
||
if i > 120 {
|
||
peak = peak.max((w.camera().eye.y - w.feet().y - cfg.eye_height).abs());
|
||
}
|
||
}
|
||
assert!(peak < 0.025, "{style:?} bob peak {peak} world units (~5 cm cap)");
|
||
assert!(peak > 0.002, "{style:?} bob should still be visible: {peak}");
|
||
}
|
||
}
|
||
|
||
#[test]
|
||
fn falls_down_a_drop_instead_of_teleporting() {
|
||
// A 1.2-unit drop: too deep to step down, inside fall_limit, so
|
||
// the originals would let you walk off and fall.
|
||
let cfg = WalkerConfig { repick_secs: 1.0e6, fall_limit: 2.0, ..cfg() };
|
||
let (mut p, mut i) = (Vec::new(), Vec::new());
|
||
floor(&mut p, &mut i, -1.0, 1.0, -2.0, 2.0, 1.2); // upper ledge
|
||
floor(&mut p, &mut i, -1.0, 1.0, -8.0, -2.0, 0.0); // lower floor
|
||
floor(&mut p, &mut i, -1.0, 1.0, -8.0, 2.0, 5.0); // ceiling
|
||
wall_x(&mut p, &mut i, -8.0, 2.0, -1.0, 0.0, 5.0);
|
||
wall_x(&mut p, &mut i, -8.0, 2.0, 1.0, 0.0, 5.0);
|
||
let level = LevelCollision::from_positions(p, i);
|
||
let mut w = LevelWalker::new(vec3f(0.0, 1.2, 1.5), 0.0, cfg, 3);
|
||
let mut heights = Vec::new();
|
||
let mut airborne_ticks = 0;
|
||
// Eye above feet on the tick the fall ENDS: that is the landing dip
|
||
// the test is about. Reading it 600 ticks later measures head bob,
|
||
// which rises above the nominal eye height by design.
|
||
let mut landing_dip = None;
|
||
let mut was_airborne = false;
|
||
for _ in 0..600 {
|
||
w.tick(1.0 / 60.0, &level);
|
||
heights.push(w.feet().y);
|
||
if w.is_airborne() {
|
||
airborne_ticks += 1;
|
||
} else if was_airborne && landing_dip.is_none() {
|
||
landing_dip = Some(w.camera().eye.y - w.feet().y);
|
||
}
|
||
was_airborne = w.is_airborne();
|
||
}
|
||
let landed = *heights.last().unwrap();
|
||
assert!((landed - 0.0).abs() < 1e-3, "lands on the lower floor: {landed}");
|
||
assert!(airborne_ticks > 4, "it FELL, over several ticks: {airborne_ticks}");
|
||
// Never teleports: no single tick moves more than gravity allows.
|
||
for pair in heights.windows(2) {
|
||
let drop = pair[0] - pair[1];
|
||
assert!(drop < 0.35, "teleported down {drop} in one tick");
|
||
}
|
||
// Landing dips the view, then eases back (Doom's deltaviewheight).
|
||
let dip = landing_dip.expect("the walker landed");
|
||
assert!(dip <= cfg.eye_height + 1e-3, "the view never rises on landing: {dip}");
|
||
assert!(dip > 0.0, "the eye is still above the feet: {dip}");
|
||
}
|
||
|
||
#[test]
|
||
fn walks_the_bridge_instead_of_the_nukage() {
|
||
// Two safe platforms joined by a hazard strip AND a clean bridge.
|
||
// Every triangle's kind is declared, so the tour can choose.
|
||
let cfg = WalkerConfig { repick_secs: 2.0, ..cfg() };
|
||
let (mut p, mut i) = (Vec::new(), Vec::new());
|
||
let mut kinds = Vec::new();
|
||
let push = |p: &mut Vec<Vec3f>,
|
||
i: &mut Vec<u32>,
|
||
kinds: &mut Vec<SurfaceKind>,
|
||
x0: f32,
|
||
x1: f32,
|
||
z0: f32,
|
||
z1: f32,
|
||
y: f32,
|
||
kind: SurfaceKind| {
|
||
floor(p, i, x0, x1, z0, z1, y);
|
||
kinds.push(kind);
|
||
kinds.push(kind);
|
||
};
|
||
// Start platform (z 0..2) and far platform (z -6..-4), joined by
|
||
// TWO corridors: nukage on the left (x -3..-1), a clean bridge on
|
||
// the right (x 1..3). The gap between them has no floor at all, so
|
||
// the tour must commit to one or the other.
|
||
push(&mut p, &mut i, &mut kinds, -3.0, 3.0, 0.0, 2.0, 0.0, SurfaceKind::Floor);
|
||
push(&mut p, &mut i, &mut kinds, -3.0, 3.0, -6.0, -4.0, 0.0, SurfaceKind::Floor);
|
||
push(&mut p, &mut i, &mut kinds, -3.0, -1.0, -4.0, 0.0, 0.0, SurfaceKind::Hazard);
|
||
push(&mut p, &mut i, &mut kinds, 1.0, 3.0, -4.0, 0.0, 0.0, SurfaceKind::Floor);
|
||
// Ceiling (nobody stands on it, but it makes the room interior).
|
||
push(&mut p, &mut i, &mut kinds, -3.0, 3.0, -6.0, 2.0, 4.0, SurfaceKind::Floor);
|
||
let level = LevelCollision::from_positions(p, i).with_kinds(kinds);
|
||
assert!(level.has_kinds(), "the fixture declares its surfaces");
|
||
// The probe agrees which corridor is which.
|
||
assert!(level.hazard_run(vec3f(-2.0, 0.0, -0.5), 0.0, &cfg) > 0.5, "left is ooze");
|
||
assert_eq!(level.hazard_run(vec3f(2.0, 0.0, -0.5), 0.0, &cfg), 0.0, "right is clean");
|
||
// Started in the middle of the start platform, facing the gap.
|
||
let mut w = LevelWalker::new(vec3f(0.0, 0.0, 1.0), 0.0, cfg, 4);
|
||
let (mut ooze_ticks, mut bridge_ticks, mut reached_far) = (0, 0, false);
|
||
for _ in 0..5400 {
|
||
w.tick(1.0 / 60.0, &level);
|
||
let feet = w.feet();
|
||
if feet.z < -0.05 && feet.z > -4.0 {
|
||
if feet.x < 0.0 {
|
||
ooze_ticks += 1;
|
||
} else {
|
||
bridge_ticks += 1;
|
||
}
|
||
}
|
||
reached_far |= feet.z < -4.0;
|
||
}
|
||
assert!(reached_far, "the tour should reach the far platform");
|
||
assert!(
|
||
bridge_ticks > ooze_ticks * 4,
|
||
"took the bridge: {bridge_ticks} bridge vs {ooze_ticks} ooze ticks"
|
||
);
|
||
}
|
||
|
||
#[test]
|
||
fn refuses_to_walk_into_a_pit() {
|
||
let cfg = WalkerConfig { fall_limit: 0.5, repick_secs: 1.0e6, ..cfg() };
|
||
let (mut p, mut i) = (Vec::new(), Vec::new());
|
||
// A ledge that ends at z = -3 with nothing beyond: a void.
|
||
floor(&mut p, &mut i, -1.0, 1.0, -3.0, 2.0, 0.0);
|
||
floor(&mut p, &mut i, -1.0, 1.0, -3.0, 2.0, 2.0);
|
||
let level = LevelCollision::from_positions(p, i);
|
||
let mut w = LevelWalker::new(vec3f(0.0, 0.0, 1.0), 0.0, cfg, 11);
|
||
for _ in 0..900 {
|
||
let ev = w.tick(1.0 / 60.0, &level);
|
||
if ev == WalkerEvent::Stranded {
|
||
panic!("the walker fell out of the level at {:?}", w.feet());
|
||
}
|
||
assert!(w.feet().z > -3.0 - 1e-3, "stepped into the void: {:?}", w.feet());
|
||
assert!((w.feet().y - 0.0).abs() < 1e-3);
|
||
}
|
||
}
|
||
|
||
#[test]
|
||
fn interior_start_is_under_the_roof_not_on_it() {
|
||
let cfg = cfg();
|
||
let (mut p, mut i) = (Vec::new(), Vec::new());
|
||
floor(&mut p, &mut i, -6.0, 6.0, -6.0, 6.0, 0.0);
|
||
floor(&mut p, &mut i, -6.0, 6.0, -6.0, 6.0, 3.0); // roof
|
||
wall_x(&mut p, &mut i, -6.0, 6.0, -6.0, 0.0, 3.0);
|
||
wall_x(&mut p, &mut i, -6.0, 6.0, 6.0, 0.0, 3.0);
|
||
wall_z(&mut p, &mut i, -6.0, 6.0, -6.0, 0.0, 3.0);
|
||
wall_z(&mut p, &mut i, -6.0, 6.0, 6.0, 0.0, 3.0);
|
||
let level = LevelCollision::from_positions(p, i);
|
||
let start = level.interior_start(&cfg).expect("a room is walkable");
|
||
assert!((start.y - 0.0).abs() < 1e-3, "on the floor, not the roof: {start:?}");
|
||
let mut w = LevelWalker::new(start, 0.0, cfg, 5);
|
||
for _ in 0..1200 {
|
||
w.tick(1.0 / 60.0, &level);
|
||
assert!(w.feet().y < 2.9, "climbed onto the roof: {:?}", w.feet());
|
||
}
|
||
}
|
||
|
||
#[test]
|
||
fn head_bob_is_speed_proportional_and_per_engine() {
|
||
let level = corridor();
|
||
let sample = |style: BobStyle| {
|
||
let cfg = WalkerConfig { bob: style, repick_secs: 1.0e6, ..cfg() };
|
||
let mut w = LevelWalker::new(vec3f(0.0, 0.0, 0.5), 0.0, cfg, 3);
|
||
assert_eq!(w.camera().eye.y, 0.0 + cfg.eye_height, "standing still: no bob");
|
||
let (mut lo, mut hi, mut crossings, mut prev) = (f32::MAX, f32::MIN, 0, 0.0f32);
|
||
for i in 0..600 {
|
||
w.tick(1.0 / 60.0, &level);
|
||
let h = w.camera().eye.y - w.feet().y - cfg.eye_height;
|
||
if i > 120 {
|
||
lo = lo.min(h);
|
||
hi = hi.max(h);
|
||
if prev <= 0.0 && h > 0.0 {
|
||
crossings += 1;
|
||
}
|
||
prev = h;
|
||
}
|
||
}
|
||
(lo, hi, crossings)
|
||
};
|
||
let (lo, hi, cycles) = sample(BobStyle::Doom);
|
||
// Magnitude is pinned by `head_bob_stays_within_a_few_centimetres`;
|
||
// here the shape matters: a real dip below the eye line, and the
|
||
// engine's cadence.
|
||
assert!(hi > 0.002, "doom bob rises: {hi}");
|
||
assert!(lo < -0.002, "doom bob dips below the eye line: {lo}");
|
||
assert!((cycles as f32 - 8.0 * 1.75).abs() < 2.5, "doom ~1.75 Hz, {cycles} in 8 s");
|
||
let (_, _, quake_cycles) = sample(BobStyle::Quake);
|
||
assert!(
|
||
(quake_cycles as f32 - 8.0 / 0.6).abs() < 3.0,
|
||
"quake cl_bobcycle 0.6 s, {quake_cycles} in 8 s"
|
||
);
|
||
let (_, duke_hi, _) = sample(BobStyle::Duke);
|
||
assert!(duke_hi > hi, "Build's stride is deeper than Doom's");
|
||
assert_eq!(sample(BobStyle::None).1, 0.0, "bob off means a locked camera");
|
||
}
|
||
|
||
#[test]
|
||
fn bob_style_follows_the_map_source() {
|
||
assert_eq!(BobStyle::from_source("doom/doom/worlds/doom1/e1m1"), BobStyle::Doom);
|
||
assert_eq!(BobStyle::from_source("duke/duke3d/worlds/duke3d/e1l1"), BobStyle::Duke);
|
||
assert_eq!(BobStyle::from_source("quake/id1/worlds/id1/e1m1"), BobStyle::Quake);
|
||
assert_eq!(BobStyle::from_source("quake3/baseq3/worlds/q3dm1"), BobStyle::Quake);
|
||
}
|
||
|
||
#[test]
|
||
fn same_seed_walks_the_same_tour() {
|
||
let level = corridor();
|
||
let cfg = cfg();
|
||
let path = |seed: u64| {
|
||
let mut w = LevelWalker::new(vec3f(0.0, 0.0, 0.0), 0.0, cfg, seed);
|
||
(0..900)
|
||
.map(|_| {
|
||
w.tick(1.0 / 60.0, &level);
|
||
(w.feet().x, w.feet().z, w.yaw())
|
||
})
|
||
.collect::<Vec<_>>()
|
||
};
|
||
assert_eq!(path(42), path(42), "a seeded tour repeats exactly");
|
||
}
|
||
|
||
/// Two storeys joined by a staircase: a lower room (y 0, z -2..6), six
|
||
/// 0.25 treads climbing to y 1.5 over z -8..-2, and an upper room
|
||
/// (y 1.5, z -14..-8). Roofed throughout, walled down both sides.
|
||
fn two_floors() -> LevelCollision {
|
||
let (mut p, mut i) = (Vec::new(), Vec::new());
|
||
floor(&mut p, &mut i, -2.0, 2.0, -2.0, 6.0, 0.0);
|
||
floor(&mut p, &mut i, -2.0, 2.0, -2.0, 6.0, 3.0);
|
||
for n in 0..6 {
|
||
let y = 0.25 * (n + 1) as f32;
|
||
let z1 = -2.0 - n as f32;
|
||
floor(&mut p, &mut i, -2.0, 2.0, z1 - 1.0, z1, y);
|
||
}
|
||
floor(&mut p, &mut i, -2.0, 2.0, -8.0, -2.0, 4.0);
|
||
floor(&mut p, &mut i, -2.0, 2.0, -14.0, -8.0, 1.5);
|
||
floor(&mut p, &mut i, -2.0, 2.0, -14.0, -8.0, 4.5);
|
||
wall_x(&mut p, &mut i, -14.0, 6.0, -2.0, 0.0, 5.0);
|
||
wall_x(&mut p, &mut i, -14.0, 6.0, 2.0, 0.0, 5.0);
|
||
wall_z(&mut p, &mut i, -2.0, 2.0, 6.0, 0.0, 5.0);
|
||
wall_z(&mut p, &mut i, -2.0, 2.0, -14.0, 0.0, 5.0);
|
||
LevelCollision::from_positions(p, i)
|
||
}
|
||
|
||
/// Wrap a glTF JSON document as a GLB (JSON chunk only — the classifier
|
||
/// never touches the binary chunk).
|
||
fn glb(json: &str) -> Vec<u8> {
|
||
let mut chunk = json.as_bytes().to_vec();
|
||
while chunk.len() % 4 != 0 {
|
||
chunk.push(b' ');
|
||
}
|
||
let mut out = Vec::new();
|
||
out.extend_from_slice(b"glTF");
|
||
out.extend_from_slice(&2u32.to_le_bytes());
|
||
out.extend_from_slice(&((12 + 8 + chunk.len()) as u32).to_le_bytes());
|
||
out.extend_from_slice(&(chunk.len() as u32).to_le_bytes());
|
||
out.extend_from_slice(b"JSON");
|
||
out.extend_from_slice(&chunk);
|
||
out
|
||
}
|
||
|
||
#[test]
|
||
fn hazard_nodes_classify_their_triangles() {
|
||
// The importer's contract: a `hazard_N` node with extras. Three
|
||
// primitives — clean floor, nukage, water — 2 triangles each.
|
||
let doc = r#"{
|
||
"nodes":[
|
||
{"name":"floor_0","mesh":0},
|
||
{"name":"hazard_1","mesh":1,"extras":{"kind":"hazard","damage":5,"flat":"NUKAGE1","liquid":true}},
|
||
{"name":"hazard_2","mesh":2,"extras":{"kind":"hazard","damage":0,"flat":"FWATER1","liquid":true}}
|
||
],
|
||
"meshes":[
|
||
{"primitives":[{"attributes":{"POSITION":0},"indices":1}]},
|
||
{"primitives":[{"attributes":{"POSITION":0},"indices":1}]},
|
||
{"primitives":[{"attributes":{"POSITION":0},"indices":1}]}
|
||
],
|
||
"accessors":[{"count":4},{"count":6}]
|
||
}"#;
|
||
let kinds = surface_kinds_from_glb(&glb(doc), 6).expect("classified");
|
||
assert_eq!(
|
||
kinds,
|
||
vec![
|
||
SurfaceKind::Floor,
|
||
SurfaceKind::Floor,
|
||
SurfaceKind::Hazard,
|
||
SurfaceKind::Hazard,
|
||
SurfaceKind::Liquid,
|
||
SurfaceKind::Liquid,
|
||
]
|
||
);
|
||
}
|
||
|
||
#[test]
|
||
fn old_maps_fall_back_to_the_flat_name_on_the_material() {
|
||
// Every classic map published before the `hazard_N` lane: the only
|
||
// evidence is the source engine's flat name on the material.
|
||
let doc = r#"{
|
||
"nodes":[{"name":"e1m1","mesh":0}],
|
||
"meshes":[{"primitives":[
|
||
{"attributes":{"POSITION":0},"indices":1,"material":0},
|
||
{"attributes":{"POSITION":0},"indices":1,"material":1},
|
||
{"attributes":{"POSITION":0},"indices":1,"material":2}
|
||
]}],
|
||
"materials":[{"name":"doom.FLOOR4_8"},{"name":"doom.NUKAGE1"},{"name":"doom.FWATER1"}],
|
||
"accessors":[{"count":4},{"count":6}]
|
||
}"#;
|
||
let kinds = surface_kinds_from_glb(&glb(doc), 6).expect("classified");
|
||
assert_eq!(kinds[0], SurfaceKind::Floor);
|
||
assert_eq!(kinds[2], SurfaceKind::Hazard, "NUKAGE damages");
|
||
assert_eq!(kinds[4], SurfaceKind::Liquid, "FWATER is only wet");
|
||
}
|
||
|
||
/// The open-air regression: every classic map with an outdoor area
|
||
/// publishes a `sky` node, the loader takes that geometry OUT of the
|
||
/// static stream, and a walk that still counted it could never
|
||
/// reproduce the model's triangle count — so the whole classification
|
||
/// was discarded and the map's nukage stopped hurting. (Doom's E1M1:
|
||
/// 17264 level + 592 hazard triangles loaded, 502 more under `sky`.)
|
||
#[test]
|
||
fn sky_geometry_is_left_out_of_the_static_walk() {
|
||
let doc = r#"{
|
||
"nodes":[
|
||
{"name":"floor_0","mesh":0},
|
||
{"name":"hazard_1","mesh":1,"extras":{"kind":"hazard","damage":5,"flat":"NUKAGE1"}},
|
||
{"name":"sky","mesh":2,"extras":{"kind":"sky","projection":"cylinder"}}
|
||
],
|
||
"meshes":[
|
||
{"primitives":[{"attributes":{"POSITION":0},"indices":1}]},
|
||
{"primitives":[{"attributes":{"POSITION":0},"indices":1}]},
|
||
{"primitives":[{"attributes":{"POSITION":0},"indices":1}]}
|
||
],
|
||
"accessors":[{"count":4},{"count":6}]
|
||
}"#;
|
||
// The loader packs 4 triangles (floor + hazard); the sky's 2 are its
|
||
// own. Classification must agree, and the hazard must survive.
|
||
let kinds = surface_kinds_from_glb(&glb(doc), 4).expect("classified without the sky");
|
||
assert_eq!(
|
||
kinds,
|
||
vec![
|
||
SurfaceKind::Floor,
|
||
SurfaceKind::Floor,
|
||
SurfaceKind::Hazard,
|
||
SurfaceKind::Hazard,
|
||
]
|
||
);
|
||
}
|
||
|
||
/// A node NAMED sky with no projection the engine knows is ordinary
|
||
/// geometry to the loader, so it must stay ordinary here too.
|
||
#[test]
|
||
fn a_sky_node_without_a_projection_is_ordinary_geometry() {
|
||
let doc = r#"{
|
||
"nodes":[
|
||
{"name":"hazard_1","mesh":0,"extras":{"kind":"hazard","damage":5}},
|
||
{"name":"sky","mesh":1,"extras":{"kind":"sky"}}
|
||
],
|
||
"meshes":[
|
||
{"primitives":[{"attributes":{"POSITION":0},"indices":1}]},
|
||
{"primitives":[{"attributes":{"POSITION":0},"indices":1}]}
|
||
],
|
||
"accessors":[{"count":4},{"count":6}]
|
||
}"#;
|
||
let kinds = surface_kinds_from_glb(&glb(doc), 4).expect("classified with the sky in");
|
||
assert_eq!(kinds.len(), 4);
|
||
assert_eq!(kinds[0], SurfaceKind::Hazard);
|
||
}
|
||
|
||
#[test]
|
||
fn a_triangle_count_that_disagrees_with_the_loader_is_refused() {
|
||
// The contract check: if this walk does not reproduce the loader's
|
||
// triangle count, the mapping is a guess and must not be used.
|
||
let doc = r#"{
|
||
"nodes":[{"name":"hazard_1","mesh":0,"extras":{"kind":"hazard","damage":5}}],
|
||
"meshes":[{"primitives":[{"attributes":{"POSITION":0},"indices":1}]}],
|
||
"accessors":[{"count":4},{"count":6}]
|
||
}"#;
|
||
assert!(surface_kinds_from_glb(&glb(doc), 2).is_some(), "matching count is used");
|
||
assert_eq!(surface_kinds_from_glb(&glb(doc), 99), None, "a mismatch is refused");
|
||
assert_eq!(surface_kinds_from_glb(b"not a glb", 2), None);
|
||
}
|
||
|
||
#[test]
|
||
fn door_geometry_is_left_out_of_the_static_walk() {
|
||
// A door node (`extras.states`) is a moving part: its triangles are
|
||
// NOT in the static stream, so the classifier must skip them too or
|
||
// every triangle after it is labelled with its neighbour's kind.
|
||
let doc = r#"{
|
||
"nodes":[
|
||
{"name":"door_1","mesh":0,"extras":{"states":["closed","open"],"default":"closed"}},
|
||
{"name":"hazard_1","mesh":1,"extras":{"kind":"hazard","damage":5}}
|
||
],
|
||
"meshes":[
|
||
{"primitives":[{"attributes":{"POSITION":0},"indices":1}]},
|
||
{"primitives":[{"attributes":{"POSITION":0},"indices":1}]}
|
||
],
|
||
"animations":[{"name":"door_1","channels":[]}],
|
||
"accessors":[{"count":4},{"count":6}]
|
||
}"#;
|
||
let kinds = surface_kinds_from_glb(&glb(doc), 2).expect("classified without the door");
|
||
assert_eq!(kinds, vec![SurfaceKind::Hazard, SurfaceKind::Hazard]);
|
||
}
|
||
|
||
#[test]
|
||
fn nav_grid_connects_two_floors_through_the_stairs() {
|
||
let cfg = cfg();
|
||
let level = two_floors();
|
||
let nav = NavGrid::build(&level, &cfg);
|
||
assert!(nav.len() > 100, "a two-room level has cells: {}", nav.len());
|
||
assert!(nav.edge_count() > nav.len(), "cells are linked: {}", nav.edge_count());
|
||
// Both storeys are represented.
|
||
let lower = (0..nav.len() as u32)
|
||
.find(|i| {
|
||
let c = nav.cell(*i).unwrap();
|
||
c.pos.y.abs() < 1e-3 && c.pos.z > 4.0
|
||
})
|
||
.expect("a cell at the back of the lower room");
|
||
let upper: Vec<u32> = (0..nav.len() as u32)
|
||
.filter(|i| {
|
||
let c = nav.cell(*i).unwrap();
|
||
(c.pos.y - 1.5).abs() < 1e-3 && c.pos.z < -9.0
|
||
})
|
||
.collect();
|
||
assert!(!upper.is_empty(), "the upper room has cells");
|
||
// The graph itself crosses the stairs.
|
||
let (mut dist, mut parent) = (Vec::new(), Vec::new());
|
||
let reached = nav.flood(lower, &std::collections::HashSet::new(), &mut dist, &mut parent);
|
||
assert!(reached > nav.len() / 2, "most of the level is reachable: {reached}/{}", nav.len());
|
||
for u in &upper {
|
||
assert_ne!(
|
||
dist[*u as usize], NAV_UNREACHED,
|
||
"upper-room cell {u} is cut off from the lower room"
|
||
);
|
||
}
|
||
// And the route it hands out actually walks up them.
|
||
let path = nav.path_to(upper[0], &parent);
|
||
assert!(!path.is_empty(), "a route exists");
|
||
let climbed = path
|
||
.windows(2)
|
||
.all(|w| {
|
||
let (a, b) = (nav.cell(w[0]).unwrap(), nav.cell(w[1]).unwrap());
|
||
b.pos.y - a.pos.y <= cfg.step_up + 1e-3
|
||
});
|
||
assert!(climbed, "no waypoint pair asks for a jump");
|
||
let top = path.iter().map(|c| nav.cell(*c).unwrap().pos.y).fold(0.0f32, f32::max);
|
||
assert!(top >= 1.5 - 1e-3, "the route reaches the upper storey: {top}");
|
||
}
|
||
|
||
#[test]
|
||
fn the_tour_climbs_to_the_other_floor_and_keeps_finding_new_ground() {
|
||
// The complaint this exists for: the local heading picker paced up
|
||
// and down one corridor. With a plan it must cross the whole map.
|
||
let cfg = cfg();
|
||
let level = two_floors();
|
||
let nav = NavGrid::build(&level, &cfg);
|
||
let mut w = LevelWalker::new(vec3f(0.0, 0.0, 5.0), 0.0, cfg, 9);
|
||
let (mut top, mut bottom) = (f32::MIN, f32::MAX);
|
||
let mut distinct_at_30s = 0;
|
||
for t in 0..7200 {
|
||
w.tick_in(1.0 / 60.0, &level, Some(&nav));
|
||
top = top.max(w.feet().y);
|
||
bottom = bottom.min(w.feet().y);
|
||
if t == 1800 {
|
||
distinct_at_30s = w.nav_stats().distinct;
|
||
}
|
||
}
|
||
let stats = w.nav_stats();
|
||
assert!(top >= 1.4, "the tour climbed to the upper room: reached y={top}");
|
||
assert!(bottom <= 0.1, "and it started on the lower one: {bottom}");
|
||
assert!(stats.replans >= 2, "it re-planned as it went: {stats:?}");
|
||
// Coverage keeps GROWING — the ping-pong signature is a distinct
|
||
// count that flattens out after a few seconds.
|
||
assert!(
|
||
stats.distinct > distinct_at_30s,
|
||
"coverage stalled: {distinct_at_30s} cells at 30 s, {} at 120 s",
|
||
stats.distinct
|
||
);
|
||
assert!(
|
||
stats.distinct * 3 > nav.len(),
|
||
"toured only {} of {} cells",
|
||
stats.distinct,
|
||
nav.len()
|
||
);
|
||
}
|
||
|
||
#[test]
|
||
fn a_planned_tour_still_prefers_the_bridge_to_the_nukage() {
|
||
let cfg = WalkerConfig { repick_secs: 2.0, ..cfg() };
|
||
let (mut p, mut i) = (Vec::new(), Vec::new());
|
||
let mut kinds = Vec::new();
|
||
let push = |p: &mut Vec<Vec3f>,
|
||
i: &mut Vec<u32>,
|
||
kinds: &mut Vec<SurfaceKind>,
|
||
x0: f32,
|
||
x1: f32,
|
||
z0: f32,
|
||
z1: f32,
|
||
y: f32,
|
||
kind: SurfaceKind| {
|
||
floor(p, i, x0, x1, z0, z1, y);
|
||
kinds.push(kind);
|
||
kinds.push(kind);
|
||
};
|
||
push(&mut p, &mut i, &mut kinds, -3.0, 3.0, 0.0, 2.0, 0.0, SurfaceKind::Floor);
|
||
push(&mut p, &mut i, &mut kinds, -3.0, 3.0, -6.0, -4.0, 0.0, SurfaceKind::Floor);
|
||
push(&mut p, &mut i, &mut kinds, -3.0, -1.0, -4.0, 0.0, 0.0, SurfaceKind::Hazard);
|
||
push(&mut p, &mut i, &mut kinds, 1.0, 3.0, -4.0, 0.0, 0.0, SurfaceKind::Floor);
|
||
push(&mut p, &mut i, &mut kinds, -3.0, 3.0, -6.0, 2.0, 4.0, SurfaceKind::Floor);
|
||
let level = LevelCollision::from_positions(p, i).with_kinds(kinds);
|
||
let nav = NavGrid::build(&level, &cfg);
|
||
// The grid knows which corridor is which.
|
||
let ooze = (0..nav.len() as u32)
|
||
.filter(|c| nav.cell(*c).unwrap().kind == SurfaceKind::Hazard)
|
||
.count();
|
||
assert!(ooze > 0, "the hazard strip is in the grid, not deleted");
|
||
let mut w = LevelWalker::new(vec3f(0.0, 0.0, 1.0), 0.0, cfg, 4);
|
||
let (mut ooze_ticks, mut bridge_ticks, mut reached_far) = (0, 0, false);
|
||
for _ in 0..5400 {
|
||
w.tick_in(1.0 / 60.0, &level, Some(&nav));
|
||
let feet = w.feet();
|
||
if feet.z < -0.05 && feet.z > -4.0 {
|
||
if feet.x < 0.0 {
|
||
ooze_ticks += 1;
|
||
} else {
|
||
bridge_ticks += 1;
|
||
}
|
||
}
|
||
reached_far |= feet.z < -4.0;
|
||
}
|
||
assert!(reached_far, "the planned tour reaches the far platform");
|
||
assert!(
|
||
bridge_ticks > ooze_ticks * 4,
|
||
"took the bridge: {bridge_ticks} bridge vs {ooze_ticks} ooze ticks"
|
||
);
|
||
}
|
||
|
||
#[test]
|
||
fn a_seeded_planned_tour_repeats_exactly() {
|
||
let level = two_floors();
|
||
let cfg = cfg();
|
||
let nav = NavGrid::build(&level, &cfg);
|
||
let path = |seed: u64| {
|
||
let mut w = LevelWalker::new(vec3f(0.0, 0.0, 5.0), 0.0, cfg, seed);
|
||
(0..1800)
|
||
.map(|_| {
|
||
w.tick_in(1.0 / 60.0, &level, Some(&nav));
|
||
(w.feet().x, w.feet().y, w.feet().z, w.yaw())
|
||
})
|
||
.collect::<Vec<_>>()
|
||
};
|
||
assert_eq!(path(42), path(42), "a seeded planned tour repeats exactly");
|
||
assert_ne!(path(42), path(43), "and two seeds do not walk in lockstep");
|
||
}
|
||
|
||
#[test]
|
||
fn a_stuck_leg_is_invalidated_and_replanned() {
|
||
// A wall the probe cannot see (the fixture lies): the walker must
|
||
// notice it makes no ground, drop that edge and route elsewhere.
|
||
let cfg = cfg();
|
||
let level = two_floors();
|
||
let nav = NavGrid::build(&level, &cfg);
|
||
let mut w = LevelWalker::new(vec3f(0.0, 0.0, 5.0), 0.0, cfg, 5);
|
||
// Freeze the body: every tick reports no progress, which is exactly
|
||
// what a lying edge looks like from inside the walker.
|
||
for _ in 0..600 {
|
||
w.tick_in(1.0 / 60.0, &level, Some(&nav));
|
||
w.pos = vec3f(0.0, 0.0, 5.0);
|
||
}
|
||
let stats = w.nav_stats();
|
||
assert!(stats.invalidated > 0, "a leg that never moves is dropped: {stats:?}");
|
||
assert!(stats.replans > 1, "and the tour re-plans: {stats:?}");
|
||
}
|
||
|
||
#[test]
|
||
fn doors_gate_their_cells_and_are_asked_for_by_the_tour() {
|
||
let cfg = cfg();
|
||
let level = two_floors();
|
||
let mut nav = NavGrid::build(&level, &cfg);
|
||
// A door across the whole lower room at z ≈ 0.
|
||
nav.mark_doors(&[(vec3f(-2.0, 0.0, -0.4), vec3f(2.0, 2.0, 0.4))]);
|
||
let gated = (0..nav.len() as u32)
|
||
.filter(|c| nav.cell(*c).unwrap().door == Some(0))
|
||
.count();
|
||
assert!(gated > 0, "the door's footprint marks cells");
|
||
for c in 0..nav.len() as u32 {
|
||
let cell = nav.cell(c).unwrap();
|
||
if cell.door.is_some() {
|
||
assert!(cell.pos.z.abs() < 1.0, "only the doorway is gated: {cell:?}");
|
||
}
|
||
}
|
||
// Walking toward the stairs, the tour asks for the door ahead.
|
||
let mut w = LevelWalker::new(vec3f(0.0, 0.0, 5.0), 0.0, cfg, 3);
|
||
let mut asked = None;
|
||
for _ in 0..3600 {
|
||
w.tick_in(1.0 / 60.0, &level, Some(&nav));
|
||
if let Some(d) = w.wanted_door() {
|
||
asked = Some(d);
|
||
break;
|
||
}
|
||
}
|
||
assert_eq!(asked, Some(0), "the tour asked the host to open door 0");
|
||
// Once the host says it is open, the request clears and it walks on.
|
||
w.set_door_open(0, true);
|
||
w.tick_in(1.0 / 60.0, &level, Some(&nav));
|
||
assert_eq!(w.wanted_door(), None, "an open door is no longer requested");
|
||
let before = w.feet().z;
|
||
for _ in 0..600 {
|
||
w.tick_in(1.0 / 60.0, &level, Some(&nav));
|
||
}
|
||
assert!(w.feet().z < before, "and it carries on through: {before} → {:?}", w.feet());
|
||
}
|
||
|
||
/// Two sealed rooms with no way between them — exactly what a classic
|
||
/// map looks like while its doors are still baked into the walls.
|
||
fn two_sealed_rooms() -> LevelCollision {
|
||
let (mut p, mut i) = (Vec::new(), Vec::new());
|
||
for (z0, z1) in [(0.0f32, 6.0f32), (-20.0, -14.0)] {
|
||
floor(&mut p, &mut i, -3.0, 3.0, z0, z1, 0.0);
|
||
floor(&mut p, &mut i, -3.0, 3.0, z0, z1, 2.5);
|
||
wall_x(&mut p, &mut i, z0, z1, -3.0, 0.0, 2.5);
|
||
wall_x(&mut p, &mut i, z0, z1, 3.0, 0.0, 2.5);
|
||
wall_z(&mut p, &mut i, -3.0, 3.0, z0, 0.0, 2.5);
|
||
wall_z(&mut p, &mut i, -3.0, 3.0, z1, 0.0, 2.5);
|
||
}
|
||
LevelCollision::from_positions(p, i)
|
||
}
|
||
|
||
/// Diagnostic against a REAL published map. Skipped unless `LEVEL_GLB`
|
||
/// points at one, so the suite stays hermetic; run as
|
||
/// `LEVEL_GLB=<path> cargo test -p makepad-render --lib -- real_level --nocapture`
|
||
/// when a map on screen behaves in a way the fixtures do not reproduce.
|
||
#[test]
|
||
fn real_level_is_a_place_a_walker_can_get_out_of() {
|
||
let Ok(path) = std::env::var("LEVEL_GLB") else { return };
|
||
let bytes = std::fs::read(&path).expect("LEVEL_GLB readable");
|
||
let model = crate::StaticModel::parse_glb(&bytes).expect("a static GLB");
|
||
let cfg = WalkerConfig::default();
|
||
let level = LevelCollision::from_packed(
|
||
&model.vertices,
|
||
crate::model::MODEL_VERTEX_FLOATS,
|
||
&model.indices,
|
||
UpAxis::Y,
|
||
)
|
||
.expect("collision");
|
||
let level = match surface_kinds_from_glb(&bytes, model.triangle_count()) {
|
||
Some(kinds) => {
|
||
let h = kinds.iter().filter(|k| **k == SurfaceKind::Hazard).count();
|
||
println!("kinds: {h} hazard of {} triangles", kinds.len());
|
||
level.with_kinds(kinds)
|
||
}
|
||
None => {
|
||
println!("kinds: none (no hazard_N nodes, no flat names)");
|
||
level
|
||
}
|
||
};
|
||
let nav = NavGrid::build(&level, &cfg);
|
||
let r = nav.refusals();
|
||
println!(
|
||
"nav: {} cells, {} edges, refused {} too tall (smallest rise {:.4}) / {} deep / {} walled, {} escape links",
|
||
nav.len(),
|
||
nav.edge_count(),
|
||
r.too_tall,
|
||
r.smallest_refused_rise,
|
||
r.too_deep,
|
||
r.walled,
|
||
r.escapes
|
||
);
|
||
println!("components: {:?}", &nav.component_sizes()[..nav.component_sizes().len().min(8)]);
|
||
let core = nav.best_start().expect("a start");
|
||
let out = nav.can_reach(core);
|
||
let trapped = out.iter().filter(|o| !**o).count();
|
||
println!("trapped cells (cannot walk back to the core): {trapped}/{}", nav.len());
|
||
// What actually separates a trapped cell from freedom: the rise to
|
||
// its nearest free neighbour, and whether the body probe refuses it.
|
||
let mut rises: Vec<(f32, bool)> = Vec::new();
|
||
for a in 0..nav.len() {
|
||
if out[a] {
|
||
continue;
|
||
}
|
||
let (ix, iz) = nav.column_xz(nav.cells[a].column);
|
||
for dz in -1i32..=1 {
|
||
for dx in -1i32..=1 {
|
||
if dx == 0 && dz == 0 {
|
||
continue;
|
||
}
|
||
let Some(col) = nav.column_index(ix as i32 + dx, iz as i32 + dz) else {
|
||
continue;
|
||
};
|
||
for b in nav.column_cells(col) {
|
||
if !out[b] {
|
||
continue;
|
||
}
|
||
let dy = nav.cells[b].pos.y - nav.cells[a].pos.y;
|
||
if dy <= 0.0 {
|
||
continue;
|
||
}
|
||
let blocked = level.path_blocked(
|
||
nav.cells[a].pos,
|
||
nav.cells[b].pos,
|
||
cfg.radius,
|
||
(cfg.step_up + hazard_escape_step(cfg.step_up)).min(cfg.height * 0.8),
|
||
cfg.height,
|
||
);
|
||
rises.push((dy, blocked));
|
||
}
|
||
}
|
||
}
|
||
}
|
||
rises.sort_by(|a, b| a.0.partial_cmp(&b.0).unwrap());
|
||
println!("trapped→free boundary pairs: {}", rises.len());
|
||
for (dy, blocked) in rises.iter().take(12) {
|
||
println!(" rise {dy:.4} ({} map units) blocked={blocked}", (dy * 64.0).round());
|
||
}
|
||
let climbable = rises
|
||
.iter()
|
||
.filter(|(dy, blocked)| *dy <= cfg.step_up + STEP_EPS + hazard_escape_step(cfg.step_up) && !*blocked)
|
||
.count();
|
||
println!(" of those, {climbable} are within the escape step and unblocked");
|
||
// Drop the body in the LOWEST floor of the map — the bottom of the
|
||
// deepest pit — and see whether it is a place you can leave.
|
||
let low = (0..nav.len() as u32)
|
||
.min_by(|a, b| {
|
||
nav.cell(*a)
|
||
.unwrap()
|
||
.pos
|
||
.y
|
||
.partial_cmp(&nav.cell(*b).unwrap().pos.y)
|
||
.unwrap()
|
||
})
|
||
.expect("cells");
|
||
let start = nav.cell(low).unwrap().pos;
|
||
println!("deepest cell {low} at {start:?}, escape flag {}", nav.cell(low).unwrap().escape);
|
||
let mut w = LevelWalker::new(start, 0.0, cfg, 3);
|
||
let (mut top, mut left) = (start.y, false);
|
||
for t in 0..3600 {
|
||
w.tick_in(1.0 / 60.0, &level, Some(&nav));
|
||
top = top.max(w.feet().y);
|
||
if !left && w.feet().y > start.y + 0.3 {
|
||
left = true;
|
||
println!("climbed out after {:.1}s at {:?}", t as f32 / 60.0, w.feet());
|
||
}
|
||
}
|
||
println!(
|
||
"after 60 s: {:?}, highest {top:.3} (started {:.3}), stats {:?}",
|
||
w.feet(),
|
||
start.y,
|
||
w.nav_stats()
|
||
);
|
||
// EVERY low-lying cell, not just the single deepest: a pit that is a
|
||
// prison anywhere on the map is the bug the user is looking at.
|
||
let mut low_cells: Vec<u32> = (0..nav.len() as u32).collect();
|
||
low_cells.sort_by(|a, b| {
|
||
nav.cell(*a)
|
||
.unwrap()
|
||
.pos
|
||
.y
|
||
.partial_cmp(&nav.cell(*b).unwrap().pos.y)
|
||
.unwrap()
|
||
});
|
||
let sample: Vec<u32> = low_cells.iter().step_by(7).take(40).copied().collect();
|
||
let mut prisons = Vec::new();
|
||
for c in &sample {
|
||
let from = nav.cell(*c).unwrap().pos;
|
||
let mut w = LevelWalker::new(from, 0.0, cfg, 5);
|
||
let mut out_ok = false;
|
||
for _ in 0..1800 {
|
||
w.tick_in(1.0 / 60.0, &level, Some(&nav));
|
||
if w.feet().y > from.y + 0.3 || w.cut_count() > 0 {
|
||
out_ok = true;
|
||
break;
|
||
}
|
||
}
|
||
if !out_ok {
|
||
prisons.push((*c, from, w.feet()));
|
||
}
|
||
}
|
||
println!(
|
||
"pit sample: {} of {} low starts could not rise 0.3 in 30 s",
|
||
prisons.len(),
|
||
sample.len()
|
||
);
|
||
for (c, from, at) in prisons.iter().take(3) {
|
||
println!(" cell {c} start {from:?} ended {at:?} escape={}", nav.cell(*c).unwrap().escape);
|
||
// Which graph edge leads UP out of here, and what does the BODY
|
||
// say when it tries to take it from a few distances back?
|
||
let up: Vec<(u32, f32)> = nav
|
||
.edges(*c)
|
||
.map(|(b, _)| (b, nav.cell(b).unwrap().pos.y - from.y))
|
||
.filter(|(_, dy)| *dy > 0.05)
|
||
.collect();
|
||
println!(" graph edges rising out of it: {up:?}");
|
||
// Can the graph route from here up to the core at all, and how far?
|
||
let (mut d, mut par) = (Vec::new(), Vec::new());
|
||
nav.flood(*c, &std::collections::HashSet::new(), &mut d, &mut par);
|
||
match d.get(core as usize).copied() {
|
||
Some(cost) if cost != NAV_UNREACHED => {
|
||
let route = nav.path_to(core, &par);
|
||
let rises: Vec<f32> = route
|
||
.windows(2)
|
||
.map(|w| nav.cell(w[1]).unwrap().pos.y - nav.cell(w[0]).unwrap().pos.y)
|
||
.collect();
|
||
let max_rise = rises.iter().cloned().fold(0.0f32, f32::max);
|
||
println!(
|
||
" route to the core: cost {cost}, {} waypoints, biggest single rise {max_rise:.3}",
|
||
route.len()
|
||
);
|
||
// The first RISING pair on the route is the step the body
|
||
// has to take. Ask the body about it, from a few
|
||
// distances back, exactly as it would arrive.
|
||
let full: Vec<u32> = std::iter::once(*c).chain(route.iter().copied()).collect();
|
||
if let Some(k) = full.windows(2).position(|w| {
|
||
nav.cell(w[1]).unwrap().pos.y - nav.cell(w[0]).unwrap().pos.y > 0.05
|
||
}) {
|
||
let (pa, pb) =
|
||
(nav.cell(full[k]).unwrap().pos, nav.cell(full[k + 1]).unwrap().pos);
|
||
let (dx, dz) = (pb.x - pa.x, pb.z - pa.z);
|
||
let len = (dx * dx + dz * dz).sqrt().max(1e-6);
|
||
println!(
|
||
" rising pair on the route: {pa:?} -> {pb:?} (rise {:.4})",
|
||
pb.y - pa.y
|
||
);
|
||
for back in [0.4f32, 0.25, 0.1, 0.0, -0.1] {
|
||
let at =
|
||
vec3f(pa.x - dx / len * back, pa.y, pa.z - dz / len * back);
|
||
let probe = LevelWalker::new(at, dx.atan2(-dz), cfg, 1);
|
||
let step = cfg.speed / 60.0;
|
||
let r = probe
|
||
.step_refusal(&level, vec3f(dx / len * step, 0.0, dz / len * step));
|
||
println!(" {back:+.2} back: {r:?}");
|
||
}
|
||
}
|
||
}
|
||
_ => println!(" NO route to the core from here"),
|
||
}
|
||
for (b, dy) in up.iter().take(2) {
|
||
let to = nav.cell(*b).unwrap().pos;
|
||
let (dx, dz) = (to.x - from.x, to.z - from.z);
|
||
let len = (dx * dx + dz * dz).sqrt().max(1e-6);
|
||
for back in [0.30f32, 0.15, 0.05, 0.0] {
|
||
let at = vec3f(from.x - dx / len * back, from.y, from.z - dz / len * back);
|
||
let mut probe = LevelWalker::new(at, dx.atan2(-dz), cfg, 1);
|
||
let step = cfg.speed / 60.0;
|
||
let r = probe.step_refusal(&level, vec3f(dx / len * step, 0.0, dz / len * step));
|
||
println!(" rise {dy:.3}, {back:.2} back: {r:?}");
|
||
let _ = &mut probe;
|
||
}
|
||
}
|
||
}
|
||
assert!(left, "the deepest pit in {path} is a prison");
|
||
}
|
||
|
||
/// Measurement against a REAL published map: every rising step between
|
||
/// adjacent grid columns (a stair tread by Doom's own step rule), judged
|
||
/// the three ways a step can be judged — by the GRAPH (is the edge
|
||
/// offered?), by the BODY from the far cell centre (`step_refusal` over
|
||
/// the whole edge), and by the BODY arriving incrementally (per-tick
|
||
/// probes marched along the edge, which is how the walker actually
|
||
/// travels). Prints a per-flight table so "the tour avoids stairs" can
|
||
/// be split into geometry (risers/lips walling the probes) versus
|
||
/// policy (the planner not wanting to). Skipped unless `LEVEL_GLB`
|
||
/// points at a map:
|
||
/// `LEVEL_GLB=<path> cargo test -p makepad-render --release --lib -- real_level_stair --nocapture`
|
||
#[test]
|
||
fn real_level_stair_steps_agree_between_graph_and_body() {
|
||
let Ok(path) = std::env::var("LEVEL_GLB") else { return };
|
||
let bytes = std::fs::read(&path).expect("LEVEL_GLB readable");
|
||
let model = crate::StaticModel::parse_glb(&bytes).expect("a static GLB");
|
||
let cfg = WalkerConfig::default();
|
||
let level = LevelCollision::from_packed(
|
||
&model.vertices,
|
||
crate::model::MODEL_VERTEX_FLOATS,
|
||
&model.indices,
|
||
UpAxis::Y,
|
||
)
|
||
.expect("collision");
|
||
let level = match surface_kinds_from_glb(&bytes, model.triangle_count()) {
|
||
Some(kinds) => level.with_kinds(kinds),
|
||
None => level,
|
||
};
|
||
let nav = NavGrid::build(&level, &cfg);
|
||
let tick = cfg.speed / 60.0;
|
||
|
||
// The body marching one edge exactly as the walker travels it:
|
||
// per-tick `step_refusal`, advancing over any step it accepts.
|
||
// Returns the first refusal (with how far along it happened).
|
||
let march = |from: Vec3f, to: Vec3f| -> (StepRefusal, f32) {
|
||
let (dx, dz) = (to.x - from.x, to.z - from.z);
|
||
let len = (dx * dx + dz * dz).sqrt().max(1e-6);
|
||
let dir = vec3f(dx / len, 0.0, dz / len);
|
||
let yaw = dir.x.atan2(-dir.z);
|
||
let mut at = from;
|
||
let mut travelled = 0.0f32;
|
||
while travelled < len + cfg.radius {
|
||
let probe = LevelWalker::new(at, yaw, cfg, 1);
|
||
let r = probe.step_refusal(&level, vec3f(dir.x * tick, 0.0, dir.z * tick));
|
||
match r {
|
||
StepRefusal::Ok { .. } => {}
|
||
other => return (other, travelled),
|
||
}
|
||
let want = vec3f(at.x + dir.x * tick, at.y, at.z + dir.z * tick);
|
||
let up = cfg.step_up + STEP_EPS + hazard_escape_step(cfg.step_up);
|
||
let Some(floor) =
|
||
level.floor_below(vec3f(want.x, want.y + up, want.z), up + cfg.fall_limit)
|
||
else {
|
||
return (StepRefusal::NoFloor, travelled);
|
||
};
|
||
at = vec3f(want.x, floor.y, want.z);
|
||
travelled += tick;
|
||
}
|
||
(StepRefusal::Ok { rise: to.y - from.y }, travelled)
|
||
};
|
||
// Where exactly is the obstruction a clearance refusal saw? Scan the
|
||
// radial rays upward: the highest ray height (above the stand) that
|
||
// still hits something within the body radius is the lip's top.
|
||
let lip_top = |stand: Vec3f| -> Option<f32> {
|
||
let mut top = None;
|
||
let mut h = 0.02f32;
|
||
while h < cfg.height {
|
||
let origin = vec3f(stand.x, stand.y + h, stand.z);
|
||
for i in 0..8 {
|
||
let a = std::f32::consts::TAU * i as f32 / 8.0;
|
||
if level.caster.any_hit(origin, vec3f(a.sin(), 0.0, -a.cos()), cfg.radius) {
|
||
top = Some(h);
|
||
break;
|
||
}
|
||
}
|
||
h += 0.01;
|
||
}
|
||
top
|
||
};
|
||
|
||
// Every rising pair between adjacent (orthogonal) columns whose rise
|
||
// is a legal step: these ARE the stairs of the map.
|
||
let mut pairs: Vec<(u32, u32)> = Vec::new();
|
||
for a in 0..nav.len() {
|
||
let (ix, iz) = nav.column_xz(nav.cells[a].column);
|
||
for (dx, dz) in [(1i32, 0i32), (0, 1), (-1, 0), (0, -1)] {
|
||
let Some(col) = nav.column_index(ix as i32 + dx, iz as i32 + dz) else {
|
||
continue;
|
||
};
|
||
for b in nav.column_cells(col) {
|
||
let dy = nav.cells[b].pos.y - nav.cells[a].pos.y;
|
||
if dy >= 0.1 && dy <= cfg.step_up + STEP_EPS {
|
||
pairs.push((a as u32, b as u32));
|
||
}
|
||
}
|
||
}
|
||
}
|
||
// Group the rising pairs into flights (connected stair edges): a
|
||
// per-flight refusal table reads like the staircase on screen.
|
||
let mut flight = vec![usize::MAX; nav.len()];
|
||
let mut nflights = 0usize;
|
||
for (a, b) in &pairs {
|
||
let (fa, fb) = (flight[*a as usize], flight[*b as usize]);
|
||
match (fa, fb) {
|
||
(usize::MAX, usize::MAX) => {
|
||
flight[*a as usize] = nflights;
|
||
flight[*b as usize] = nflights;
|
||
nflights += 1;
|
||
}
|
||
(f, usize::MAX) => flight[*b as usize] = f,
|
||
(usize::MAX, f) => flight[*a as usize] = f,
|
||
(f, g) if f != g => {
|
||
for s in flight.iter_mut() {
|
||
if *s == g {
|
||
*s = f;
|
||
}
|
||
}
|
||
}
|
||
_ => {}
|
||
}
|
||
}
|
||
#[derive(Default)]
|
||
struct Tally {
|
||
steps: usize,
|
||
graph_missing: usize,
|
||
up_walled: usize,
|
||
up_no_clear: usize,
|
||
up_other: usize,
|
||
down_walled: usize,
|
||
down_no_clear: usize,
|
||
down_other: usize,
|
||
lip_tops: Vec<f32>,
|
||
sample: Option<Vec3f>,
|
||
}
|
||
let mut tallies: std::collections::HashMap<usize, Tally> =
|
||
std::collections::HashMap::new();
|
||
for (a, b) in &pairs {
|
||
let f = flight[*a as usize];
|
||
let t = tallies.entry(f).or_default();
|
||
t.steps += 1;
|
||
let (pa, pb) = (nav.cells[*a as usize].pos, nav.cells[*b as usize].pos);
|
||
t.sample.get_or_insert(pa);
|
||
if !nav.edges(*a).any(|(c, _)| c == *b) {
|
||
t.graph_missing += 1;
|
||
}
|
||
for (from, to, walled, no_clear, other) in [
|
||
(pa, pb, &mut t.up_walled, &mut t.up_no_clear, &mut t.up_other),
|
||
(pb, pa, &mut t.down_walled, &mut t.down_no_clear, &mut t.down_other),
|
||
] {
|
||
let (r, at) = march(from, to);
|
||
match r {
|
||
StepRefusal::Ok { .. } => {}
|
||
StepRefusal::Walled => *walled += 1,
|
||
StepRefusal::NoClearance { .. } => {
|
||
*no_clear += 1;
|
||
let (dx, dz) = (to.x - from.x, to.z - from.z);
|
||
let len = (dx * dx + dz * dz).sqrt().max(1e-6);
|
||
let spot = vec3f(
|
||
from.x + dx / len * at,
|
||
from.y.max(to.y),
|
||
from.z + dz / len * at,
|
||
);
|
||
if let Some(top) = lip_top(spot) {
|
||
t.lip_tops.push(top);
|
||
}
|
||
}
|
||
_ => *other += 1,
|
||
}
|
||
}
|
||
}
|
||
let mut rows: Vec<(usize, Tally)> = tallies.into_iter().collect();
|
||
rows.sort_by(|x, y| y.1.steps.cmp(&x.1.steps));
|
||
let mut total = Tally::default();
|
||
for (_, t) in &rows {
|
||
total.steps += t.steps;
|
||
total.graph_missing += t.graph_missing;
|
||
total.up_walled += t.up_walled;
|
||
total.up_no_clear += t.up_no_clear;
|
||
total.up_other += t.up_other;
|
||
total.down_walled += t.down_walled;
|
||
total.down_no_clear += t.down_no_clear;
|
||
total.down_other += t.down_other;
|
||
total.lip_tops.extend_from_slice(&t.lip_tops);
|
||
}
|
||
println!(
|
||
"stair steps: {} in {} flights; graph refused {}; body UP walled {} / no-clearance {} / other {}; DOWN walled {} / no-clearance {} / other {}",
|
||
total.steps,
|
||
rows.len(),
|
||
total.graph_missing,
|
||
total.up_walled,
|
||
total.up_no_clear,
|
||
total.up_other,
|
||
total.down_walled,
|
||
total.down_no_clear,
|
||
total.down_other,
|
||
);
|
||
println!(" flight steps graph- up W/NC/o down W/NC/o near");
|
||
for (f, t) in rows.iter().take(20) {
|
||
println!(
|
||
" {:>6} {:>5} {:>6} {:>2}/{:>2}/{:>2} {:>2}/{:>2}/{:>2} {:?}",
|
||
f,
|
||
t.steps,
|
||
t.graph_missing,
|
||
t.up_walled,
|
||
t.up_no_clear,
|
||
t.up_other,
|
||
t.down_walled,
|
||
t.down_no_clear,
|
||
t.down_other,
|
||
t.sample.unwrap_or(vec3f(0.0, 0.0, 0.0)),
|
||
);
|
||
}
|
||
// The graph-refused pairs, dissected: which probe ray said Walled,
|
||
// how far along it hit, and the smallest knee height that passes.
|
||
let mut shown = 0;
|
||
for (a, b) in &pairs {
|
||
if nav.edges(*a).any(|(c, _)| c == *b) || shown >= 24 {
|
||
continue;
|
||
}
|
||
shown += 1;
|
||
let (pa, pb) = (nav.cells[*a as usize].pos, nav.cells[*b as usize].pos);
|
||
let dy = pb.y - pa.y;
|
||
let (dx, dz) = (pb.x - pa.x, pb.z - pa.z);
|
||
let dist = (dx * dx + dz * dz).sqrt().max(1e-6);
|
||
let dir = vec3f(dx / dist, 0.0, dz / dist);
|
||
let side = vec3f(-dir.z, 0.0, dir.x);
|
||
let knee = cfg.step_up + (cfg.height - cfg.step_up) * 0.15;
|
||
let mut hits = String::new();
|
||
for (label, h) in [("knee", knee), ("chest", cfg.height * 0.85)] {
|
||
for l in [-cfg.radius, 0.0, cfg.radius] {
|
||
let origin = vec3f(pa.x + side.x * l, pa.y + h, pa.z + side.z * l);
|
||
if let Some((t, _)) = level.caster.nearest_hit(origin, dir, dist + cfg.radius)
|
||
{
|
||
hits.push_str(&format!(" {label}@{l:+.2} t={t:.2}"));
|
||
}
|
||
}
|
||
}
|
||
let mut min_knee = None;
|
||
let mut h = knee;
|
||
while h < cfg.height * 0.85 {
|
||
if !level.path_blocked(pa, pb, cfg.radius, h, cfg.height) {
|
||
// path_blocked derives its own ray height from the step
|
||
// argument; report the raw ray height that passed.
|
||
min_knee = Some(knee_height(h, cfg.height));
|
||
break;
|
||
}
|
||
h += 0.02;
|
||
}
|
||
println!(
|
||
" graph-refused {}->{} rise {dy:.3} at {pa:?}:{hits} (lowest passing ray {min_knee:?})",
|
||
a, b
|
||
);
|
||
}
|
||
if !total.lip_tops.is_empty() {
|
||
let mut tops = total.lip_tops.clone();
|
||
tops.sort_by(|a, b| a.partial_cmp(b).unwrap());
|
||
println!(
|
||
" no-clearance lip tops above the stand: min {:.3} median {:.3} max {:.3} ({} measured)",
|
||
tops[0],
|
||
tops[tops.len() / 2],
|
||
tops[tops.len() - 1],
|
||
tops.len()
|
||
);
|
||
let knee = knee_height(cfg.step_up, cfg.height);
|
||
let under = tops.iter().filter(|t| **t < knee).count();
|
||
println!(
|
||
" of those, {under} sit under the shared knee height {knee:.3} (tolerated once the band probes agree)"
|
||
);
|
||
}
|
||
}
|
||
|
||
#[test]
|
||
fn a_nukage_pit_with_a_one_step_rim_is_a_place_you_can_leave() {
|
||
// Doom's rule is step <= 24 map units, INCLUSIVE, and a sector floor
|
||
// baked through a float pipeline lands a hair over as often as under.
|
||
// A rim exactly one step tall used to read as a wall, and a walker in
|
||
// the green swamp was walled into it.
|
||
let cfg = WalkerConfig::default(); // the real Doom body: step 0.375
|
||
let (mut p, mut i) = (Vec::new(), Vec::new());
|
||
let mut kinds = Vec::new();
|
||
let slab = |p: &mut Vec<Vec3f>,
|
||
i: &mut Vec<u32>,
|
||
kinds: &mut Vec<SurfaceKind>,
|
||
x0: f32,
|
||
x1: f32,
|
||
z0: f32,
|
||
z1: f32,
|
||
y: f32,
|
||
kind: SurfaceKind| {
|
||
floor(p, i, x0, x1, z0, z1, y);
|
||
kinds.push(kind);
|
||
kinds.push(kind);
|
||
};
|
||
// A sunken nukage pool (z -4..0) with clean ground either side, one
|
||
// step up — and the step is the float the importer actually bakes.
|
||
let rim = 0.375_f32 * 1.000_002;
|
||
slab(&mut p, &mut i, &mut kinds, -3.0, 3.0, 0.0, 4.0, rim, SurfaceKind::Floor);
|
||
slab(&mut p, &mut i, &mut kinds, -3.0, 3.0, -4.0, 0.0, 0.0, SurfaceKind::Hazard);
|
||
slab(&mut p, &mut i, &mut kinds, -3.0, 3.0, -8.0, -4.0, rim, SurfaceKind::Floor);
|
||
slab(&mut p, &mut i, &mut kinds, -3.0, 3.0, -8.0, 4.0, 4.0, SurfaceKind::Floor);
|
||
let level = LevelCollision::from_positions(p, i).with_kinds(kinds);
|
||
let nav = NavGrid::build(&level, &cfg);
|
||
// The graph knows the way out of the pool.
|
||
let in_pool: Vec<u32> = (0..nav.len() as u32)
|
||
.filter(|c| nav.cell(*c).unwrap().kind == SurfaceKind::Hazard)
|
||
.collect();
|
||
assert!(!in_pool.is_empty(), "the pool is in the grid");
|
||
let escapes = in_pool
|
||
.iter()
|
||
.filter(|c| {
|
||
nav.edges(**c)
|
||
.any(|(b, _)| nav.cell(b).unwrap().kind != SurfaceKind::Hazard)
|
||
})
|
||
.count();
|
||
assert!(escapes > 0, "no cell of the pool has a way out of it");
|
||
// And the body climbs it: dropped in the middle of the pool, the
|
||
// tour is on clean ground inside twenty seconds.
|
||
let start = nav.cell(in_pool[in_pool.len() / 2]).unwrap().pos;
|
||
let mut w = LevelWalker::new(start, 0.0, cfg, 6);
|
||
let mut escaped = false;
|
||
for _ in 0..1200 {
|
||
w.tick_in(1.0 / 60.0, &level, Some(&nav));
|
||
escaped |= w.feet().y > 0.3;
|
||
}
|
||
assert!(escaped, "still in the swamp at {:?}", w.feet());
|
||
}
|
||
|
||
#[test]
|
||
fn an_external_route_is_followed_verbatim() {
|
||
// The player_nav seam: the planner owns WHERE, this module owns HOW.
|
||
let cfg = cfg();
|
||
let level = two_floors();
|
||
let nav = NavGrid::build(&level, &cfg);
|
||
let start = vec3f(0.0, 0.0, 5.0);
|
||
let from = nav.cell_at(start).expect("a cell under the start");
|
||
let goal = (0..nav.len() as u32)
|
||
.find(|i| {
|
||
let c = nav.cell(*i).unwrap();
|
||
(c.pos.y - 1.5).abs() < 1e-3 && c.pos.z < -9.0
|
||
})
|
||
.expect("an upstairs cell");
|
||
let (mut dist, mut parent) = (Vec::new(), Vec::new());
|
||
nav.flood(from, &std::collections::HashSet::new(), &mut dist, &mut parent);
|
||
let route = nav.path_to(goal, &parent);
|
||
assert!(route.len() > 4, "a real route: {}", route.len());
|
||
|
||
let mut w = LevelWalker::new(start, 0.0, cfg, 8);
|
||
w.set_external_planner(true);
|
||
assert!(w.has_external_planner());
|
||
w.set_route(route.clone());
|
||
for _ in 0..7200 {
|
||
w.tick_in(1.0 / 60.0, &level, Some(&nav));
|
||
if w.route().is_empty() {
|
||
break;
|
||
}
|
||
}
|
||
assert!(w.route().is_empty(), "the route was walked to the end");
|
||
let end = nav.cell(goal).unwrap().pos;
|
||
let (dx, dz) = (w.feet().x - end.x, w.feet().z - end.z);
|
||
assert!((dx * dx + dz * dz).sqrt() < 1.0, "arrived at the goal: {:?}", w.feet());
|
||
// And the tour engine did NOT invent goals of its own on the way.
|
||
let stats = w.nav_stats();
|
||
assert_eq!(stats.replans, 0, "the built-in planner stayed out of it: {stats:?}");
|
||
assert_eq!(stats.cuts, 0, "and it did not cut anywhere");
|
||
// With the route done, the planner's heading is what the body holds.
|
||
w.set_target_yaw(Some(1.0));
|
||
for _ in 0..120 {
|
||
w.tick_in(1.0 / 60.0, &level, Some(&nav));
|
||
}
|
||
assert!((w.yaw() - 1.0).abs() < 0.15, "held the planner's heading: {}", w.yaw());
|
||
// Doors are the planner's to ask for in this mode.
|
||
w.request_door(Some(3));
|
||
w.tick_in(1.0 / 60.0, &level, Some(&nav));
|
||
assert_eq!(w.wanted_door(), Some(3));
|
||
w.set_door_open(3, true);
|
||
w.tick_in(1.0 / 60.0, &level, Some(&nav));
|
||
assert_eq!(w.wanted_door(), None);
|
||
}
|
||
|
||
#[test]
|
||
fn orthogonal_and_diagonal_steps_agree_on_open_ground() {
|
||
// Parity check for the planner: on clean open floor a diagonal step
|
||
// is as good as an orthogonal one. (Against a rim CORNER it is not —
|
||
// the landing clearance refuses it — which is why the planner should
|
||
// prefer orthogonal exits out of a sunken area.)
|
||
let cfg = cfg();
|
||
let (mut p, mut i) = (Vec::new(), Vec::new());
|
||
floor(&mut p, &mut i, -4.0, 4.0, -4.0, 4.0, 0.0);
|
||
floor(&mut p, &mut i, -4.0, 4.0, -4.0, 4.0, 3.0);
|
||
let level = LevelCollision::from_positions(p, i);
|
||
let w = LevelWalker::new(vec3f(0.0, 0.0, 0.0), 0.0, cfg, 1);
|
||
let step = cfg.speed / 60.0;
|
||
for (dx, dz) in [(1.0, 0.0), (0.0, 1.0), (0.707, 0.707), (-0.707, 0.707)] {
|
||
let r = w.step_refusal(&level, vec3f(dx * step, 0.0, dz * step));
|
||
assert!(matches!(r, StepRefusal::Ok { .. }), "({dx},{dz}) refused: {r:?}");
|
||
}
|
||
}
|
||
|
||
#[test]
|
||
fn a_map_cut_into_rooms_reports_its_pieces() {
|
||
let cfg = cfg();
|
||
let nav = NavGrid::build(&two_sealed_rooms(), &cfg);
|
||
let sizes = nav.component_sizes();
|
||
assert!(sizes.len() >= 2, "two sealed rooms are two pieces: {sizes:?}");
|
||
assert!(sizes[0] > 20 && sizes[1] > 20, "both rooms have room: {sizes:?}");
|
||
let start = nav.best_start().expect("a start");
|
||
let here = nav.component_of(start).unwrap();
|
||
// And there is somewhere else to go.
|
||
let other = nav.next_region(start, &vec![0.0; nav.len()]).expect("another region");
|
||
assert_ne!(nav.component_of(other), Some(here), "the cut lands in a DIFFERENT room");
|
||
}
|
||
|
||
#[test]
|
||
fn a_seen_room_is_left_for_one_it_has_not_seen() {
|
||
// The tour must not spend the night in the room it started in just
|
||
// because the rest of the map is behind a wall it cannot open.
|
||
let cfg = cfg();
|
||
let level = two_sealed_rooms();
|
||
let nav = NavGrid::build(&level, &cfg);
|
||
let start = nav.cell(nav.best_start().unwrap()).unwrap().pos;
|
||
let mut w = LevelWalker::new(start, 0.0, cfg, 12);
|
||
let first_room = nav.component_of(nav.cell_at(start).unwrap()).unwrap();
|
||
let (mut cut_to_other, mut flashes) = (false, 0);
|
||
for _ in 0..18_000 {
|
||
w.tick_in(1.0 / 60.0, &level, Some(&nav));
|
||
if w.take_flash() {
|
||
flashes += 1;
|
||
}
|
||
if let Some(c) = nav.cell_at(w.feet()) {
|
||
cut_to_other |= nav.component_of(c) != Some(first_room);
|
||
}
|
||
}
|
||
let stats = w.nav_stats();
|
||
assert!(cut_to_other, "never left the first room: {stats:?}");
|
||
assert!(stats.cuts >= 1, "the cut is counted: {stats:?}");
|
||
assert_eq!(flashes as u64, stats.cuts, "every cut flashes exactly once");
|
||
}
|
||
|
||
#[test]
|
||
fn a_teleport_pad_cuts_to_its_destination() {
|
||
let cfg = cfg();
|
||
let level = two_sealed_rooms();
|
||
let mut nav = NavGrid::build(&level, &cfg);
|
||
// A pad in the near room, landing in the far one.
|
||
nav.mark_teleports(&[(
|
||
vec3f(-1.0, 0.0, 0.5),
|
||
vec3f(1.0, 1.0, 1.5),
|
||
vec3f(0.0, 0.0, -17.0),
|
||
std::f32::consts::PI,
|
||
)]);
|
||
let pad = (0..nav.len() as u32)
|
||
.find(|c| nav.cell(*c).unwrap().teleport == Some(0))
|
||
.expect("the pad marked its cells");
|
||
assert!(nav.teleport_target(0).is_some());
|
||
// The planner can now route from the near room into the far one:
|
||
// the pad is a ONE-WAY edge, exactly like Doom's.
|
||
let (mut dist, mut parent) = (Vec::new(), Vec::new());
|
||
nav.flood(pad, &std::collections::HashSet::new(), &mut dist, &mut parent);
|
||
let far = (0..nav.len())
|
||
.filter(|i| nav.cell(*i as u32).unwrap().pos.z < -14.0)
|
||
.filter(|i| dist[*i] != NAV_UNREACHED)
|
||
.count();
|
||
assert!(far > 20, "the far room is reachable through the pad: {far} cells");
|
||
// Standing on the pad cuts to the far room, facing the given way.
|
||
let mut w = LevelWalker::new(nav.cell(pad).unwrap().pos, 0.0, cfg, 2);
|
||
w.tick_in(1.0 / 60.0, &level, Some(&nav));
|
||
assert!(w.feet().z < -14.0, "teleported: {:?}", w.feet());
|
||
assert!((w.yaw() - std::f32::consts::PI).abs() < 1e-3, "arrives facing the anchor's way");
|
||
assert!(w.take_flash(), "a teleport flashes");
|
||
assert_eq!(w.cut_count(), 1);
|
||
}
|
||
|
||
#[test]
|
||
fn nav_cells_stay_a_body_clear_of_the_walls() {
|
||
let cfg = cfg();
|
||
let level = corridor();
|
||
let nav = NavGrid::build(&level, &cfg);
|
||
assert!(!nav.is_empty(), "a corridor has walkable cells");
|
||
for c in 0..nav.len() as u32 {
|
||
let p = nav.cell(c).unwrap().pos;
|
||
assert!(
|
||
p.x > -1.0 + cfg.radius - 1e-3 && p.x < 1.0 - cfg.radius + 1e-3,
|
||
"cell inside a wall: {p:?}"
|
||
);
|
||
assert!((p.y - 0.0).abs() < 1e-3, "cells sit on the floor: {p:?}");
|
||
}
|
||
// Every cell is found again from its own position.
|
||
for c in 0..nav.len() as u32 {
|
||
assert_eq!(nav.cell_at(nav.cell(c).unwrap().pos), Some(c));
|
||
}
|
||
}
|
||
|
||
#[test]
|
||
fn z_up_sources_are_converted_at_build_time() {
|
||
// One triangle lying flat in a Z-up source (constant z) must become
|
||
// a floor (constant y) after conversion.
|
||
let verts: Vec<f32> = vec![
|
||
0.0, 0.0, 5.0, //
|
||
1.0, 0.0, 5.0, //
|
||
0.0, 1.0, 5.0, //
|
||
];
|
||
let level =
|
||
LevelCollision::from_packed(&verts, 3, &[0, 1, 2], UpAxis::Z).expect("built");
|
||
let (min, max) = level.bounds();
|
||
assert!((min.y - 5.0).abs() < 1e-6 && (max.y - 5.0).abs() < 1e-6, "{min:?} {max:?}");
|
||
let hit = level.floor_below(vec3f(0.2, 9.0, -0.2), 10.0).expect("floor under the probe");
|
||
assert!((hit.y - 5.0).abs() < 1e-4);
|
||
assert!(hit.flatness > 0.99, "converted triangle is flat: {hit:?}");
|
||
}
|
||
}
|
||
|
||
// player_nav: shared synthetic-level builders, so the player-behaviour
|
||
// planner's test suite builds its fixtures the same way this module's tests
|
||
// do (triangle soups through `LevelCollision::from_positions`). The `tests`
|
||
// module above keeps its private copies — it is frozen; new suites use these.
|
||
#[cfg(test)]
|
||
pub(crate) mod test_geometry {
|
||
use super::*;
|
||
|
||
/// Append a quad (two triangles) to a triangle soup.
|
||
pub fn quad(pos: &mut Vec<Vec3f>, idx: &mut Vec<u32>, a: Vec3f, b: Vec3f, c: Vec3f, d: Vec3f) {
|
||
let n = pos.len() as u32;
|
||
pos.extend_from_slice(&[a, b, c, d]);
|
||
idx.extend_from_slice(&[n, n + 1, n + 2, n, n + 2, n + 3]);
|
||
}
|
||
|
||
/// A horizontal slab top at `y` spanning the given x/z range.
|
||
pub fn floor(
|
||
pos: &mut Vec<Vec3f>,
|
||
idx: &mut Vec<u32>,
|
||
x0: f32,
|
||
x1: f32,
|
||
z0: f32,
|
||
z1: f32,
|
||
y: f32,
|
||
) {
|
||
quad(
|
||
pos,
|
||
idx,
|
||
vec3f(x0, y, z0),
|
||
vec3f(x1, y, z0),
|
||
vec3f(x1, y, z1),
|
||
vec3f(x0, y, z1),
|
||
);
|
||
}
|
||
|
||
/// A vertical wall spanning x0..x1 at `z`, from y0 to y1.
|
||
pub fn wall_z(
|
||
pos: &mut Vec<Vec3f>,
|
||
idx: &mut Vec<u32>,
|
||
x0: f32,
|
||
x1: f32,
|
||
z: f32,
|
||
y0: f32,
|
||
y1: f32,
|
||
) {
|
||
quad(
|
||
pos,
|
||
idx,
|
||
vec3f(x0, y0, z),
|
||
vec3f(x1, y0, z),
|
||
vec3f(x1, y1, z),
|
||
vec3f(x0, y1, z),
|
||
);
|
||
}
|
||
|
||
/// A vertical wall spanning z0..z1 at `x`, from y0 to y1.
|
||
pub fn wall_x(
|
||
pos: &mut Vec<Vec3f>,
|
||
idx: &mut Vec<u32>,
|
||
z0: f32,
|
||
z1: f32,
|
||
x: f32,
|
||
y0: f32,
|
||
y1: f32,
|
||
) {
|
||
quad(
|
||
pos,
|
||
idx,
|
||
vec3f(x, y0, z0),
|
||
vec3f(x, y0, z1),
|
||
vec3f(x, y1, z1),
|
||
vec3f(x, y1, z0),
|
||
);
|
||
}
|
||
}
|
||
|
||
// ---------------------------------------------------------------------------
|
||
// The map's units, and a route a body can actually walk
|
||
// ---------------------------------------------------------------------------
|
||
|
||
/// What went wrong on Quake 1 maps, pinned.
|
||
///
|
||
/// Three separate faults, all of which read to a viewer as one thing — a
|
||
/// walker that spins, stops and gets stuck on corners:
|
||
///
|
||
/// 1. the body was in the PRESET's units, not the map's (a Quake 1 level is
|
||
/// published at 1/32, twice a Doom level's metres per map unit);
|
||
/// 2. the nav lattice was a fixed 0.5 m instead of one body wide, so the
|
||
/// graph was finer than the legs walking it;
|
||
/// 3. the walker stood still for any heading change over 34°, and walked
|
||
/// at a speed its own turn rate could not steer — so it orbited close
|
||
/// waypoints instead of reaching them.
|
||
#[cfg(test)]
|
||
mod walk_in_the_maps_units {
|
||
use super::test_geometry::{floor, wall_x, wall_z};
|
||
use super::*;
|
||
|
||
/// A roofed room `span` across, floor at 0.
|
||
fn room(span: f32, height: f32) -> LevelCollision {
|
||
let (mut p, mut i) = (Vec::new(), Vec::new());
|
||
let h = span * 0.5;
|
||
floor(&mut p, &mut i, -h, h, -h, h, 0.0);
|
||
floor(&mut p, &mut i, -h, h, -h, h, height);
|
||
wall_x(&mut p, &mut i, -h, h, -h, 0.0, height);
|
||
wall_x(&mut p, &mut i, -h, h, h, 0.0, height);
|
||
wall_z(&mut p, &mut i, -h, h, -h, 0.0, height);
|
||
wall_z(&mut p, &mut i, -h, h, h, 0.0, height);
|
||
LevelCollision::from_positions(p, i)
|
||
}
|
||
|
||
#[test]
|
||
fn a_declared_step_puts_the_whole_body_in_the_maps_units() {
|
||
let preset = WalkerConfig::for_style(BobStyle::Quake);
|
||
// Quake 1 publishes at 1/32: its 18-unit step is 0.5625, twice the
|
||
// 18-at-1/64 the preset carries.
|
||
let quake1 = preset.with_declared(Some(0.5625), Some(1.4375));
|
||
let k = 0.5625 / preset.step_up;
|
||
assert!((k - 2.0).abs() < 0.01, "the Quake 1 scale is 2x: {k}");
|
||
assert!((quake1.step_up - 0.5625).abs() < 1e-4, "{}", quake1.step_up);
|
||
assert!((quake1.radius - preset.radius * k).abs() < 1e-4, "{}", quake1.radius);
|
||
assert!((quake1.height - preset.height * k).abs() < 1e-4, "{}", quake1.height);
|
||
assert!((quake1.speed - preset.speed * k).abs() < 1e-3, "{}", quake1.speed);
|
||
// Gravity is a length per second squared: it scales once too, or a
|
||
// body in a double-scale world falls in slow motion.
|
||
assert!((quake1.gravity - preset.gravity * k).abs() < 1e-3, "{}", quake1.gravity);
|
||
assert!((quake1.fall_limit - preset.fall_limit * k).abs() < 1e-3, "{}", quake1.fall_limit);
|
||
// The eye is declared outright, not scaled: it is what the map says.
|
||
assert!((quake1.eye_height - 1.4375).abs() < 1e-4, "{}", quake1.eye_height);
|
||
|
||
// A map at the preset's own scale changes nothing but the eye.
|
||
let doom = WalkerConfig::for_style(BobStyle::Doom).with_declared(Some(0.375), Some(0.6406));
|
||
let base = WalkerConfig::for_style(BobStyle::Doom);
|
||
assert!((doom.step_up - base.step_up).abs() < 1e-6, "{}", doom.step_up);
|
||
assert!((doom.radius - base.radius).abs() < 1e-6, "{}", doom.radius);
|
||
assert!((doom.speed - base.speed).abs() < 1e-6, "{}", doom.speed);
|
||
|
||
// Declaring nothing (Build states no step height) keeps the preset,
|
||
// and a nonsense declaration is refused rather than believed.
|
||
let none = WalkerConfig::for_style(BobStyle::Duke).with_declared(None, None);
|
||
assert_eq!(none.step_up, WalkerConfig::for_style(BobStyle::Duke).step_up);
|
||
let junk = WalkerConfig::for_style(BobStyle::Doom).with_declared(Some(400.0), None);
|
||
assert_eq!(junk.step_up, base.step_up, "a 400 m step is a bad sidecar, not a scale");
|
||
let nan = WalkerConfig::for_style(BobStyle::Doom).with_declared(Some(f32::NAN), None);
|
||
assert_eq!(nan.step_up, base.step_up);
|
||
}
|
||
|
||
#[test]
|
||
fn the_nav_lattice_is_one_body_wide_whatever_the_map_scale() {
|
||
let level = room(24.0, 4.0);
|
||
let doom = WalkerConfig::for_style(BobStyle::Doom);
|
||
let quake1 = WalkerConfig::for_style(BobStyle::Quake).with_declared(Some(0.5625), None);
|
||
let small = NavGrid::build(&level, &doom);
|
||
let big = NavGrid::build(&level, &quake1);
|
||
assert!((small.cell_size() - doom.radius * 2.0).abs() < 1e-4, "{}", small.cell_size());
|
||
assert!((big.cell_size() - quake1.radius * 2.0).abs() < 1e-4, "{}", big.cell_size());
|
||
assert!(
|
||
big.cell_size() > small.cell_size() * 1.9,
|
||
"a body twice as wide gets a lattice twice as coarse: {} vs {}",
|
||
big.cell_size(),
|
||
small.cell_size()
|
||
);
|
||
}
|
||
|
||
/// Put a walker in an open room on an external route to one cell, and
|
||
/// report how long it took to get there (in ticks) and how far it
|
||
/// wandered on the way.
|
||
fn drive_to(cfg: WalkerConfig, target: Vec3f, ticks: usize) -> (Option<usize>, f32) {
|
||
let level = room(32.0, 6.0);
|
||
let grid = NavGrid::build(&level, &cfg);
|
||
let start = vec3f(0.0, 0.0, 0.0);
|
||
let goal = grid.cell_at(target).expect("target is walkable");
|
||
let goal_pos = grid.cell(goal).expect("cell").pos;
|
||
// Facing -Z: the target below is off to the side, which is what a
|
||
// route corner looks like from the body's point of view.
|
||
let mut w = LevelWalker::new(start, 0.0, cfg, 3);
|
||
w.set_external_planner(true);
|
||
w.set_route(vec![goal]);
|
||
let mut travelled = 0.0;
|
||
let mut prev = start;
|
||
for t in 0..ticks {
|
||
w.tick_in(1.0 / 60.0, &level, Some(&grid));
|
||
let feet = w.feet();
|
||
travelled += ((feet.x - prev.x).powi(2) + (feet.z - prev.z).powi(2)).sqrt();
|
||
prev = feet;
|
||
let gap =
|
||
((feet.x - goal_pos.x).powi(2) + (feet.z - goal_pos.z).powi(2)).sqrt();
|
||
if gap < grid.cell_size() * 0.6 || w.route().is_empty() {
|
||
return (Some(t), travelled);
|
||
}
|
||
}
|
||
(None, travelled)
|
||
}
|
||
|
||
#[test]
|
||
fn a_waypoint_inside_the_turning_circle_is_reached_and_not_orbited() {
|
||
// The Quake 1 body: 3.8 m/s over 1.6 rad/s is a 2.4 m turning
|
||
// circle, and its nav cells are a metre apart. A waypoint 1.5 m to
|
||
// the side sits well inside that circle.
|
||
let cfg = WalkerConfig::for_style(BobStyle::Quake).with_declared(Some(0.5625), None);
|
||
let radius = cfg.turn_radius();
|
||
assert!(radius > 2.0, "the Quake 1 tour has a wide turning circle: {radius}");
|
||
let target = vec3f(1.5, 0.0, 0.0);
|
||
let (arrived, travelled) = drive_to(cfg, target, 60 * 8);
|
||
let arrived = arrived.expect("the body must reach a waypoint inside its turning circle");
|
||
// Orbiting shows up as distance without arrival: the straight line
|
||
// is 1.5 m, and a body that circles covers many times that.
|
||
assert!(
|
||
travelled < 6.0,
|
||
"walked {travelled:.1} m to a point 1.5 m away — that is an orbit, not a path"
|
||
);
|
||
assert!(arrived < 60 * 5, "took {arrived} ticks to walk 1.5 m");
|
||
}
|
||
|
||
#[test]
|
||
fn the_body_covers_ground_while_it_turns() {
|
||
// A route corner behind the shoulder: the heading error starts well
|
||
// over the "facing the target" gate. The body used to stand
|
||
// perfectly still until it had spun to within 34° — which is the
|
||
// stop-spin-go stutter, and (being no progress) it also tripped the
|
||
// planner's watchdog, whose dropped legs then came back cell by
|
||
// cell, so every one of THOSE turned 45° too.
|
||
let cfg = WalkerConfig::for_style(BobStyle::Doom);
|
||
let level = room(32.0, 6.0);
|
||
let grid = NavGrid::build(&level, &cfg);
|
||
// Straight out to the side: yaw 0 looks down -Z, so +X is 90° off.
|
||
let goal = grid.cell_at(vec3f(6.0, 0.0, 0.0)).expect("walkable");
|
||
let mut w = LevelWalker::new(vec3f(0.0, 0.0, 0.0), 0.0, cfg, 3);
|
||
w.set_external_planner(true);
|
||
w.set_route(vec![goal]);
|
||
let mut moved_while_turning = 0.0;
|
||
for _ in 0..18 {
|
||
let before = w.feet();
|
||
w.tick_in(1.0 / 60.0, &level, Some(&grid));
|
||
// Still turning: nowhere near the target heading yet.
|
||
assert!(
|
||
w.yaw().abs() < std::f32::consts::FRAC_PI_2 - 0.2,
|
||
"the turn should not be finished in 0.3 s"
|
||
);
|
||
let feet = w.feet();
|
||
moved_while_turning +=
|
||
((feet.x - before.x).powi(2) + (feet.z - before.z).powi(2)).sqrt();
|
||
}
|
||
assert!(
|
||
moved_while_turning > 0.02,
|
||
"the body stood still for the whole turn ({moved_while_turning:.3} m)"
|
||
);
|
||
}
|
||
|
||
#[test]
|
||
fn a_walker_never_walks_faster_than_its_turn_can_steer() {
|
||
// The invariant behind both of the above: the circle a body traces
|
||
// (speed / turn rate) must fit inside the distance to what it is
|
||
// steering at.
|
||
let cfg = WalkerConfig::for_style(BobStyle::Quake).with_declared(Some(0.5625), None);
|
||
let level = room(32.0, 6.0);
|
||
let grid = NavGrid::build(&level, &cfg);
|
||
let goal = grid.cell_at(vec3f(1.2, 0.0, 0.6)).expect("walkable");
|
||
let goal_pos = grid.cell(goal).expect("cell").pos;
|
||
let mut w = LevelWalker::new(vec3f(0.0, 0.0, 0.0), 0.0, cfg, 3);
|
||
w.set_external_planner(true);
|
||
w.set_route(vec![goal]);
|
||
for _ in 0..240 {
|
||
let before = w.feet();
|
||
w.tick_in(1.0 / 60.0, &level, Some(&grid));
|
||
if w.route().is_empty() {
|
||
return; // arrived, which is the point
|
||
}
|
||
let feet = w.feet();
|
||
let speed =
|
||
((feet.x - before.x).powi(2) + (feet.z - before.z).powi(2)).sqrt() * 60.0;
|
||
let gap =
|
||
((before.x - goal_pos.x).powi(2) + (before.z - goal_pos.z).powi(2)).sqrt();
|
||
// The cap is on the speed the body WANTS; the actual one eases
|
||
// down over `SPEED_EASE_SECS`, and the gap closes while it does.
|
||
let lag = speed * SPEED_EASE_SECS;
|
||
assert!(
|
||
speed <= cfg.turn_rate * (gap + lag) + 0.05,
|
||
"walked {speed:.2} m/s at a waypoint {gap:.2} m away — a circle of \
|
||
{:.2} m round a point it can never reach",
|
||
speed / cfg.turn_rate
|
||
);
|
||
}
|
||
panic!("never reached a waypoint 1.3 m away in four seconds");
|
||
}
|
||
|
||
#[test]
|
||
fn a_fresh_route_forgets_the_old_ones_slide() {
|
||
// The "try the other way round the obstruction" offset is armed by
|
||
// the stuck watchdog and cleared by the next plan — except that the
|
||
// clearing lives in the BUILT-IN tour's replan, which an external
|
||
// planner never runs. So on a `player_nav` tour the first give-up
|
||
// left the body steering 34° off every bearing it was handed, for
|
||
// the rest of the level, and a body that crabs converges on nothing.
|
||
let cfg = WalkerConfig::for_style(BobStyle::Doom);
|
||
let level = room(32.0, 6.0);
|
||
let grid = NavGrid::build(&level, &cfg);
|
||
let goal = grid.cell_at(vec3f(0.0, 0.0, -6.0)).expect("walkable");
|
||
let mut w = LevelWalker::new(vec3f(0.0, 0.0, 0.0), 0.0, cfg, 3);
|
||
w.set_external_planner(true);
|
||
w.set_route(vec![goal]);
|
||
w.tick_in(1.0 / 60.0, &level, Some(&grid));
|
||
// Arm it the way the watchdog does.
|
||
w.nav.as_mut().expect("nav state").slide = -0.6;
|
||
w.set_route(vec![goal]);
|
||
assert_eq!(
|
||
w.nav.as_ref().expect("nav state").slide,
|
||
0.0,
|
||
"a fresh route must not inherit the last one's slide offset"
|
||
);
|
||
// And the body converges on it.
|
||
let goal_pos = grid.cell(goal).expect("cell").pos;
|
||
let mut best = f32::MAX;
|
||
for _ in 0..60 * 8 {
|
||
w.tick_in(1.0 / 60.0, &level, Some(&grid));
|
||
let feet = w.feet();
|
||
best = best
|
||
.min(((feet.x - goal_pos.x).powi(2) + (feet.z - goal_pos.z).powi(2)).sqrt());
|
||
}
|
||
assert!(
|
||
best < grid.cell_size(),
|
||
"a crabbing body never converges: closest approach {best:.2} m"
|
||
);
|
||
}
|
||
}
|
||
|
||
#[cfg(test)]
|
||
mod level_vehicle_tests {
|
||
use super::*;
|
||
|
||
fn quad(p: &mut Vec<Vec3f>, i: &mut Vec<u32>, a: Vec3f, b: Vec3f, c: Vec3f, d: Vec3f) {
|
||
let n = p.len() as u32;
|
||
p.extend_from_slice(&[a, b, c, d]);
|
||
i.extend_from_slice(&[n, n + 1, n + 2, n, n + 2, n + 3]);
|
||
}
|
||
|
||
fn floor(p: &mut Vec<Vec3f>, i: &mut Vec<u32>, x0: f32, x1: f32, z0: f32, z1: f32, y: f32) {
|
||
quad(p, i, vec3f(x0, y, z0), vec3f(x1, y, z0), vec3f(x1, y, z1), vec3f(x0, y, z1));
|
||
}
|
||
|
||
/// Wall in the x/y plane at `z`, spanning x0..x1, y0..y1.
|
||
fn wall_z(p: &mut Vec<Vec3f>, i: &mut Vec<u32>, x0: f32, x1: f32, z: f32, y0: f32, y1: f32) {
|
||
quad(p, i, vec3f(x0, y0, z), vec3f(x1, y0, z), vec3f(x1, y1, z), vec3f(x0, y1, z));
|
||
}
|
||
|
||
/// A room 8×8, floor 0, ceiling `roof`, with a doorway in the z=0 wall:
|
||
/// opening x -1..1, lintel from `door_h` up to the ceiling. Room extends
|
||
/// z 0..8; open ground z<0.
|
||
fn doorway_room(roof: f32, door_h: f32) -> LevelCollision {
|
||
let (mut p, mut i) = (Vec::new(), Vec::new());
|
||
floor(&mut p, &mut i, -8.0, 8.0, -8.0, 8.0, 0.0);
|
||
floor(&mut p, &mut i, -4.0, 4.0, 0.0, 8.0, roof);
|
||
// The z=0 wall around the opening.
|
||
wall_z(&mut p, &mut i, -4.0, -1.0, 0.0, 0.0, roof);
|
||
wall_z(&mut p, &mut i, 1.0, 4.0, 0.0, 0.0, roof);
|
||
wall_z(&mut p, &mut i, -1.0, 1.0, 0.0, door_h, roof); // lintel
|
||
// Enclosing walls: sides at x ±4, far wall at z 8.
|
||
quad(
|
||
&mut p,
|
||
&mut i,
|
||
vec3f(-4.0, 0.0, 0.0),
|
||
vec3f(-4.0, 0.0, 8.0),
|
||
vec3f(-4.0, roof, 8.0),
|
||
vec3f(-4.0, roof, 0.0),
|
||
);
|
||
quad(
|
||
&mut p,
|
||
&mut i,
|
||
vec3f(4.0, 0.0, 0.0),
|
||
vec3f(4.0, 0.0, 8.0),
|
||
vec3f(4.0, roof, 8.0),
|
||
vec3f(4.0, roof, 0.0),
|
||
);
|
||
wall_z(&mut p, &mut i, -4.0, 4.0, 8.0, 0.0, roof);
|
||
LevelCollision::from_positions(p, i)
|
||
}
|
||
|
||
#[test]
|
||
fn ray_hit_reports_distance_and_a_normal_facing_the_ray() {
|
||
let level = doorway_room(3.0, 2.0);
|
||
let (t, n) = level
|
||
.ray_hit(vec3f(2.0, 1.0, 2.0), vec3f(0.0, 0.0, -1.0), 10.0)
|
||
.expect("the z=0 wall is 2 m away");
|
||
assert!((t - 2.0).abs() < 1.0e-3, "distance {t}");
|
||
assert!(n.z > 0.99, "normal {n:?} must face back along the ray");
|
||
// Up into the ceiling.
|
||
let (t, n) = level
|
||
.ray_hit(vec3f(0.0, 1.0, 4.0), vec3f(0.0, 1.0, 0.0), 10.0)
|
||
.expect("ceiling above");
|
||
assert!((t - 2.0).abs() < 1.0e-3, "ceiling distance {t}");
|
||
assert!(n.y < -0.99, "ceiling normal {n:?} pushes down");
|
||
}
|
||
|
||
#[test]
|
||
fn ground_under_stands_a_body_on_the_floor_not_the_ceiling() {
|
||
let level = doorway_room(3.0, 2.0);
|
||
// Inside the room, spawned mid-air: the room's floor, though the
|
||
// ceiling is a nearer surface for a probe from the sky.
|
||
assert_eq!(level.ground_under(0.0, 4.0, 1.2, 1.0), Some(0.0));
|
||
// Spawned above the roof: the roof is standable from up there.
|
||
assert_eq!(level.ground_under(0.0, 4.0, 3.5, 1.0), Some(3.0));
|
||
}
|
||
|
||
#[test]
|
||
fn ground_under_lifts_a_body_buried_under_a_raised_floor() {
|
||
// Two slabs: ground at 0 (z<0 half) — modelled by a low slab — and a
|
||
// raised floor at 1.5 with headroom above.
|
||
let (mut p, mut i) = (Vec::new(), Vec::new());
|
||
floor(&mut p, &mut i, -4.0, 4.0, -4.0, 4.0, 1.5);
|
||
floor(&mut p, &mut i, -4.0, 4.0, -4.0, 4.0, 4.0); // ceiling
|
||
let level = LevelCollision::from_positions(p, i);
|
||
// A car spawned at y 0.6 under the 1.5 floor belongs ON that floor.
|
||
assert_eq!(level.ground_under(0.0, 0.0, 0.6, 1.0), Some(1.5));
|
||
}
|
||
|
||
#[test]
|
||
fn room_at_measures_headroom_and_span() {
|
||
let level = doorway_room(3.0, 2.0);
|
||
let (headroom, span) = level.room_at(vec3f(0.0, 0.5, 4.0)).expect("indoors");
|
||
assert!((headroom - 3.0).abs() < 0.05, "headroom {headroom}");
|
||
// Walls at x ±4 bound the narrowest axis (the z probe escapes
|
||
// through the doorway to open ground).
|
||
assert!((span - 8.0).abs() < 0.5, "span {span} should be the 8 m width");
|
||
// Outside: no ceiling, no measurement.
|
||
assert!(level.room_at(vec3f(6.0, 0.5, 4.0)).is_none());
|
||
}
|
||
|
||
#[test]
|
||
fn a_body_taller_than_the_door_cannot_pass_a_shorter_one_can() {
|
||
let level = doorway_room(3.0, 2.0);
|
||
// A footprint sweep straight through the doorway, x -0.6..0.6.
|
||
let moves: Vec<(Vec3f, Vec3f)> = [-0.6f32, 0.0, 0.6]
|
||
.iter()
|
||
.map(|&x| (vec3f(x, 0.0, -2.0), vec3f(x, 0.0, 2.0)))
|
||
.collect();
|
||
// 1.4 m tall body: knee, waist, roof rays all under the 2 m lintel.
|
||
assert!(
|
||
!level.moves_blocked(&moves, 0.0, &[0.4, 0.8, 1.3]),
|
||
"a 1.4 m body must fit a 2 m doorway"
|
||
);
|
||
// 2.4 m tall body: the roof ray meets the lintel.
|
||
assert!(
|
||
level.moves_blocked(&moves, 0.0, &[0.4, 1.2, 2.3]),
|
||
"a 2.4 m body must be stopped by the 2 m lintel"
|
||
);
|
||
// Off to the side, any height meets the wall.
|
||
let side = [(vec3f(2.5, 0.0, -2.0), vec3f(2.5, 0.0, 2.0))];
|
||
assert!(level.moves_blocked(&side, 0.0, &[0.4, 1.2]), "the wall blocks");
|
||
}
|
||
}
|