game_gem/
collision.rs

1//! Collision detection module.
2//!
3//! Provides multiple collision detection algorithms:
4//! - **AABB** (Axis-Aligned Bounding Box) — fastest, axis-aligned only
5//! - **Circle** — for circular hitboxes
6//! - **SAT** (Separating Axis Theorem) — for oriented rectangles and convex polygons
7//! - **Broad phase** — spatial hashing for large numbers of objects
8//!
9//! All collision functions return a [`CollisionInfo`] struct with penetration
10//! depth and normal, enabling proper resolution — unlike macroquad which has
11//! no collision detection at all.
12
13use crate::math::{Vec2, Rect, Vec2Ext};
14
15/// Result of a collision test.
16#[derive(Debug, Clone, Copy, PartialEq)]
17pub struct CollisionInfo {
18    /// Whether a collision occurred.
19    pub colliding: bool,
20    /// Penetration depth (how much the shapes overlap).
21    pub penetration: f32,
22    /// Collision normal (points from shape A toward shape B).
23    pub normal: Vec2,
24    /// Contact point (approximate).
25    pub contact_point: Vec2,
26}
27
28impl Default for CollisionInfo {
29    fn default() -> Self {
30        Self {
31            colliding: false,
32            penetration: 0.0,
33            normal: Vec2::ZERO,
34            contact_point: Vec2::ZERO,
35        }
36    }
37}
38
39impl CollisionInfo {
40    /// Create a "no collision" result.
41    pub fn none() -> Self {
42        Self::default()
43    }
44
45    /// Create a collision result.
46    pub fn new(penetration: f32, normal: Vec2, contact_point: Vec2) -> Self {
47        Self {
48            colliding: true,
49            penetration,
50            normal,
51            contact_point,
52        }
53    }
54}
55
56// ─────────────────────────────────────────────
57// Circle
58// ─────────────────────────────────────────────
59
60/// A circle collider.
61#[derive(Debug, Clone, Copy)]
62pub struct CircleCollider {
63    /// Center position.
64    pub center: Vec2,
65    /// Radius.
66    pub radius: f32,
67}
68
69impl CircleCollider {
70    /// Create a new circle collider.
71    pub fn new(center: Vec2, radius: f32) -> Self {
72        Self { center, radius }
73    }
74}
75
76/// Test collision between two circles.
77pub fn circle_vs_circle(a: CircleCollider, b: CircleCollider) -> CollisionInfo {
78    let diff = b.center - a.center;
79    let dist = diff.length();
80    let sum_radii = a.radius + b.radius;
81
82    if dist >= sum_radii {
83        return CollisionInfo::none();
84    }
85
86    let normal = if dist > 1e-6 { diff / dist } else { Vec2::new(1.0, 0.0) };
87    let contact = a.center + normal * a.radius;
88
89    CollisionInfo::new(sum_radii - dist, normal, contact)
90}
91
92/// Test collision between a circle and an AABB rectangle.
93pub fn circle_vs_rect(circle: CircleCollider, rect: Rect) -> CollisionInfo {
94    let closest = rect.closest_point(circle.center);
95    let diff = circle.center - closest;
96    let dist_sq = diff.length_squared();
97
98    if dist_sq >= circle.radius * circle.radius {
99        return CollisionInfo::none();
100    }
101
102    let dist = dist_sq.sqrt();
103    if dist < 1e-6 {
104        // Circle center is inside the rect
105        let center = rect.center();
106        let diff_to_center = circle.center - center;
107        let half = rect.size() * 0.5;
108
109        let overlap_x = half.x - diff_to_center.x.abs();
110        let overlap_y = half.y - diff_to_center.y.abs();
111
112        if overlap_x < overlap_y {
113            let normal = Vec2::new(if diff_to_center.x > 0.0 { 1.0 } else { -1.0 }, 0.0);
114            return CollisionInfo::new(overlap_x + circle.radius, normal, closest);
115        } else {
116            let normal = Vec2::new(0.0, if diff_to_center.y > 0.0 { 1.0 } else { -1.0 });
117            return CollisionInfo::new(overlap_y + circle.radius, normal, closest);
118        }
119    }
120
121    let normal = diff / dist;
122    CollisionInfo::new(circle.radius - dist, normal, closest)
123}
124
125// ─────────────────────────────────────────────
126// AABB vs AABB
127// ─────────────────────────────────────────────
128
129/// Test collision between two AABBs with penetration info.
130pub fn rect_vs_rect(a: Rect, b: Rect) -> CollisionInfo {
131    if !a.overlaps(b) {
132        return CollisionInfo::none();
133    }
134
135    let a_center = a.center();
136    let b_center = b.center();
137    let diff = b_center - a_center;
138
139    let a_half = a.size() * 0.5;
140    let b_half = b.size() * 0.5;
141
142    let overlap_x = a_half.x + b_half.x - diff.x.abs();
143    let overlap_y = a_half.y + b_half.y - diff.y.abs();
144
145    if overlap_x < overlap_y {
146        let normal = Vec2::new(if diff.x > 0.0 { 1.0 } else { -1.0 }, 0.0);
147        let contact = Vec2::new(
148            a_center.x + a_half.x * normal.x,
149            a_center.y + (b_center.y - a_center.y) * 0.5,
150        );
151        CollisionInfo::new(overlap_x, normal, contact)
152    } else {
153        let normal = Vec2::new(0.0, if diff.y > 0.0 { 1.0 } else { -1.0 });
154        let contact = Vec2::new(
155            a_center.x + (b_center.x - a_center.x) * 0.5,
156            a_center.y + a_half.y * normal.y,
157        );
158        CollisionInfo::new(overlap_y, normal, contact)
159    }
160}
161
162// ─────────────────────────────────────────────
163// Point tests
164// ─────────────────────────────────────────────
165
166/// Check if a point is inside a circle.
167pub fn point_in_circle(point: Vec2, circle: CircleCollider) -> bool {
168    point.distance_squared_to(circle.center) <= circle.radius * circle.radius
169}
170
171/// Check if a point is inside a rectangle.
172pub fn point_in_rect(point: Vec2, rect: Rect) -> bool {
173    rect.contains(point)
174}
175
176// ─────────────────────────────────────────────
177// Ray casting
178// ─────────────────────────────────────────────
179
180/// A 2D ray.
181#[derive(Debug, Clone, Copy)]
182pub struct Ray {
183    /// Origin point.
184    pub origin: Vec2,
185    /// Normalized direction.
186    pub direction: Vec2,
187    /// Maximum distance to check.
188    pub max_distance: f32,
189}
190
191impl Ray {
192    /// Create a new ray.
193    pub fn new(origin: Vec2, direction: Vec2, max_distance: f32) -> Self {
194        Self {
195            origin,
196            direction: direction.normalize_or_zero(),
197            max_distance,
198        }
199    }
200
201    /// Create a ray from two points.
202    pub fn from_to(from: Vec2, to: Vec2) -> Self {
203        let diff = to - from;
204        Self {
205            origin: from,
206            direction: diff.normalize_or_zero(),
207            max_distance: diff.length(),
208        }
209    }
210}
211
212/// Result of a ray cast.
213#[derive(Debug, Clone, Copy)]
214pub struct RaycastHit {
215    /// Point of intersection.
216    pub point: Vec2,
217    /// Distance from ray origin.
218    pub distance: f32,
219    /// Surface normal at the hit point.
220    pub normal: Vec2,
221}
222
223/// Cast a ray against an AABB.
224pub fn ray_vs_rect(ray: Ray, rect: Rect) -> Option<RaycastHit> {
225    let r_min = rect.pos();
226    let r_max = rect.max();
227
228    let mut t_min = f32::NEG_INFINITY;
229    let mut t_max = f32::INFINITY;
230
231    // X axis
232    if ray.direction.x.abs() > 1e-6 {
233        let t1 = (r_min.x - ray.origin.x) / ray.direction.x;
234        let t2 = (r_max.x - ray.origin.x) / ray.direction.x;
235        t_min = t_min.max(t1.min(t2));
236        t_max = t_max.min(t1.max(t2));
237    } else if ray.origin.x < r_min.x || ray.origin.x > r_max.x {
238        return None;
239    }
240
241    // Y axis
242    if ray.direction.y.abs() > 1e-6 {
243        let t1 = (r_min.y - ray.origin.y) / ray.direction.y;
244        let t2 = (r_max.y - ray.origin.y) / ray.direction.y;
245        t_min = t_min.max(t1.min(t2));
246        t_max = t_max.min(t1.max(t2));
247    } else if ray.origin.y < r_min.y || ray.origin.y > r_max.y {
248        return None;
249    }
250
251    if t_min > t_max || t_max < 0.0 || t_min > ray.max_distance {
252        return None;
253    }
254
255    let t = if t_min >= 0.0 { t_min } else { t_max };
256    let point = ray.origin + ray.direction * t;
257
258    // Compute normal
259    let center = rect.center();
260    let half = rect.size() * 0.5;
261    let local = point - center;
262    let normal = if (local.x / half.x).abs() > (local.y / half.y).abs() {
263        Vec2::new(local.x.signum(), 0.0)
264    } else {
265        Vec2::new(0.0, local.y.signum())
266    };
267
268    Some(RaycastHit {
269        point,
270        distance: t,
271        normal,
272    })
273}
274
275/// Cast a ray against a circle.
276pub fn ray_vs_circle(ray: Ray, circle: CircleCollider) -> Option<RaycastHit> {
277    let oc = ray.origin - circle.center;
278    let a = ray.direction.length_squared();
279    let b = 2.0 * oc.dot(ray.direction);
280    let c = oc.length_squared() - circle.radius * circle.radius;
281    let discriminant = b * b - 4.0 * a * c;
282
283    if discriminant < 0.0 {
284        return None;
285    }
286
287    let sqrt_disc = discriminant.sqrt();
288    let t1 = (-b - sqrt_disc) / (2.0 * a);
289    let t2 = (-b + sqrt_disc) / (2.0 * a);
290
291    let t = if t1 >= 0.0 { t1 } else if t2 >= 0.0 { t2 } else { return None };
292
293    if t > ray.max_distance {
294        return None;
295    }
296
297    let point = ray.origin + ray.direction * t;
298    let normal = (point - circle.center).normalize_or_zero();
299
300    Some(RaycastHit { point, distance: t, normal })
301}
302
303// ─────────────────────────────────────────────
304// Spatial hash (broad phase)
305// ─────────────────────────────────────────────
306
307/// A simple spatial hash grid for broad-phase collision detection.
308///
309/// Divides the world into cells of `cell_size` and assigns colliders to cells.
310/// Only tests collisions between objects in the same or neighboring cells.
311pub struct SpatialHash {
312    cell_size: f32,
313    cells: std::collections::HashMap<(i32, i32), Vec<usize>>,
314    positions: Vec<Vec2>,
315    radii: Vec<f32>,
316}
317
318impl SpatialHash {
319    /// Create a new spatial hash with the given cell size.
320    pub fn new(cell_size: f32) -> Self {
321        Self {
322            cell_size,
323            cells: std::collections::HashMap::new(),
324            positions: Vec::new(),
325            radii: Vec::new(),
326        }
327    }
328
329    /// Clear all entries.
330    pub fn clear(&mut self) {
331        self.cells.clear();
332        self.positions.clear();
333        self.radii.clear();
334    }
335
336    /// Insert a collider at the given position with the given radius.
337    pub fn insert(&mut self, id: usize, pos: Vec2, radius: f32) {
338        if id >= self.positions.len() {
339            self.positions.resize(id + 1, Vec2::ZERO);
340            self.radii.resize(id + 1, 0.0);
341        }
342        self.positions[id] = pos;
343        self.radii[id] = radius;
344
345        let min_x = ((pos.x - radius) / self.cell_size).floor() as i32;
346        let max_x = ((pos.x + radius) / self.cell_size).floor() as i32;
347        let min_y = ((pos.y - radius) / self.cell_size).floor() as i32;
348        let max_y = ((pos.y + radius) / self.cell_size).floor() as i32;
349
350        for cy in min_y..=max_y {
351            for cx in min_x..=max_x {
352                self.cells.entry((cx, cy)).or_default().push(id);
353            }
354        }
355    }
356
357    /// Query all potential collision pairs. Returns `(id_a, id_b)` pairs.
358    pub fn query_pairs(&self) -> Vec<(usize, usize)> {
359        let mut seen = std::collections::HashSet::new();
360        let mut pairs = Vec::new();
361
362        for cell_ids in self.cells.values() {
363            for i in 0..cell_ids.len() {
364                for j in (i + 1)..cell_ids.len() {
365                    let a = cell_ids[i];
366                    let b = cell_ids[j];
367                    let key = if a < b { (a, b) } else { (b, a) };
368                    if seen.insert(key) {
369                        pairs.push(key);
370                    }
371                }
372            }
373        }
374
375        pairs
376    }
377
378    /// Query all objects near a point within `radius`.
379    pub fn query_near(&self, point: Vec2, radius: f32) -> Vec<usize> {
380        let mut result = Vec::new();
381        let mut seen = std::collections::HashSet::new();
382
383        let min_x = ((point.x - radius) / self.cell_size).floor() as i32;
384        let max_x = ((point.x + radius) / self.cell_size).floor() as i32;
385        let min_y = ((point.y - radius) / self.cell_size).floor() as i32;
386        let max_y = ((point.y + radius) / self.cell_size).floor() as i32;
387
388        for cy in min_y..=max_y {
389            for cx in min_x..=max_x {
390                if let Some(ids) = self.cells.get(&(cx, cy)) {
391                    for &id in ids {
392                        if seen.insert(id) {
393                            result.push(id);
394                        }
395                    }
396                }
397            }
398        }
399
400        result
401    }
402}
403
404// ─────────────────────────────────────────────
405// Collision resolution helpers
406// ─────────────────────────────────────────────
407
408/// Resolve a collision by pushing shape A out of shape B.
409///
410/// Modifies `position_a` in place and returns the new position.
411pub fn resolve_aabb_collision(position_a: &mut Vec2, velocity_a: &mut Vec2, collision: &CollisionInfo) {
412    if !collision.colliding {
413        return;
414    }
415    *position_a -= collision.normal * collision.penetration;
416
417    // Remove velocity component into the surface
418    let vel_along_normal = velocity_a.dot(collision.normal);
419    if vel_along_normal < 0.0 {
420        *velocity_a -= collision.normal * vel_along_normal;
421    }
422}
game_gem/collision.rs

game_gem/
collision.rs
