/// @module std::physics::collision
/// Collision Detection
///
/// Axis-Aligned Bounding Box (AABB) collision detection with spatial hashing
/// for efficient broad-phase collision queries.
/// Create an AABB from min/max corners
///
/// @param min_x - minimum x coordinate
/// @param min_y - minimum y coordinate
/// @param max_x - maximum x coordinate
/// @param max_y - maximum y coordinate
pub fn aabb(min_x, min_y, max_x, max_y) {
{ min_x: min_x, min_y: min_y, max_x: max_x, max_y: max_y }
}
/// Create an AABB centered at (cx, cy) with half-extents (hw, hh)
pub fn aabb_centered(cx, cy, hw, hh) {
{ min_x: cx - hw, min_y: cy - hh, max_x: cx + hw, max_y: cy + hh }
}
/// Create an AABB from a position and size
pub fn aabb_from_pos(x, y, w, h) {
{ min_x: x, min_y: y, max_x: x + w, max_y: y + h }
}
/// Test if two AABBs overlap
///
/// @param a - first AABB
/// @param b - second AABB
/// @returns true if the AABBs overlap
pub fn aabb_overlaps(a, b) {
a.min_x <= b.max_x && a.max_x >= b.min_x &&
a.min_y <= b.max_y && a.max_y >= b.min_y
}
/// Compute the overlap area between two AABBs (0 if no overlap)
pub fn aabb_overlap_area(a, b) {
let ox = min(a.max_x, b.max_x) - max(a.min_x, b.min_x);
let oy = min(a.max_y, b.max_y) - max(a.min_y, b.min_y);
if ox > 0.0 && oy > 0.0 {
ox * oy
} else {
0.0
}
}
/// Test if AABB a fully contains AABB b
pub fn aabb_contains(a, b) {
a.min_x <= b.min_x && a.max_x >= b.max_x &&
a.min_y <= b.min_y && a.max_y >= b.max_y
}
/// Test if point (px, py) is inside an AABB
pub fn aabb_contains_point(box, px, py) {
px >= box.min_x && px <= box.max_x &&
py >= box.min_y && py <= box.max_y
}
/// Compute the union (smallest enclosing AABB) of two AABBs
pub fn aabb_union(a, b) {
{
min_x: min(a.min_x, b.min_x),
min_y: min(a.min_y, b.min_y),
max_x: max(a.max_x, b.max_x),
max_y: max(a.max_y, b.max_y)
}
}
/// Compute the intersection AABB of two AABBs (None if no overlap)
pub fn aabb_intersection(a, b) {
let ix_min = max(a.min_x, b.min_x);
let iy_min = max(a.min_y, b.min_y);
let ix_max = min(a.max_x, b.max_x);
let iy_max = min(a.max_y, b.max_y);
if ix_min <= ix_max && iy_min <= iy_max {
{ min_x: ix_min, min_y: iy_min, max_x: ix_max, max_y: iy_max }
} else {
None
}
}
/// Expand an AABB by a margin on all sides
pub fn aabb_expand(box, margin) {
{
min_x: box.min_x - margin,
min_y: box.min_y - margin,
max_x: box.max_x + margin,
max_y: box.max_y + margin
}
}
/// Get the center of an AABB
pub fn aabb_center(box) {
{
x: (box.min_x + box.max_x) / 2.0,
y: (box.min_y + box.max_y) / 2.0
}
}
/// Get the width and height of an AABB
pub fn aabb_size(box) {
{
width: box.max_x - box.min_x,
height: box.max_y - box.min_y
}
}
/// Compute minimum separation vector between two overlapping AABBs
///
/// Returns the smallest displacement to separate a from b.
/// Returns None if no overlap.
///
/// @param a - first AABB
/// @param b - second AABB
/// @returns { x, y } separation vector (move a by this to separate), or None
pub fn aabb_separation(a, b) {
if !aabb_overlaps(a, b) {
return None;
}
// Compute overlap extents on each axis
let overlap_x = min(a.max_x, b.max_x) - max(a.min_x, b.min_x);
let overlap_y = min(a.max_y, b.max_y) - max(a.min_y, b.min_y);
// Direction: push a away from b (from b's center toward a's center)
let ca_x = (a.min_x + a.max_x) / 2.0;
let cb_x = (b.min_x + b.max_x) / 2.0;
let ca_y = (a.min_y + a.max_y) / 2.0;
let cb_y = (b.min_y + b.max_y) / 2.0;
if overlap_x <= overlap_y {
// Separate along x (minimum penetration axis)
let mut dir = 1.0;
if ca_x < cb_x {
dir = -1.0;
}
{ x: dir * overlap_x, y: 0.0 }
} else {
// Separate along y
let mut dir = 1.0;
if ca_y < cb_y {
dir = -1.0;
}
{ x: 0.0, y: dir * overlap_y }
}
}
// ===== Broad-Phase: N-body collision detection =====
/// Find all colliding pairs in an array of AABBs (brute force O(n²))
///
/// @param boxes - array of AABB objects
/// @returns array of { i, j } index pairs where boxes[i] overlaps boxes[j]
pub fn find_collisions_brute(boxes) {
let mut pairs = [];
let n = boxes.len();
for i in range(0, n) {
let box_i = boxes[i];
for j in range(i + 1, n) {
let box_j = boxes[j];
if aabb_overlaps(box_i, box_j) {
pairs.push({ i: i, j: j });
}
}
}
pairs
}
/// Sort-and-sweep broad-phase collision detection
///
/// More efficient than brute force for sparse scenes. Sorts boxes by
/// min_x and only tests pairs that overlap on the x-axis.
///
/// @param boxes - array of AABB objects
/// @returns array of { i, j } index pairs of overlapping boxes
pub fn find_collisions_sweep(boxes) {
let n = boxes.len();
// Build index array sorted by min_x
let mut indices = [];
for i in range(0, n) {
let b = boxes[i];
indices.push({ idx: i, min_x: b.min_x });
}
// Simple insertion sort by min_x (sufficient for typical counts)
for i in range(1, n) {
let key = indices[i];
let mut j = i - 1;
let mut cont = j >= 0;
if cont {
let ej = indices[j];
cont = ej.min_x > key.min_x;
}
while cont {
let ej = indices[j];
indices[j + 1] = ej;
j = j - 1;
cont = j >= 0;
if cont {
let ej2 = indices[j];
cont = ej2.min_x > key.min_x;
}
}
indices[j + 1] = key;
}
let mut pairs = [];
for i in range(0, n) {
let entry_i = indices[i];
let ai = entry_i.idx;
let a = boxes[ai];
for j in range(i + 1, n) {
let entry_j = indices[j];
let bi = entry_j.idx;
let b = boxes[bi];
// If b starts after a ends on x-axis, no more overlaps with a
if b.min_x > a.max_x {
break;
}
// Check full AABB overlap (x already overlaps, just check y)
if a.min_y <= b.max_y && a.max_y >= b.min_y {
let mut lo = ai;
let mut hi = bi;
if lo > hi {
let tmp = lo;
lo = hi;
hi = tmp;
}
pairs.push({ i: lo, j: hi });
}
}
}
pairs
}
// ===== Collision Response =====
/// Elastic collision response for two bodies with AABBs
///
/// Computes post-collision velocities using conservation of momentum
/// and kinetic energy. Uses the minimum separation axis as collision normal.
///
/// @param body_a - { aabb, vx, vy, mass }
/// @param body_b - { aabb, vx, vy, mass }
/// @returns { a: { vx, vy }, b: { vx, vy } } post-collision velocities
pub fn elastic_response(body_a, body_b) {
// Bind fields to locals to avoid borrow issues with nested field access
let aabb_a = body_a.aabb;
let aabb_b = body_b.aabb;
let vx_a = body_a.vx;
let vy_a = body_a.vy;
let vx_b = body_b.vx;
let vy_b = body_b.vy;
let ma = body_a.mass;
let mb = body_b.mass;
let sep = aabb_separation(aabb_a, aabb_b);
if sep == None {
return { a: { vx: vx_a, vy: vy_a }, b: { vx: vx_b, vy: vy_b } };
}
// Normalize separation vector
let len_sep = sqrt(sep.x * sep.x + sep.y * sep.y);
if len_sep < 0.000001 {
return { a: { vx: vx_a, vy: vy_a }, b: { vx: vx_b, vy: vy_b } };
}
let nx = sep.x / len_sep;
let ny = sep.y / len_sep;
// Relative velocity along normal
let dvx = vx_a - vx_b;
let dvy = vy_a - vy_b;
let dvn = dvx * nx + dvy * ny;
// Don't resolve if separating
if dvn > 0.0 {
return { a: { vx: vx_a, vy: vy_a }, b: { vx: vx_b, vy: vy_b } };
}
let inv_total = 2.0 / (ma + mb);
let impulse_a = mb * inv_total * dvn;
let impulse_b = ma * inv_total * dvn;
return {
a: { vx: vx_a - impulse_a * nx, vy: vy_a - impulse_a * ny },
b: { vx: vx_b + impulse_b * nx, vy: vy_b + impulse_b * ny }
};
}