/*
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"

namespace world {

static const v2f_t path_margin(5, 5);

// The path finder will try to walk in the eight directions listed below.
static const tile_index_t path_offsets[8] = {
	{+1, 0}, {+1, +1}, {0, +1}, {-1, +1},
	{-1, 0}, {-1, -1}, {0, -1}, {+1, -1}
};

path_finder_t::~path_finder_t()
{
	delete[] nodes;
}

void path_finder_t::setup_nodes(v2f_t src_, v2f_t dst_, cflags_t cflags_)
{
	rectf_t src_margin, dst_margin;
	tile_index_t end;

	src = src_;
	dst = dst_;
	cflags = cflags_;

	tile_center = v2f_t(0.5, 0.5);
	shortest_dist = INFINITY;

	src_margin[0] = src - path_margin;
	src_margin[1] = src + path_margin;
	dst_margin[0] = dst - path_margin;
	dst_margin[1] = dst + path_margin;
	bounds = src_margin | dst_margin;

	base = tile_index_at(bounds[0]);
	end = tile_index_at(bounds[1]);

	width = end[0] - base[0] + 1;
	height = end[1] - base[1] + 1;

	nodes = new path_node_t[width * height];
	for (size_t i = 0; i < width * height; i++) {
		nodes[i].accessible = true;
		nodes[i].dist = INFINITY;
	}
}

void path_finder_t::eliminate_nodes(rectf_t bounds)
{
	rect_t<coord_t, 2> index_bounds;
	tile_index_t index;

	bounds[0] -= tile_center;
	bounds[1] -= tile_center;

	index_bounds[0] = tile_index_t(bounds[0].ceil()) - base;
	index_bounds[1] = tile_index_t(bounds[1].floor()) - base;

	if (index_bounds[0][0] < 0)
		index_bounds[0][0] = 0;
	if (index_bounds[0][1] < 0)
		index_bounds[0][1] = 0;
	if (index_bounds[1][0] >= (coord_t)width)
		index_bounds[1][0] = width - 1;
	if (index_bounds[1][1] >= (coord_t)height)
		index_bounds[1][1] = height - 1;

	for (index[1] = index_bounds[0][1]; index[1] <= index_bounds[1][1]; index[1]++)
	for (index[0] = index_bounds[0][0]; index[0] <= index_bounds[1][0]; index[0]++) {
		path_node_t *node;

		node = nodes + index[1] * width + index[0];
		node->accessible = false;
	}
}

path_node_t *path_finder_t::node_at(tile_index_t index)
{
	return nodes + index[1] * width + index[0];
}

bool path_finder_t::is_accessible(tile_index_t index)
{
	if (index[0] < 0 || index[1] < 0 ||
	    index[0] >= (coord_t)width || index[1] >= (coord_t)height)
		return false;

	return node_at(index)->accessible;
}

// Walking diagonally requires an additional accessibility test. The tables
// below list when it's needed and which tile is to be tested. For example,
// when walking north-west, the north and the west neighbors have to be tested
// for accessibility.
bool path_finder_t::diagonal_test(tile_index_t index, size_t i)
{
	static const bool do_test[8] = {
		false, true, false, true, false, true, false, true
	};
	static const tile_index_t offsets[8][2] = {
		{},
		{{+1, 0}, {0, +1}},
		{},
		{{0, +1}, {-1, 0}},
		{},
		{{-1, 0}, {0, -1}},
		{},
		{{0, -1}, {+1, 0}}
	};

	if (!do_test[i])
		return true;

	for (size_t j = 0; j < 2; j++)
		if (!is_accessible(index + offsets[i][j]))
			return false;

	return true;
}

static const int visit_orders[4][8] = {
	{0, 7, 1, 2, 6, 5, 3, 4}, // prefer +x
	{2, 3, 1, 0, 4, 7, 5, 6}, // prefer +y
	{4, 5, 3, 2, 6, 1, 7, 0}, // prefer -x
	{6, 5, 7, 0, 4, 3, 1, 2}  // prefer -y
};

static const int *visit_order(v2f_t delta)
{
	if (delta[1] > delta[0]) {
		if (delta[1] > -delta[0])
			return visit_orders[1];
		else
			return visit_orders[2];
	} else {
		if (delta[1] > -delta[0])
			return visit_orders[0];
		else
			return visit_orders[3];
	}

	return visit_orders[0];
}

void path_finder_t::find_r(tile_index_t index, float dist, float limit)
{
	path_node_t *node;
	v2f_t delta;
	float dist_to_dst;
	const int *order;

	node = nodes + index[1] * width + index[0];

	if (!node->accessible)
		return;
	if (node->dist <= dist)
		return;

	node->dist = dist;
	path.push_back(index);

	delta = dst - v2f_t(base + index) - tile_center;
	dist_to_dst = delta.len();
	if (dist_to_dst < 1.0f && dist + dist_to_dst < shortest_dist) {
		shortest_path = path;
		shortest_dist = dist + dist_to_dst;
		return;
	}

	order = visit_order(delta);

	for (size_t i = 0; i < 8; i++) {
		tile_index_t offset, next;

		offset = path_offsets[order[i]];
		next = index + offset;

		if (!is_accessible(next))
			continue;

		if (!diagonal_test(index, order[i]))
			continue;

		if (dist + v2f_t(offset).len() > limit)
			continue;

		find_r(next, dist + v2f_t(offset).len(), limit);
		if (shortest_path.size())
			return;
	}

	path.pop_back();
}

bool path_finder_t::find(void)
{
	tile_index_t start;

	start = tile_index_at(src) - base;
	find_r(start, 0.0f, 100.0f);

	return shortest_path.size() > 0;
}

void path_finder_t::export_path(std::list<v2f_t> *list)
{
	list->clear();

	for (tile_index_t &index : shortest_path)
		list->push_back(v2f_t(index + base) + tile_center);

	list->push_back(dst);
}

} // namespace world