#include "LevelGen.h"

#include "Entity.h"
#include "ExMath.h"
#include "Game.h"
#include "Level.h"
#include "Log.h"
#include "rovdefs.h"
#include "World.h"

int gNumLevels = 0;
int gEnemiesEnabled = 1;

static struct SpawnedEntity* entitiesList = NULL;
static int numSpawnedEntities = 0;

/* Attempt number limits to prevent the code from entering infinite loops */
#define LVLGEN_VALIDATE_ATTEMPTS 256
#define LVLGEN_SPAWN_ATTEMPTS 1024
#define LVLGEN_LADDER_ATTEMPTS 256
#define LVLGEN_ROOM_ATTEMPTS 256

/* Room config flags */
#define ROOM_DOORS		(1 << 0)
#define ROOM_LANTERNS	(1 << 1)
#define ROOM_CHESTS		(1 << 2)
#define ROOM_MIMICS		(1 << 3)

struct FloorConfig
{
	char		enterName[64];
	char		songName[32];
	char		bossName[32];
	char		skyName[RPK_NAME_LENGTH];
	int8_t		wallHeight; /* If the number is negative, a skybox is rendered instead of the ceiling */
	uint8_t		ambientBrightness; /* 0 for full dark, 255 for fullbright */
	uint8_t		fogDepth;
	uint8_t		tileset;
	uint32_t	flags;
	int32_t		spawnTableId;
	uint32_t	numLayers;
	uint32_t	layersIndex;
	uint32_t	bossEntity;
	uint32_t	bossColour;
	uint32_t	fogColour;
	uint32_t	ambientParticleColour;
	float		ambientParticleSpeed;
};

enum LayerType
{
	LVLGEN_LAYER_FILL,
	LVLGEN_LAYER_CAVERN,
	LVLGEN_LAYER_RIVER,
	LVLGEN_LAYER_ROOMS,
	LVLGEN_LAYER_TEMPLATE
};

struct LayerConfig
{
	enum LayerType type;
	union
	{
		struct
		{
			char tile;
		} fill;
		struct
		{
			int density; // 0-100, chance of placing a wall tile instead of a floor tile
			int smoothing; // Number of iterations of smoothing done on the noise result
		} cavern;
		struct
		{
			float scale; // Scale of the noisemap used
			float width; // Upper threshold on noise where the river bed begins
			float waterLevel; // Upper threshold on noise where tiles are replaced by 'waterTile'
			char waterTile;
		} river;
		struct
		{
			int flags;
			int count;
			char floorTile;
		} rooms;
		struct
		{
			int id;
			short x, y;
		} template;
	};
};

struct TemplateConfig
{
	uint16_t w, h;
	uint32_t numEntities;
	char *tiles;
	struct TemplateEntity
	{
		uint32_t type;
		float x, y;
	} *entities;
};

struct EntitySpawnConfig
{
	int16_t amount;
	uint16_t type;
};

static struct FloorConfig *floors;
static struct LayerConfig *layers;
static struct TemplateConfig *templates;
static struct EntitySpawnConfig *entitySpawns;
static int numTemplates;

/* Keeps track of which tiles shouldn't have rooms placed on top of */
static char *disallowedMap;

/*****************************************************************************/
/* 2D Perlin "Improved Noise" Implementation                                 */
/*    based on reference: https://mrl.cs.nyu.edu/~perlin/noise/              */
/*****************************************************************************/

static const int prmt[] = {
151,160,137,91,90,15,131,13,201,95,96,53,194,233,7,225,140,36,103,30,69,142,8,
99,37,240,21,10,23,190,6,148,247,120,234,75,0,26,197,62,94,252,219,203,117,35,
11,32,57,177,33,88,237,149,56,87,174,20,125,136,171,168,68,175,74,165,71,134,
139,48,27,166,77,146,158,231,83,111,229,122,60,211,133,230,220,105,92,41,55,46,
245,40,244,102,143,54,65,25,63,161,1,216,80,73,209,76,132,187,208,89,18,169,200,
196,135,130,116,188,159,86,164,100,109,198,173,186,3,64,52,217,226,250,124,123,
5,202,38,147,118,126,255,82,85,212,207,206,59,227,47,16,58,17,182,189,28,42,223,
183,170,213,119,248,152,2,44,154,163,70,221,153,101,155,167,43,172,9,129,22,39,
253,19,98,108,110,79,113,224,232,178,185, 112,104,218,246,97,228,251,34,242,193,
238,210,144,12,191,179,162,241,81,51,145,235,249,14,239,107,49,192,214,31,181,
199,106,157,184,84,204,176,115,121,50,45,127,4,150,254,138,236,205,93,222,114,
67,29,24,72,243,141,128,195,78,66,215,61,156,180,
/* Duplicated so bounds checking is not needed. */
151,160,137,91,90,15,131,13,201,95,96,53,194,233,7,225,140,36,103,30,69,142,8,
99,37,240,21,10,23,190,6,148,247,120,234,75,0,26,197,62,94,252,219,203,117,35,
11,32,57,177,33,88,237,149,56,87,174,20,125,136,171,168,68,175,74,165,71,134,
139,48,27,166,77,146,158,231,83,111,229,122,60,211,133,230,220,105,92,41,55,46,
245,40,244,102,143,54,65,25,63,161,1,216,80,73,209,76,132,187,208,89,18,169,200,
196,135,130,116,188,159,86,164,100,109,198,173,186,3,64,52,217,226,250,124,123,
5,202,38,147,118,126,255,82,85,212,207,206,59,227,47,16,58,17,182,189,28,42,223,
183,170,213,119,248,152,2,44,154,163,70,221,153,101,155,167,43,172,9,129,22,39,
253,19,98,108,110,79,113,224,232,178,185, 112,104,218,246,97,228,251,34,242,193,
238,210,144,12,191,179,162,241,81,51,145,235,249,14,239,107,49,192,214,31,181,
199,106,157,184,84,204,176,115,121,50,45,127,4,150,254,138,236,205,93,222,114,
67,29,24,72,243,141,128,195,78,66,215,61,156,180
};

static float Noise_Fade(float t)
{
	return t * t * t * (t * (t * 6 - 15) + 10);;
}

static float Noise_Lerp(float t, float a, float b)
{
	return a + t * (b - a);
}

static float Noise_Grad(int hash, float x, float y, float z)
{
	/* Convert low 4 bits of hash code into 12 gradient directions */
	int h = hash & 15;
	float u = h < 8 ? x : y;
	float v = h < 4 ? y : (h == 12 || h == 14 ? x : z);
	return ((h & 1) == 0 ? u : -u) + ((h & 2) == 0 ? v : -v);
}

static float ImprovedNoise(float x, float y, float z)
{
	float u, v, w;
	int A, B;
	int AA, AB, BA, BB;
	float vl00, vl01, vl10, vl11;

	int X = (int)Math_Floor(x) & 255;
	int Y = (int)Math_Floor(y) & 255;
	int Z = (int)Math_Floor(z) & 255;

	x -= Math_Floor(x); y -= Math_Floor(y); z -= Math_Floor(z);
	u = Noise_Fade(x); v = Noise_Fade(y); w = Noise_Fade(z);

	A  = prmt[X] + Y;
	AA = prmt[A] + Z;
	AB = prmt[A + 1] + Z;
	B  = prmt[X + 1] + Y;
	BA = prmt[B] + Z;
	BB = prmt[B + 1] + Z;

	vl00 = Noise_Lerp(u, Noise_Grad(prmt[AA],     x, y, z),         Noise_Grad(prmt[BA],     x - 1, y, z));
	vl01 = Noise_Lerp(u, Noise_Grad(prmt[AB],     x, y - 1, z),     Noise_Grad(prmt[BB],     x - 1, y - 1, z));
	vl10 = Noise_Lerp(u, Noise_Grad(prmt[AA + 1], x, y, z - 1),     Noise_Grad(prmt[BA + 1], x - 1, y, z - 1));
	vl11 = Noise_Lerp(u, Noise_Grad(prmt[AB + 1], x, y - 1, z - 1), Noise_Grad(prmt[BB + 1], x - 1, y - 1, z - 1));
	return Noise_Lerp(w, Noise_Lerp(v, vl00, vl01), Noise_Lerp(v, vl10, vl11));
}

/*****************************************************************************/

void LvlGen_Fill(enum TileType tile)
{
	for (int i = 0; i < LEVEL_SIZE * LEVEL_SIZE; i++)
	{
		Level.tilemap[i] = tile;
	}
}

static int LvlGen_CountSurroundingWalls(int x, int y)
{
	int result = 0;
	int xx, yy;

	for (yy = y - 1; yy <= y + 1; yy++)
	{
		for (xx = x - 1; xx <= x + 1; xx++)
		{
			if (xx < 0 || xx >= LEVEL_SIZE || yy < 0 || yy >= LEVEL_SIZE)
			{
				result++;
				continue;
			}

			if (Level.tilemap[xx + yy * LEVEL_SIZE] == TILE_STONE)
				result++;
		}
	}

	return result;
}

// https://www.roguebasin.com/index.php?title=Cellular_Automata_Method_for_Generating_Random_Cave-Like_Levels
static void LvlGen_CarveCaverns(int wallChance, int numIterations)
{
	static char tmplvl[LEVEL_SIZE * LEVEL_SIZE];
	int x, y, i, j;

	for (y = 0; y < LEVEL_SIZE; y++)
	{
		for (x = 0; x < LEVEL_SIZE; x++)
		{
			Level.tilemap[x + y * LEVEL_SIZE] = RNG_CHANCE(wallChance) ? TILE_STONE : TILE_GROUND;
			if ((y == 0 || y == LEVEL_SIZE - 1) || (x == 0 || x == LEVEL_SIZE - 1))
				Level.tilemap[x + y * LEVEL_SIZE] = TILE_STONE;
			tmplvl[x + y * LEVEL_SIZE] = TILE_GROUND;
		}
	}

	for (i = 0; i < numIterations; i++)
	{
		for (x = 0; x < LEVEL_SIZE; x++)
		{
			for (y = 0; y < LEVEL_SIZE; y++)
			{
				if (LvlGen_CountSurroundingWalls(x, y) >= 5)
					tmplvl[x + y * LEVEL_SIZE] = TILE_STONE;
			}
		}
	
		for (j = 0; j < LEVEL_SIZE * LEVEL_SIZE; j++)
			Level.tilemap[j] = tmplvl[j];
	}
}

static void LvlGen_CarveRivers(float scale, float width, float waterLevel, enum TileType waterTile)
{
	int x, y;
	float depthoffs = (Math_RandomFloat() * 2.0f - 1.0f) * 976.3247f;
	for (y = 0; y < LEVEL_SIZE; y++)
	{
		for (x = 0; x < LEVEL_SIZE; x++)
		{
			float noise = Math_Abs(ImprovedNoise((float)x / scale, (float)y / scale, depthoffs));
			if (noise < width)
			{
				if (noise < waterLevel)
					Level.tilemap[x + y * LEVEL_SIZE] = waterTile;
				else
					Level.tilemap[x + y * LEVEL_SIZE] = TILE_GROUND;
			}
		}
	}
}

static void LvlGen_DisallowRect(struct IntRect *rect)
{
	int x, y;
	for (y = rect->y0; y <= rect->y1; y++)
		for (x = rect->x0; x <= rect->x1; x++)
			disallowedMap[x + y * LEVEL_SIZE]++;
}

static void BuildRoom(struct IntRect *room, enum TileType floorTile, int flags)
{
	int x, y;
	for (y = room->y0; y <= room->y1; y++)
	{
		for (x = room->x0; x <= room->x1; x++)
		{
			int isMiddleX = (x - room->x0) == (room->x1 - room->x0) / 2;
			int isMiddleY = (y - room->y0) == (room->y1 - room->y0) / 2;

			int edge = (x == room->x0 || x == room->x1) || (y == room->y0 || y == room->y1);
			int shouldHaveDoor = edge && (isMiddleX || isMiddleY);

			if ((flags & ROOM_CHESTS) && isMiddleX && isMiddleY)
			{
				int type = (flags & ROOM_MIMICS) && RNG_CHANCE(1) ? SpecialEntities[SPECIAL_DEF_MIMIC] : SpecialEntities[SPECIAL_DEF_CHEST];
				struct SpawnedEntity chest = { type, x + 0.5f, y + 0.5f , 0.0f, false };
				entitiesList[numSpawnedEntities++] = chest;
				if (RNG_CHANCE(65) && (flags & ROOM_LANTERNS))
				{
					struct SpawnedEntity lantern = { SpecialEntities[SPECIAL_DEF_LANTERN], x + 0.5f, y + 0.5f, Level.wallHeight - 0.6f, false };
					entitiesList[numSpawnedEntities++] = lantern;
				}
			}

			Level.tilemap[x + y * LEVEL_SIZE] = floorTile;
			if (edge)
			{
				Level.tilemap[x + y * LEVEL_SIZE] = TILE_BRICK;
				if (shouldHaveDoor)
				{
					int dx = 0, dy = 0; /* Normal vector of the door facing out of the room */
					if (isMiddleX)
					{
						if (y == room->y0) { dy = -1; }
						else { dy = 1; }

						if (flags & ROOM_LANTERNS)
						{
							/* Add lanterns on either side of the door */
							struct SpawnedEntity lantern = { SpecialEntities[SPECIAL_DEF_LANTERN], x - 0.5f, y + 0.5f + dy * 0.7f, 0.0f, false };
							if (!Lvl_IsWall(x - 1, y + dy)) entitiesList[numSpawnedEntities++] = lantern;
							if (!Lvl_IsWall(x + 1, y + dy)) {
								lantern.x = x + 1.5f; entitiesList[numSpawnedEntities++] = lantern;
							}
						}
					}
					else
					{
						if (x == room->x0) { dx = -1; }
						else { dx = 1; }

						if (flags & ROOM_LANTERNS)
						{
							/* Add lanterns on either side of the door */
							struct SpawnedEntity lantern = { SpecialEntities[SPECIAL_DEF_LANTERN], x + 0.5f + dx * 0.7f, y - 0.5f, 0.0f, false };
							if (!Lvl_IsWall(x + dx, y - 1)) entitiesList[numSpawnedEntities++] = lantern;
							if (!Lvl_IsWall(x + dx, y + 1)) { lantern.y = y + 1.5f; entitiesList[numSpawnedEntities++] = lantern; }
						}
					}
					/* Place the door if there isn't a wall in front of it */
					if (!Lvl_IsWall(x + dx, y + dy))
					{
						int waterStepX = x + dx;
						int waterStepY = y + dy;

						Level.tilemap[x + y * LEVEL_SIZE] = (flags & ROOM_DOORS) ? TILE_DOOR_CLOSED : floorTile;

						/* Add bridges over water tiles */
						while (Level.tilemap[waterStepX + waterStepY * LEVEL_SIZE] == TILE_WATER)
						{
							Level.tilemap[waterStepX + waterStepY * LEVEL_SIZE] = TILE_WOODPATH;
							if (waterStepX > 1 && waterStepX < (LEVEL_SIZE - 1)) waterStepX += dx;
							if (waterStepY > 1 && waterStepY < (LEVEL_SIZE - 1)) waterStepY += dy;
						}
					}
				}
			}
		}
	}
	LvlGen_DisallowRect(room);
}

static bool LvlGen_CanPlaceRoom(struct IntRect *room)
{
	int x, y;
	for (y = room->y0; y <= room->y1; y++)
	{
		for (x = room->x0; x <= room->x1; x++)
		{
			if (disallowedMap[x + y * LEVEL_SIZE])
				return false;
		}
	}
	return true;
}

static void LvlGen_AddRooms(int count, enum TileType floorTile, int flags)
{
	int i, numTries;

	for (i = 0; i < count; i++)
	{
		struct IntRect room;
		int x, y, w, h;

		for (numTries = 0; numTries < LVLGEN_ROOM_ATTEMPTS; numTries++)
		{
			w = RNG_RANGE(6, 8);
			h = RNG_RANGE(6, 8);
			x = RNG_RANGE(0, LEVEL_SIZE - w);
			y = RNG_RANGE(0, LEVEL_SIZE - h);

			room.x0 = x;
			room.y0 = y;
			room.x1 = x + w;
			room.y1 = y + h;

			if (LvlGen_CanPlaceRoom(&room))
			{
				BuildRoom(&room, floorTile, flags);
				break;
			}
		}

		if (numTries == LVLGEN_ROOM_ATTEMPTS)
		{
			Msg_Warning("Ran out of space to place %d more rooms", count - i);
			return;
		}
	}
}

static void LvlGen_PlaceTemplate(struct TemplateConfig *templ, int xo, int yo)
{
	int x, y;
	uint32_t i;
	for (y = 0; y < templ->h; y++)
	{
		int yy = y + yo;
		if (yy < 0 || yy >= LEVEL_SIZE)
			continue;
		for (x = 0; x < templ->w; x++)
		{
			int xx = x + xo;
			if (xx < 0 || xx >= LEVEL_SIZE)
				continue;
			Level.tilemap[xx + yy * LEVEL_SIZE] = templ->tiles[x + y * templ->w];
			disallowedMap[xx + yy * LEVEL_SIZE]++;
		}
	}

	for (i = 0; i < templ->numEntities; i++)
	{
		struct SpawnedEntity e;
		e.type = templ->entities[i].type;
		e.x = (float)xo + templ->entities[i].x;
		e.y = (float)yo + templ->entities[i].y;
		e.z = 0.0f;
		e.isBoss = false;
		entitiesList[numSpawnedEntities++] = e;
	}
}

static void LvlGen_AddSurroundingWalls(void)
{
	int x, y;
	for (y = 0; y < LEVEL_SIZE; y++)
	{
		for (x = 0; x < LEVEL_SIZE; x++)
		{
			if ((y == 0 || y == LEVEL_SIZE - 1) || (x == 0 || x == LEVEL_SIZE - 1))
				Level.tilemap[x + y * LEVEL_SIZE] = TILE_STONE;
		}
	}
}

static void FloodFill(unsigned char *passable, int x, int y)
{
	unsigned oldColor = 'a';
	unsigned newColor = 'B';

	int x1 = x;

	while (x1 < LEVEL_SIZE && passable[x1 + y * LEVEL_SIZE] == oldColor)
	{
		passable[x1 + y * LEVEL_SIZE] = newColor;
		x1++;
	}

	x1 = x - 1;
	while (x1 >= 0 && passable[x1 + y * LEVEL_SIZE] == oldColor)
	{
		passable[x1 + y * LEVEL_SIZE] = newColor;
		x1--;
	}

	x1 = x;
	while (x1 < LEVEL_SIZE && passable[x1 + y * LEVEL_SIZE] == newColor)
	{
		if (y > 0 && passable[x1 + (y - 1) * LEVEL_SIZE] == oldColor)
		{
			FloodFill(passable, x1, y - 1);
		}
		x1++;
	}

	x1 = x - 1;
	while (x1 >= 0 && passable[x1 + y * LEVEL_SIZE] == newColor)
	{
		if (y > 0 && passable[x1 + (y - 1) * LEVEL_SIZE] == oldColor)
		{
			FloodFill(passable, x1, y - 1);
		}
		x1--;
	}

	x1 = x;
	while (x1 < LEVEL_SIZE && passable[x1 + y * LEVEL_SIZE] == newColor)
	{
		if (y < (LEVEL_SIZE - 1) && passable[x1 + (y + 1) * LEVEL_SIZE] == oldColor)
		{
			FloodFill(passable, x1, y + 1);
		}
		x1++;
	}

	x1 = x - 1;
	while (x1 >= 0 && passable[x1 + y * LEVEL_SIZE] == newColor)
	{
		if (y < (LEVEL_SIZE - 1) && passable[x1 + (y + 1) * LEVEL_SIZE] == oldColor)
		{
			FloodFill(passable, x1, y + 1);
		}
		x1--;
	}
}

static bool IsTilePassable(int x, int y)
{
	if (Lvl_IsWall(x, y) && !Lvl_IsDoor(x, y))
		return false;
	if (Level.tilemap[x + y * LEVEL_SIZE] == TILE_HURT || Level.tilemap[x + y * LEVEL_SIZE] == TILE_LAVA)
		return false;
	return true;
}

static bool LvlGen_Validate(void)
{
	static unsigned char passable[LEVEL_SIZE * LEVEL_SIZE];
	int i;

	if (Lvl_IsWall(Level.enterX, Level.enterY))
		return false;

	for (i = 0; i < LEVEL_SIZE * LEVEL_SIZE; i++)
	{
		passable[i] = IsTilePassable(i % LEVEL_SIZE, i / LEVEL_SIZE) ? 'a' : 'c';
	}

	/* Ensure that the exit position is reachable from the entrance position */
	FloodFill(passable, Level.enterX, Level.enterY);
	//for (int i = 0; i < LEVEL_SIZE; i++)
	//{
	//	for (int j = 0; j < LEVEL_SIZE; j++)
	//	{
	//		putc(passable[j + i * LEVEL_SIZE], stdout);
	//	}
	//	putc('\n', stdout);
	//}

	return passable[Level.exitX + Level.exitY * LEVEL_SIZE] == 'B';
}

static bool IsValidEnemyPos(int type, int x, int y, const int spawnX, const int spawnY)
{
	if (Lvl_HasLineOfSight((float)spawnX, (float)spawnY, (float)x, (float)y))
		return false;
	if ((x == spawnX && y == spawnY))
		return false;
	return Level.tilemap[x + y * LEVEL_SIZE] == Obj_SpawnTileForType(type);
}

static void LvlGen_BuildTiles(struct FloorConfig *floor, int enterX, int enterY)
{
	struct IntRect ladderRoomRect = { enterX - 2, enterY - 2, enterX + 2, enterY + 2 };
	uint32_t i;

	if (Level.flags & LEVEL_NOENTRANCE)
		disallowedMap[enterX + enterY * LEVEL_SIZE]++;
	else
		LvlGen_DisallowRect(&ladderRoomRect);
	
	for (i = 0; i < floor->numLayers; i++)
	{
		struct LayerConfig *layer = &layers[floor->layersIndex + i];
		switch (layer->type)
		{
		case LVLGEN_LAYER_FILL:
			LvlGen_Fill(layer->fill.tile);
			break;
		case LVLGEN_LAYER_CAVERN:
			LvlGen_CarveCaverns(layer->cavern.density, layer->cavern.smoothing);
			break;
		case LVLGEN_LAYER_RIVER:
			LvlGen_CarveRivers(layer->river.scale, layer->river.width, layer->river.waterLevel, layer->river.waterTile);
			break;
		case LVLGEN_LAYER_ROOMS:
			LvlGen_AddRooms(layer->rooms.count, layer->rooms.floorTile, layer->rooms.flags);
			break;
		case LVLGEN_LAYER_TEMPLATE:
			LvlGen_PlaceTemplate(&templates[layer->template.id], layer->template.x, layer->template.y);
			break;
		}
	}

	if (!(Level.flags & LEVEL_NOENTRANCE))
		BuildRoom(&ladderRoomRect, TILE_GROUND, (ROOM_DOORS | ROOM_LANTERNS));
	LvlGen_AddSurroundingWalls();
}

static void LvlGen_ChooseExitPosition(int enterX, int enterY, int *exitX, int *exitY)
{
	int ladderDownX, ladderDownY;
	int tries = 0;

	do
	{
		if (tries++ >= LVLGEN_LADDER_ATTEMPTS)
		{
			ladderDownX = RNG_RANGE(1, LEVEL_SIZE - 1);
			ladderDownY = RNG_RANGE(1, LEVEL_SIZE - 1);
			/* If an exit still can't be found, ignore the spawning rules completely and just place it somewhere */
			if (tries >= LVLGEN_LADDER_ATTEMPTS * 2)
				break;
		}
		else
		{
			float distance = Math_RandomFloat() * 20.0f + 20.0f;
			float angle = Math_RandomFloat() * MATH_PI;
			ladderDownX = (int)(enterX + Math_Sin(angle) * distance);
			ladderDownY = (int)(enterY + Math_Cos(angle) * distance);
		}
	} while (OUTOFBOUNDS(ladderDownX, ladderDownY) || Level.tilemap[ladderDownX + ladderDownY * LEVEL_SIZE] != TILE_GROUND);

	if (tries >= LVLGEN_LADDER_ATTEMPTS)
	{
		Msg_Info("Had to place ladder in a random position");
	}

	*exitX = ladderDownX;
	*exitY = ladderDownY;
}

static void LvlGen_SpawnEnemies(struct FloorConfig *floor, int enterX, int enterY)
{
	int i, tries;

	if (floor->bossName[0] != '\0')
	{
		struct SpawnedEntity boss;
		boss.type = floor->bossEntity;
		boss.x = LEVEL_SIZE / 2;
		boss.y = LEVEL_SIZE / 2;
		boss.z = 0.0f;
		boss.isBoss = 1;
		while (Lvl_IsWall((int)boss.x, (int)boss.y))
		{
			boss.y++;
		}
		entitiesList[numSpawnedEntities++] = boss;
	}

	if (floor->spawnTableId == -1)
		return;

	struct EntitySpawnConfig *spawn = &entitySpawns[floor->spawnTableId];
	while (spawn->amount != -1)
	{
		for (i = 0; i < spawn->amount; i++)
		{
			struct SpawnedEntity e;
			e.type = spawn->type;
			e.isBoss = 0;
			e.z = 0.0f;

			for (tries = 0; tries < LVLGEN_SPAWN_ATTEMPTS; tries++)
			{
				e.x = RNG_RANGE(1, LEVEL_SIZE - 1);
				e.y = RNG_RANGE(1, LEVEL_SIZE - 1);
				if (IsValidEnemyPos(e.type, (int)e.x, (int)e.y, enterX, enterY))
					break;
			}
			if (tries == LVLGEN_SPAWN_ATTEMPTS)
				Msg_Warning("Exceeded entity spawn attempt limit, ignoring placement rules.");

			e.x += 0.5f;
			e.y += 0.5f;
			entitiesList[numSpawnedEntities++] = e;
		}
		spawn++;
	}
}

int LvlGen_Generate(int depth, int enterX, int enterY, struct SpawnedEntity **spawnedEntities)
{
	struct FloorConfig *floor = &floors[depth - 1];
	int levelTries;

	Msg_Info("LvlGen_Generate: Building floor %d, entrance @ %d, %d", depth, enterX, enterY);

	entitiesList = SDL_calloc(WORLD_MAX_ENTITIES, sizeof(struct SpawnedEntity));
	numSpawnedEntities = 0;
	*spawnedEntities = entitiesList;

	LvlGen_SetLevelProperties(depth);

	disallowedMap = SDL_malloc(LEVEL_SIZE * LEVEL_SIZE);

	for (levelTries = 0; levelTries < LVLGEN_VALIDATE_ATTEMPTS; levelTries++)
	{
		int ladderX, ladderY;
		SDL_memset(disallowedMap, 0, LEVEL_SIZE * LEVEL_SIZE);

		numSpawnedEntities = 0;

		// Don't generate rooms right next to the spawn ladder
		for (int y = -1; y <= 1; y++)
		{
			for (int x = -1; x <= 1; x++)
			{
				disallowedMap[(enterX + x) + (enterY + y) * LEVEL_SIZE] = 1;
			}
		}

		LvlGen_BuildTiles(floor, enterX, enterY);
		LvlGen_ChooseExitPosition(enterX, enterY, &ladderX, &ladderY);

		// Make sure the 3x3 area around the spawn room is free, so multiplayer games don't have players spawning inside walls
		for (int y = -1; y <= 1; y++)
		{
			for (int x = -1; x <= 1; x++)
			{
				Level.tilemap[(enterX + x) + (enterY + y) * LEVEL_SIZE] = TILE_GROUND;
			}
		}

		Level.enterX = enterX;
		Level.enterY = enterY;
		Level.exitX = ladderX;
		Level.exitY = ladderY;

		if (depth > 1 && Level.flags & LEVEL_HASLADDERUP)
			Level.tilemap[Level.enterX + Level.enterY * LEVEL_SIZE] = TILE_LADDER_UP;
		if (depth < gNumLevels && Level.flags & LEVEL_HASLADDERDOWN)
			Level.tilemap[Level.exitX + Level.exitY * LEVEL_SIZE] = TILE_LADDER_DOWN;

		if (LvlGen_Validate())
			break;
	}

	SDL_free(disallowedMap);

	if (levelTries >= LVLGEN_VALIDATE_ATTEMPTS)
		Msg_Warning("Layout of floor %d is impossible after %d generation attempts.", depth, levelTries);
	else
		Msg_Info("Successfully generated level on attempt %d", levelTries);

	if (gEnemiesEnabled)
		LvlGen_SpawnEnemies(floor, enterX, enterY);

	return numSpawnedEntities;
}

void LvlGen_SetLevelProperties(int depth)
{
	struct FloorConfig *floor = &floors[depth - 1];
	Level.wallHeight = floor->wallHeight;
	Level.ambientBrightness = floor->ambientBrightness;
	Level.fogDepth = floor->fogDepth;
	Level.tileset = floor->tileset;
	Level.bossColour = floor->bossColour;
	Level.fogColour = floor->fogColour;
	Level.flags = floor->flags;
	Level.skybox = LvlGen_GetSkyboxForFloor(depth);
	Level.ambientParticleColour = floor->ambientParticleColour;
	Level.ambientParticleSpeed = floor->ambientParticleSpeed;

	SDL_memcpy(Level.bossName, floor->bossName, 32);
	SDL_memcpy(Level.enterName, floor->enterName, 64);
	SDL_memcpy(Level.songName, floor->songName, 32);
}

static Bmp_t *skyCache;

static void LoadSkies(const RPKFile *rpk)
{
	int i;

	skyCache = SDL_calloc(gNumLevels, sizeof(Bmp_t));

	for (i = 0; i < gNumLevels; i++)
	{
		if (floors[i].skyName[0] == '\0')
			continue;
		skyCache[i] = Bmp_CreateFromPAKEntry(rpk, floors[i].skyName);
		if (skyCache[i].w != 1024 && skyCache[i].w != 512)
		{
			Msg_Error("%s: Invalid sky width, must be 512 or 1024 pixels wide.", floors[i].skyName);
		}
	}
}

Bmp_t *LvlGen_GetSkyboxForFloor(int floor)
{
	if (floors[floor - 1].skyName[0] == '\0')
		return NULL;
	return &skyCache[floor - 1];
}

#define FLOORCONF_SIZE 8
#define LVLGEN_HEADER_SIZE (FLOORCONF_SIZE * 12)

void LvlGen_Init(const RPKFile *rpk)
{
	SDL_RWops *rw;
	int i;
	size_t len;
	void *data;

	int numLayers, numEntitySpawns;

	len = RPK_GetEntryData(rpk, "LVLGEN", &data);
	rw = SDL_RWFromConstMem(data, len);
	if (!rw)
		Msg_Fatal("Could not read LVLGEN entry from mod file");

	gNumLevels = SDL_ReadLE32(rw);
	numLayers = SDL_ReadLE32(rw);
	numTemplates = SDL_ReadLE32(rw);

	floors = SDL_calloc(gNumLevels, sizeof(struct FloorConfig));
	layers = SDL_calloc(numLayers, sizeof(struct LayerConfig));
	templates = SDL_calloc(numTemplates, sizeof(struct TemplateConfig));

	rw->read(rw, floors, sizeof(struct FloorConfig), gNumLevels);

	for (i = 0; i < numLayers; i++)
	{
		struct LayerConfig *layer = &layers[i];
		layer->type = SDL_ReadU8(rw);
		switch (layer->type)
		{
		case LVLGEN_LAYER_FILL:
			layer->fill.tile = SDL_ReadU8(rw);
			break;
		case LVLGEN_LAYER_CAVERN:
			layer->cavern.density = SDL_ReadU8(rw);
			layer->cavern.smoothing = SDL_ReadU8(rw);
			break;
		case LVLGEN_LAYER_RIVER:
			rw->read(rw, &layer->river.scale, sizeof(float), 1);
			rw->read(rw, &layer->river.width, sizeof(float), 1);
			rw->read(rw, &layer->river.waterLevel, sizeof(float), 1);
			layer->river.waterTile = SDL_ReadU8(rw);
			break;
		case LVLGEN_LAYER_ROOMS:
			layer->rooms.flags = SDL_ReadLE16(rw);
			layer->rooms.count = SDL_ReadU8(rw);
			layer->rooms.floorTile = SDL_ReadU8(rw);
			break;
		case LVLGEN_LAYER_TEMPLATE:
			layer->template.id = SDL_ReadLE32(rw);
			layer->template.x = SDL_ReadLE16(rw);
			layer->template.y = SDL_ReadLE16(rw);
			break;
		}
	}

	for (i = 0; i < numTemplates; i++)
	{
		struct TemplateConfig *templ = &templates[i];
		templ->w = SDL_ReadLE16(rw);
		templ->h = SDL_ReadLE16(rw);

		templ->tiles = SDL_malloc(templ->w * templ->h);
		rw->read(rw, templ->tiles, 1, templ->w * templ->h);

		templ->numEntities = SDL_ReadLE32(rw);
		templ->entities = SDL_calloc(templ->numEntities, sizeof(struct TemplateEntity));
		rw->read(rw, templ->entities, sizeof(struct TemplateEntity), templ->numEntities);
	}

	numEntitySpawns = SDL_ReadLE32(rw);
	entitySpawns = SDL_calloc(numEntitySpawns, sizeof(struct EntitySpawnConfig));
	rw->read(rw, entitySpawns, sizeof(struct EntitySpawnConfig), numEntitySpawns);

	LoadSkies(rpk);
}

void LvlGen_Cleanup(void)
{
	int i;
	SDL_free(layers);
	for (i = 0; i < numTemplates; i++)
	{
		SDL_free(templates[i].tiles);
		SDL_free(templates[i].entities);
	}
	SDL_free(templates);
	SDL_free(entitySpawns);
	for (i = 0; i < gNumLevels; i++)
	{
		if (floors[i].skyName[0] != '\0')
			Bmp_Destroy(&skyCache[i]);
	}
	SDL_free(skyCache);
	SDL_free(floors);
}
