neurodoom 0.6.7

// BSP / blockmap traversal runs per-tick per-entity and per-hitscan;
// indices into `map.sectors`, `map.lines`, `map.sides`, `map.subsectors`,
// `map.nodes` are guaranteed in-bounds by the map loader's own validation
// (load_* fns bounds-check every index before pushing). See rationale in
// src/render/mod.rs for the global policy.
#![allow(clippy::indexing_slicing)]

//! Entity motion, collision, sight-line checks, and BSP / blockmap
//! queries. Stateless free functions on `&mut Entity` + `&MapData`,
//! usable from any [`crate::rules::GameRules`] implementation.

use crate::game_data::MobjFlag;
use crate::map::{BlockMap, Line, MapData, BOXBOTTOM, BOXLEFT, BOXRIGHT, BOXTOP};
use crate::math::*;
use crate::world::Entity;

// --- Constants ---

/// Maximum movement per tic before splitting into substeps.
pub const MAXMOVE: Fixed = 30 * FRACUNIT;

/// Maximum step height a thing can walk up.
pub const MAXSTEPHEIGHT: Fixed = 24 * FRACUNIT;

/// Maximum safe dropoff height.
pub const MAXDROPOFF: Fixed = 24 * FRACUNIT;

/// Gravity acceleration per tic.
pub const GRAVITY: Fixed = FRACUNIT;

/// Friction multiplier per tic (~0.91 in fixed-point).
pub const FRICTION: Fixed = 0xe800;

/// Speed threshold below which momentum is zeroed.
pub const STOPSPEED: Fixed = 0x1000;

/// Shift to convert world coords → blockmap coords.
// Re-export from map.rs — single source of truth
pub use crate::map::MAPBLOCKSHIFT;

/// Result from check_position.
pub struct CheckResult {
    pub ok: bool,
    pub floor_z: Fixed,
    pub ceiling_z: Fixed,
    pub dropoff_z: Fixed,
}

/// Check if a thing with given radius can occupy position (x, y).
/// Only checks against map geometry (lines), not other things.
pub fn check_position(map: &MapData, radius: Fixed, x: Fixed, y: Fixed) -> CheckResult {
    let bbox = [
        y + radius, // top
        y - radius, // bottom
        x - radius, // left
        x + radius, // right
    ];

    let (floor_z, ceiling_z) = find_sector_heights(map, x, y);
    let mut result = CheckResult {
        ok: true,
        floor_z,
        ceiling_z,
        dropoff_z: floor_z,
    };

    let bm = &map.blockmap;
    let xl = world_to_block(bbox[BOXLEFT] - bm.origin_x);
    let xh = world_to_block(bbox[BOXRIGHT] - bm.origin_x);
    let yl = world_to_block(bbox[BOXBOTTOM] - bm.origin_y);
    let yh = world_to_block(bbox[BOXTOP] - bm.origin_y);

    for bx in xl..=xh {
        for by in yl..=yh {
            for line_idx in blockmap_lines(bm, bx, by) {
                if !check_line(map, &bbox, &map.lines[line_idx], &mut result) {
                    result.ok = false;
                    return result;
                }
            }
        }
    }

    result
}

/// Attempt to move an entity to (x, y). Returns true if successful.
pub fn try_move(entity: &mut Entity, map: &MapData, x: Fixed, y: Fixed) -> bool {
    if entity.flags.contains(MobjFlag::NoClip) {
        entity.x = x;
        entity.y = y;
        let (fz, cz) = find_sector_heights(map, x, y);
        entity.floor_z = fz;
        entity.ceiling_z = cz;
        return true;
    }

    let result = check_position(map, entity.radius, x, y);

    if !result.ok { return false; }
    if result.ceiling_z - result.floor_z < entity.height { return false; }
    if !entity.flags.contains(MobjFlag::Teleport) && result.floor_z - entity.z > MAXSTEPHEIGHT {
        return false;
    }
    if !entity.flags.intersects(MobjFlag::Dropoff | MobjFlag::Float)
        && result.floor_z - result.dropoff_z > MAXDROPOFF
    {
        return false;
    }

    entity.x = x;
    entity.y = y;
    entity.floor_z = result.floor_z;
    entity.ceiling_z = result.ceiling_z;
    true
}

/// Apply XY momentum to an entity, handling collision and friction.
pub fn xy_movement(entity: &mut Entity, map: &MapData) {
    if entity.momx == 0 && entity.momy == 0 { return; }

    let mut xmove = entity.momx.clamp(-MAXMOVE, MAXMOVE);
    let mut ymove = entity.momy.clamp(-MAXMOVE, MAXMOVE);

    loop {
        let (px, py) = if xmove.abs() > MAXMOVE / 2 || ymove.abs() > MAXMOVE / 2 {
            let px = entity.x + xmove / 2;
            let py = entity.y + ymove / 2;
            xmove /= 2;
            ymove /= 2;
            (px, py)
        } else {
            let px = entity.x + xmove;
            let py = entity.y + ymove;
            xmove = 0;
            ymove = 0;
            (px, py)
        };

        if !try_move(entity, map, px, py) {
            // Wall sliding: try moving along each axis independently
            if try_move(entity, map, px, entity.y) {
                entity.momy = 0; // blocked in Y, slide along X
            } else if try_move(entity, map, entity.x, py) {
                entity.momx = 0; // blocked in X, slide along Y
            } else {
                entity.momx = 0;
                entity.momy = 0;
                return;
            }
            // Slide resolved; any remaining xmove/ymove is discarded.
            break;
        }

        if xmove == 0 && ymove == 0 { break; }
    }

    // Friction (only when on ground)
    if entity.z > entity.floor_z { return; }
    let speed = fixed_mul(entity.momx, entity.momx) + fixed_mul(entity.momy, entity.momy);
    if speed < fixed_mul(STOPSPEED, STOPSPEED) {
        entity.momx = 0;
        entity.momy = 0;
    } else {
        entity.momx = fixed_mul(entity.momx, FRICTION);
        entity.momy = fixed_mul(entity.momy, FRICTION);
    }
}

/// Apply Z movement (gravity, floor/ceiling clamping).
pub fn z_movement(entity: &mut Entity) {
    if !entity.flags.contains(MobjFlag::NoGravity) {
        if entity.momz == 0 {
            entity.momz = -GRAVITY * 2;
        } else {
            entity.momz -= GRAVITY;
        }
    }

    entity.z += entity.momz;

    if entity.z <= entity.floor_z {
        if entity.momz < 0 { entity.momz = 0; }
        entity.z = entity.floor_z;
    }

    if entity.z + entity.height > entity.ceiling_z {
        if entity.momz > 0 { entity.momz = 0; }
        entity.z = entity.ceiling_z - entity.height;
    }
}

// --- Line of sight ---

/// Check if a straight line between two points is unobstructed.
/// Uses the REJECT table for quick rejection, then BSP traversal.
/// `z1`/`z2` are eye heights, `h2` is the target's full height.
#[allow(clippy::too_many_arguments)] // geometric args don't cluster naturally
pub fn check_sight(
    map: &MapData,
    x1: Fixed, y1: Fixed, z1: Fixed,
    x2: Fixed, y2: Fixed, z2: Fixed, h2: Fixed,
) -> bool {
    // Quick REJECT table lookup
    let ss1 = find_subsector(map, x1, y1);
    let ss2 = find_subsector(map, x2, y2);
    if ss1 < map.subsectors.len() && ss2 < map.subsectors.len() {
        let s1 = map.subsectors[ss1].sector as usize;
        let s2 = map.subsectors[ss2].sector as usize;
        let num_sectors = map.sectors.len();
        let pnum = s1 * num_sectors + s2;
        let byte = pnum >> 3;
        let bit = 1 << (pnum & 7);
        if byte < map.reject.len() && (map.reject[byte] & bit) != 0 {
            return false; // REJECT says no LOS possible
        }
    }

    // Set up sight trace
    let dx = x2 - x1;
    let dy = y2 - y1;
    let eye_z = z1;
    let mut top_slope = (z2 + h2) - eye_z;
    let mut bottom_slope = z2 - eye_z;

    // Traverse BSP
    cross_bsp_node(
        map,
        map.root_node(),
        x1, y1, dx, dy,
        x2, y2,
        eye_z,
        &mut top_slope,
        &mut bottom_slope,
    )
}

/// Which side of a dividing line (x, y, dx, dy) is point (px, py) on?
/// Returns 0 (front), 1 (back), or 2 (on).
fn divline_side(px: Fixed, py: Fixed, x: Fixed, y: Fixed, dx: Fixed, dy: Fixed) -> i32 {
    if dx == 0 {
        if px == x { return 2; }
        return if (px <= x) == (dy > 0) { 1 } else { 0 };
    }
    if dy == 0 {
        if py == y { return 2; }
        return if (py <= y) == (dx < 0) { 1 } else { 0 };
    }
    let ldx = (px - x) as i64;
    let ldy = (py - y) as i64;
    let left = (dy >> FRACBITS) as i64 * ldx;
    let right = ldy * (dx >> FRACBITS) as i64;
    if right < left { 0 } else if left == right { 2 } else { 1 }
}

/// Fractional intercept point along the trace line where it crosses divl.
#[allow(clippy::too_many_arguments)] // 2 parametric lines, 4 scalars each
fn sight_intercept(
    trace_x: Fixed, trace_y: Fixed, trace_dx: Fixed, trace_dy: Fixed,
    divl_x: Fixed, divl_y: Fixed, divl_dx: Fixed, divl_dy: Fixed,
) -> Fixed {
    let den = fixed_mul(divl_dy >> 8, trace_dx) - fixed_mul(divl_dx >> 8, trace_dy);
    if den == 0 { return 0; }
    let num = fixed_mul((divl_x - trace_x) >> 8, divl_dy)
            + fixed_mul((trace_y - divl_y) >> 8, divl_dx);
    fixed_div(num, den)
}

/// Check all segs in a subsector for sight blockage.
#[allow(clippy::too_many_arguments)] // mirrors P_CrossSubsector from Doom source
fn cross_subsector(
    map: &MapData,
    ssnum: usize,
    trace_x: Fixed, trace_y: Fixed, trace_dx: Fixed, trace_dy: Fixed,
    t2x: Fixed, t2y: Fixed,
    eye_z: Fixed,
    top_slope: &mut Fixed,
    bottom_slope: &mut Fixed,
) -> bool {
    let sub = &map.subsectors[ssnum];
    let first = sub.first_line as usize;
    let count = sub.num_lines as usize;

    for i in first..first + count {
        if i >= map.segs.len() { break; }
        let seg = &map.segs[i];
        let line = &map.lines[seg.line as usize];

        let v1 = &map.vertexes[line.v1 as usize];
        let v2 = &map.vertexes[line.v2 as usize];

        // Check if trace crosses this seg
        let s1 = divline_side(v1.x, v1.y, trace_x, trace_y, trace_dx, trace_dy);
        let s2 = divline_side(v2.x, v2.y, trace_x, trace_y, trace_dx, trace_dy);
        if s1 == s2 { continue; } // line isn't crossed

        let ldx = v2.x - v1.x;
        let ldy = v2.y - v1.y;
        let s1b = divline_side(trace_x, trace_y, v1.x, v1.y, ldx, ldy);
        let s2b = divline_side(t2x, t2y, v1.x, v1.y, ldx, ldy);
        if s1b == s2b { continue; } // trace doesn't actually cross

        // One-sided line blocks sight
        let Some(back_id) = line.back_sector else {
            return false;
        };

        // Two-sided: check opening
        let front = &map.sectors[line.front_sector as usize];
        let back = &map.sectors[back_id as usize];

        // No height difference = no occluder
        if front.floor_height == back.floor_height
            && front.ceiling_height == back.ceiling_height
        {
            continue;
        }

        let opentop = front.ceiling_height.min(back.ceiling_height);
        let openbottom = front.floor_height.max(back.floor_height);

        // Totally closed door
        if openbottom >= opentop {
            return false;
        }

        let frac = sight_intercept(
            trace_x, trace_y, trace_dx, trace_dy,
            v1.x, v1.y, ldx, ldy,
        );
        if frac <= 0 { continue; }

        if front.floor_height != back.floor_height {
            let slope = fixed_div(openbottom - eye_z, frac);
            if slope > *bottom_slope {
                *bottom_slope = slope;
            }
        }
        if front.ceiling_height != back.ceiling_height {
            let slope = fixed_div(opentop - eye_z, frac);
            if slope < *top_slope {
                *top_slope = slope;
            }
        }

        if *top_slope <= *bottom_slope {
            return false;
        }
    }

    true
}

/// Recursively traverse BSP nodes to check sight.
#[allow(clippy::too_many_arguments)] // mirrors P_CrossBSPNode from Doom source
fn cross_bsp_node(
    map: &MapData,
    bspnum: u16,
    trace_x: Fixed, trace_y: Fixed, trace_dx: Fixed, trace_dy: Fixed,
    t2x: Fixed, t2y: Fixed,
    eye_z: Fixed,
    top_slope: &mut Fixed,
    bottom_slope: &mut Fixed,
) -> bool {
    if bspnum & crate::map::NF_SUBSECTOR != 0 {
        let ssnum = if bspnum == 0xFFFF { 0 } else { (bspnum & !crate::map::NF_SUBSECTOR) as usize };
        return cross_subsector(
            map, ssnum,
            trace_x, trace_y, trace_dx, trace_dy,
            t2x, t2y, eye_z, top_slope, bottom_slope,
        );
    }

    let node = &map.nodes[bspnum as usize];
    let side = divline_side(trace_x, trace_y, node.x, node.y, node.dx, node.dy);
    let side = if side == 2 { 0 } else { side as usize };

    // Cross the starting side
    if !cross_bsp_node(
        map, node.children[side],
        trace_x, trace_y, trace_dx, trace_dy,
        t2x, t2y, eye_z, top_slope, bottom_slope,
    ) {
        return false;
    }

    // If t2 is on the same side, no need to cross the other
    let other_side = divline_side(t2x, t2y, node.x, node.y, node.dx, node.dy);
    if other_side == 2 || other_side == side as i32 {
        return true;
    }

    // Cross the ending side
    cross_bsp_node(
        map, node.children[side ^ 1],
        trace_x, trace_y, trace_dx, trace_dy,
        t2x, t2y, eye_z, top_slope, bottom_slope,
    )
}

// --- Internal helpers ---

/// Convert world coordinate to blockmap index.
fn world_to_block(coord: Fixed) -> i32 {
    coord >> MAPBLOCKSHIFT
}

/// Find the subsector index at a world position using BSP lookup.
pub fn find_subsector(map: &MapData, x: Fixed, y: Fixed) -> usize {
    let mut node_id = map.root_node();
    loop {
        if node_id & crate::map::NF_SUBSECTOR != 0 {
            return if node_id == 0xFFFF {
                0
            } else {
                (node_id & !crate::map::NF_SUBSECTOR) as usize
            };
        }
        let node = &map.nodes[node_id as usize];
        let side = crate::render::bsp::point_on_side(x, y, node.x, node.y, node.dx, node.dy);
        node_id = node.children[side];
    }
}

/// Find floor and ceiling heights at a world position using BSP lookup.
#[inline]
pub fn find_sector_heights(map: &MapData, x: Fixed, y: Fixed) -> (Fixed, Fixed) {
    let ssect = find_subsector(map, x, y);
    if ssect < map.subsectors.len() {
        let sector = &map.sectors[map.subsectors[ssect].sector as usize];
        (sector.floor_height, sector.ceiling_height)
    } else {
        (0, 128 * FRACUNIT)
    }
}

/// Zero-allocation iterator over line indices in a blockmap cell.
struct BlockmapLineIter<'a> {
    lists: &'a [u16],
    offset: usize,
}

impl Iterator for BlockmapLineIter<'_> {
    type Item = usize;
    #[inline]
    fn next(&mut self) -> Option<usize> {
        if self.offset >= self.lists.len() {
            return None;
        }
        let val = self.lists[self.offset];
        if val == 0xFFFF {
            return None;
        }
        self.offset += 1;
        Some(val as usize)
    }
}

fn blockmap_lines(bm: &BlockMap, bx: i32, by: i32) -> BlockmapLineIter<'_> {
    if bx < 0 || by < 0 || bx as usize >= bm.width || by as usize >= bm.height {
        return BlockmapLineIter { lists: &[], offset: 0 };
    }
    let block_idx = by as usize * bm.width + bx as usize;
    if block_idx >= bm.offsets.len() {
        return BlockmapLineIter { lists: &[], offset: 0 };
    }
    let mut offset = bm.offsets[block_idx] as usize;
    // Skip the header (first entry is often 0)
    if offset < bm.lists.len() && bm.lists[offset] == 0 {
        offset += 1;
    }
    BlockmapLineIter { lists: &bm.lists, offset }
}

/// Check a single line against a moving thing's bounding box.
/// Updates result floor/ceiling/dropoff. Returns false if blocked.
fn check_line(
    map: &MapData,
    bbox: &[Fixed; 4],
    line: &Line,
    result: &mut CheckResult,
) -> bool {
    // Quick bounding box rejection
    if bbox[BOXRIGHT] <= line.bbox[BOXLEFT]
        || bbox[BOXLEFT] >= line.bbox[BOXRIGHT]
        || bbox[BOXTOP] <= line.bbox[BOXBOTTOM]
        || bbox[BOXBOTTOM] >= line.bbox[BOXTOP]
    {
        return true;
    }

    // P_BoxOnLineSide: returns -1 if box straddles line, else 0 or 1
    if box_on_line_side(bbox, line, map) != -1 {
        return true; // box entirely on one side — line doesn't block
    }

    // One-sided line: always blocks
    let Some(back_id) = line.back_sector else {
        return false;
    };

    // ML_BLOCKING (flag 0x0001): line blocks all movement (e.g. windows, railings)
    if line.flags & 0x0001 != 0 {
        return false;
    }

    // Two-sided line: compute opening
    let front = &map.sectors[line.front_sector as usize];
    let back = &map.sectors[back_id as usize];

    let opentop = front.ceiling_height.min(back.ceiling_height);
    let openbottom = front.floor_height.max(back.floor_height);
    let lowfloor = front.floor_height.min(back.floor_height);

    if opentop < result.ceiling_z {
        result.ceiling_z = opentop;
    }
    if openbottom > result.floor_z {
        result.floor_z = openbottom;
    }
    if lowfloor < result.dropoff_z {
        result.dropoff_z = lowfloor;
    }

    true
}

/// Doom's P_PointOnLineSide: which side of a linedef is a point on?
/// Returns 0 (front) or 1 (back).
fn point_on_line_side(x: Fixed, y: Fixed, line: &Line, map: &MapData) -> i32 {
    let v1 = &map.vertexes[line.v1 as usize];

    if line.dx == 0 {
        return if x <= v1.x {
            if line.dy > 0 { 1 } else { 0 }
        } else if line.dy < 0 {
            1
        } else {
            0
        };
    }
    if line.dy == 0 {
        return if y <= v1.y {
            if line.dx < 0 { 1 } else { 0 }
        } else if line.dx > 0 {
            1
        } else {
            0
        };
    }

    let dx = x - v1.x;
    let dy = y - v1.y;
    let left = fixed_mul(line.dy >> FRACBITS, dx);
    let right = fixed_mul(dy, line.dx >> FRACBITS);
    if right < left { 0 } else { 1 }
}

/// Doom's P_BoxOnLineSide: returns 0, 1, or -1 (straddles).
fn box_on_line_side(bbox: &[Fixed; 4], line: &Line, map: &MapData) -> i32 {
    let v1 = &map.vertexes[line.v1 as usize];
    let (p1, p2) = match line.slope_type {
        crate::map::SlopeType::Horizontal => {
            let mut p1 = (bbox[BOXTOP] > v1.y) as i32;
            let mut p2 = (bbox[BOXBOTTOM] > v1.y) as i32;
            if line.dx < 0 {
                p1 ^= 1;
                p2 ^= 1;
            }
            (p1, p2)
        }
        crate::map::SlopeType::Vertical => {
            let mut p1 = (bbox[BOXRIGHT] < v1.x) as i32;
            let mut p2 = (bbox[BOXLEFT] < v1.x) as i32;
            if line.dy < 0 {
                p1 ^= 1;
                p2 ^= 1;
            }
            (p1, p2)
        }
        crate::map::SlopeType::Positive => {
            let p1 = point_on_line_side(bbox[BOXLEFT], bbox[BOXTOP], line, map);
            let p2 = point_on_line_side(bbox[BOXRIGHT], bbox[BOXBOTTOM], line, map);
            (p1, p2)
        }
        crate::map::SlopeType::Negative => {
            let p1 = point_on_line_side(bbox[BOXRIGHT], bbox[BOXTOP], line, map);
            let p2 = point_on_line_side(bbox[BOXLEFT], bbox[BOXBOTTOM], line, map);
            (p1, p2)
        }
    };

    if p1 == p2 { p1 } else { -1 }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn world_to_block_conversion() {
        // 128 map units = 1 block
        assert_eq!(world_to_block(0), 0);
        assert_eq!(world_to_block(128 << FRACBITS), 1);
        assert_eq!(world_to_block(256 << FRACBITS), 2);
    }
}