/*
This file is part of Minitrem.

Minitrem is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 2 of the License, or
(at your option) any later version.

Minitrem is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with Minitrem.  If not, see <http://www.gnu.org/licenses/>.
*/

#include "common.hpp"
#include <sstream>

namespace world {

sector_index_t sector_index_at(v2f_t x)
{
	return sector_index_t((x / SECTOR_SIZE).floor());
}

tile_index_t tile_index_at(v2f_t x)
{
	return sector_index_t(x.floor());
}

world_t::world_t(void)
{
	prng.seed(125);
	perlin.generate(&prng, 32);
}

// FIXME: rename
static cflags_t tiles[256] = {0};

void register_tile(uint8_t type, cflags_t cflags)
{
	tiles[type] = cflags;
}

void world_t::generate(sector_t *sector, sector_index_t index, sector_level_t level)
{
	bool gen_tiles = false, gen_decos = false;

	sector->index = index;
	sector->bounds.v[0] = (v2f_t)index * SECTOR_SIZE;
	sector->bounds.v[1] = sector->bounds.v[0] + v2f_t(SECTOR_SIZE, SECTOR_SIZE);

	if (sector->level == SECTOR_EMPTY) {
		if (level == SECTOR_PARTIAL)
			gen_tiles = true;
		else if (level == SECTOR_FULL)
			gen_tiles = gen_decos = true;
	} else if (sector->level == SECTOR_PARTIAL)
		gen_decos = true;

	sector->level = level;
	generator(this, index, sector, gen_tiles, gen_decos, generator_data);

	stats.sectors++;
	stats.tiles += SECTOR_SIZE * SECTOR_SIZE;

	if (sector->level < SECTOR_FULL)
		return;

	for (coord_t ty = 0; ty < SECTOR_SIZE; ty++)
	for (coord_t tx = 0; tx < SECTOR_SIZE; tx++) {
		tile_t *tile;
		tile_index_t local(tx, ty);

		tile = sector->tiles + ty * SECTOR_SIZE + tx;
		tile->neighbors = 0;

		for (size_t i = 0; i < 8; i++) {
			tile_index_t neighbor_index;
			tile_t *neighbor;

			neighbor_index = index * SECTOR_SIZE + local + neighbor_offsets[i];
			neighbor = get_tile(neighbor_index, SECTOR_PARTIAL);

			if (neighbor->type == tile->type)
				tile->neighbors |= (1 << i);
		}
	}
}

bool world_t::find_path(v2f_t src, v2f_t dst, cmodel_t *cmodel, entity_t *ignore,
                        std::list<v2f_t> *path)
{
	path_finder_t finder;
	rectf_t bounds;
	v2f_t cmodel_dims;

	finder.setup_nodes(src, dst, cmodel->cflags);

	cmodel_dims = cmodel->bounds.dims();

	for (size_t y = 0; y < finder.height; y++)
	for (size_t x = 0; x < finder.width; x++) {
		tile_index_t index;
		rectf_t combined;

		index = finder.base + tile_index_t(x, y);

		if (!(tiles[get_tile(index, SECTOR_FULL)->type] & cmodel->cflags))
			continue;

		combined[0] = v2f_t(index)  - cmodel_dims / 2;
		combined[1] = v2f_t(index) + v2f_t(1.0f, 1.0f) + cmodel_dims / 2;

		finder.eliminate_nodes(combined);
	}

	bounds = finder.bounds;
	bounds[0] -= cmodel_dims / 2;
	bounds[1] += cmodel_dims / 2;

	for (entity_t *ent : get_entities(bounds, cmodel->cflags)) {
		v2f_t center;
		v2f_t combined_dims;
		rectf_t combined;

		if (ent == ignore)
			continue;

		if (!(ent->cmodel.cflags & cmodel->cflags))
			continue;

		center = ent->cmodel.bounds.center();
		combined_dims = ent->cmodel.bounds.dims() + cmodel_dims;
		combined[0] = center - combined_dims / 2;
		combined[1] = center + combined_dims / 2;

		finder.eliminate_nodes(combined);
	}
	if (!finder.find())
		return false;

	finder.export_path(path);
	return true;
}

sector_t *world_t::get_sector(sector_index_t index, sector_level_t level)
{
	sector_t *sector;

	sector = &sectors[index];

	if (sector->level < level)
		generate(sector, index, level);

	return sector;
}

tile_t *world_t::get_tile(tile_index_t index, sector_level_t level)
{
	sector_index_t sector_index;
	sector_t *sector;
	int64_t tx, ty;

	sector_index[0] = divide_rmi(index[0], (int64_t)SECTOR_SIZE, &tx);
	sector_index[1] = divide_rmi(index[1], (int64_t)SECTOR_SIZE, &ty);
	sector = get_sector(sector_index, level);

	return sector->tiles + ty * SECTOR_SIZE + tx;
}

std::list<sector_t*> world_t::get_sectors(rectf_t rect, sector_level_t level)
{
	sector_index_t base, upper;
	std::list<sector_t*> list;

	base = sector_index_at(rect.v[0]);
	upper = sector_index_at(rect.v[1]);

	for (int64_t y = base[1]; y <= upper[1]; y++)
	for (int64_t x = base[0]; x <= upper[0]; x++) {
		sector_index_t index(x, y);
		list.push_back(get_sector(index, level));
	}

	return list;
}

static size_t cookie = 0;

std::list<entity_t*> world_t::get_entities(rectf_t rect, cflags_t cflags)
{
	std::list<entity_t*> list;

	cookie++;

	for (sector_t *sector : get_sectors(rect, SECTOR_FULL))
	for (entity_t *ent : sector->ents) {
		if (ent->cookie == cookie)
			continue;

		ent->cookie = cookie;

		if (!(ent->cmodel.cflags & cflags))
			continue;

		if (!(rect && ent->cmodel.bounds))
			continue;

		list.push_back(ent);
	}

	return list;
}

std::list<entity_t*> world_t::get_render_entities(rectf_t rect)
{
	std::list<entity_t*> list;

	cookie++;

	for (sector_t *sector : get_sectors(rect, SECTOR_FULL))
	for (entity_t *ent : sector->ents) {
		if (ent->cookie == cookie)
			continue;

		if (!(rect && ent->render_bounds))
			continue;

		ent->cookie = cookie;

		list.push_back(ent);
	}

	return list;
}

bool world_t::test_rect(const cmodel_t *cmodel, const entity_t *ignore)
{
	cookie++;

	for (sector_t *sector : get_sectors(cmodel->bounds, SECTOR_FULL)) {
		rect_t<coord_t, 2> bounds;
		tile_index_t index;

		bounds[0] = (cmodel->bounds[0] - sector->bounds[0]).floor();
		bounds[1] = (cmodel->bounds[1] - sector->bounds[0]).floor();

		if (bounds[0][0] < 0)
			bounds[0][0] = 0;
		if (bounds[0][1] < 0)
			bounds[0][1] = 0;
		if (bounds[1][0] >= (coord_t)SECTOR_SIZE)
			bounds[1][0] = SECTOR_SIZE - 1;
		if (bounds[1][1] >= (coord_t)SECTOR_SIZE)
			bounds[1][1] = SECTOR_SIZE - 1;

		for (index[1] = bounds[0][1]; index[1] <= bounds[1][1]; index[1]++)
		for (index[0] = bounds[0][0]; index[0] <= bounds[1][0]; index[0]++) {
			tile_t *tile;

			tile = sector->tiles + index[1] * SECTOR_SIZE + index[0];

			if (tiles[tile->type] & cmodel->cflags)
				return true;
		}

		for (entity_t *ent : sector->ents) {
			if (ent == ignore)
				continue;

			if (ent->cookie == cookie)
				continue;

			ent->cookie = cookie;

			if (!(ent->cmodel.cflags & cmodel->cflags))
				continue;

			if (!(cmodel->bounds && ent->cmodel.bounds))
				continue;

			return true;
		}
	}

	return false;
}

static const v2f_t transforms[4] = {
	{+1, +1}, {-1, +1}, {-1, -1}, {+1, -1}
};

static const tile_index_t transforms_index[4] = {
	{+1, +1}, {-1, +1}, {-1, -1}, {+1, -1}
};

static const tile_index_t offsets_index[4] = {
	{0, 0}, {-1, 0}, {-1, -1}, {0, -1}
};

static inline size_t quadrant(v2f_t dx)
{
	if (dx[0] == 0.0f && dx[1] == 0.0f)
		return 4;

	if (dx[1] >= 0.0f) {
		if (dx[0] >= 0.0f)
			return 0;
		else
			return 1;
	} else {
		if (dx[0] >= 0.0f)
			return 3;
		else
			return 2;
	}
}

trace_t ray_v_rect(v2f_t start, v2f_t end, rectf_t rect)
{
	v2f_t dx, tdelta, dims;
	size_t quad;
	trace_t res;

	if (rect.contains(start)) {
		res.hit = true;
		res.end = start;
		res.frac = 0.0f;
		return res;
	}

	dx = end - start;

	quad = quadrant(dx);
	if (quad == 4)
		goto out_no_hit;

	// If necessary, transform (with simple X/Y reflections) the coordinate
	// system, so that dx lies in the first quadrant.

	start ^= transforms[quad];
	dx ^= transforms[quad];
	end ^= transforms[quad];

	dims = rect.dims();
	rect.v[0] ^= transforms[quad];
	rect.v[1] ^= transforms[quad];

	// Find the closest point on the rectangle and transform the coordinates
	// so that it lies at (0, 0).

	tdelta[0] = std::min(rect.v[0][0], rect.v[1][0]);
	tdelta[1] = std::min(rect.v[0][1], rect.v[1][1]);
	start -= tdelta;

	// Project onto x = 0.
	res.frac = -start[0] / dx[0];
	if (res.frac >= 0.0f && res.frac <= 1.0f) {
		float y;

		y = start[1] + res.frac * dx[1];
		if (y >= 0 && y <= dims[1]) {
			res.hit = true;
			res.end = (v2f_t(0, y) + tdelta) ^ transforms[quad];
			return res;
		}
	}

	// Project onto y = 0.
	res.frac = -start[1] / dx[1];
	if (res.frac >= 0.0f && res.frac <= 1.0f) {
		float x;

		x = start[0] + res.frac * dx[0];
		if (x >= 0 && x <= dims[0]) {
			res.hit = true;
			res.end = (v2f_t(x, 0) + tdelta) ^ transforms[quad];
			return res;
		}
	}

out_no_hit:
	res.hit = false;
	res.end = end ^ transforms[quad];
	res.frac = 1.0f;
	return res;
}


trace_t world_t::ray_v_ents(v2f_t start, v2f_t end, cflags_t cflags,
                            const entity_t *ignore)
{
	trace_t best;
	rectf_t rect;

	best.hit = false;
	best.frac = 2.0f;

	rect = rectf_t(start, end).norm();

	for (entity_t *ent : get_entities(rect, cflags)) {
		trace_t trace;

		if (ent == ignore)
			continue;

		trace = ray_v_rect(start, end, ent->cmodel.bounds);
		if (!trace.hit)
			continue;

		if (trace.frac < best.frac) {
			best = trace;
			best.tile = nullptr;
			best.ent = ent;
		}
	}

	return best;
}


trace_t world_t::ray_v_tiles(v2f_t start, v2f_t end, cflags_t cflags)
{
	v2f_t x, dx;
	size_t quad;
	trace_t res;

	dx = end - start;

	quad = quadrant(dx);
	if (quad == 4) {
		res.hit = false;
		res.end = end;
		res.frac = 1.0f;
		return res;
	}

	start ^= transforms[quad];
	dx ^= transforms[quad];
	end ^= transforms[quad];

	x = start;

	while (1) {
		v2f_t mod, P;
		tile_index_t index;
		tile_t *tile;

		if (x[0] >= end[0] && x[1] >= end[1]) {
			res.hit = false;
			res.end = end ^ transforms[quad];
			res.frac = 1.0f;
			return res;
		}

		index = (tile_index_t(x.floor()) ^ transforms_index[quad]) +
		        offsets_index[quad];
		tile = get_tile(index, SECTOR_FULL);

		if (tiles[tile->type] & cflags) {
			res.hit = true;
			res.end = x ^ transforms[quad];
			res.frac = (x - start).len() / (end - start).len();
			res.ent = nullptr;
			res.tile = tile;
			return res;
		}

		mod = x - x.floor();

		// Project onto x = const.
		P[0] = 1.0f - mod[0];
		P[1] = P[0] / dx[0] * dx[1];
		if (mod[1] + P[1] >= 0.0f && mod[1] + P[1] <= 1.0f)
		{
			x += P;
			x[0] = std::round(x[0]);
			continue;
		}

		// Project onto y = const.
		P[1] = 1.0f - mod[1];
		P[0] = P[1] / dx[1] * dx[0];
		x += P;
		x[1] = std::round(x[1]);
	}
}

trace_t world_t::ray_v_all(v2f_t start, v2f_t end, cflags_t cflags,
                          const entity_t *ignore)
{
	trace_t v_tiles, v_ents;

	v_tiles = ray_v_tiles(start, end, cflags);
	v_ents = ray_v_ents(start, end, cflags, ignore);

	if (v_tiles.frac < v_ents.frac)
		return v_tiles;
	else
		return v_ents;
}


entity_t::entity_t(int type_)
{
	type = type_;
}

entity_t::~entity_t(void)
{
}

void entity_t::link_to_sector(sector_t *sector)
{
	parents.push_back(sector);
	sector->ents.insert(this);
}

void entity_t::link(world_t *world_)
{
	rectf_t total_bounds;
	float fx, fy;
	sector_index_t base;
	float xlip, ylip;
	size_t xsecs, ysecs;

	if (world)
		unlink();

	world = world_;

	total_bounds = cmodel.bounds | render_bounds;

	fx = floor(total_bounds[0][0]);
	fy = floor(total_bounds[0][1]);

	base = sector_index_at(v2f_t(fx, fy));
	xlip = total_bounds[1][0] - (base[0] + 1) * SECTOR_SIZE;
	ylip = total_bounds[1][1] - (base[1] + 1) * SECTOR_SIZE;

	if (xlip > 0.0f)
		xsecs = ceil(xlip / SECTOR_SIZE) + 1;
	else
		xsecs = 1;

	if (ylip > 0.0f)
		ysecs = ceil(ylip / SECTOR_SIZE) + 1;
	else
		ysecs = 1;

	for (int64_t y = 0; y < (int64_t)ysecs; y++)
	for (int64_t x = 0; x < (int64_t)xsecs; x++) {
		sector_index_t index = base + sector_index_t(x, y);
		sector_t *sector;

		sector = world->get_sector(index, SECTOR_FULL);
		link_to_sector(sector);
	}

	world->stats.entities++;
}

void entity_t::unlink(void)
{
	for (sector_t *sector : parents) {
		if (sector->ents.find(this) == sector->ents.end()) {
			printf("entity_t::unlink: %p should belong to %p (%" PRIi64", %" PRIi64") but it doesn't\n",
			       this, sector, sector->index[0], sector->index[1]);
			continue;
		}

		sector->ents.erase(sector->ents.find(this));
	}

	parents.clear();
	world->stats.entities--;
	world = 0;
}

} // namespace world