world: rays and line of sight through sectors, terrain, tiles and shapes

3 files changed, 309 insertions, 2 deletions

diff --git a/examples/sectorview.c b/examples/sectorview.c
index 821ce52..2d5b5df 100644
--- a/examples/sectorview.c
+++ b/examples/sectorview.c
@@ -4,7 +4,8 @@
  * build:  ./build.sh -d -m 3d,sector,world,font obj/sectorview
  * run:    obj/sectorview            (from the folder with examples/)
  *
- * click to grab the mouse, tab lets go. w and s walk, a and d strafe, space jumps, e presses a button close to you.
+ * click to grab the mouse, tab lets go, a click after that shoots a ray and the top line says what it hit. w and s walk, a and d strafe,
+ * space jumps, e presses a button close to you.
  * the door is a box in the world that the program lifts, nothing else about it is built in
  * the map is examples/maps/house.kmap, it is plain text so change it and run again. try moving the watcher
  */
@@ -118,6 +119,16 @@ static int event(kon_program_t *program, const kon_event_t *ev, void *user)
 	int i, n, ids[8];
 
 	if (kon_fpEvent(&state->input, program, ev)) return 1;
+	if (ev->type == KON_EVENT_MOUSE_DOWN && kon_isMouseCaptured(program->window)) {
+		static const char *const kinds[] = { "nothing", "a wall", "the floor", "the ceiling", "a collider", "the ground", "a tile" };
+		kon_rayHit_t hit;
+		kon_vec3_t eye = KON_VEC3(state->body.position.x, state->feet + EYE, state->body.position.z);
+		kon_vec3_t dir = KON_VEC3(sinf(state->input.yaw) * cosf(state->input.pitch), sinf(state->input.pitch), -cosf(state->input.yaw) * cosf(state->input.pitch));
+
+		if (kon_worldRay(&state->world, eye, dir, 50.0f, &hit)) snprintf(state->note, sizeof(state->note), "shot %s, %.1f away", kinds[hit.kind], (double)hit.distance);
+		else snprintf(state->note, sizeof(state->note), "shot, hit nothing");
+		return 1;
+	}
 	if (ev->type == KON_EVENT_KEY_DOWN && ev->key == KON_KEY_SPACE) {
 		kon_bodyJump(&state->body);
 		return 1;
@@ -229,7 +240,7 @@ static void draw(kon_program_t *program, kon_framebuffer_t *game, void *user)
 	kon_fillRectangle(game, game->width / 2 - 3, game->height / 2, 7, 1, COL_NOTE);
 	kon_fillRectangle(game, game->width / 2, game->height / 2 - 3, 1, 7, COL_NOTE);
 	if (program->font) {
-		snprintf(line, sizeof(line), "room %d   click to look, e presses buttons, space jumps", state->body.sector);
+		snprintf(line, sizeof(line), "room %d   click shoots a ray, e presses buttons, space jumps", state->body.sector);
 		kon_drawText(game, program->font, 8, 16, line, COL_DIM);
 		if (state->note[0]) kon_drawText(game, program->font, 8, 30, state->note, COL_NOTE);
 	}
diff --git a/kon/konworld.c b/kon/konworld.c
index be9d2c2..adf7f77 100644
--- a/kon/konworld.c
+++ b/kon/konworld.c
@@ -483,3 +483,271 @@ void kon_worldMove(kon_world_t *world, kon_body_t *body, float dx, float dz, dou
 		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);
+}
diff --git a/kon/konworld.h b/kon/konworld.h
index bce5187..364d400 100644
--- a/kon/konworld.h
+++ b/kon/konworld.h
@@ -120,4 +120,32 @@ void kon_worldPlace(const kon_world_t *world, kon_body_t *body);
    of the world. then gravity: steps up are taken at once and drops are falls. dt is seconds */
 void kon_worldMove(kon_world_t *world, kon_body_t *body, float dx, float dz, double dt);
 
+/*** rays ***/
+
+typedef enum kon_hitKind {
+	KON_HIT_NONE = 0,
+	KON_HIT_WALL,     /* a wall of a sector, or the step or lintel of an opening */
+	KON_HIT_FLOOR,
+	KON_HIT_CEILING,
+	KON_HIT_COLLIDER,
+	KON_HIT_TERRAIN,
+	KON_HIT_TILE
+} kon_hitKind_t;
+
+typedef struct kon_rayHit {
+	int kind;
+	float distance;
+	kon_vec3_t point, normal; /* normal faces back at the ray */
+	int sector;   /* the room a wall, floor or ceiling belongs to, -1 for the rest */
+	int edge;     /* which wall of that room, -1 for the rest */
+	int collider; /* the index, -1 for the rest */
+} kon_rayHit_t;
+
+/* shoots a ray and finds the first thing it hits within maxDistance. direction does not have to be 1 long. hit can be NULL.
+   a ray through the rooms of a sector map has to start inside one. shapes the ray starts inside are not hit */
+int kon_worldRay(const kon_world_t *world, kon_vec3_t origin, kon_vec3_t direction, float maxDistance, kon_rayHit_t *hit);
+
+/* 1 if nothing is between the two points. for "can the monster see me" and "is the light reaching here" */
+int kon_worldVisible(const kon_world_t *world, kon_vec3_t from, kon_vec3_t to);
+
 #endif