/* SPDX-License-Identifier: MIT */
/*
 * konworld.c
 *
 * 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.
 */

#include "konworld.h"

#include <math.h>
#include <stdlib.h>
#include <string.h>

#define KON_SECTOR_SET 48

/*** shapes ***/

kon_collider_t kon_colliderBox(kon_vec3_t min, kon_vec3_t max)
{
	kon_collider_t c = {0};

	c.type = KON_COLLIDER_BOX;
	c.enabled = 1;
	c.min = min;
	c.max = max;
	return c;
}

kon_collider_t kon_colliderCylinder(kon_vec3_t bottom, float radius, float height)
{
	kon_collider_t c = {0};

	c.type = KON_COLLIDER_CYLINDER;
	c.enabled = 1;
	c.center = bottom;
	c.radius = radius;
	c.height = height;
	return c;
}

kon_collider_t kon_colliderSphere(kon_vec3_t center, float radius)
{
	kon_collider_t c = {0};

	c.type = KON_COLLIDER_SPHERE;
	c.enabled = 1;
	c.center = center;
	c.radius = radius;
	return c;
}

kon_collider_t kon_colliderPlane(kon_vec3_t point, kon_vec3_t normal)
{
	kon_collider_t c = {0};

	c.type = KON_COLLIDER_PLANE;
	c.enabled = 1;
	c.normal = kon_vec3Normalize(normal);
	c.offset = kon_vec3Dot(c.normal, point);
	return c;
}

/*** the world ***/

void kon_worldInit(kon_world_t *world)
{
	memset(world, 0, sizeof(*world));
	world->tileHeight = 1.0f;
	world->gravity = 20.0f;
	world->stepHeight = 0.35f;
	world->maxSlope = 1.0f;
}

void kon_worldFree(kon_world_t *world)
{
	free(world->colliders);
	world->colliders = NULL;
	world->colliderCount = world->colliderCap = 0;
}

int kon_worldAdd(kon_world_t *world, kon_collider_t collider)
{
	int i;

	for (i = 0; i < world->colliderCount; i++) {
		if (world->colliders[i].type == KON_COLLIDER_NONE) {
			world->colliders[i] = collider;
			return i;
		}
	}
	if (world->colliderCount == world->colliderCap) {
		int cap = world->colliderCap ? world->colliderCap * 2 : 16;
		kon_collider_t *grown = realloc(world->colliders, (size_t)cap * sizeof(*grown));

		if (!grown) return -1;
		world->colliders = grown;
		world->colliderCap = cap;
	}
	world->colliders[world->colliderCount] = collider;
	return world->colliderCount++;
}

kon_collider_t *kon_worldCollider(kon_world_t *world, int index)
{
	if (index < 0 || index >= world->colliderCount || world->colliders[index].type == KON_COLLIDER_NONE) return NULL;
	return &world->colliders[index];
}

void kon_worldRemove(kon_world_t *world, int index)
{
	if (index < 0 || index >= world->colliderCount) return;
	memset(&world->colliders[index], 0, sizeof(world->colliders[index]));
}

/*** ground ***/

static float kon_colliderTop_(const kon_collider_t *c, float x, float z)
{
	switch (c->type) {
	case KON_COLLIDER_BOX:
		if (x >= c->min.x && x <= c->max.x && z >= c->min.z && z <= c->max.z) return c->max.y;
		break;
	case KON_COLLIDER_CYLINDER: {
		float dx = x - c->center.x, dz = z - c->center.z;

		if (dx * dx + dz * dz <= c->radius * c->radius) return c->center.y + c->height;
		break;
	}
	case KON_COLLIDER_PLANE:
		if (c->normal.y >= 0.7f) return (c->offset - c->normal.x * x - c->normal.z * z) / c->normal.y;
		break;
	default:
		break;
	}
	return KON_NO_GROUND;
}

float kon_worldGround(const kon_world_t *world, float x, float z, float feet, int hint, int *sector)
{
	float ground = KON_NO_GROUND;
	int s = -1, i, any = 0;

	if (world->sectors) {
		any = 1;
		s = kon_sectorAt(world->sectors, x, z, hint);
		if (s >= 0) ground = world->sectors->sectors[s].floor;
	}
	if (s < 0 && world->terrain) {
		any = 1;
		if (x >= 0.0f && z >= 0.0f && x <= (float)world->terrain->columns && z <= (float)world->terrain->rows) ground = kon_terrainHeight(world->terrain, x, z);
	}
	if (s < 0 && ground == KON_NO_GROUND && world->tiles) {
		any = 1;
		if (x >= 0.0f && z >= 0.0f && x < (float)world->tiles->columns && z < (float)world->tiles->rows) ground = 0.0f;
	}
	if (!any) ground = 0.0f;

	for (i = 0; i < world->colliderCount; i++) {
		const kon_collider_t *c = &world->colliders[i];
		float top;

		if (!c->enabled || c->type == KON_COLLIDER_NONE) continue;
		top = kon_colliderTop_(c, x, z);
		if (top != KON_NO_GROUND && top <= feet + world->stepHeight && top > ground) ground = top;
	}
	if (sector) *sector = s;
	return ground;
}

/*** pushing out ***/

static float kon_clampf_(float v, float lo, float hi)
{
	return v < lo ? lo : (v > hi ? hi : v);
}

/* the body can't step onto something that ends above its step, and something that starts above its head is no problem */
static int kon_blocks_(const kon_world_t *world, const kon_body_t *body, float lo, float hi)
{
	return hi > body->position.y + world->stepHeight && lo < body->position.y + body->height;
}

static int kon_pushSegment_(float *x, float *z, float r, float ax, float az, float bx, float bz, float nx, float nz)
{
	float ex = bx - ax, ez = bz - az, len2 = ex * ex + ez * ez;
	float t = len2 > 0.0f ? ((*x - ax) * ex + (*z - az) * ez) / len2 : 0.0f;
	float cx, cz, dx, dz, d;

	t = kon_clampf_(t, 0.0f, 1.0f);
	cx = ax + ex * t;
	cz = az + ez * t;
	dx = *x - cx;
	dz = *z - cz;
	d = sqrtf(dx * dx + dz * dz);
	if (d >= r) return 0;
	if (d < 1.0e-5f) {
		dx = nx;
		dz = nz;
		d = 0.0f;
	} else {
		dx /= d;
		dz /= d;
	}
	*x += dx * (r - d);
	*z += dz * (r - d);
	return 1;
}

static int kon_pushBox_(float *x, float *z, float r, float minX, float minZ, float maxX, float maxZ)
{
	float cx = kon_clampf_(*x, minX, maxX), cz = kon_clampf_(*z, minZ, maxZ);
	float dx = *x - cx, dz = *z - cz, d2 = dx * dx + dz * dz;

	if (d2 >= r * r) return 0;
	if (d2 > 1.0e-10f) {
		float d = sqrtf(d2);

		*x += dx / d * (r - d);
		*z += dz / d * (r - d);
	} else {
		/* the middle is inside, leave through the nearest side */
		float left = *x - minX, right = maxX - *x, up = *z - minZ, down = maxZ - *z;
		float best = left;

		if (right < best) best = right;
		if (up < best) best = up;
		if (down < best) best = down;
		if (best == left) *x = minX - r;
		else if (best == right) *x = maxX + r;
		else if (best == up) *z = minZ - r;
		else *z = maxZ + r;
	}
	return 1;
}

static int kon_pushCircle_(float *x, float *z, float r, float cx, float cz, float cr)
{
	float dx = *x - cx, dz = *z - cz, d = sqrtf(dx * dx + dz * dz), reach = r + cr;

	if (d >= reach) return 0;
	if (d < 1.0e-5f) {
		*x = cx + reach;
		return 1;
	}
	*x = cx + dx / d * reach;
	*z = cz + dz / d * reach;
	return 1;
}

/* is the way from one room into the next blocked for this body, because of the step, or because it would not fit */
static int kon_gapBlocks_(const kon_world_t *world, const kon_body_t *body, const kon_sector_t *from, const kon_sector_t *to)
{
	float stand = body->position.y > to->floor ? body->position.y : to->floor;

	if (to->floor - body->position.y > world->stepHeight) return 1;
	if (to->ceiling - stand < body->height) return 1;
	if (from->ceiling - stand < body->height) return 1;
	return 0;
}

static int kon_sectorSet_(const kon_sectorMap_t *map, int start, int *set)
{
	int n = 0, ring, i, k, j;

	set[n++] = start;
	for (ring = 0; ring < 2; ring++) {
		int count = n;

		for (i = 0; i < count; i++) {
			const kon_sector_t *sector = &map->sectors[set[i]];

			for (k = 0; k < sector->count; k++) {
				int p = map->edges[sector->first + k].portal;

				if (p < 0) continue;
				for (j = 0; j < n; j++) if (set[j] == p) break;
				if (j == n && n < KON_SECTOR_SET) set[n++] = p;
			}
		}
	}
	return n;
}

/* one pass over everything the body can bump into. touching is set to the last collider that moved it */
static int kon_pushAll_(const kon_world_t *world, kon_body_t *body, float *x, float *z)
{
	float r = body->radius, feet = body->position.y, top = feet + body->height;
	int moved = 0, i;

	if (world->sectors && body->sector >= 0) {
		const kon_sectorMap_t *map = world->sectors;
		int set[KON_SECTOR_SET], n = kon_sectorSet_(map, body->sector, set), a, k;

		for (a = 0; a < n; a++) {
			const kon_sector_t *sector = &map->sectors[set[a]];

			for (k = 0; k < sector->count; k++) {
				kon_vec2_t p = kon_sectorCorner(map, set[a], k), q = kon_sectorCorner(map, set[a], k + 1);
				float ex = q.x - p.x, ez = q.y - p.y, len = sqrtf(ex * ex + ez * ez);
				int portal = map->edges[sector->first + k].portal;

				if (len <= 0.0f) continue;
				if (portal < 0) {
					if (!(feet < sector->ceiling && top > sector->floor)) continue;
				} else if (!kon_gapBlocks_(world, body, sector, &map->sectors[portal])) {
					continue;
				}
				moved |= kon_pushSegment_(x, z, r, p.x, p.y, q.x, q.y, ez / len, -ex / len);
			}
		}
	}

	if (world->tiles) {
		const kon_tilemap_t *tiles = world->tiles;
		int column, row, c0 = (int)floorf(*x - r), c1 = (int)floorf(*x + r), r0 = (int)floorf(*z - r), r1 = (int)floorf(*z + r);

		if (kon_blocks_(world, body, 0.0f, world->tileHeight)) {
			for (row = r0; row <= r1; row++) {
				for (column = c0; column <= c1; column++) {
					int solid = 1;

					if (column >= 0 && row >= 0 && column < tiles->columns && row < tiles->rows) {
						uint16_t id = kon_tilemapAt(tiles, column, row);

						solid = id < world->solidCount && world->solid[id];
					}
					if (solid) moved |= kon_pushBox_(x, z, r, (float)column, (float)row, (float)column + 1.0f, (float)row + 1.0f);
				}
			}
		}
	}

	for (i = 0; i < world->colliderCount; i++) {
		const kon_collider_t *c = &world->colliders[i];
		int hit = 0;

		if (!c->enabled) continue;
		switch (c->type) {
		case KON_COLLIDER_BOX:
			if (kon_blocks_(world, body, c->min.y, c->max.y)) hit = kon_pushBox_(x, z, r, c->min.x, c->min.z, c->max.x, c->max.z);
			break;
		case KON_COLLIDER_CYLINDER:
			if (kon_blocks_(world, body, c->center.y, c->center.y + c->height)) hit = kon_pushCircle_(x, z, r, c->center.x, c->center.z, c->radius);
			break;
		case KON_COLLIDER_SPHERE:
			if (kon_blocks_(world, body, c->center.y - c->radius, c->center.y + c->radius)) hit = kon_pushCircle_(x, z, r, c->center.x, c->center.z, c->radius);
			break;
		case KON_COLLIDER_PLANE:
			if (c->normal.y < 0.7f) {
				float nh = sqrtf(c->normal.x * c->normal.x + c->normal.z * c->normal.z);
				float d = c->normal.x * *x + c->normal.y * (feet + body->height * 0.5f) + c->normal.z * *z - c->offset;

				if (nh > 1.0e-4f && d < r * nh) {
					float t = (r * nh - d) / (nh * nh);

					*x += c->normal.x * t;
					*z += c->normal.z * t;
					hit = 1;
				}
			}
			break;
		default:
			break;
		}
		if (hit) body->touching = i;
		moved |= hit;
	}
	return moved;
}

/*** moving ***/

/* tries to stand at x, z. the body is only changed if it works */
static int kon_try_(const kon_world_t *world, kon_body_t *body, float x, float z, float oldX, float oldZ)
{
	kon_body_t probe = *body;
	float ground, dist;
	int pass, s;

	probe.sector = body->sector;
	for (pass = 0; pass < 4; pass++) {
		if (!kon_pushAll_(world, &probe, &x, &z)) break;
	}
	ground = kon_worldGround(world, x, z, body->position.y, body->sector, &s);
	if (ground == KON_NO_GROUND) return 0;

	if (world->terrain && s < 0 && kon_sectorAt(world->sectors, oldX, oldZ, -1) < 0) {
		float before = kon_terrainHeight(world->terrain, oldX, oldZ), after = kon_terrainHeight(world->terrain, x, z);

		dist = sqrtf((x - oldX) * (x - oldX) + (z - oldZ) * (z - oldZ));
		if (after > body->position.y && after - before > world->maxSlope * dist + 1.0e-4f) return 0;
	}
	body->position.x = x;
	body->position.z = z;
	body->touching = probe.touching;
	if (s >= 0) body->sector = s;
	return 1;
}

void kon_bodyInit(kon_body_t *body, float x, float y, float z, float radius, float height)
{
	memset(body, 0, sizeof(*body));
	body->position = KON_VEC3(x, y, z);
	body->radius = radius;
	body->height = height;
	body->sector = -1;
	body->touching = -1;
	body->jumpSpeed = 6.0f;
}

int kon_bodyJump(kon_body_t *body)
{
	if (!body->onGround || body->jumpSpeed <= 0.0f) return 0;
	body->vy = body->jumpSpeed;
	body->onGround = 0;
	return 1;
}

void kon_worldPlace(const kon_world_t *world, kon_body_t *body)
{
	int s;
	float ground = kon_worldGround(world, body->position.x, body->position.z, body->position.y, body->sector, &s);

	if (s >= 0) body->sector = s;
	if (ground != KON_NO_GROUND) body->position.y = ground;
	body->vy = 0.0f;
	body->onGround = 1;
}

void kon_worldMove(kon_world_t *world, kon_body_t *body, float dx, float dz, double dt)
{
	float x = body->position.x, z = body->position.z, ground, ceiling = 1.0e30f;
	int s;

	body->touching = -1;
	if (dx != 0.0f || dz != 0.0f) {
		if (!kon_try_(world, body, x + dx, z + dz, x, z)) {
			if (!kon_try_(world, body, x + dx, z, x, z)) kon_try_(world, body, x, z + dz, x, z);
		}
	}

	ground = kon_worldGround(world, body->position.x, body->position.z, body->position.y, body->sector, &s);
	if (s >= 0) {
		body->sector = s;
		ceiling = world->sectors->sectors[s].ceiling;
	}
	if (ground == KON_NO_GROUND) ground = body->position.y;

	if (body->vy <= 0.0f && body->position.y - ground <= world->stepHeight) {
		body->position.y = ground;
		body->vy = 0.0f;
		body->onGround = 1;
	} else {
		body->vy -= world->gravity * (float)dt;
		body->position.y += body->vy * (float)dt;
		body->onGround = 0;
		if (body->vy <= 0.0f && body->position.y <= ground) {
			body->position.y = ground;
			body->vy = 0.0f;
			body->onGround = 1;
		}
	}
	if (body->position.y + body->height > ceiling) {
		body->position.y = ceiling - body->height;
		if (body->vy > 0.0f) body->vy = 0.0f;
	}
}

/*** rays ***/

typedef struct kon_ray {
	kon_vec3_t origin, dir;
	float best; /* the nearest hit so far, starts at maxDistance */
	kon_rayHit_t hit;
} kon_ray_t;

static void kon_rayKeep_(kon_ray_t *ray, float t, int kind, kon_vec3_t normal, int sector, int edge, int collider)
{
	if (t < 0.0f || t >= ray->best) return;
	ray->best = t;
	ray->hit.kind = kind;
	ray->hit.distance = t;
	ray->hit.point = KON_VEC3(ray->origin.x + ray->dir.x * t, ray->origin.y + ray->dir.y * t, ray->origin.z + ray->dir.z * t);
	if (kon_vec3Dot(normal, ray->dir) > 0.0f) normal = KON_VEC3(-normal.x, -normal.y, -normal.z);
	ray->hit.normal = normal;
	ray->hit.sector = sector;
	ray->hit.edge = edge;
	ray->hit.collider = collider;
}

/* walks the ray from room to room through the openings until it runs into something */
static void kon_raySectors_(const kon_world_t *world, kon_ray_t *ray)
{
	const kon_sectorMap_t *map = world->sectors;
	int s = kon_sectorAt(map, ray->origin.x, ray->origin.z, -1), hops;
	float enter = 0.0f;

	for (hops = 0; s >= 0 && hops < 256; hops++) {
		const kon_sector_t *sector = &map->sectors[s];
		float exitT = 1.0e30f, floorT = 1.0e30f, ceilT = 1.0e30f, y;
		int exitEdge = -1, k;

		for (k = 0; k < sector->count; k++) {
			kon_vec2_t p = kon_sectorCorner(map, s, k), q = kon_sectorCorner(map, s, k + 1);
			float ex = q.x - p.x, ez = q.y - p.y, len = sqrtf(ex * ex + ez * ez), nx, nz, along, t, hx, hz;

			if (len <= 0.0f) continue;
			nx = ez / len;
			nz = -ex / len;
			along = nx * ray->dir.x + nz * ray->dir.z;
			if (along >= -1.0e-7f) continue;
			t = (nx * (p.x - ray->origin.x) + nz * (p.y - ray->origin.z)) / along;
			if (t < enter - 1.0e-4f) continue;
			hx = ray->origin.x + ray->dir.x * t - p.x;
			hz = ray->origin.z + ray->dir.z * t - p.y;
			along = (hx * ex + hz * ez) / (len * len);
			if (along < -1.0e-5f || along > 1.0f + 1.0e-5f) continue;
			if (t < exitT) {
				exitT = t;
				exitEdge = k;
			}
		}
		if (ray->dir.y < -1.0e-7f) floorT = (sector->floor - ray->origin.y) / ray->dir.y;
		if (ray->dir.y > 1.0e-7f) ceilT = (sector->ceiling - ray->origin.y) / ray->dir.y;
		if (floorT < enter) floorT = 1.0e30f;
		if (ceilT < enter) ceilT = 1.0e30f;

		if (floorT <= exitT && floorT <= ceilT) {
			kon_rayKeep_(ray, floorT, KON_HIT_FLOOR, KON_VEC3(0, 1, 0), s, -1, -1);
			return;
		}
		if (ceilT <= exitT) {
			kon_rayKeep_(ray, ceilT, KON_HIT_CEILING, KON_VEC3(0, -1, 0), s, -1, -1);
			return;
		}
		if (exitEdge < 0 || exitT >= ray->best) return;

		y = ray->origin.y + ray->dir.y * exitT;
		{
			kon_vec2_t p = kon_sectorCorner(map, s, exitEdge), q = kon_sectorCorner(map, s, exitEdge + 1);
			float ex = q.x - p.x, ez = q.y - p.y, len = sqrtf(ex * ex + ez * ez);
			int portal = map->edges[sector->first + exitEdge].portal;

			if (portal >= 0 && y >= map->sectors[portal].floor && y <= map->sectors[portal].ceiling) {
				enter = exitT;
				s = portal;
				continue;
			}
			kon_rayKeep_(ray, exitT, KON_HIT_WALL, KON_VEC3(ez / len, 0, -ex / len), s, exitEdge, -1);
			return;
		}
	}
}

static void kon_rayBox_(kon_ray_t *ray, kon_vec3_t min, kon_vec3_t max, int index)
{
	float lo = 0.0f, hi = ray->best, o[3], d[3], a[3], b[3];
	int i, axis = -1, sign = 0;

	o[0] = ray->origin.x; o[1] = ray->origin.y; o[2] = ray->origin.z;
	d[0] = ray->dir.x; d[1] = ray->dir.y; d[2] = ray->dir.z;
	a[0] = min.x; a[1] = min.y; a[2] = min.z;
	b[0] = max.x; b[1] = max.y; b[2] = max.z;

	for (i = 0; i < 3; i++) {
		if (fabsf(d[i]) < 1.0e-9f) {
			if (o[i] < a[i] || o[i] > b[i]) return;
		} else {
			float t0 = (a[i] - o[i]) / d[i], t1 = (b[i] - o[i]) / d[i];
			int s = -1;

			if (t0 > t1) {
				float swap = t0;

				t0 = t1;
				t1 = swap;
				s = 1;
			}
			if (t0 > lo) {
				lo = t0;
				axis = i;
				sign = s;
			}
			if (t1 < hi) hi = t1;
			if (lo > hi) return;
		}
	}
	if (axis < 0) return; /* started inside */
	{
		kon_vec3_t normal = KON_VEC3(0, 0, 0);

		if (axis == 0) normal.x = (float)sign;
		else if (axis == 1) normal.y = (float)sign;
		else normal.z = (float)sign;
		kon_rayKeep_(ray, lo, KON_HIT_COLLIDER, normal, -1, -1, index);
	}
}

static void kon_rayCylinder_(kon_ray_t *ray, kon_vec3_t base, float radius, float height, int index)
{
	float ox = ray->origin.x - base.x, oz = ray->origin.z - base.z, a = ray->dir.x * ray->dir.x + ray->dir.z * ray->dir.z;
	float bottom = base.y, top = base.y + height, t;

	if (a > 1.0e-9f) {
		float b = ox * ray->dir.x + oz * ray->dir.z, c = ox * ox + oz * oz - radius * radius, disc = b * b - a * c;

		if (disc >= 0.0f && c > 0.0f) {
			float y;

			t = (-b - sqrtf(disc)) / a;
			y = ray->origin.y + ray->dir.y * t;
			if (t >= 0.0f && y >= bottom && y <= top) kon_rayKeep_(ray, t, KON_HIT_COLLIDER, kon_vec3Normalize(KON_VEC3(ox + ray->dir.x * t, 0, oz + ray->dir.z * t)), -1, -1, index);
		}
	}
	if (fabsf(ray->dir.y) > 1.0e-9f) {
		int k;

		for (k = 0; k < 2; k++) {
			float y = k ? top : bottom, dx, dz;

			t = (y - ray->origin.y) / ray->dir.y;
			dx = ox + ray->dir.x * t;
			dz = oz + ray->dir.z * t;
			if (t >= 0.0f && dx * dx + dz * dz <= radius * radius) kon_rayKeep_(ray, t, KON_HIT_COLLIDER, KON_VEC3(0, k ? 1.0f : -1.0f, 0), -1, -1, index);
		}
	}
}

static void kon_raySphere_(kon_ray_t *ray, kon_vec3_t center, float radius, int index)
{
	kon_vec3_t oc = kon_vec3Sub(ray->origin, center);
	float b = kon_vec3Dot(oc, ray->dir), c = kon_vec3Dot(oc, oc) - radius * radius, disc = b * b - c, t;

	if (disc < 0.0f || c <= 0.0f) return;
	t = -b - sqrtf(disc);
	kon_rayKeep_(ray, t, KON_HIT_COLLIDER, kon_vec3Normalize(KON_VEC3(oc.x + ray->dir.x * t, oc.y + ray->dir.y * t, oc.z + ray->dir.z * t)), -1, -1, index);
}

static void kon_rayTiles_(const kon_world_t *world, kon_ray_t *ray)
{
	const kon_tilemap_t *tiles = world->tiles;
	int column = (int)floorf(ray->origin.x), row = (int)floorf(ray->origin.z), stepC = ray->dir.x > 0 ? 1 : -1, stepR = ray->dir.z > 0 ? 1 : -1, face = 0, n;
	float nextC = ray->dir.x > 0 ? (float)column + 1.0f : (float)column, nextR = ray->dir.z > 0 ? (float)row + 1.0f : (float)row;
	float tC = fabsf(ray->dir.x) > 1.0e-9f ? (nextC - ray->origin.x) / ray->dir.x : 1.0e30f, tR = fabsf(ray->dir.z) > 1.0e-9f ? (nextR - ray->origin.z) / ray->dir.z : 1.0e30f;
	float dC = fabsf(ray->dir.x) > 1.0e-9f ? (float)stepC / ray->dir.x : 1.0e30f, dR = fabsf(ray->dir.z) > 1.0e-9f ? (float)stepR / ray->dir.z : 1.0e30f, t = 0.0f;

	for (n = 0; n < 4096 && t < ray->best; n++) {
		int solid = 1;

		if (column >= 0 && row >= 0 && column < tiles->columns && row < tiles->rows) {
			uint16_t id = kon_tilemapAt(tiles, column, row);

			solid = id < world->solidCount && world->solid[id];
		}
		if (solid && n > 0) {
			float y = ray->origin.y + ray->dir.y * t;

			if (y >= 0.0f && y <= world->tileHeight) {
				kon_vec3_t normal = face == 0 ? KON_VEC3((float)-stepC, 0, 0) : KON_VEC3(0, 0, (float)-stepR);

				kon_rayKeep_(ray, t, KON_HIT_TILE, normal, -1, -1, -1);
				return;
			}
		}
		if (tC < tR) {
			t = tC;
			tC += dC;
			column += stepC;
			face = 0;
		} else {
			t = tR;
			tR += dR;
			row += stepR;
			face = 1;
		}
		if (tC >= 1.0e29f && tR >= 1.0e29f) return;
	}
}

int kon_worldRay(const kon_world_t *world, kon_vec3_t origin, kon_vec3_t direction, float maxDistance, kon_rayHit_t *hit)
{
	kon_ray_t ray;
	float length = kon_vec3Length(direction);
	int i;

	if (hit) memset(hit, 0, sizeof(*hit));
	if (length < 1.0e-6f || maxDistance <= 0.0f) return 0;
	memset(&ray, 0, sizeof(ray));
	ray.origin = origin;
	ray.dir = KON_VEC3(direction.x / length, direction.y / length, direction.z / length);
	ray.best = maxDistance;
	ray.hit.sector = ray.hit.edge = ray.hit.collider = -1;

	if (world->sectors) kon_raySectors_(world, &ray);
	if (world->terrain) {
		kon_vec3_t point;

		if (kon_terrainRay(world->terrain, origin, ray.dir, ray.best, &point)) {
			float dx = point.x - origin.x, dy = point.y - origin.y, dz = point.z - origin.z;
			float h = 0.5f, nx = kon_terrainHeight(world->terrain, point.x - h, point.z) - kon_terrainHeight(world->terrain, point.x + h, point.z);
			float nz = kon_terrainHeight(world->terrain, point.x, point.z - h) - kon_terrainHeight(world->terrain, point.x, point.z + h);

			kon_rayKeep_(&ray, sqrtf(dx * dx + dy * dy + dz * dz), KON_HIT_TERRAIN, kon_vec3Normalize(KON_VEC3(nx, 2.0f * h, nz)), -1, -1, -1);
		}
	}
	if (world->tiles) kon_rayTiles_(world, &ray);
	for (i = 0; i < world->colliderCount; i++) {
		const kon_collider_t *c = &world->colliders[i];

		if (!c->enabled) continue;
		switch (c->type) {
		case KON_COLLIDER_BOX: kon_rayBox_(&ray, c->min, c->max, i); break;
		case KON_COLLIDER_CYLINDER: kon_rayCylinder_(&ray, c->center, c->radius, c->height, i); break;
		case KON_COLLIDER_SPHERE: kon_raySphere_(&ray, c->center, c->radius, i); break;
		case KON_COLLIDER_PLANE: {
			float along = kon_vec3Dot(c->normal, ray.dir);

			if (along < -1.0e-7f) kon_rayKeep_(&ray, (c->offset - kon_vec3Dot(c->normal, origin)) / along, KON_HIT_COLLIDER, c->normal, -1, -1, i);
			break;
		}
		default: break;
		}
	}
	if (hit) *hit = ray.hit;
	return ray.hit.kind != KON_HIT_NONE;
}

int kon_worldVisible(const kon_world_t *world, kon_vec3_t from, kon_vec3_t to)
{
	kon_vec3_t d = kon_vec3Sub(to, from);
	float length = kon_vec3Length(d);

	if (length < 1.0e-6f) return 1;
	return !kon_worldRay(world, from, d, length - 1.0e-3f, NULL);
}