//! Collision helpers: overlap tests for 2D shapes (v0.2 step 12). Pure
//! logic, no GPU, ungated.
//!
//! Scope (design doc, v0.2): "do these overlap, and by how much". Overlap
//! and the minimum translation vector are library code; RESPONSE (stop,
//! slide, bounce, trigger) stays in the game, because response is design,
//! not geometry. This is not a physics engine; forces, stacking, and
//! sweeps are rapier's job the day a game needs them.
//!
//! Conventions, decided once and tested below:
//!   * overlap is STRICT: touching edges is not overlapping (two tiles
//!     side by side share an edge all day and never collide; a resolved
//!     push lands exactly touching and stays clean next frame: no jitter)
//!   * containment is INCLUSIVE: a point on the edge is inside (clicking
//!     a sprite's outline counts)

use crate::math::Vec2;
use crate::transform::Transform;

/// An axis-aligned bounding box: the min corner and the max corner.
#[derive(Clone, Copy, Debug, PartialEq)]
pub struct Aabb {
    pub min: Vec2,
    pub max: Vec2,
}

#[derive(Clone, Copy, Debug, PartialEq)]
pub struct Circle {
    pub center: Vec2,
    pub radius: f32,
}

impl Aabb {
    pub fn from_min_max(min: Vec2, max: Vec2) -> Self {
        // A box with min > max is not "empty", it is a bug (usually a NaN
        // or a sign slip upstream). Loud in debug, free in release.
        debug_assert!(min.x <= max.x && min.y <= max.y, "Aabb: min must be <= max");
        Self { min, max }
    }

    /// The box you get from a Transform + a sprite size: a center and a size.
    pub fn from_center_size(center: Vec2, size: Vec2) -> Self {
        let half = size * 0.5;
        Self::from_min_max(center - half, center + half)
    }

    pub fn center(self) -> Vec2 {
        (self.min + self.max) * 0.5
    }

    pub fn half_extents(self) -> Vec2 {
        (self.max - self.min) * 0.5
    }

    /// Grown (or shrunk, with negative `by`) equally on every side. Handy
    /// for "am I NEAR the door" triggers around an existing box.
    pub fn expanded(self, by: f32) -> Self {
        Self::from_min_max(self.min - Vec2::splat(by), self.max + Vec2::splat(by))
    }
}

/// A sprite's world-space bounds. Note the seam: stored 3D, queried 2D.
/// `from_xy_size` parks the sprite's (w, h) in the transform's scale, and
/// translation is the top-left corner (Mawida's y-down 2D convention).
pub fn sprite_bounds(t: &Transform) -> Aabb {
    let pos = t.translation.truncate(); // Vec3 -> Vec2: 2D is z = 0, applied
    let size = t.scale.truncate(); // from_xy_size parked (w, h) here
    Aabb::from_min_max(pos, pos + size)
}

/// True when `a` and `b` overlap with positive area.
///
/// Convention (documented and tested): touching edges is NOT overlapping.
///
/// ```
/// use mawida::collide::{aabb_vs_aabb, Aabb};
/// use mawida::math::Vec2;
///
/// let a = Aabb::from_min_max(Vec2::ZERO, Vec2::new(2.0, 2.0));
/// let b = Aabb::from_min_max(Vec2::new(1.0, 1.0), Vec2::new(3.0, 3.0));
/// assert!(aabb_vs_aabb(a, b));
/// ```
pub fn aabb_vs_aabb(a: Aabb, b: Aabb) -> bool {
    a.min.x < b.max.x && b.min.x < a.max.x // x intervals overlap
        && a.min.y < b.max.y && b.min.y < a.max.y // y intervals overlap
}

/// The minimum translation vector: the smallest push that, added to `a`'s
/// position, separates it from `b`. `None` when they do not overlap.
///
/// Push along the SHALLOWER axis, away from `b`'s center: a player one
/// unit deep into a floor but overlapping it four units wide is pushed UP
/// by one, never sideways by four (the teleport bug).
pub fn aabb_penetration(a: Aabb, b: Aabb) -> Option<Vec2> {
    let dx = a.max.x.min(b.max.x) - a.min.x.max(b.min.x); // overlap depth, x
    let dy = a.max.y.min(b.max.y) - a.min.y.max(b.min.y); // overlap depth, y
    if dx <= 0.0 || dy <= 0.0 {
        return None; // separated (or just touching) on some axis
    }
    if dx < dy {
        let sign = if a.center().x < b.center().x { -1.0 } else { 1.0 };
        Some(Vec2::new(sign * dx, 0.0))
    } else {
        let sign = if a.center().y < b.center().y { -1.0 } else { 1.0 };
        Some(Vec2::new(0.0, sign * dy))
    }
}

/// True when the circles overlap with positive area. Touching is not
/// overlap. `distance_squared` avoids the square root: compare squared
/// lengths against the squared radius sum.
pub fn circle_vs_circle(a: Circle, b: Circle) -> bool {
    let r = a.radius + b.radius;
    a.center.distance_squared(b.center) < r * r
}

/// True when the circle and the box overlap.
///
/// ```
/// use mawida::collide::{circle_vs_aabb, Aabb, Circle};
/// use mawida::math::Vec2;
///
/// let b = Aabb::from_min_max(Vec2::ZERO, Vec2::new(4.0, 4.0));
/// let c = Circle { center: Vec2::new(5.0, 2.0), radius: 1.5 };
/// assert!(circle_vs_aabb(c, b));
/// ```
pub fn circle_vs_aabb(c: Circle, b: Aabb) -> bool {
    // The clever line: clamp the center into the box to find the closest
    // point on (or in) the box, then it is a point-vs-circle test.
    let closest = c.center.clamp(b.min, b.max);
    c.center.distance_squared(closest) < c.radius * c.radius
}

/// True when the point is inside the box, ON THE EDGE INCLUDED.
/// Containment is inclusive (unlike overlap): clicking an outline counts.
pub fn point_vs_aabb(p: Vec2, b: Aabb) -> bool {
    p.x >= b.min.x && p.x <= b.max.x && p.y >= b.min.y && p.y <= b.max.y
}

pub fn point_vs_circle(p: Vec2, c: Circle) -> bool {
    p.distance_squared(c.center) <= c.radius * c.radius
}

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

    /// Exact == is for values that are exactly representable (halves, small
    /// ints). Everything computed gets tolerance. 1e-6 is plenty at sprite
    /// scale.
    fn assert_vec2_eq(got: Vec2, want: Vec2) {
        assert!(got.abs_diff_eq(want, 1e-6), "got {got:?}, want {want:?}");
    }

    #[test]
    fn center_size_round_trips() {
        let b = Aabb::from_center_size(Vec2::new(3.0, 4.0), Vec2::new(2.0, 6.0));
        assert_eq!(b.min, Vec2::new(2.0, 1.0));
        assert_eq!(b.max, Vec2::new(4.0, 7.0));
        assert_eq!(b.center(), Vec2::new(3.0, 4.0));
        assert_eq!(b.half_extents(), Vec2::new(1.0, 3.0));
    }

    #[test]
    fn sprite_bounds_uses_the_z0_seam() {
        let t = Transform::from_xy_size(10.0, 20.0, 30.0, 40.0);
        let b = sprite_bounds(&t);
        assert_eq!(b.min, Vec2::new(10.0, 20.0));
        assert_eq!(b.max, Vec2::new(40.0, 60.0));
    }

    #[test]
    fn boxes_overlap_when_both_axes_overlap() {
        let a = Aabb::from_min_max(Vec2::ZERO, Vec2::new(2.0, 2.0));
        let b = Aabb::from_min_max(Vec2::new(1.0, 1.0), Vec2::new(3.0, 3.0));
        assert!(aabb_vs_aabb(a, b));
        // x intervals overlap, y intervals do not: no collision
        let below = Aabb::from_min_max(Vec2::new(0.0, 5.0), Vec2::new(2.0, 6.0));
        assert!(!aabb_vs_aabb(a, below));
    }

    #[test]
    fn touching_edges_is_not_overlap() {
        // THE convention decision: strict inequality. Two tiles side by
        // side share an edge all day and never collide.
        let a = Aabb::from_min_max(Vec2::ZERO, Vec2::ONE);
        let b = Aabb::from_min_max(Vec2::new(1.0, 0.0), Vec2::new(2.0, 1.0));
        assert!(!aabb_vs_aabb(a, b));
    }

    #[test]
    fn zero_size_aabb_is_a_point() {
        // degenerate: a zero-size box has no area, so it never overlaps itself...
        let p = Aabb::from_min_max(Vec2::splat(0.5), Vec2::splat(0.5));
        assert!(!aabb_vs_aabb(p, p));
        // ...but strictly inside a fat box, the interval test still says yes
        let unit = Aabb::from_min_max(Vec2::ZERO, Vec2::ONE);
        assert!(aabb_vs_aabb(p, unit));
    }

    #[test]
    fn penetration_picks_the_shallow_axis() {
        // A player 1 unit deep into a floor, but overlapping it 4 units
        // wide. The correct push is UP by 1, never sideways by 4.
        let player = Aabb::from_min_max(Vec2::new(0.0, 8.0), Vec2::new(4.0, 11.0));
        let floor = Aabb::from_min_max(Vec2::new(-10.0, 10.0), Vec2::new(10.0, 20.0));
        let mtv = aabb_penetration(player, floor).unwrap();
        assert_vec2_eq(mtv, Vec2::new(0.0, -1.0)); // y-down: -1.0 means "up"

        // The push RESOLVES: the moved box touches the floor, and touching
        // is not overlapping, so the pair is clean next frame. No jitter.
        let moved = Aabb::from_min_max(player.min + mtv, player.max + mtv);
        assert!(!aabb_vs_aabb(moved, floor));
        assert!(aabb_penetration(moved, floor).is_none());
    }

    #[test]
    fn penetration_table() {
        // table-driven: a 2x2 box at (x, y), against a 2x2 box at the origin
        let unit =
            |x: f32, y: f32| Aabb::from_min_max(Vec2::new(x, y), Vec2::new(x + 2.0, y + 2.0));
        let cases: [(Aabb, Aabb, Option<Vec2>); 4] = [
            (unit(0.0, 0.0), unit(1.5, 0.0), Some(Vec2::new(-0.5, 0.0))), // b right: push a left
            (unit(0.0, 0.0), unit(-1.5, 0.0), Some(Vec2::new(0.5, 0.0))), // b left:  push a right
            (unit(0.0, 0.0), unit(0.0, 1.5), Some(Vec2::new(0.0, -0.5))), // b below: push a up
            (unit(0.0, 0.0), unit(3.0, 0.0), None),                       // separated
        ];
        for (i, (a, b, want)) in cases.into_iter().enumerate() {
            assert_eq!(aabb_penetration(a, b), want, "case {i}");
        }
    }

    #[test]
    fn circles_overlap_by_distance() {
        let a = Circle { center: Vec2::ZERO, radius: 1.0 };
        assert!(circle_vs_circle(a, Circle { center: Vec2::new(1.5, 0.0), radius: 1.0 }));
        assert!(!circle_vs_circle(a, Circle { center: Vec2::new(3.0, 0.0), radius: 1.0 }));
        // touching exactly (distance == radius sum): same strict convention
        assert!(!circle_vs_circle(a, Circle { center: Vec2::new(2.0, 0.0), radius: 1.0 }));
    }

    #[test]
    fn concentric_circles_overlap() {
        // degenerate: same center. Distance 0 is less than any positive
        // radius sum, so containment counts as overlap, no special case.
        let big = Circle { center: Vec2::splat(4.0), radius: 2.0 };
        let small = Circle { center: Vec2::splat(4.0), radius: 0.5 };
        assert!(circle_vs_circle(big, small));
    }

    #[test]
    fn circle_hits_box_side_but_misses_corner() {
        let b = Aabb::from_min_max(Vec2::ZERO, Vec2::new(4.0, 4.0));
        // beside the box: closest point (4, 2), distance 1 < radius 1.5: hit
        assert!(circle_vs_aabb(Circle { center: Vec2::new(5.0, 2.0), radius: 1.5 }, b));
        // off the corner: closest (4, 4), distance sqrt(2) = 1.414.. > 1.2:
        // miss. A box-vs-box test would call this a hit; the round corner
        // is the whole point of having circles.
        assert!(!circle_vs_aabb(Circle { center: Vec2::new(5.0, 5.0), radius: 1.2 }, b));
    }

    #[test]
    fn circle_center_inside_box_still_overlaps() {
        // degenerate: clamp returns the center itself, distance 0: any
        // positive radius overlaps. The formula covers "inside" free.
        let b = Aabb::from_min_max(Vec2::ZERO, Vec2::new(4.0, 4.0));
        assert!(circle_vs_aabb(Circle { center: Vec2::new(2.0, 2.0), radius: 0.1 }, b));
    }

    #[test]
    fn point_hit_tests_are_inclusive() {
        let b = Aabb::from_min_max(Vec2::ZERO, Vec2::new(10.0, 10.0));
        assert!(point_vs_aabb(Vec2::new(5.0, 5.0), b));
        assert!(point_vs_aabb(Vec2::new(10.0, 10.0), b)); // on the corner: counts
        assert!(!point_vs_aabb(Vec2::new(10.1, 5.0), b));

        let c = Circle { center: Vec2::ZERO, radius: 5.0 };
        assert!(point_vs_circle(Vec2::new(3.0, 4.0), c)); // 3-4-5: exactly on the rim
        assert!(!point_vs_circle(Vec2::new(3.1, 4.0), c));
    }
}

// ---------------------------------------------------------------------------
// SAT: rotated boxes, the next rung (item 11)
// ---------------------------------------------------------------------------

/// An oriented (rotated) box: center, half extents, rotation in radians.
/// The moment a box may rotate, min/max corners stop describing it and the
/// separating axis theorem takes over.
#[derive(Clone, Copy, Debug, PartialEq)]
pub struct Obb {
    pub center: Vec2,
    pub half: Vec2,
    /// Rotation about the center, radians, counter-clockwise.
    pub rotation: f32,
}

impl Obb {
    /// The box's two local axes (unit vectors), rotated into world space.
    fn axes(self) -> [Vec2; 2] {
        let (sin, cos) = self.rotation.sin_cos();
        [Vec2::new(cos, sin), Vec2::new(-sin, cos)]
    }

    /// The four world-space corners.
    fn corners(self) -> [Vec2; 4] {
        let [ax, ay] = self.axes();
        let (ex, ey) = (ax * self.half.x, ay * self.half.y);
        [
            self.center - ex - ey,
            self.center + ex - ey,
            self.center + ex + ey,
            self.center - ex + ey,
        ]
    }

    /// Project the box onto a unit axis: the (min, max) interval.
    fn project(self, axis: Vec2) -> (f32, f32) {
        let mut lo = f32::INFINITY;
        let mut hi = f32::NEG_INFINITY;
        for c in self.corners() {
            let d = c.dot(axis);
            lo = lo.min(d);
            hi = hi.max(d);
        }
        (lo, hi)
    }
}

/// The separating axis theorem for two rotated boxes, with the MTV.
///
/// The whole idea in five steps: two CONVEX shapes are disjoint iff some
/// line exists onto which their projections do not overlap; for polygons
/// only the edge normals can be that line (4 axes for two boxes); project
/// both boxes onto each axis (dot products) giving two intervals; any axis
/// with disjoint intervals means NO collision, stop early; if every axis
/// overlaps, the axis with the SMALLEST overlap is the MTV direction and
/// its depth the length. Returns the push that separates `a` from `b`,
/// or `None`. Touching is not overlap, same convention as everything here.
pub fn obb_vs_obb(a: Obb, b: Obb) -> Option<Vec2> {
    let axes = [a.axes(), b.axes()];
    let mut min_depth = f32::INFINITY;
    let mut min_axis = Vec2::ZERO;

    for axis in axes.into_iter().flatten() {
        let (a_lo, a_hi) = a.project(axis);
        let (b_lo, b_hi) = b.project(axis);
        let overlap = a_hi.min(b_hi) - a_lo.max(b_lo);
        if overlap <= 0.0 {
            return None; // a separating axis: disjoint, stop early
        }
        if overlap < min_depth {
            min_depth = overlap;
            min_axis = axis;
        }
    }

    // Push a AWAY from b along the smallest-overlap axis.
    let sign = if (a.center - b.center).dot(min_axis) < 0.0 { -1.0 } else { 1.0 };
    Some(min_axis * sign * min_depth)
}

// ---------------------------------------------------------------------------
// The broad phase: a uniform grid (item 12)
// ---------------------------------------------------------------------------

/// The O(n^2) every-pair loop is honest and fine for dozens of entities;
/// past that, most pairs are nowhere near each other and testing them is
/// pure waste. The uniform grid is the simplest broad phase: hash each box
/// into the cells it touches, and only boxes SHARING a cell become
/// candidate pairs for the narrow phase (the precise tests above).
pub struct SpatialGrid {
    cell: f32,
    cells: std::collections::HashMap<(i32, i32), Vec<(u64, Aabb)>>,
}

impl SpatialGrid {
    /// `cell` should be around the size of a typical object: too small and
    /// objects span many cells (insert cost), too big and cells hold many
    /// objects (pair cost). A power of two near your sprite size is fine.
    pub fn new(cell: f32) -> Self {
        debug_assert!(cell > 0.0);
        Self {
            cell,
            cells: std::collections::HashMap::new(),
        }
    }

    fn cell_range(&self, b: Aabb) -> (i32, i32, i32, i32) {
        (
            (b.min.x / self.cell).floor() as i32,
            (b.min.y / self.cell).floor() as i32,
            (b.max.x / self.cell).floor() as i32,
            (b.max.y / self.cell).floor() as i32,
        )
    }

    /// File `id`'s box into every cell it touches. Rebuild the grid each
    /// frame (clear + insert): cheaper and simpler than incremental updates
    /// at teaching scale.
    pub fn insert(&mut self, id: u64, aabb: Aabb) {
        let (x0, y0, x1, y1) = self.cell_range(aabb);
        for gy in y0..=y1 {
            for gx in x0..=x1 {
                self.cells.entry((gx, gy)).or_default().push((id, aabb));
            }
        }
    }

    pub fn clear(&mut self) {
        // keep the allocated cell Vecs: same reuse discipline as the batcher
        for v in self.cells.values_mut() {
            v.clear();
        }
    }

    /// Candidate pairs: ids sharing at least one cell whose boxes ALSO
    /// overlap (the cheap test runs here so the caller only sees real
    /// candidates). Deduplicated: a pair spanning several cells reports
    /// once. Each pair is (low id, high id).
    pub fn candidate_pairs(&self) -> Vec<(u64, u64)> {
        let mut seen = std::collections::HashSet::new();
        let mut out = Vec::new();
        for bucket in self.cells.values() {
            for (i, (id_a, box_a)) in bucket.iter().enumerate() {
                for (id_b, box_b) in &bucket[i + 1..] {
                    let key = (*id_a.min(id_b), *id_a.max(id_b));
                    if aabb_vs_aabb(*box_a, *box_b) && seen.insert(key) {
                        out.push(key);
                    }
                }
            }
        }
        out
    }
}

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

    #[test]
    fn sat_finds_the_separating_axis_an_aabb_test_misses() {
        // The classic case: a diamond (45-degree box) near a's corner. The
        // two AABBs overlap, but the diamond's slanted edge clears the
        // corner: SAT finds the separating axis, the AABB test cannot.
        let a = Obb { center: Vec2::new(0.0, 0.0), half: Vec2::ONE, rotation: 0.0 };
        let b = Obb {
            center: Vec2::new(2.2, 2.2),
            half: Vec2::ONE,
            rotation: std::f32::consts::FRAC_PI_4,
        };
        // Their axis-aligned bounds overlap (b's AABB reaches 2.2 - sqrt(2)
        // = 0.79 on both axes, inside a's 1.0)...
        assert!(obb_vs_obb(a, b).is_none()); // ...but the shapes do not.

        // Slide the diamond in: now they genuinely overlap, and the MTV
        // resolves (the push lands exactly touching, which is not overlap).
        let b2 = Obb { center: Vec2::new(1.6, 1.6), ..b };
        let mtv = obb_vs_obb(a, b2).expect("overlapping");
        let moved = Obb { center: a.center + mtv, ..a };
        assert!(obb_vs_obb(moved, b2).is_none());
    }

    #[test]
    fn sat_axis_aligned_matches_aabb_penetration() {
        // With zero rotation SAT must agree with the interval test.
        let a = Obb { center: Vec2::new(0.0, 0.0), half: Vec2::ONE, rotation: 0.0 };
        let b = Obb { center: Vec2::new(1.5, 0.0), half: Vec2::ONE, rotation: 0.0 };
        let mtv = obb_vs_obb(a, b).expect("overlapping");
        assert!(mtv.abs_diff_eq(Vec2::new(-0.5, 0.0), 1e-5)); // push a left by the 0.5 overlap
    }

    #[test]
    fn grid_culls_far_pairs_and_keeps_near_ones() {
        let mut grid = SpatialGrid::new(64.0);
        let unit = |x: f32, y: f32| Aabb::from_min_max(Vec2::new(x, y), Vec2::new(x + 10.0, y + 10.0));
        // two overlapping boxes in one corner, one far away
        grid.insert(1, unit(0.0, 0.0));
        grid.insert(2, unit(5.0, 5.0));
        grid.insert(3, unit(1000.0, 1000.0));

        let pairs = grid.candidate_pairs();
        assert_eq!(pairs, vec![(1, 2)]); // the far box produced NO candidate

        // a box spanning several cells still reports each pair once
        grid.clear();
        grid.insert(1, Aabb::from_min_max(Vec2::ZERO, Vec2::new(200.0, 10.0)));
        grid.insert(2, Aabb::from_min_max(Vec2::new(100.0, 0.0), Vec2::new(130.0, 10.0)));
        assert_eq!(grid.candidate_pairs(), vec![(1, 2)]);
    }
}
