Something went wrong. Try again.
HEXWORK - A Lantern in the Deep: 3D ASCII terminal roguelike RPG in Rust.
Entirely designed and built by Muse Spark 1.3 to evaluate if I like the model.
Something went wrong. Try again.
20 kB · 558 lines
Rust
at main
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559//! Fixed-point DDA raycaster over [`ChunkedGrid`] (docs/05 §5.2 step 2).//!//! One ray per cell column-half (docs/05 §5.2 step 2: `w` rays × `2h`//! half-block samples); traversal is Amanatides & Woo DDA with integer//! stepping, so identical inputs give identical hits on every platform.//!//! # Determinism contract (docs/04 §4.10 rule 2)//! - Voxel traversal is pure integer math on Q10 fixed-point positions//! ([`FP_SCALE`] = 1024 units per voxel). No RNG, no hash maps, no//! platform-dependent iteration order.//! - `f32` appears only at the boundary: direction normalization, the//! final `dist` conversion, and [`ray_dir`] trigonometry (`sqrt`,//! `sin_cos`, `tan`). Those can differ by 1 ulp across libm builds, so//! `dist` is **display-only: never hash it**. Screenshot hashes pin//! pixels, which quantize through the density ramp. Hit voxel, face,//! and material are bit-exact for identical inputs.//! - Solid means `material != AIR`. Unloaded chunks read as AIR via//! [`ChunkedGrid::get_world`], i.e. a miss — never a wall. Callers that//! must distinguish "empty" from "unknown" check//! [`ChunkedGrid::is_loaded`] themselves.
use hexwork_core::voxel::{material::AIR, ChunkedGrid};
/// Fixed-point scale: 1024 integer units per voxel (Q10).////// Sub-voxel resolution is ~1/1024 voxel; `dist` quantization error is/// bounded by 1/1024 voxel plus one rounding step (docs/05 §5.2: "no/// float drift, deterministic screenshots").const FP_SCALE: i64 = 1024;
/// Stand-in `tMax`/`tDelta` for an axis with zero direction: that axis is/// never stepped.const FP_INF: i64 = i64::MAX / 4;
/// Which voxel face a ray entered through (docs/05 §5.2 step 3: DDA gives/// the normal free — it is the axis of the last step).////// Convention: `XNeg` is the face on the voxel's negative-X side (outward/// normal −X). A ray stepping in +X enters through `XNeg`; a ray stepping/// in −X enters through `XPos`. Same rule for Y/Z.#[derive(Clone, Copy, Debug, PartialEq, Eq)]pub enum Face { XNeg, XPos, YNeg, YPos, ZNeg, ZPos,}
/// A primary-ray hit: voxel address, entry face, material, and display/// distance (docs/05 §5.2 step 3).#[derive(Clone, Copy, Debug, PartialEq)]pub struct RayHit { /// Distance along the ray in world units (display-only, never hashed; /// see the module-level determinism contract). pub dist: f32, /// Hit voxel coordinates. pub x: i32, /// Hit voxel coordinates. pub y: i32, /// Hit voxel coordinates. pub z: i32, /// Face the ray entered through (axis of the last DDA step). pub face: Face, /// Voxel material id (`hexwork_core::voxel::material`), never AIR. pub material: u8,}
/// Face entered when stepping along `axis` (0/1/2 = X/Y/Z) with the given/// nonzero `step` direction.fn entry_face(axis: usize, step: i32) -> Face { match (axis, step > 0) { (0, true) => Face::XNeg, (0, false) => Face::XPos, (1, true) => Face::YNeg, (1, false) => Face::YPos, (_, true) => Face::ZNeg, (_, false) => Face::ZPos, }}
/// Material at integer voxel `v`; out-of-`i32`-range reads as AIR (miss).fn voxel_material(grid: &ChunkedGrid, v: [i64; 3]) -> u8 { let x = i32::try_from(v[0]).ok(); let y = i32::try_from(v[1]).ok(); let z = i32::try_from(v[2]).ok(); match (x, y, z) { (Some(x), Some(y), Some(z)) => grid.get_world(x, y, z).material, _ => AIR, }}
/// Cast a primary ray through `grid` (docs/05 §5.2 step 2).////// - `origin`/`dir` are world-space; `dir` need not be normalized (it is/// normalized once up front — an `f32` boundary op; traversal after/// that is integer)./// - `max_dist` is the per-quality-tier range (docs/05 §5.2: "max/// distance per quality tier"), a parameter — never a global. Hits/// past it are truncated to a miss./// - Fixed-point: positions × 1024 (`Q10`), integer DDA stepping;/// converted back to `f32` for `dist` only./// - Degenerate inputs (zero/NaN/non-finite direction or origin,/// non-positive or NaN `max_dist`) return `None` — never NaN, never a/// panic./// - A ray starting inside a solid voxel hits it at `dist == 0.0` with/// the face opposing the dominant ray axis (documented convention so/// the camera never sees through a wall it clips into).pub fn cast(grid: &ChunkedGrid, origin: [f32; 3], dir: [f32; 3], max_dist: f32) -> Option<RayHit> { if !max_dist.is_finite() || max_dist <= 0.0 { return None; } for v in origin.iter().chain(dir.iter()) { if !v.is_finite() { return None; } } let len_sq = dir[0] * dir[0] + dir[1] * dir[1] + dir[2] * dir[2]; if !len_sq.is_finite() || len_sq <= 0.0 { return None; } // f32 boundary: normalize once; everything below is integer. let len = len_sq.sqrt(); let dir_n = [dir[0] / len, dir[1] / len, dir[2] / len]; let dfp = [ (dir_n[0] * FP_SCALE as f32).round() as i64, (dir_n[1] * FP_SCALE as f32).round() as i64, (dir_n[2] * FP_SCALE as f32).round() as i64, ]; if dfp == [0, 0, 0] { return None; } let ofp = [ (origin[0] * FP_SCALE as f32).round() as i64, (origin[1] * FP_SCALE as f32).round() as i64, (origin[2] * FP_SCALE as f32).round() as i64, ]; let mut v = [ ofp[0].div_euclid(FP_SCALE), ofp[1].div_euclid(FP_SCALE), ofp[2].div_euclid(FP_SCALE), ];
// Origin inside solid: hit at zero with the face opposing the // dominant axis (see doc above). let mat0 = voxel_material(grid, v); if mat0 != AIR { let mut axis = 0; if dfp[1].abs() > dfp[axis].abs() { axis = 1; } if dfp[2].abs() > dfp[axis].abs() { axis = 2; } let step0: i32 = if dfp[axis] > 0 { 1 } else { -1 }; if let (Some(x), Some(y), Some(z)) = ( i32::try_from(v[0]).ok(), i32::try_from(v[1]).ok(), i32::try_from(v[2]).ok(), ) { return Some(RayHit { dist: 0.0, x, y, z, face: entry_face(axis, step0), material: mat0, }); } return None; }
let mut step = [0i32; 3]; let mut tmax = [0i64; 3]; let mut tdelta = [0i64; 3]; for (i, t) in tmax.iter_mut().enumerate() { let d = dfp[i]; if d > 0 { step[i] = 1; let frac = ofp[i].rem_euclid(FP_SCALE); *t = (FP_SCALE - frac) * FP_SCALE / d; tdelta[i] = FP_SCALE * FP_SCALE / d; } else if d < 0 { step[i] = -1; let frac = ofp[i].rem_euclid(FP_SCALE); // Exactly on a boundary heading negative: the shared face is // crossed at once (t == 0 step into the negative neighbor). *t = frac * FP_SCALE / (-d); tdelta[i] = FP_SCALE * FP_SCALE / (-d); } else { *t = FP_INF; tdelta[i] = FP_INF; } }
// Exact f32→f64 widening, ×1024 exact for sane ranges; saturates for // absurd ones. Compared against integer t: no drift. let max_fp = (f64::from(max_dist) * FP_SCALE as f64).round() as i64; // One DDA step crosses one voxel plane; within max_dist at most // 3×max_dist + slack planes are crossed. Hard cap guarantees // termination (docs/04 §4.10: no hangs in render paths). let cap: usize = ((3.0 * max_dist + 8.0) as usize).clamp(64, 2_000_000); let mut steps: usize = 0; loop { // Lowest axis index wins ties (X, then Y, then Z): deterministic // diagonal staircases, pinned by the diagonal test below. let mut axis = 0; if tmax[1] < tmax[axis] { axis = 1; } if tmax[2] < tmax[axis] { axis = 2; } let t = tmax[axis]; if t > max_fp { return None; } v[axis] += i64::from(step[axis]); tmax[axis] += tdelta[axis]; steps += 1; if steps > cap { return None; } let mat = voxel_material(grid, v); if mat != AIR { // Display-only conversion back to f32 (never hashed). let dist = t as f32 / FP_SCALE as f32; if dist > max_dist { return None; } if let (Some(x), Some(y), Some(z)) = ( i32::try_from(v[0]).ok(), i32::try_from(v[1]).ok(), i32::try_from(v[2]).ok(), ) { return Some(RayHit { dist, x, y, z, face: entry_face(axis, step[axis]), material: mat, }); } return None; } }}
/// Camera for one primary-ray per cell column-half (docs/05 §5.2 step 2).////// `w` × `h` are frame cells; each cell takes 2 vertical (half-block)/// samples, so [`ray_dir`] serves `w` × `2h` rays. `fov_deg` is the/// vertical field of view in degrees (motion-sickness law, docs/05/// §5.4.4: capped at 75°); `yaw`/`pitch` are radians — yaw 0 faces +X,/// positive yaw turns toward +Y, positive pitch looks up (+Z, matching/// the voxel convention that +Z is up).#[derive(Clone, Copy, Debug)]pub struct Frustum { pub w: usize, pub h: usize, pub fov_deg: f32, pub yaw: f32, pub pitch: f32,}
impl Frustum { /// Build a frustum, enforcing the 75° FOV cap (docs/05 §5.4.4) and /// nonzero dimensions eagerly. pub fn new(w: usize, h: usize, fov_deg: f32, yaw: f32, pitch: f32) -> Self { assert!( (0.0..=75.0).contains(&fov_deg), "FOV cap 75° (docs/05 §5.4.4 motion-sickness law)" ); assert!(w > 0 && h > 0, "frustum dimensions must be nonzero"); Self { w, h, fov_deg, yaw, pitch, } }}
/// Direction of the ray through column `px` (0..`w`) and half-row/// `py_half` (0..`2h`; `py_half == 0` is the top half-block row).////// Camera space is forward +X, right +Y, up +Z, pitched then yawed;/// result is unit-length. The horizontal half-FOV is derived from the/// vertical FOV and the sample aspect `w / 2h` (docs/05 §5.2 step 2)./// `f32` trig here is a display-path input: traversal downstream is/// integer (see the module determinism contract).pub fn ray_dir(f: &Frustum, px: usize, py_half: usize) -> [f32; 3] { assert!( (0.0..=75.0).contains(&f.fov_deg), "FOV cap 75° (docs/05 §5.4.4 motion-sickness law)" ); assert!(f.w > 0 && f.h > 0, "frustum dimensions must be nonzero"); debug_assert!(px < f.w, "column out of range"); debug_assert!(py_half < f.h * 2, "half-row out of range"); let w = f.w as f32; let h2 = (f.h * 2) as f32; let u = (px as f32 + 0.5) / w * 2.0 - 1.0; let vv = 1.0 - (py_half as f32 + 0.5) / h2 * 2.0; let half_tan = (f.fov_deg * std::f32::consts::PI / 360.0).tan(); let aspect = w / h2; let (sin_yaw, cos_yaw) = f.yaw.sin_cos(); let (sin_pitch, cos_pitch) = f.pitch.sin_cos(); // Camera space: forward +X, right +Y, up +Z. let cam = [1.0, u * half_tan * aspect, vv * half_tan]; // Pitch about the Y (lateral) axis, then yaw about Z (up). let x1 = cam[0] * cos_pitch - cam[2] * sin_pitch; let z1 = cam[0] * sin_pitch + cam[2] * cos_pitch; let x2 = x1 * cos_yaw - cam[1] * sin_yaw; let y2 = x1 * sin_yaw + cam[1] * cos_yaw; let inv = 1.0 / (x2 * x2 + y2 * y2 + z1 * z1).sqrt(); [x2 * inv, y2 * inv, z1 * inv]}
#[cfg(test)]mod tests { use super::*; use hexwork_core::voxel::{material, Voxel};
fn put(grid: &mut ChunkedGrid, x: i32, y: i32, z: i32, mat: u8) { grid.set_world( x, y, z, Voxel { material: mat, ..Voxel::default() }, ); }
/// Stone slab at x == 5, y/z in −8..=8. fn x_wall() -> ChunkedGrid { let mut grid = ChunkedGrid::new(); for y in -8..=8 { for z in -8..=8 { put(&mut grid, 5, y, z, material::STONE); } } grid }
fn approx(a: f32, b: f32) -> bool { (a - b).abs() <= 0.01 }
#[test] fn axis_aligned_hit_positive_x_face() { let grid = x_wall(); let hit = cast(&grid, [0.5, 0.5, 0.5], [1.0, 0.0, 0.0], 100.0).expect("ray must hit the slab"); assert_eq!((hit.x, hit.y, hit.z), (5, 0, 0)); assert_eq!(hit.face, Face::XNeg); assert_eq!(hit.material, material::STONE); assert!(approx(hit.dist, 4.5), "dist was {}", hit.dist); }
#[test] fn axis_aligned_hit_negative_x_face() { let grid = x_wall(); let hit = cast(&grid, [10.5, 0.5, 0.5], [-1.0, 0.0, 0.0], 100.0).expect("ray must hit the slab"); assert_eq!((hit.x, hit.y, hit.z), (5, 0, 0)); assert_eq!(hit.face, Face::XPos); assert!(approx(hit.dist, 4.5), "dist was {}", hit.dist); }
#[test] fn axis_aligned_hit_y_face() { let mut grid = ChunkedGrid::new(); for x in -8..=8 { for z in -8..=8 { put(&mut grid, x, 4, z, material::WOOD); } } let hit = cast(&grid, [0.5, 0.5, 0.5], [0.0, 1.0, 0.0], 100.0).expect("ray must hit the wall"); assert_eq!((hit.x, hit.y, hit.z), (0, 4, 0)); assert_eq!(hit.face, Face::YNeg); assert!(approx(hit.dist, 3.5), "dist was {}", hit.dist); }
#[test] fn axis_aligned_hit_top_face() { let mut grid = ChunkedGrid::new(); for x in -8..=8 { for y in -8..=8 { put(&mut grid, x, y, 0, material::IRON); } } let hit = cast(&grid, [0.5, 0.5, 5.5], [0.0, 0.0, -1.0], 100.0).expect("ray must hit the floor"); assert_eq!((hit.x, hit.y, hit.z), (0, 0, 0)); // Stepping −Z enters through the voxel's top (+Z) face. assert_eq!(hit.face, Face::ZPos); assert!(approx(hit.dist, 4.5), "dist was {}", hit.dist); }
#[test] fn diagonal_hit_staircase_face() { let mut grid = ChunkedGrid::new(); put(&mut grid, 3, 3, 0, material::BRASS); let hit = cast(&grid, [0.5, 0.5, 0.5], [1.0, 1.0, 0.0], 100.0) .expect("diagonal ray must hit the block"); assert_eq!((hit.x, hit.y, hit.z), (3, 3, 0)); // X-before-Y tie-break lands the last step on +Y. assert_eq!(hit.face, Face::YNeg); assert!( approx(hit.dist, 2.5 * std::f32::consts::SQRT_2), "dist was {}", hit.dist ); }
#[test] fn miss_through_loaded_air() { let mut grid = ChunkedGrid::new(); grid.activate(0, 0, 0); assert!(grid.is_loaded(0, 0, 0)); assert_eq!(cast(&grid, [0.5, 0.5, 0.5], [1.0, 0.0, 0.0], 40.0), None); }
#[test] fn unloaded_reads_as_air_miss() { let grid = ChunkedGrid::new(); assert!(!grid.is_loaded(0, 0, 0)); // Nothing is loaded anywhere on this ray: must be a miss, and the // grid must stay empty (no accidental chunk creation on read). assert_eq!( cast(&grid, [-100.5, 0.5, 0.5], [1.0, 0.3, 0.1], 500.0), None ); assert_eq!(grid.loaded_count(), 0); }
#[test] fn max_dist_truncates_hit() { let grid = x_wall(); assert_eq!(cast(&grid, [0.5, 0.5, 0.5], [1.0, 0.0, 0.0], 4.0), None); // Exact-boundary hit at 4.5 is kept (inclusive range). assert!(cast(&grid, [0.5, 0.5, 0.5], [1.0, 0.0, 0.0], 4.5).is_some()); assert!(cast(&grid, [0.5, 0.5, 0.5], [1.0, 0.0, 0.0], 100.0).is_some()); }
#[test] fn same_cast_twice_is_identical() { let grid = x_wall(); let a = cast(&grid, [0.5, 1.25, -0.75], [1.0, 0.2, -0.1], 60.0); let b = cast(&grid, [0.5, 1.25, -0.75], [1.0, 0.2, -0.1], 60.0); assert_eq!(a, b); let (a, b) = (a.expect("hit"), b.expect("hit")); assert_eq!(a.dist.to_bits(), b.dist.to_bits()); }
#[test] fn grazing_ray_keeps_axis_face() { let grid = x_wall(); // Nearly axis-aligned: the last step is still along X. let hit = cast(&grid, [0.5, 0.5, 0.5], [1.0, 0.001, 0.0], 100.0).expect("grazing ray must hit"); assert_eq!(hit.face, Face::XNeg); assert_eq!(hit.x, 5); // Origin exactly on a voxel boundary, heading +X: no panic, no // stuck step, still an X-face hit on the same row. let hit = cast(&grid, [0.5, 1.0, 0.5], [1.0, 0.0, 0.0], 100.0) .expect("boundary-origin ray must hit"); assert_eq!(hit.face, Face::XNeg); assert_eq!((hit.x, hit.y), (5, 1)); }
#[test] fn origin_inside_solid_hits_at_zero() { let mut grid = ChunkedGrid::new(); put(&mut grid, 2, 0, 0, material::STONE); let hit = cast(&grid, [2.5, 0.5, 0.5], [1.0, 0.0, 0.0], 100.0) .expect("inside-solid ray must report the voxel"); assert_eq!((hit.x, hit.y, hit.z), (2, 0, 0)); assert_eq!(hit.dist, 0.0); assert_eq!(hit.face, Face::XNeg); }
#[test] fn degenerate_inputs_return_none() { let grid = x_wall(); assert_eq!(cast(&grid, [0.5, 0.5, 0.5], [0.0, 0.0, 0.0], 100.0), None); assert_eq!( cast(&grid, [0.5, 0.5, 0.5], [f32::NAN, 0.0, 0.0], 100.0), None ); assert_eq!( cast(&grid, [f32::INFINITY, 0.5, 0.5], [1.0, 0.0, 0.0], 100.0), None ); assert_eq!(cast(&grid, [0.5, 0.5, 0.5], [1.0, 0.0, 0.0], 0.0), None); assert_eq!(cast(&grid, [0.5, 0.5, 0.5], [1.0, 0.0, 0.0], -5.0), None); assert_eq!( cast(&grid, [0.5, 0.5, 0.5], [1.0, 0.0, 0.0], f32::NAN), None ); // Sub-fixed-point direction still normalizes before quantization: // tiny but nonzero dirs behave like their unit direction. assert!(cast(&grid, [0.5, 0.5, 0.5], [1e-9, 0.0, 0.0], 100.0).is_some()); }
#[test] fn frustum_center_and_corners() { let f = Frustum::new(120, 36, 75.0, 0.0, 0.0); let norm = |d: [f32; 3]| (d[0] * d[0] + d[1] * d[1] + d[2] * d[2]).sqrt(); let center = ray_dir(&f, 60, 36); assert!((norm(center) - 1.0).abs() < 1e-4); assert!((center[0] - 1.0).abs() < 0.01, "center ray {center:?}"); // Vertical half-angle of the top/bottom-center rays stays within // half the vertical FOV (37.5°) plus a pixel of slack. for py in [0, 71] { let d = ray_dir(&f, 60, py); assert!((norm(d) - 1.0).abs() < 1e-4); let vert = d[2].abs().atan2(d[0]); assert!( vert.to_degrees() <= 38.5, "vertical half-angle {vert:?} at py {py}" ); } // Left/right corners are mirror-symmetric and normalized. let left = ray_dir(&f, 0, 36); let right = ray_dir(&f, 119, 36); assert!((norm(left) - 1.0).abs() < 1e-4); assert!((norm(right) - 1.0).abs() < 1e-4); assert!(left[1] < 0.0 && right[1] > 0.0); assert!((left[1] + right[1]).abs() < 1e-4, "{left:?} vs {right:?}"); // Top looks up, bottom looks down. assert!(ray_dir(&f, 60, 0)[2] > 0.0); assert!(ray_dir(&f, 60, 71)[2] < 0.0); // Yaw π/2 turns the center ray onto +Y. let turned = Frustum::new(120, 36, 75.0, std::f32::consts::FRAC_PI_2, 0.0); let d = ray_dir(&turned, 60, 36); assert!((d[1] - 1.0).abs() < 0.01, "yawed ray {d:?}"); }
#[test] #[should_panic(expected = "FOV cap")] fn fov_cap_enforced() { let f = Frustum { w: 120, h: 36, fov_deg: 90.0, yaw: 0.0, pitch: 0.0, }; let _ = ray_dir(&f, 60, 36); }}