add 2d collision header

1 files changed, 265 insertions, 0 deletions

diff --git a/kon/koncollide.h b/kon/koncollide.h
new file mode 100644
index 0000000..d312533
--- /dev/null
+++ b/kon/koncollide.h
@@ -0,0 +1,265 @@
+/* SPDX-License-Identifier: MIT */
+/*
+ * koncollide.h
+ *
+ * Copyright (c) 2026 KonAki
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a copy
+ * of this software and associated documentation files (the "Software"), to deal
+ * in the Software without restriction, including without limitation the rights
+ * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+ * copies of the Software, and to permit persons to whom the Software is
+ * furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be included in all
+ * copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+ * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+ * SOFTWARE.
+ */
+
+#ifndef KONCOLLIDE_H
+#define KONCOLLIDE_H
+
+#include <math.h>
+
+#include "konmath.h"
+
+/*** definition ***/
+
+/* 2d shapes. x, y is the top left corner of a box and the centre of a circle. nothing here cares which way y points,
+   the words up and down in the comments are for screen space where y grows downward */
+typedef struct kon_box2 { float x, y, w, h; } kon_box2_t;
+typedef struct kon_circle2 { float x, y, r; } kon_circle2_t;
+
+#define KON_BOX2(x, y, w, h) ((kon_box2_t){(float)(x), (float)(y), (float)(w), (float)(h)})
+#define KON_CIRCLE2(x, y, r) ((kon_circle2_t){(float)(x), (float)(y), (float)(r)})
+
+/* what a ray or a sweep found. time is how far along it was (0 to 1 for a sweep, a distance for a ray when dir is a unit vector),
+   normal points back out of the thing that was hit, point is where it happened */
+typedef struct kon_hit2 {
+	float time;
+	kon_vec2_t normal;
+	kon_vec2_t point;
+} kon_hit2_t;
+
+/* shapes that only touch at an edge do not overlap. every function returns 1 for a hit and 0 for a miss */
+
+static inline int kon_boxOverlap(kon_box2_t a, kon_box2_t b);
+static inline int kon_boxContains(kon_box2_t box, kon_vec2_t point);
+static inline int kon_circleOverlap(kon_circle2_t a, kon_circle2_t b);
+static inline int kon_circleBoxOverlap(kon_circle2_t circle, kon_box2_t box);
+
+/* how far to move a to get it out of b, along the shorter way out. push is left alone on a miss */
+static inline int kon_boxPush(kon_box2_t a, kon_box2_t b, kon_vec2_t *push);
+static inline int kon_circleBoxPush(kon_circle2_t circle, kon_box2_t box, kon_vec2_t *push);
+
+/* dir does not have to be a unit vector, but time is in units of dir then. maxTime cuts the ray short */
+static inline int kon_rayBox(kon_vec2_t origin, kon_vec2_t dir, float maxTime, kon_box2_t box, kon_hit2_t *hit);
+static inline int kon_rayCircle(kon_vec2_t origin, kon_vec2_t dir, float maxTime, kon_circle2_t circle, kon_hit2_t *hit);
+
+/* moves a by velocity and tells you where it first touches b. time 1 is the end of the move, so a moves by velocity * time before it stops.
+   a box that already overlaps b hits at time 0 */
+static inline int kon_sweepBox(kon_box2_t a, kon_vec2_t velocity, kon_box2_t b, kon_hit2_t *hit);
+
+/*** implementation ***/
+
+static inline float kon_collideMin_(float a, float b) { return a < b ? a : b; }
+static inline float kon_collideMax_(float a, float b) { return a > b ? a : b; }
+
+static inline int kon_boxOverlap(kon_box2_t a, kon_box2_t b)
+{
+	return a.x < b.x + b.w && b.x < a.x + a.w && a.y < b.y + b.h && b.y < a.y + a.h;
+}
+
+static inline int kon_boxContains(kon_box2_t box, kon_vec2_t point)
+{
+	return point.x >= box.x && point.x < box.x + box.w && point.y >= box.y && point.y < box.y + box.h;
+}
+
+static inline int kon_circleOverlap(kon_circle2_t a, kon_circle2_t b)
+{
+	float dx = b.x - a.x, dy = b.y - a.y, r = a.r + b.r;
+
+	return dx * dx + dy * dy < r * r;
+}
+
+static inline kon_vec2_t kon_boxClosest_(kon_box2_t box, float x, float y)
+{
+	kon_vec2_t p;
+
+	p.x = kon_collideMax_(box.x, kon_collideMin_(x, box.x + box.w));
+	p.y = kon_collideMax_(box.y, kon_collideMin_(y, box.y + box.h));
+	return p;
+}
+
+static inline int kon_circleBoxOverlap(kon_circle2_t circle, kon_box2_t box)
+{
+	kon_vec2_t p = kon_boxClosest_(box, circle.x, circle.y);
+	float dx = circle.x - p.x, dy = circle.y - p.y;
+
+	return dx * dx + dy * dy < circle.r * circle.r;
+}
+
+static inline int kon_boxPush(kon_box2_t a, kon_box2_t b, kon_vec2_t *push)
+{
+	float left, right, up, down;
+	float ax = a.x + a.w * 0.5f, ay = a.y + a.h * 0.5f, bx = b.x + b.w * 0.5f, by = b.y + b.h * 0.5f;
+	float px, py;
+
+	if (!kon_boxOverlap(a, b)) return 0;
+
+	left = a.x + a.w - b.x;
+	right = b.x + b.w - a.x;
+	up = a.y + a.h - b.y;
+	down = b.y + b.h - a.y;
+	px = ax < bx ? -left : right;
+	py = ay < by ? -up : down;
+
+	if (fabsf(px) <= fabsf(py)) {
+		push->x = px;
+		push->y = 0.0f;
+	} else {
+		push->x = 0.0f;
+		push->y = py;
+	}
+	return 1;
+}
+
+static inline int kon_circleBoxPush(kon_circle2_t circle, kon_box2_t box, kon_vec2_t *push)
+{
+	kon_vec2_t p = kon_boxClosest_(box, circle.x, circle.y);
+	float dx = circle.x - p.x, dy = circle.y - p.y;
+	float d2 = dx * dx + dy * dy;
+
+	if (d2 >= circle.r * circle.r) return 0;
+
+	if (d2 > 0.0f) {
+		float d = sqrtf(d2), s = (circle.r - d) / d;
+
+		push->x = dx * s;
+		push->y = dy * s;
+		return 1;
+	}
+
+	/* the centre is inside the box, go out the nearest side */
+	{
+		float left = circle.x - box.x, right = box.x + box.w - circle.x;
+		float up = circle.y - box.y, down = box.y + box.h - circle.y;
+		float m = kon_collideMin_(kon_collideMin_(left, right), kon_collideMin_(up, down));
+
+		push->x = push->y = 0.0f;
+		if (m == left) push->x = -(left + circle.r);
+		else if (m == right) push->x = right + circle.r;
+		else if (m == up) push->y = -(up + circle.r);
+		else push->y = down + circle.r;
+	}
+	return 1;
+}
+
+/* where a moving interval along one axis is inside the other one. returns 0 if it never is */
+static inline int kon_slab_(float start, float size, float v, float lo, float hi, float *enter, float *exit)
+{
+	if (v == 0.0f) {
+		if (start + size <= lo || start >= hi) return 0;
+		*enter = -INFINITY;
+		*exit = INFINITY;
+		return 1;
+	}
+	{
+		float t1 = (lo - (start + size)) / v, t2 = (hi - start) / v;
+
+		*enter = kon_collideMin_(t1, t2);
+		*exit = kon_collideMax_(t1, t2);
+	}
+	return 1;
+}
+
+static inline int kon_sweepBox(kon_box2_t a, kon_vec2_t velocity, kon_box2_t b, kon_hit2_t *hit)
+{
+	float enterX, exitX, enterY, exitY, enter, exit;
+
+	if (kon_boxOverlap(a, b)) {
+		kon_vec2_t push;
+
+		kon_boxPush(a, b, &push);
+		hit->time = 0.0f;
+		hit->normal = kon_vec2Normalize(push);
+		hit->point = KON_VEC2(a.x + a.w * 0.5f, a.y + a.h * 0.5f);
+		return 1;
+	}
+
+	if (!kon_slab_(a.x, a.w, velocity.x, b.x, b.x + b.w, &enterX, &exitX)) return 0;
+	if (!kon_slab_(a.y, a.h, velocity.y, b.y, b.y + b.h, &enterY, &exitY)) return 0;
+
+	enter = kon_collideMax_(enterX, enterY);
+	exit = kon_collideMin_(exitX, exitY);
+	if (enter >= exit || enter > 1.0f || exit <= 0.0f || enter < 0.0f) return 0;
+
+	hit->time = enter;
+	if (enterX > enterY) hit->normal = KON_VEC2(velocity.x > 0.0f ? -1.0f : 1.0f, 0.0f);
+	else hit->normal = KON_VEC2(0.0f, velocity.y > 0.0f ? -1.0f : 1.0f);
+	hit->point = KON_VEC2(a.x + a.w * 0.5f + velocity.x * enter, a.y + a.h * 0.5f + velocity.y * enter);
+	return 1;
+}
+
+static inline int kon_rayBox(kon_vec2_t origin, kon_vec2_t dir, float maxTime, kon_box2_t box, kon_hit2_t *hit)
+{
+	float enterX, exitX, enterY, exitY, enter, exit;
+
+	if (!kon_slab_(origin.x, 0.0f, dir.x, box.x, box.x + box.w, &enterX, &exitX)) return 0;
+	if (!kon_slab_(origin.y, 0.0f, dir.y, box.y, box.y + box.h, &enterY, &exitY)) return 0;
+
+	enter = kon_collideMax_(enterX, enterY);
+	exit = kon_collideMin_(exitX, exitY);
+	if (enter >= exit || exit <= 0.0f || enter > maxTime) return 0;
+
+	/* starting inside the box counts as a hit right at the origin */
+	if (enter < 0.0f) {
+		hit->time = 0.0f;
+		hit->normal = KON_VEC2(0.0f, 0.0f);
+		hit->point = origin;
+		return 1;
+	}
+
+	hit->time = enter;
+	if (enterX > enterY) hit->normal = KON_VEC2(dir.x > 0.0f ? -1.0f : 1.0f, 0.0f);
+	else hit->normal = KON_VEC2(0.0f, dir.y > 0.0f ? -1.0f : 1.0f);
+	hit->point = KON_VEC2(origin.x + dir.x * enter, origin.y + dir.y * enter);
+	return 1;
+}
+
+static inline int kon_rayCircle(kon_vec2_t origin, kon_vec2_t dir, float maxTime, kon_circle2_t circle, kon_hit2_t *hit)
+{
+	float fx = origin.x - circle.x, fy = origin.y - circle.y;
+	float a = dir.x * dir.x + dir.y * dir.y;
+	float b = 2.0f * (fx * dir.x + fy * dir.y);
+	float c = fx * fx + fy * fy - circle.r * circle.r;
+	float disc, t;
+
+	if (c <= 0.0f) {
+		hit->time = 0.0f;
+		hit->normal = KON_VEC2(0.0f, 0.0f);
+		hit->point = origin;
+		return 1;
+	}
+	if (a == 0.0f) return 0;
+
+	disc = b * b - 4.0f * a * c;
+	if (disc < 0.0f) return 0;
+
+	t = (-b - sqrtf(disc)) / (2.0f * a);
+	if (t < 0.0f || t > maxTime) return 0;
+
+	hit->time = t;
+	hit->point = KON_VEC2(origin.x + dir.x * t, origin.y + dir.y * t);
+	hit->normal = kon_vec2Normalize(KON_VEC2(hit->point.x - circle.x, hit->point.y - circle.y));
+	return 1;
+}
+
+#endif /* KONCOLLIDE_H */