path: root/kon/koncollide.h

/* 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"

#ifdef __cplusplus
extern "C" {
#endif

/*** 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;

#ifdef __cplusplus
static inline kon_box2_t kon_makeBox2_(float x, float y, float w, float h) { kon_box2_t b; b.x = x; b.y = y; b.w = w; b.h = h; return b; }
static inline kon_circle2_t kon_makeCircle2_(float x, float y, float r) { kon_circle2_t c; c.x = x; c.y = y; c.r = r; return c; }
#define KON_BOX2(x, y, w, h) kon_makeBox2_((float)(x), (float)(y), (float)(w), (float)(h))
#define KON_CIRCLE2(x, y, r) kon_makeCircle2_((float)(x), (float)(y), (float)(r))
#else
#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)})
#endif

/* 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;
}


#ifdef __cplusplus
}
#endif
#endif /* KONCOLLIDE_H */