1 files changed, 445 insertions, 3 deletions

diff --git a/kon/kon3d.c b/kon/kon3d.c
index 8184039..6d6cee7 100644
--- a/kon/kon3d.c
+++ b/kon/kon3d.c
@@ -28,6 +28,7 @@
 #include <math.h>
 #include <stdio.h>
 #include <stdlib.h>
+#include <string.h>
 
 /*** private ***/
 
@@ -71,7 +72,12 @@ void kon_fpInit(kon_fp_t *fp, const kon_tilemap_t *map, int column, int row)
 	fp->speed = 2.5f;
 	fp->turnSpeed = 2.0f;
 	fp->fov = KON_DEG2RAD(60);
+	fp->farZ = 40.0f;
 	fp->forward = fp->strafe = fp->turn = 0;
+	fp->feet = 0.0f;
+	fp->fall = 0.0f;
+	fp->maxSlope = 1.0f;
+	fp->gravity = 20.0f;
 	fp->body = KON_BOX2(((float)column + 0.5f) * (float)map->tileWidth - size * 0.5f, ((float)row + 0.5f) * (float)map->tileHeight - size * 0.5f, size, size);
 }
 
@@ -109,22 +115,74 @@ int kon_fpEvent(kon_fp_t *fp, kon_program_t *program, const kon_event_t *ev)
 	return 1;
 }
 
-void kon_fpUpdate(kon_fp_t *fp, kon_program_t *program, const kon_tilemap_t *map, const uint8_t *solid, int solidCount, double dt)
+static float kon_groundAt_(const kon_fp_t *fp, const kon_tilemap_t *map, const kon_terrain_t *terrain)
+{
+	return kon_terrainHeight(terrain, (fp->body.x + fp->body.w * 0.5f) / (float)map->tileWidth, (fp->body.y + fp->body.h * 0.5f) / (float)map->tileHeight);
+}
+
+/* going up more than maxSlope allows, from the ground height before the move to the one at the body now */
+static int kon_tooSteep_(const kon_fp_t *fp, const kon_tilemap_t *map, const kon_terrain_t *terrain, float before, float oldX, float oldY)
+{
+	float dx = (fp->body.x - oldX) / (float)map->tileWidth, dy = (fp->body.y - oldY) / (float)map->tileHeight;
+	float run = sqrtf(dx * dx + dy * dy);
+
+	return run > 0.0f && kon_groundAt_(fp, map, terrain) - before > fp->maxSlope * run;
+}
+
+void kon_fpPlace(kon_fp_t *fp, const kon_tilemap_t *map, const kon_terrain_t *terrain)
+{
+	fp->feet = terrain ? kon_groundAt_(fp, map, terrain) : 0.0f;
+	fp->fall = 0.0f;
+}
+
+void kon_fpUpdate(kon_fp_t *fp, kon_program_t *program, const kon_tilemap_t *map, const uint8_t *solid, int solidCount, const kon_terrain_t *terrain, double dt)
 {
 	float step = fp->speed * (float)dt * (float)map->tileWidth;
 	float fx = sinf(fp->yaw), fz = -cosf(fp->yaw);
 	float dx = (fx * (float)fp->forward - fz * (float)fp->strafe) * step;
 	float dz = (fz * (float)fp->forward + fx * (float)fp->strafe) * step;
+	float oldX = fp->body.x, oldY = fp->body.y, ground = 0.0f, before = 0.0f;
 
 	if (kon_debugConsoleOpen(program->debug) && kon_isMouseCaptured(program->window)) kon_setMouseCapture(program->window, false);
 
 	fp->yaw += (float)fp->turn * fp->turnSpeed * (float)dt;
+	if (terrain) before = kon_groundAt_(fp, map, terrain);
 	kon_tilemapMove(map, &fp->body, dx, dz, solid, solidCount);
+
+	if (!terrain) return;
+
+	/* too steep to climb, try sliding along it on one axis before giving up */
+	if (kon_tooSteep_(fp, map, terrain, before, oldX, oldY)) {
+		float newX = fp->body.x, newY = fp->body.y;
+
+		fp->body.x = newX;
+		fp->body.y = oldY;
+		if (kon_tooSteep_(fp, map, terrain, before, oldX, oldY)) {
+			fp->body.x = oldX;
+			fp->body.y = newY;
+			if (kon_tooSteep_(fp, map, terrain, before, oldX, oldY)) fp->body.y = oldY;
+		}
+	}
+
+	ground = kon_groundAt_(fp, map, terrain);
+	if (fp->feet < ground) {
+		float t = (float)dt * 18.0f;
+
+		fp->feet += (ground - fp->feet) * (t > 1.0f ? 1.0f : t);
+		fp->fall = 0.0f;
+	} else if (fp->feet > ground) {
+		fp->fall += fp->gravity * (float)dt;
+		fp->feet -= fp->fall * (float)dt;
+		if (fp->feet <= ground) {
+			fp->feet = ground;
+			fp->fall = 0.0f;
+		}
+	}
 }
 
 kon_vec3_t kon_fpEye(const kon_fp_t *fp, const kon_tilemap_t *map)
 {
-	return KON_VEC3((fp->body.x + fp->body.w * 0.5f) / (float)map->tileWidth, fp->eyeHeight, (fp->body.y + fp->body.h * 0.5f) / (float)map->tileHeight);
+	return KON_VEC3((fp->body.x + fp->body.w * 0.5f) / (float)map->tileWidth, fp->feet + fp->eyeHeight, (fp->body.y + fp->body.h * 0.5f) / (float)map->tileHeight);
 }
 
 kon_camera_t kon_fpCamera(const kon_fp_t *fp, const kon_tilemap_t *map)
@@ -136,7 +194,7 @@ kon_camera_t kon_fpCamera(const kon_fp_t *fp, const kon_tilemap_t *map)
 	camera.target = KON_VEC3(eye.x + sinf(fp->yaw) * cosf(fp->pitch), eye.y + sinf(fp->pitch), eye.z - cosf(fp->yaw) * cosf(fp->pitch));
 	camera.fov = fp->fov;
 	camera.nearZ = 0.05f;
-	camera.farZ = 40.0f;
+	camera.farZ = fp->farZ;
 	return camera;
 }
 
@@ -206,6 +264,390 @@ void kon_drawLevel(kon_framebuffer_t *fb, const kon_camera_t *camera, const kon_
 		KON_VEC3(0, -1, 0), KON_VEC2(0, 0), KON_VEC2(w, d));
 }
 
+/*** terrain ***/
+
+static float *kon_corner_(const kon_terrain_t *terrain, int column, int row)
+{
+	return &terrain->heights[(size_t)row * (size_t)(terrain->columns + 1) + (size_t)column];
+}
+
+static void kon_chunkBounds_(kon_terrain_t *terrain, int cx, int cz)
+{
+	int x0 = cx * terrain->chunk, z0 = cz * terrain->chunk;
+	int x1 = x0 + terrain->chunk, z1 = z0 + terrain->chunk;
+	float low, high;
+	int x, z;
+
+	if (x1 > terrain->columns) x1 = terrain->columns;
+	if (z1 > terrain->rows) z1 = terrain->rows;
+	low = high = *kon_corner_(terrain, x0, z0);
+	for (z = z0; z <= z1; z++) {
+		for (x = x0; x <= x1; x++) {
+			float h = *kon_corner_(terrain, x, z);
+
+			if (h < low) low = h;
+			if (h > high) high = h;
+		}
+	}
+	terrain->chunkMin[cz * terrain->chunkColumns + cx] = low;
+	terrain->chunkMax[cz * terrain->chunkColumns + cx] = high;
+}
+
+/* every chunk that has a corner inside the cell rectangle, a corner on a border belongs to both chunks */
+static void kon_boundsAround_(kon_terrain_t *terrain, int x0, int z0, int x1, int z1)
+{
+	int cx0 = (x0 - 1) / terrain->chunk, cx1 = x1 / terrain->chunk;
+	int cz0 = (z0 - 1) / terrain->chunk, cz1 = z1 / terrain->chunk;
+	int cx, cz;
+
+	if (x0 < 1) cx0 = 0;
+	if (z0 < 1) cz0 = 0;
+	if (cx1 >= terrain->chunkColumns) cx1 = terrain->chunkColumns - 1;
+	if (cz1 >= terrain->chunkRows) cz1 = terrain->chunkRows - 1;
+	for (cz = cz0; cz <= cz1; cz++) {
+		for (cx = cx0; cx <= cx1; cx++) kon_chunkBounds_(terrain, cx, cz);
+	}
+}
+
+kon_terrain_t *kon_terrainCreate(int columns, int rows)
+{
+	kon_terrain_t *terrain;
+	size_t chunks;
+
+	if (columns < 1 || rows < 1 || columns > 4096 || rows > 4096) return NULL;
+	terrain = calloc(1, sizeof(kon_terrain_t));
+	if (!terrain) return NULL;
+
+	terrain->columns = columns;
+	terrain->rows = rows;
+	terrain->chunk = 16;
+	terrain->chunkColumns = (columns + terrain->chunk - 1) / terrain->chunk;
+	terrain->chunkRows = (rows + terrain->chunk - 1) / terrain->chunk;
+	chunks = (size_t)terrain->chunkColumns * (size_t)terrain->chunkRows;
+
+	terrain->heights = calloc((size_t)(columns + 1) * (size_t)(rows + 1), sizeof(float));
+	terrain->chunkMin = calloc(chunks, sizeof(float));
+	terrain->chunkMax = calloc(chunks, sizeof(float));
+	if (!terrain->heights || !terrain->chunkMin || !terrain->chunkMax) {
+		kon_terrainFree(terrain);
+		return NULL;
+	}
+	return terrain;
+}
+
+void kon_terrainFree(kon_terrain_t *terrain)
+{
+	if (!terrain) return;
+	free(terrain->heights);
+	free(terrain->chunkMin);
+	free(terrain->chunkMax);
+	free(terrain);
+}
+
+float kon_terrainCorner(const kon_terrain_t *terrain, int column, int row)
+{
+	if (!terrain || column < 0 || row < 0 || column > terrain->columns || row > terrain->rows) return 0.0f;
+	return *kon_corner_(terrain, column, row);
+}
+
+void kon_terrainSetCorner(kon_terrain_t *terrain, int column, int row, float height)
+{
+	if (!terrain || column < 0 || row < 0 || column > terrain->columns || row > terrain->rows) return;
+	*kon_corner_(terrain, column, row) = height;
+	kon_boundsAround_(terrain, column, row, column, row);
+}
+
+float kon_terrainHeight(const kon_terrain_t *terrain, float x, float z)
+{
+	float fx, fz, a, b, c, d;
+	int column, row;
+
+	if (!terrain) return 0.0f;
+	if (x < 0.0f) x = 0.0f;
+	if (z < 0.0f) z = 0.0f;
+	if (x > (float)terrain->columns) x = (float)terrain->columns;
+	if (z > (float)terrain->rows) z = (float)terrain->rows;
+
+	column = (int)x;
+	row = (int)z;
+	if (column >= terrain->columns) column = terrain->columns - 1;
+	if (row >= terrain->rows) row = terrain->rows - 1;
+	fx = x - (float)column;
+	fz = z - (float)row;
+
+	a = *kon_corner_(terrain, column, row);
+	b = *kon_corner_(terrain, column + 1, row);
+	c = *kon_corner_(terrain, column + 1, row + 1);
+	d = *kon_corner_(terrain, column, row + 1);
+
+	/* the cell is split from its top left corner to its bottom right one */
+	if (fz >= fx) return a + (d - a) * fz + (c - d) * fx;
+	return a + (b - a) * fx + (c - b) * fz;
+}
+
+void kon_terrainRaise(kon_terrain_t *terrain, float x, float z, float radius, float amount)
+{
+	int x0, x1, z0, z1, column, row;
+
+	if (!terrain || radius <= 0.0f) return;
+	x0 = (int)floorf(x - radius);
+	x1 = (int)ceilf(x + radius);
+	z0 = (int)floorf(z - radius);
+	z1 = (int)ceilf(z + radius);
+	if (x0 < 0) x0 = 0;
+	if (z0 < 0) z0 = 0;
+	if (x1 > terrain->columns) x1 = terrain->columns;
+	if (z1 > terrain->rows) z1 = terrain->rows;
+	if (x0 > x1 || z0 > z1) return;
+
+	for (row = z0; row <= z1; row++) {
+		for (column = x0; column <= x1; column++) {
+			float dx = (float)column - x, dz = (float)row - z;
+			float f = 1.0f - sqrtf(dx * dx + dz * dz) / radius;
+
+			if (f <= 0.0f) continue;
+			*kon_corner_(terrain, column, row) += amount * f * f * (3.0f - 2.0f * f);
+		}
+	}
+	kon_boundsAround_(terrain, x0, z0, x1, z1);
+}
+
+void kon_terrainFill(kon_terrain_t *terrain, float height)
+{
+	int i, count;
+
+	if (!terrain) return;
+	count = (terrain->columns + 1) * (terrain->rows + 1);
+	for (i = 0; i < count; i++) terrain->heights[i] = height;
+	kon_boundsAround_(terrain, 0, 0, terrain->columns, terrain->rows);
+}
+
+int kon_terrainRay(const kon_terrain_t *terrain, kon_vec3_t origin, kon_vec3_t direction, float maxDistance, kon_vec3_t *hit)
+{
+	float length = sqrtf(direction.x * direction.x + direction.y * direction.y + direction.z * direction.z);
+	float step = 0.1f, t, from = 0.0f;
+	int i;
+
+	if (!terrain || length < 0.0001f) return 0;
+	direction = KON_VEC3(direction.x / length, direction.y / length, direction.z / length);
+
+	for (t = step; t <= maxDistance; t += step) {
+		float x = origin.x + direction.x * t, y = origin.y + direction.y * t, z = origin.z + direction.z * t;
+
+		if (x < 0.0f || z < 0.0f || x > (float)terrain->columns || z > (float)terrain->rows) {
+			from = t;
+			continue;
+		}
+		if (y > kon_terrainHeight(terrain, x, z)) {
+			from = t;
+			continue;
+		}
+
+		/* it went under between from and t, narrow it down */
+		for (i = 0; i < 10; i++) {
+			float mid = (from + t) * 0.5f;
+
+			if (origin.y + direction.y * mid > kon_terrainHeight(terrain, origin.x + direction.x * mid, origin.z + direction.z * mid)) from = mid;
+			else t = mid;
+		}
+		if (hit) {
+			hit->x = origin.x + direction.x * t;
+			hit->z = origin.z + direction.z * t;
+			hit->y = kon_terrainHeight(terrain, hit->x, hit->z);
+		}
+		return 1;
+	}
+	return 0;
+}
+
+int kon_terrainSave(const kon_terrain_t *terrain, const char *path)
+{
+	FILE *file;
+	int column, row;
+
+	if (!terrain || !path) return 1;
+	file = fopen(path, "w");
+	if (!file) return 1;
+
+	fprintf(file, "kter %d %d\n", terrain->columns, terrain->rows);
+	for (row = 0; row <= terrain->rows; row++) {
+		for (column = 0; column <= terrain->columns; column++) fprintf(file, column ? " %.4f" : "%.4f", (double)*kon_corner_(terrain, column, row));
+		fputc('\n', file);
+	}
+	return fclose(file) != 0;
+}
+
+kon_terrain_t *kon_terrainLoad(const char *path)
+{
+	kon_terrain_t *terrain;
+	FILE *file;
+	char magic[8];
+	int columns, rows, column, row;
+
+	if (!path) return NULL;
+	file = fopen(path, "r");
+	if (!file) return NULL;
+
+	if (fscanf(file, "%7s %d %d", magic, &columns, &rows) != 3 || strcmp(magic, "kter") != 0) {
+		fclose(file);
+		return NULL;
+	}
+	terrain = kon_terrainCreate(columns, rows);
+	if (!terrain) {
+		fclose(file);
+		return NULL;
+	}
+
+	for (row = 0; row <= rows; row++) {
+		for (column = 0; column <= columns; column++) {
+			float h;
+
+			if (fscanf(file, "%f", &h) != 1) {
+				kon_terrainFree(terrain);
+				fclose(file);
+				return NULL;
+			}
+			*kon_corner_(terrain, column, row) = h;
+		}
+	}
+	fclose(file);
+	kon_boundsAround_(terrain, 0, 0, columns, rows);
+	return terrain;
+}
+
+/* the six planes of the view, pointing inwards, from the rows of the view projection matrix */
+static void kon_frustum_(kon_mat4_t vp, float planes[6][4])
+{
+	const float *m = vp.m;
+	int i, j;
+
+	for (j = 0; j < 4; j++) {
+		planes[0][j] = m[j * 4 + 3] + m[j * 4 + 0];
+		planes[1][j] = m[j * 4 + 3] - m[j * 4 + 0];
+		planes[2][j] = m[j * 4 + 3] + m[j * 4 + 1];
+		planes[3][j] = m[j * 4 + 3] - m[j * 4 + 1];
+		planes[4][j] = m[j * 4 + 3] + m[j * 4 + 2];
+		planes[5][j] = m[j * 4 + 3] - m[j * 4 + 2];
+	}
+	for (i = 0; i < 6; i++) {
+		float length = sqrtf(planes[i][0] * planes[i][0] + planes[i][1] * planes[i][1] + planes[i][2] * planes[i][2]);
+
+		for (j = 0; j < 4 && length > 0.0f; j++) planes[i][j] /= length;
+	}
+}
+
+static int kon_sphereVisible_(float planes[6][4], float x, float y, float z, float radius)
+{
+	int i;
+
+	for (i = 0; i < 6; i++) {
+		if (planes[i][0] * x + planes[i][1] * y + planes[i][2] * z + planes[i][3] < -radius) return 0;
+	}
+	return 1;
+}
+
+void kon_drawTerrain(kon_framebuffer_t *fb, const kon_camera_t *camera, const kon_terrain_t *terrain, const kon_light_t *light)
+{
+	kon_mat4_t vp = kon_cameraViewProjection(camera, fb->width, fb->height);
+	float planes[6][4];
+	int cx, cz;
+
+	if (!terrain || !terrain->material) return;
+	kon_frustum_(vp, planes);
+
+	for (cz = 0; cz < terrain->chunkRows; cz++) {
+		for (cx = 0; cx < terrain->chunkColumns; cx++) {
+			int x0 = cx * terrain->chunk, z0 = cz * terrain->chunk;
+			int x1 = x0 + terrain->chunk, z1 = z0 + terrain->chunk;
+			float low = terrain->chunkMin[cz * terrain->chunkColumns + cx], high = terrain->chunkMax[cz * terrain->chunkColumns + cx];
+			float halfW, halfD, halfH, radius;
+			int x, z;
+
+			if (x1 > terrain->columns) x1 = terrain->columns;
+			if (z1 > terrain->rows) z1 = terrain->rows;
+			halfW = (float)(x1 - x0) * 0.5f;
+			halfD = (float)(z1 - z0) * 0.5f;
+			halfH = (high - low) * 0.5f;
+			radius = sqrtf(halfW * halfW + halfD * halfD + halfH * halfH);
+			if (!kon_sphereVisible_(planes, (float)x0 + halfW, low + halfH, (float)z0 + halfD, radius)) continue;
+
+			for (z = z0; z < z1; z++) {
+				for (x = x0; x < x1; x++) {
+					float ha = *kon_corner_(terrain, x, z), hb = *kon_corner_(terrain, x + 1, z);
+					float hc = *kon_corner_(terrain, x + 1, z + 1), hd = *kon_corner_(terrain, x, z + 1);
+					kon_vec3_t a = KON_VEC3((float)x, ha, (float)z), b = KON_VEC3((float)x + 1, hb, (float)z);
+					kon_vec3_t c = KON_VEC3((float)x + 1, hc, (float)z + 1), d = KON_VEC3((float)x, hd, (float)z + 1);
+					kon_vec3_t upper = kon_vec3Normalize(KON_VEC3(hd - hc, 1.0f, ha - hd)), lower = kon_vec3Normalize(KON_VEC3(ha - hb, 1.0f, hb - hc));
+					kon_vertex_t va = { a, upper, KON_VEC2((float)x, (float)z) }, vd = { d, upper, KON_VEC2((float)x, (float)z + 1) }, vc = { c, upper, KON_VEC2((float)x + 1, (float)z + 1) };
+					kon_vertex_t wa = { a, lower, va.uv }, wc = { c, lower, vc.uv }, wb = { b, lower, KON_VEC2((float)x + 1, (float)z) };
+
+					kon_drawTriangle3D(fb, vp, va, vd, vc, terrain->material, light, KON_RENDER_DEFAULT);
+					kon_drawTriangle3D(fb, vp, wa, wc, wb, terrain->material, light, KON_RENDER_DEFAULT);
+				}
+			}
+		}
+	}
+}
+
+#if defined(KON_DEVELOPER) && defined(KON_MODULE_DEBUG)
+
+static void kon_cmdTerrainSave_(kon_debug_t *debug, void *user, int argc, char **argv)
+{
+	if (argc < 2) {
+		kon_debugLog(debug, "tsave file");
+		return;
+	}
+	if (kon_terrainSave(user, argv[1]) == 0) kon_debugLog(debug, "saved %s", argv[1]);
+	else kon_debugLog(debug, "could not save %s", argv[1]);
+}
+
+/* loads into the same struct so whatever points at the terrain keeps working */
+static void kon_cmdTerrainLoad_(kon_debug_t *debug, void *user, int argc, char **argv)
+{
+	kon_terrain_t *terrain = user, *loaded;
+	const kon_material_t *material = terrain->material;
+
+	if (argc < 2) {
+		kon_debugLog(debug, "tload file");
+		return;
+	}
+	loaded = kon_terrainLoad(argv[1]);
+	if (!loaded) {
+		kon_debugLog(debug, "could not load %s", argv[1]);
+		return;
+	}
+
+	free(terrain->heights);
+	free(terrain->chunkMin);
+	free(terrain->chunkMax);
+	*terrain = *loaded;
+	terrain->material = material;
+	free(loaded);
+	kon_debugLog(debug, "loaded %s", argv[1]);
+}
+
+static void kon_cmdTerrainFill_(kon_debug_t *debug, void *user, int argc, char **argv)
+{
+	kon_terrainFill(user, argc > 1 ? (float)atof(argv[1]) : 0.0f);
+	kon_debugLog(debug, "filled");
+}
+
+void kon_terrainDebug(kon_terrain_t *terrain, kon_debug_t *debug)
+{
+	kon_debugCommand(debug, "tsave", "tsave file: write the terrain as text", kon_cmdTerrainSave_, terrain);
+	kon_debugCommand(debug, "tload", "tload file: read a terrain back", kon_cmdTerrainLoad_, terrain);
+	kon_debugCommand(debug, "tfill", "tfill height: flatten everything", kon_cmdTerrainFill_, terrain);
+}
+
+#else
+
+void kon_terrainDebug(kon_terrain_t *terrain, kon_debug_t *debug)
+{
+	(void)terrain; (void)debug;
+}
+
+#endif
+
 float kon_distanceFade(float distance, float falloff)
 {
 	return 1.0f / (1.0f + distance * falloff);