path: root/kon/konsector.h

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

/* a map made of rooms: loading, saving, looking things up, building a mesh and drawing it. it needs konsofren.h and konmath.h next to it
 * and nothing else, so it is copy and paste like the other single header libs. it turns on the 3D part of konsofren, so include it
 * before konsofren.h or define KONSOFREN_3D yourself. in exactly one .c file:
 *
 *	#define KONSOFREN_IMPLEMENTATION   (once, wherever konsofren is)
 *	#define KONSECTOR_IMPLEMENTATION
 *	#include "konsector.h"
 *
 * a map can come from a file or from a string in your own source, kon_sectorParse takes the text either way */

#ifndef KONSECTOR_H
#define KONSECTOR_H

#include <stddef.h>

#ifndef KONSOFREN_3D
#define KONSOFREN_3D
#endif

#include "konmath.h"
#include "konsofren.h"

#ifndef KONSOFREN_HAS_3D
#error "this needs the 3D part of konsofren, define KONSOFREN_3D before the first include of konsofren.h (build.sh does it for -m 3d, model and sector)"
#endif

/*** definition ***/

/* a map is rooms seen from above. every room (sector) is a polygon of vertices with a floor and a ceiling height, and every
   edge of the polygon is a wall. where two sectors share an edge it is an opening instead of a wall, and if their heights
   differ there is a step or a lintel there. the plan is x going east and z going south, y is up like everywhere else.
   a room cannot sit on top of another one */

#define KON_NAME_LENGTH 24
#define KON_ENTITY_PROPS 8

typedef struct kon_sectorEdge {
	int portal;  /* the sector on the other side, -1 for a wall with nothing behind it */
	int texture; /* index into the map's textures, -1 uses the sector's wall texture */
} kon_sectorEdge_t;

typedef struct kon_sector {
	int first, count; /* where its corners start in indices and edges, and how many there are */
	float floor, ceiling;
	float light; /* 0 to 1, how bright the room is, 1 */
	int floorTexture, ceilingTexture, wallTexture; /* -1 for none */
} kon_sector_t;

typedef struct kon_entityProp {
	char key[16];
	char value[32];
} kon_entityProp_t;

/* things placed in the map that are not walls: where you start, doors, buttons, lights. the engine only reads them,
   what a kind does is up to the game. name and target are how things point at each other, a button with the target "door1"
   is meant for the entity named "door1" */
typedef struct kon_entity {
	char kind[KON_NAME_LENGTH];
	char name[KON_NAME_LENGTH];
	char target[KON_NAME_LENGTH];
	kon_vec3_t position;
	float angle; /* radians, 0 faces north (towards -z) and it turns clockwise from above like the camera yaw */
	int sector;  /* the sector it is in, -1 if the position is outside every sector */
	int propCount;
	kon_entityProp_t props[KON_ENTITY_PROPS];
} kon_entity_t;

/* a flat picture placed by its four corners, for anything the rooms can't make: a painting, a face at a window, a sign.
   the corners go bottom left, bottom right, top right, top left as seen from the front, and the picture covers the whole texture.
   the back is not drawn unless doubleSided is 1 */
typedef struct kon_sectorQuad {
	kon_vec3_t corners[4];
	int texture;
	float light; /* 0 to 1, 1 */
	int doubleSided;
} kon_sectorQuad_t;

typedef struct kon_sectorMap {
	int vertexCount;
	kon_vec2_t *vertices; /* x, z */

	/* the corners of a sector are indices[first] to indices[first + count - 1], counter clockwise seen from above.
	   edge n runs from corner n to corner n + 1 and the last one closes the loop */
	int sectorCount;
	kon_sector_t *sectors;
	int indexCount;
	int *indices;
	kon_sectorEdge_t *edges;

	int quadCount;
	kon_sectorQuad_t *quads;

	int entityCount;
	kon_entity_t *entities;

	int textureCount;
	char (*textures)[KON_NAME_LENGTH]; /* names only, the game decides what picture goes with each */
} kon_sectorMap_t;

/*** loading ***/

/* reads a map from text. returns NULL and fills error (if it is not NULL) with something like "line 12: sector 2 has a ceiling below its floor".
   a clockwise sector is turned around, anything else wrong is an error */
kon_sectorMap_t *kon_sectorParse(const char *text, char *error, size_t errorSize);
kon_sectorMap_t *kon_sectorLoad(const char *path, char *error, size_t errorSize);
void kon_sectorFree(kon_sectorMap_t *map);

/* the same text format, so a map can be edited in the game and saved. returns 0 on success */
int kon_sectorSave(const kon_sectorMap_t *map, const char *path);

/*** drawing ***/

/* the walls, floors and ceilings of a map as triangles, built once and drawn every frame */
typedef struct kon_sectorMesh kon_sectorMesh_t;

/* NULL if there is no memory. the map has to stay alive while the mesh is used, and the mesh has to be built again if the map changes */
kon_sectorMesh_t *kon_sectorBuild(const kon_sectorMap_t *map);
void kon_sectorMeshFree(kon_sectorMesh_t *mesh);

/* materials[n] is what texture n of the map looks like, a texture without one (or -1) is grey. light is the light of the whole
   map, every room scales it by its own light value. rooms that are off screen are skipped */
void kon_sectorDraw(kon_framebuffer_t *fb, const kon_camera_t *camera, const kon_sectorMesh_t *mesh, const kon_material_t *materials, int materialCount, const kon_light_t *light);

/*** looking things up ***/

/* the sector that holds the point, or -1. hint is a sector to try first (and its neighbours), pass -1 if you have none.
   moving things should pass the sector they were in last frame, that makes this a few comparisons instead of a search */
int kon_sectorAt(const kon_sectorMap_t *map, float x, float z, int hint);

/* where corner n of a sector is */
kon_vec2_t kon_sectorCorner(const kon_sectorMap_t *map, int sector, int n);

/* the texture of an edge, the sector's own wall texture when the edge has none */
int kon_sectorWallTexture(const kon_sectorMap_t *map, int sector, int edge);

/* -1 if the name is not used in the map */
int kon_sectorTextureIndex(const kon_sectorMap_t *map, const char *name);

/*** entities ***/

/* the first entity with this name, or -1 */
int kon_entityFind(const kon_sectorMap_t *map, const char *name);

/* fills out with the indices of every entity named like this, up to max, and returns how many there are in total.
   this is how a button finds what it is for: ask for the entities named like its target */
int kon_entityTargets(const kon_sectorMap_t *map, const char *name, int *out, int max);

/* props are the key=value pairs written after the entity in the file. they are text, these read them as numbers */
const char *kon_entityString(const kon_entity_t *entity, const char *key, const char *fallback);
float kon_entityFloat(const kon_entity_t *entity, const char *key, float fallback);
int kon_entityInt(const kon_entity_t *entity, const char *key, int fallback);

/*** implementation ***/

#ifdef KONSECTOR_IMPLEMENTATION

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

#define WORD_LENGTH 128
#define MAX_FILE (16 * 1024 * 1024)

/*** private ***/

typedef struct kon_builder {
	kon_sectorMap_t *map;
	int vertexCap, sectorCap, lineCap, indexCap, edgeCap, quadCap, entityCap, textureCap;
	int *sectorLine; /* the line each sector was written on, for the errors found afterwards */
	int line;
	char *error;
	size_t errorSize;
} kon_builder_t;

static int kon_fail_(kon_builder_t *b, int line, const char *format, ...)
{
	va_list args;
	int used = 0;

	if (b->error && b->errorSize > 0) {
		if (line > 0) used = snprintf(b->error, b->errorSize, "line %d: ", line);
		if (used < 0 || (size_t)used >= b->errorSize) used = 0;
		va_start(args, format);
		vsnprintf(b->error + used, b->errorSize - (size_t)used, format, args);
		va_end(args);
	}
	return 0;
}

static int kon_grow_(void **array, int *capacity, size_t size, int needed)
{
	void *bigger;
	int cap = *capacity;

	if (needed <= cap) return 1;
	if (cap < 8) cap = 8;
	while (cap < needed) cap *= 2;
	bigger = realloc(*array, (size_t)cap * size);
	if (!bigger) return 0;
	*array = bigger;
	*capacity = cap;
	return 1;
}

/* the next word of a line, NULL at the end of it. the line ends at a newline or a #. the word is copied into out */
static const char *kon_word_(const char *p, char *out, size_t size)
{
	size_t n = 0;

	while (*p == ' ' || *p == '\t' || *p == '\r') p++;
	if (*p == '\0' || *p == '\n' || *p == '#') return NULL;
	while (*p != '\0' && *p != ' ' && *p != '\t' && *p != '\r' && *p != '\n' && *p != '#') {
		if (n + 1 < size) out[n++] = *p;
		p++;
	}
	out[n] = '\0';
	return p;
}

static int kon_number_(const char *word, double *value)
{
	char *end;

	if (*word == '\0') return 0;
	*value = strtod(word, &end);
	return *end == '\0' && isfinite(*value);
}

static int kon_texture_(kon_builder_t *b, const char *name, int *index)
{
	kon_sectorMap_t *map = b->map;
	int i;

	if (strcmp(name, "-") == 0) {
		*index = -1;
		return 1;
	}
	for (i = 0; i < map->textureCount; i++) {
		if (strcmp(map->textures[i], name) == 0) {
			*index = i;
			return 1;
		}
	}
	if (strlen(name) >= KON_NAME_LENGTH) return 0;
	if (!kon_grow_((void **)&map->textures, &b->textureCap, sizeof(map->textures[0]), map->textureCount + 1)) return 0;
	strcpy(map->textures[map->textureCount], name);
	*index = map->textureCount++;
	return 1;
}

static double kon_area_(const kon_sectorMap_t *map, const kon_sector_t *sector)
{
	double sum = 0.0;
	int i;

	for (i = 0; i < sector->count; i++) {
		kon_vec2_t a = map->vertices[map->indices[sector->first + i]];
		kon_vec2_t b = map->vertices[map->indices[sector->first + (i + 1) % sector->count]];

		sum += (double)a.x * (double)b.y - (double)b.x * (double)a.y;
	}
	return sum * 0.5;
}

static double kon_side_(kon_vec2_t a, kon_vec2_t b, kon_vec2_t p)
{
	return ((double)b.x - (double)a.x) * ((double)p.y - (double)a.y) - ((double)b.y - (double)a.y) * ((double)p.x - (double)a.x);
}

static int kon_onSegment_(kon_vec2_t a, kon_vec2_t b, kon_vec2_t p)
{
	return p.x >= (a.x < b.x ? a.x : b.x) && p.x <= (a.x > b.x ? a.x : b.x) && p.y >= (a.y < b.y ? a.y : b.y) && p.y <= (a.y > b.y ? a.y : b.y);
}

/* touching counts as crossing */
static int kon_crossing_(kon_vec2_t a, kon_vec2_t b, kon_vec2_t c, kon_vec2_t d)
{
	double d1 = kon_side_(a, b, c), d2 = kon_side_(a, b, d), d3 = kon_side_(c, d, a), d4 = kon_side_(c, d, b);

	if (((d1 > 0 && d2 < 0) || (d1 < 0 && d2 > 0)) && ((d3 > 0 && d4 < 0) || (d3 < 0 && d4 > 0))) return 1;
	if (d1 == 0 && kon_onSegment_(a, b, c)) return 1;
	if (d2 == 0 && kon_onSegment_(a, b, d)) return 1;
	if (d3 == 0 && kon_onSegment_(c, d, a)) return 1;
	if (d4 == 0 && kon_onSegment_(c, d, b)) return 1;
	return 0;
}

static int kon_checkSector_(kon_builder_t *b, int s)
{
	kon_sectorMap_t *map = b->map;
	kon_sector_t *sector = &map->sectors[s];
	int line = b->sectorLine[s], i, j;
	double area;

	if (sector->count < 3) return kon_fail_(b, line, "sector %d needs at least 3 corners", s);
	if (!(sector->ceiling > sector->floor)) return kon_fail_(b, line, "sector %d has a ceiling that is not above its floor", s);

	for (i = 0; i < sector->count; i++) {
		kon_vec2_t p = kon_sectorCorner(map, s, i), q = kon_sectorCorner(map, s, i + 1);

		if (p.x == q.x && p.y == q.y) return kon_fail_(b, line, "sector %d has an edge with no length at corner %d", s, i);
	}

	for (i = 0; i < sector->count; i++) {
		for (j = i + 2; j < sector->count; j++) {
			if (i == 0 && j == sector->count - 1) continue;
			if (kon_crossing_(kon_sectorCorner(map, s, i), kon_sectorCorner(map, s, i + 1), kon_sectorCorner(map, s, j), kon_sectorCorner(map, s, j + 1))) {
				return kon_fail_(b, line, "sector %d crosses itself, edges %d and %d touch", s, i, j);
			}
		}
	}

	area = kon_area_(map, sector);
	if (area == 0.0) return kon_fail_(b, line, "sector %d has no area", s);

	/* the shoelace sum is positive going clockwise on a plan with z pointing down, the format wants the other way round */
	if (area > 0.0) {
		int *c = &map->indices[sector->first];
		kon_sectorEdge_t *e = &map->edges[sector->first];

		for (i = 0, j = sector->count - 1; i < j; i++, j--) {
			int t = c[i];

			c[i] = c[j];
			c[j] = t;
		}
		/* the corners are reversed, so edge n now runs along old edge count - 2 - n backwards. the closing edge stays the closing edge */
		for (i = 0, j = sector->count - 2; i < j; i++, j--) {
			kon_sectorEdge_t t = e[i];

			e[i] = e[j];
			e[j] = t;
		}
	}
	return 1;
}

static int kon_samePoint_(kon_vec2_t a, kon_vec2_t b)
{
	return a.x == b.x && a.y == b.y;
}

static int kon_linkPortals_(kon_builder_t *b)
{
	kon_sectorMap_t *map = b->map;
	int s, t, i, j;

	for (s = 0; s < map->sectorCount; s++) {
		for (i = 0; i < map->sectors[s].count; i++) {
			kon_vec2_t p = kon_sectorCorner(map, s, i), q = kon_sectorCorner(map, s, i + 1);

			map->edges[map->sectors[s].first + i].portal = -1;
			for (t = 0; t < map->sectorCount; t++) {
				if (t == s) continue;
				for (j = 0; j < map->sectors[t].count; j++) {
					kon_vec2_t u = kon_sectorCorner(map, t, j), v = kon_sectorCorner(map, t, j + 1);

					if (kon_samePoint_(p, u) && kon_samePoint_(q, v)) {
						return kon_fail_(b, b->sectorLine[s], "sectors %d and %d overlap along an edge, they run the same way", s, t);
					}
					if (kon_samePoint_(p, v) && kon_samePoint_(q, u)) map->edges[map->sectors[s].first + i].portal = t;
				}
			}
		}
	}
	return 1;
}

/*** loading ***/

static int kon_parseSector_(kon_builder_t *b, const char *p)
{
	kon_sectorMap_t *map = b->map;
	kon_sector_t *sector;
	char word[WORD_LENGTH], value[WORD_LENGTH];
	double floorHeight, ceilingHeight, number;
	int line = b->line;

	if (!(p = kon_word_(p, word, sizeof(word))) || !kon_number_(word, &floorHeight)) return kon_fail_(b, line, "sector needs a floor height");
	if (!(p = kon_word_(p, word, sizeof(word))) || !kon_number_(word, &ceilingHeight)) return kon_fail_(b, line, "sector needs a ceiling height");

	if (!kon_grow_((void **)&map->sectors, &b->sectorCap, sizeof(*map->sectors), map->sectorCount + 1)) return kon_fail_(b, 0, "out of memory");
	if (!kon_grow_((void **)&b->sectorLine, &b->lineCap, sizeof(int), map->sectorCount + 1)) return kon_fail_(b, 0, "out of memory");
	sector = &map->sectors[map->sectorCount];
	memset(sector, 0, sizeof(*sector));
	sector->floor = (float)floorHeight;
	sector->ceiling = (float)ceilingHeight;
	sector->light = 1.0f;
	sector->floorTexture = sector->ceilingTexture = sector->wallTexture = -1;
	sector->first = map->indexCount;
	b->sectorLine[map->sectorCount] = line;

	/* key value pairs until the colon */
	for (;;) {
		if (!(p = kon_word_(p, word, sizeof(word)))) return kon_fail_(b, line, "sector needs a colon before its corners");
		if (strcmp(word, ":") == 0) break;
		if (kon_number_(word, &number)) return kon_fail_(b, line, "the corners of a sector come after a colon");
		if (!(p = kon_word_(p, value, sizeof(value)))) return kon_fail_(b, line, "%s needs a value", word);

		if (strcmp(word, "light") == 0) {
			if (!kon_number_(value, &number) || number < 0.0 || number > 1.0) return kon_fail_(b, line, "light is a number from 0 to 1");
			sector->light = (float)number;
		} else if (strcmp(word, "floor") == 0) {
			if (!kon_texture_(b, value, &sector->floorTexture)) return kon_fail_(b, line, "bad texture name %s", value);
		} else if (strcmp(word, "ceiling") == 0) {
			if (!kon_texture_(b, value, &sector->ceilingTexture)) return kon_fail_(b, line, "bad texture name %s", value);
		} else if (strcmp(word, "wall") == 0) {
			if (!kon_texture_(b, value, &sector->wallTexture)) return kon_fail_(b, line, "bad texture name %s", value);
		} else {
			return kon_fail_(b, line, "unknown sector setting %s", word);
		}
	}

	while ((p = kon_word_(p, word, sizeof(word)))) {
		if (!kon_number_(word, &number) || number != floor(number) || number < 0.0 || number >= (double)map->vertexCount) {
			return kon_fail_(b, line, "%s is not a vertex that was defined above", word);
		}
		if (!kon_grow_((void **)&map->indices, &b->indexCap, sizeof(int), map->indexCount + 1)) return kon_fail_(b, 0, "out of memory");
		if (!kon_grow_((void **)&map->edges, &b->edgeCap, sizeof(*map->edges), map->indexCount + 1)) return kon_fail_(b, 0, "out of memory");
		map->indices[map->indexCount] = (int)number;
		map->edges[map->indexCount].portal = -1;
		map->edges[map->indexCount].texture = -1;
		map->indexCount++;
	}
	sector->count = map->indexCount - sector->first;
	map->sectorCount++;
	return 1;
}

static int kon_parseQuad_(kon_builder_t *b, const char *p)
{
	kon_sectorMap_t *map = b->map;
	kon_sectorQuad_t *quad;
	char word[WORD_LENGTH];
	double v[12];
	int i, line = b->line;

	if (!kon_grow_((void **)&map->quads, &b->quadCap, sizeof(*map->quads), map->quadCount + 1)) return kon_fail_(b, 0, "out of memory");
	quad = &map->quads[map->quadCount];
	memset(quad, 0, sizeof(*quad));
	quad->light = 1.0f;

	if (!(p = kon_word_(p, word, sizeof(word)))) return kon_fail_(b, line, "quad needs a texture");
	if (!kon_texture_(b, word, &quad->texture)) return kon_fail_(b, line, "bad texture name %s", word);
	for (i = 0; i < 12; i++) {
		if (!(p = kon_word_(p, word, sizeof(word))) || !kon_number_(word, &v[i])) return kon_fail_(b, line, "quad needs 12 numbers, x y z for each of its 4 corners");
	}
	for (i = 0; i < 4; i++) quad->corners[i] = KON_VEC3((float)v[i * 3], (float)v[i * 3 + 1], (float)v[i * 3 + 2]);

	while ((p = kon_word_(p, word, sizeof(word)))) {
		if (strcmp(word, "double") == 0) {
			quad->doubleSided = 1;
		} else if (strcmp(word, "light") == 0) {
			double light;

			if (!(p = kon_word_(p, word, sizeof(word))) || !kon_number_(word, &light) || light < 0.0 || light > 1.0) return kon_fail_(b, line, "light is a number from 0 to 1");
			quad->light = (float)light;
		} else {
			return kon_fail_(b, line, "unknown quad setting %s", word);
		}
	}
	map->quadCount++;
	return 1;
}

static int kon_parseEntity_(kon_builder_t *b, const char *p)
{
	kon_sectorMap_t *map = b->map;
	kon_entity_t *entity;
	char word[WORD_LENGTH];
	double v[4];
	int i, line = b->line;

	if (!kon_grow_((void **)&map->entities, &b->entityCap, sizeof(*map->entities), map->entityCount + 1)) return kon_fail_(b, 0, "out of memory");
	entity = &map->entities[map->entityCount];
	memset(entity, 0, sizeof(*entity));
	entity->sector = -1;

	if (!(p = kon_word_(p, word, sizeof(word)))) return kon_fail_(b, line, "entity needs a kind");
	if (strlen(word) >= KON_NAME_LENGTH) return kon_fail_(b, line, "the kind %s is too long", word);
	strcpy(entity->kind, word);

	for (i = 0; i < 4; i++) {
		if (!(p = kon_word_(p, word, sizeof(word))) || !kon_number_(word, &v[i])) return kon_fail_(b, line, "entity needs x y z and an angle");
	}
	entity->position = KON_VEC3((float)v[0], (float)v[1], (float)v[2]);
	entity->angle = (float)(v[3] * 3.14159265358979323846 / 180.0);

	while ((p = kon_word_(p, word, sizeof(word)))) {
		char *equals = strchr(word, '=');

		if (!equals || equals == word) return kon_fail_(b, line, "%s should be written key=value", word);
		*equals++ = '\0';

		if (strcmp(word, "name") == 0 || strcmp(word, "target") == 0) {
			char *dest = word[0] == 'n' ? entity->name : entity->target;

			if (strlen(equals) >= KON_NAME_LENGTH) return kon_fail_(b, line, "the %s %s is too long", word, equals);
			strcpy(dest, equals);
		} else {
			if (entity->propCount >= KON_ENTITY_PROPS) return kon_fail_(b, line, "an entity can have %d settings at most", KON_ENTITY_PROPS);
			if (strlen(word) >= sizeof(entity->props[0].key) || strlen(equals) >= sizeof(entity->props[0].value)) return kon_fail_(b, line, "the setting %s is too long", word);
			strcpy(entity->props[entity->propCount].key, word);
			strcpy(entity->props[entity->propCount].value, equals);
			entity->propCount++;
		}
	}
	map->entityCount++;
	return 1;
}

static int kon_parseLine_(kon_builder_t *b, const char *p, int *started)
{
	kon_sectorMap_t *map = b->map;
	char word[WORD_LENGTH];
	double number, x, z;
	int line = b->line;

	if (!(p = kon_word_(p, word, sizeof(word)))) return 1;

	if (!*started) {
		if (strcmp(word, "kmap") != 0) return kon_fail_(b, line, "a map starts with \"kmap 1\"");
		if (!(p = kon_word_(p, word, sizeof(word))) || !kon_number_(word, &number) || number != 1.0) return kon_fail_(b, line, "this reads kmap version 1");
		*started = 1;
		return 1;
	}

	if (strcmp(word, "v") == 0) {
		char a[WORD_LENGTH], c[WORD_LENGTH];

		if (!(p = kon_word_(p, a, sizeof(a))) || !(p = kon_word_(p, c, sizeof(c))) || !kon_number_(a, &x) || !kon_number_(c, &z)) return kon_fail_(b, line, "v needs x and z");
		if (!kon_grow_((void **)&map->vertices, &b->vertexCap, sizeof(*map->vertices), map->vertexCount + 1)) return kon_fail_(b, 0, "out of memory");
		map->vertices[map->vertexCount++] = KON_VEC2((float)x, (float)z);
		return 1;
	}
	if (strcmp(word, "sector") == 0) return kon_parseSector_(b, p);
	if (strcmp(word, "quad") == 0) return kon_parseQuad_(b, p);
	if (strcmp(word, "entity") == 0) return kon_parseEntity_(b, p);
	if (strcmp(word, "edge") == 0) {
		char a[WORD_LENGTH], c[WORD_LENGTH], name[WORD_LENGTH];
		double s, n;

		if (!(p = kon_word_(p, a, sizeof(a))) || !(p = kon_word_(p, c, sizeof(c))) || !(p = kon_word_(p, name, sizeof(name))) || !kon_number_(a, &s) || !kon_number_(c, &n)) {
			return kon_fail_(b, line, "edge needs a sector, an edge number and a texture");
		}
		if (s < 0 || s >= map->sectorCount || s != floor(s)) return kon_fail_(b, line, "there is no sector %s above", a);
		if (n < 0 || n >= map->sectors[(int)s].count || n != floor(n)) return kon_fail_(b, line, "sector %s has no edge %s", a, c);
		if (!kon_texture_(b, name, &map->edges[map->sectors[(int)s].first + (int)n].texture)) return kon_fail_(b, line, "bad texture name %s", name);
		return 1;
	}
	return kon_fail_(b, line, "unknown word %s", word);
}

kon_sectorMap_t *kon_sectorParse(const char *text, char *error, size_t errorSize)
{
	kon_builder_t b;
	kon_sectorMap_t *map;
	const char *p = text;
	int started = 0, i;

	if (error && errorSize > 0) error[0] = '\0';
	if (!text) return NULL;
	map = calloc(1, sizeof(*map));
	if (!map) return NULL;
	memset(&b, 0, sizeof(b));
	b.map = map;
	b.error = error;
	b.errorSize = errorSize;

	while (*p != '\0') {
		b.line++;
		if (!kon_parseLine_(&b, p, &started)) goto bad;
		while (*p != '\0' && *p != '\n') p++;
		if (*p == '\n') p++;
	}

	if (!started) {
		kon_fail_(&b, 0, "the map is empty, it should start with \"kmap 1\"");
		goto bad;
	}
	for (i = 0; i < map->sectorCount; i++) {
		if (!kon_checkSector_(&b, i)) goto bad;
	}
	if (!kon_linkPortals_(&b)) goto bad;
	for (i = 0; i < map->entityCount; i++) map->entities[i].sector = kon_sectorAt(map, map->entities[i].position.x, map->entities[i].position.z, -1);

	free(b.sectorLine);
	return map;

bad:
	free(b.sectorLine);
	kon_sectorFree(map);
	return NULL;
}

kon_sectorMap_t *kon_sectorLoad(const char *path, char *error, size_t errorSize)
{
	kon_sectorMap_t *map;
	FILE *file;
	char *text;
	long size;

	if (error && errorSize > 0) error[0] = '\0';
	file = path ? fopen(path, "rb") : NULL;
	if (!file) {
		if (error && errorSize > 0) snprintf(error, errorSize, "could not open %s", path ? path : "(null)");
		return NULL;
	}
	fseek(file, 0, SEEK_END);
	size = ftell(file);
	fseek(file, 0, SEEK_SET);
	if (size < 0 || size > MAX_FILE) {
		fclose(file);
		if (error && errorSize > 0) snprintf(error, errorSize, "%s is too big for a map", path);
		return NULL;
	}
	text = malloc((size_t)size + 1);
	if (!text) {
		fclose(file);
		return NULL;
	}
	if (fread(text, 1, (size_t)size, file) != (size_t)size) {
		free(text);
		fclose(file);
		if (error && errorSize > 0) snprintf(error, errorSize, "could not read %s", path);
		return NULL;
	}
	text[size] = '\0';
	fclose(file);

	map = kon_sectorParse(text, error, errorSize);
	free(text);
	return map;
}

void kon_sectorFree(kon_sectorMap_t *map)
{
	if (!map) return;
	free(map->vertices);
	free(map->sectors);
	free(map->indices);
	free(map->edges);
	free(map->quads);
	free(map->entities);
	free(map->textures);
	free(map);
}

int kon_sectorSave(const kon_sectorMap_t *map, const char *path)
{
	FILE *file;
	int i, j;

	if (!map || !path) return 1;
	file = fopen(path, "w");
	if (!file) return 1;

	fprintf(file, "kmap 1\n\n");
	for (i = 0; i < map->vertexCount; i++) fprintf(file, "v %.9g %.9g\n", (double)map->vertices[i].x, (double)map->vertices[i].y);
	fputc('\n', file);

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

		fprintf(file, "sector %.9g %.9g light %.9g floor %s ceiling %s wall %s :", (double)s->floor, (double)s->ceiling, (double)s->light,
			s->floorTexture >= 0 ? map->textures[s->floorTexture] : "-", s->ceilingTexture >= 0 ? map->textures[s->ceilingTexture] : "-",
			s->wallTexture >= 0 ? map->textures[s->wallTexture] : "-");
		for (j = 0; j < s->count; j++) fprintf(file, " %d", map->indices[s->first + j]);
		fputc('\n', file);
	}
	for (i = 0; i < map->sectorCount; i++) {
		for (j = 0; j < map->sectors[i].count; j++) {
			int texture = map->edges[map->sectors[i].first + j].texture;

			if (texture >= 0) fprintf(file, "edge %d %d %s\n", i, j, map->textures[texture]);
		}
	}
	fputc('\n', file);

	for (i = 0; i < map->quadCount; i++) {
		const kon_sectorQuad_t *q = &map->quads[i];

		fprintf(file, "quad %s", q->texture >= 0 ? map->textures[q->texture] : "-");
		for (j = 0; j < 4; j++) fprintf(file, " %.9g %.9g %.9g", (double)q->corners[j].x, (double)q->corners[j].y, (double)q->corners[j].z);
		if (q->doubleSided) fprintf(file, " double");
		if (q->light != 1.0f) fprintf(file, " light %.9g", (double)q->light);
		fputc('\n', file);
	}
	if (map->quadCount > 0) fputc('\n', file);

	for (i = 0; i < map->entityCount; i++) {
		const kon_entity_t *e = &map->entities[i];

		fprintf(file, "entity %s %.9g %.9g %.9g %.9g", e->kind, (double)e->position.x, (double)e->position.y, (double)e->position.z, (double)e->angle * 180.0 / 3.14159265358979323846);
		if (e->name[0]) fprintf(file, " name=%s", e->name);
		if (e->target[0]) fprintf(file, " target=%s", e->target);
		for (j = 0; j < e->propCount; j++) fprintf(file, " %s=%s", e->props[j].key, e->props[j].value);
		fputc('\n', file);
	}
	return fclose(file) != 0;
}

/*** looking things up ***/

kon_vec2_t kon_sectorCorner(const kon_sectorMap_t *map, int sector, int n)
{
	const kon_sector_t *s = &map->sectors[sector];

	return map->vertices[map->indices[s->first + n % s->count]];
}

int kon_sectorWallTexture(const kon_sectorMap_t *map, int sector, int edge)
{
	int texture = map->edges[map->sectors[sector].first + edge].texture;

	return texture >= 0 ? texture : map->sectors[sector].wallTexture;
}

int kon_sectorTextureIndex(const kon_sectorMap_t *map, const char *name)
{
	int i;

	for (i = 0; i < map->textureCount; i++) {
		if (strcmp(map->textures[i], name) == 0) return i;
	}
	return -1;
}

static int kon_inside_(const kon_sectorMap_t *map, int sector, float x, float z)
{
	int i, count = map->sectors[sector].count, inside = 0;

	for (i = 0; i < count; i++) {
		kon_vec2_t a = kon_sectorCorner(map, sector, i), b = kon_sectorCorner(map, sector, i + 1);

		if ((a.y > z) != (b.y > z) && x < (b.x - a.x) * (z - a.y) / (b.y - a.y) + a.x) inside = !inside;
	}
	return inside;
}

int kon_sectorAt(const kon_sectorMap_t *map, float x, float z, int hint)
{
	int i;

	if (!map) return -1;
	if (hint >= 0 && hint < map->sectorCount) {
		const kon_sector_t *s = &map->sectors[hint];

		if (kon_inside_(map, hint, x, z)) return hint;
		for (i = 0; i < s->count; i++) {
			int next = map->edges[s->first + i].portal;

			if (next >= 0 && kon_inside_(map, next, x, z)) return next;
		}
	}
	for (i = 0; i < map->sectorCount; i++) {
		if (kon_inside_(map, i, x, z)) return i;
	}
	return -1;
}

/*** entities ***/

int kon_entityFind(const kon_sectorMap_t *map, const char *name)
{
	int i;

	if (!map || !name || !name[0]) return -1;
	for (i = 0; i < map->entityCount; i++) {
		if (strcmp(map->entities[i].name, name) == 0) return i;
	}
	return -1;
}

int kon_entityTargets(const kon_sectorMap_t *map, const char *name, int *out, int max)
{
	int i, total = 0;

	if (!map || !name || !name[0]) return 0;
	for (i = 0; i < map->entityCount; i++) {
		if (strcmp(map->entities[i].name, name) != 0) continue;
		if (out && total < max) out[total] = i;
		total++;
	}
	return total;
}

const char *kon_entityString(const kon_entity_t *entity, const char *key, const char *fallback)
{
	int i;

	for (i = 0; entity && i < entity->propCount; i++) {
		if (strcmp(entity->props[i].key, key) == 0) return entity->props[i].value;
	}
	return fallback;
}

float kon_entityFloat(const kon_entity_t *entity, const char *key, float fallback)
{
	const char *text = kon_entityString(entity, key, NULL);
	double value;

	return text && kon_number_(text, &value) ? (float)value : fallback;
}

int kon_entityInt(const kon_entity_t *entity, const char *key, int fallback)
{
	const char *text = kon_entityString(entity, key, NULL);
	double value;

	return text && kon_number_(text, &value) ? (int)value : fallback;
}

/*** drawing ***/

typedef struct kon_sectorTri {
	kon_vertex_t v[3];
	int texture;
	float light;
	int twoSided;
} kon_sectorTri_t;

struct kon_sectorMesh {
	const kon_sectorMap_t *map;
	int triCount, triCap;
	kon_sectorTri_t *tris;
	int *first, *count; /* the triangles of each sector, the quads come after all of them */
	kon_vec3_t *center;
	float *radius;
	int quadFirst;
};

static int kon_addTriangle_(kon_sectorMesh_t *mesh, kon_vertex_t a, kon_vertex_t b, kon_vertex_t c, int texture, float light, int twoSided)
{
	kon_sectorTri_t *t;

	if (!kon_grow_((void **)&mesh->tris, &mesh->triCap, sizeof(*mesh->tris), mesh->triCount + 1)) return 0;
	t = &mesh->tris[mesh->triCount++];
	t->v[0] = a;
	t->v[1] = b;
	t->v[2] = c;
	t->texture = texture;
	t->light = light;
	t->twoSided = twoSided;
	return 1;
}

static kon_vertex_t kon_vertex_(float x, float y, float z, kon_vec3_t normal, float u, float v)
{
	kon_vertex_t r;

	r.position = KON_VEC3(x, y, z);
	r.normal = normal;
	r.uv = KON_VEC2(u, v);
	return r;
}

/* a wall seen from inside the room: left is the corner on the viewer's left, u counts from there, v from the top of the world so
   textures line up from room to room */
static int kon_addWall_(kon_sectorMesh_t *mesh, kon_vec2_t left, kon_vec2_t right, float low, float high, kon_vec3_t normal, float length, int texture)
{
	kon_vertex_t bl = kon_vertex_(left.x, low, left.y, normal, 0.0f, -low), br = kon_vertex_(right.x, low, right.y, normal, length, -low);
	kon_vertex_t tr = kon_vertex_(right.x, high, right.y, normal, length, -high), tl = kon_vertex_(left.x, high, left.y, normal, 0.0f, -high);

	return kon_addTriangle_(mesh, bl, br, tr, texture, 1.0f, 0) && kon_addTriangle_(mesh, bl, tr, tl, texture, 1.0f, 0);
}

/* is p inside the triangle abc, corners themselves do not count */
static int kon_inTriangle_(kon_vec2_t a, kon_vec2_t b, kon_vec2_t c, kon_vec2_t p)
{
	double d1 = kon_side_(a, b, p), d2 = kon_side_(b, c, p), d3 = kon_side_(c, a, p);
	int negative = d1 < 0 || d2 < 0 || d3 < 0, positive = d1 > 0 || d2 > 0 || d3 > 0;

	if (kon_samePoint_(p, a) || kon_samePoint_(p, b) || kon_samePoint_(p, c)) return 0;
	return !(negative && positive);
}

/* cuts the corners off one at a time. a corner can go when it turns the right way and no other corner is inside the triangle it makes.
   out gets 3 * (n - 2) corner numbers, in the same winding as the polygon */
static int kon_triangulate_(const kon_sectorMap_t *map, int sector, int *out)
{
	int n = map->sectors[sector].count, left = n, produced = 0, i;
	int *list = malloc((size_t)n * sizeof(int));

	if (!list) return 0;
	for (i = 0; i < n; i++) list[i] = i;

	while (left > 3) {
		int found = -1, k;

		for (k = 0; k < left && found < 0; k++) {
			int ia = list[(k + left - 1) % left], ib = list[k], ic = list[(k + 1) % left], m, blocked = 0;
			kon_vec2_t a = kon_sectorCorner(map, sector, ia), b = kon_sectorCorner(map, sector, ib), c = kon_sectorCorner(map, sector, ic);

			/* these polygons run the wrong way for the usual maths because z points down, so a corner that bends the right way is negative */
			if (kon_side_(a, b, c) >= 0) continue;
			for (m = 0; m < left && !blocked; m++) {
				if (list[m] != ia && list[m] != ib && list[m] != ic && kon_inTriangle_(a, b, c, kon_sectorCorner(map, sector, list[m]))) blocked = 1;
			}
			if (!blocked) found = k;
		}

		/* a polygon with flat corners can leave no clean ear, take any corner that does not bend the wrong way, then any at all */
		for (k = 0; k < left && found < 0; k++) {
			kon_vec2_t a = kon_sectorCorner(map, sector, list[(k + left - 1) % left]), b = kon_sectorCorner(map, sector, list[k]), c = kon_sectorCorner(map, sector, list[(k + 1) % left]);

			if (kon_side_(a, b, c) == 0) found = k;
		}
		if (found < 0) found = 0;

		out[produced++] = list[(found + left - 1) % left];
		out[produced++] = list[found];
		out[produced++] = list[(found + 1) % left];
		memmove(&list[found], &list[found + 1], (size_t)(left - found - 1) * sizeof(int));
		left--;
	}
	out[produced++] = list[0];
	out[produced++] = list[1];
	out[produced++] = list[2];
	free(list);
	return 1;
}

static int kon_buildSector_(kon_sectorMesh_t *mesh, int s)
{
	const kon_sectorMap_t *map = mesh->map;
	const kon_sector_t *sector = &map->sectors[s];
	kon_vec3_t up = KON_VEC3(0, 1, 0), down = KON_VEC3(0, -1, 0);
	int *ears = malloc((size_t)(sector->count - 2) * 3 * sizeof(int));
	int i, ok = 1;

	if (!ears) return 0;
	if (!kon_triangulate_(map, s, ears)) {
		free(ears);
		return 0;
	}

	for (i = 0; i < sector->count - 2 && ok; i++) {
		kon_vec2_t p[3];
		int k;

		for (k = 0; k < 3; k++) p[k] = kon_sectorCorner(map, s, ears[i * 3 + k]);
		ok = kon_addTriangle_(mesh, kon_vertex_(p[0].x, sector->floor, p[0].y, up, p[0].x, p[0].y), kon_vertex_(p[1].x, sector->floor, p[1].y, up, p[1].x, p[1].y),
			kon_vertex_(p[2].x, sector->floor, p[2].y, up, p[2].x, p[2].y), sector->floorTexture, 1.0f, 0);
		if (ok) ok = kon_addTriangle_(mesh, kon_vertex_(p[0].x, sector->ceiling, p[0].y, down, p[0].x, p[0].y), kon_vertex_(p[2].x, sector->ceiling, p[2].y, down, p[2].x, p[2].y),
			kon_vertex_(p[1].x, sector->ceiling, p[1].y, down, p[1].x, p[1].y), sector->ceilingTexture, 1.0f, 0);
	}
	free(ears);

	for (i = 0; i < sector->count && ok; i++) {
		kon_vec2_t p = kon_sectorCorner(map, s, i), q = kon_sectorCorner(map, s, i + 1);
		float dx = q.x - p.x, dz = q.y - p.y, length = sqrtf(dx * dx + dz * dz);
		kon_vec3_t inward = KON_VEC3(dz / length, 0.0f, -dx / length);
		int portal = map->edges[sector->first + i].portal, texture = kon_sectorWallTexture(map, s, i);

		/* seen from inside the room the corner p is on the right and q on the left */
		if (portal < 0) {
			ok = kon_addWall_(mesh, q, p, sector->floor, sector->ceiling, inward, length, texture);
		} else {
			const kon_sector_t *other = &map->sectors[portal];
			float lowTop = other->floor < sector->ceiling ? other->floor : sector->ceiling;
			float highBottom = other->ceiling > sector->floor ? other->ceiling : sector->floor;

			if (other->floor > sector->floor) ok = kon_addWall_(mesh, q, p, sector->floor, lowTop, inward, length, texture);
			if (ok && other->ceiling < sector->ceiling) ok = kon_addWall_(mesh, q, p, highBottom, sector->ceiling, inward, length, texture);
		}
	}
	return ok;
}

kon_sectorMesh_t *kon_sectorBuild(const kon_sectorMap_t *map)
{
	kon_sectorMesh_t *mesh;
	int s, i, k;

	if (!map) return NULL;
	mesh = calloc(1, sizeof(*mesh));
	if (!mesh) return NULL;
	mesh->map = map;
	mesh->first = calloc((size_t)map->sectorCount + 1, sizeof(int));
	mesh->count = calloc((size_t)map->sectorCount + 1, sizeof(int));
	mesh->center = calloc((size_t)map->sectorCount + 1, sizeof(kon_vec3_t));
	mesh->radius = calloc((size_t)map->sectorCount + 1, sizeof(float));
	if (!mesh->first || !mesh->count || !mesh->center || !mesh->radius) goto bad;

	for (s = 0; s < map->sectorCount; s++) {
		const kon_sector_t *sector = &map->sectors[s];
		float minX = 1e30f, maxX = -1e30f, minZ = 1e30f, maxZ = -1e30f, hx, hz, hy;

		mesh->first[s] = mesh->triCount;
		if (!kon_buildSector_(mesh, s)) goto bad;
		mesh->count[s] = mesh->triCount - mesh->first[s];

		for (i = 0; i < sector->count; i++) {
			kon_vec2_t p = kon_sectorCorner(map, s, i);

			if (p.x < minX) minX = p.x;
			if (p.x > maxX) maxX = p.x;
			if (p.y < minZ) minZ = p.y;
			if (p.y > maxZ) maxZ = p.y;
		}
		hx = (maxX - minX) * 0.5f;
		hz = (maxZ - minZ) * 0.5f;
		hy = (sector->ceiling - sector->floor) * 0.5f;
		mesh->center[s] = KON_VEC3(minX + hx, sector->floor + hy, minZ + hz);
		mesh->radius[s] = sqrtf(hx * hx + hy * hy + hz * hz);
	}

	mesh->quadFirst = mesh->triCount;
	for (i = 0; i < map->quadCount; i++) {
		const kon_sectorQuad_t *q = &map->quads[i];
		kon_vec3_t right = kon_vec3Sub(q->corners[1], q->corners[0]), top = kon_vec3Sub(q->corners[3], q->corners[0]);
		kon_vec3_t normal = kon_vec3Normalize(kon_vec3Cross(right, top));
		kon_vertex_t v[4];

		for (k = 0; k < 4; k++) {
			static const float u[4] = { 0, 1, 1, 0 }, w[4] = { 1, 1, 0, 0 };

			v[k] = kon_vertex_(q->corners[k].x, q->corners[k].y, q->corners[k].z, normal, u[k], w[k]);
		}
		if (!kon_addTriangle_(mesh, v[0], v[1], v[2], q->texture, q->light, q->doubleSided) || !kon_addTriangle_(mesh, v[0], v[2], v[3], q->texture, q->light, q->doubleSided)) goto bad;
	}
	return mesh;

bad:
	kon_sectorMeshFree(mesh);
	return NULL;
}

void kon_sectorMeshFree(kon_sectorMesh_t *mesh)
{
	if (!mesh) return;
	free(mesh->tris);
	free(mesh->first);
	free(mesh->count);
	free(mesh->center);
	free(mesh->radius);
	free(mesh);
}

static void kon_drawRange_(kon_framebuffer_t *fb, kon_mat4_t vp, const kon_sectorMesh_t *mesh, int from, int count, const kon_material_t *materials, int materialCount, const kon_light_t *light, float sectorLight)
{
	static const kon_material_t grey = { NULL, 0xFF808080, KON_FILTER_NEAREST, NULL };
	kon_light_t lit;
	int i;

	if (light) {
		lit = *light;
		lit.ambient *= sectorLight;
		lit.intensity *= sectorLight;
	}
	for (i = from; i < from + count; i++) {
		const kon_sectorTri_t *t = &mesh->tris[i];
		const kon_material_t *material = t->texture >= 0 && t->texture < materialCount ? &materials[t->texture] : &grey;
		kon_renderFlags_t flags = t->twoSided ? KON_RENDER_DEPTH : KON_RENDER_DEFAULT;

		if (light && t->light != 1.0f) {
			kon_light_t quadLight = lit;

			quadLight.ambient = light->ambient * t->light;
			quadLight.intensity = light->intensity * t->light;
			kon_drawTriangle3D(fb, vp, t->v[0], t->v[1], t->v[2], material, &quadLight, flags);
		} else {
			kon_drawTriangle3D(fb, vp, t->v[0], t->v[1], t->v[2], material, light ? &lit : NULL, flags);
		}
	}
}

void kon_sectorDraw(kon_framebuffer_t *fb, const kon_camera_t *camera, const kon_sectorMesh_t *mesh, const kon_material_t *materials, int materialCount, const kon_light_t *light)
{
	kon_mat4_t vp;
	kon_frustum_t frustum;
	int s;

	if (!fb || !camera || !mesh) return;
	vp = kon_cameraViewProjection(camera, fb->width, fb->height);
	frustum = kon_frustumFromMatrix(vp);

	for (s = 0; s < mesh->map->sectorCount; s++) {
		if (!kon_frustumSphere(&frustum, mesh->center[s], mesh->radius[s])) continue;
		kon_drawRange_(fb, vp, mesh, mesh->first[s], mesh->count[s], materials, materialCount, light, mesh->map->sectors[s].light);
	}
	kon_drawRange_(fb, vp, mesh, mesh->quadFirst, mesh->triCount - mesh->quadFirst, materials, materialCount, light, 1.0f);
}

#endif /* KONSECTOR_IMPLEMENTATION */

#endif /* KONSECTOR_H */