#include <psemek/app/application_base.hpp>
#include <psemek/app/default_application_factory.hpp>
#include <psemek/phys/engine_2d.hpp>
#include <psemek/gfx/painter.hpp>
#include <psemek/math/simplex.hpp>
#include <psemek/math/math.hpp>
#include <psemek/math/camera.hpp>
#include <psemek/math/scale.hpp>
#include <psemek/math/quaternion.hpp>
#include <psemek/util/hash_table.hpp>
#include <psemek/util/clock.hpp>
#include <psemek/util/overload.hpp>
#include <psemek/random/generator.hpp>
#include <psemek/random/uniform.hpp>
#include <psemek/random/normal.hpp>
#include <psemek/random/weighted.hpp>
#include <psemek/random/uniform_hemisphere.hpp>
#include <psemek/cg/convex_hull_2d/graham.hpp>
#include <psemek/log/log.hpp>
#include <psemek/util/thread.hpp>
#include <psemek/util/to_string.hpp>
#include <psemek/prof/profiler.hpp>

#include <deque>

using namespace psemek;

static float const sim_dt = 0.005f;
static float const gravity = 25.f;
static float const air_friction = 1.f;
static float const ground_friction = 100.f;
static float const hills_friction = 100.f;
static float const spring_damping = 10.f;
static float const max_spring_force = 25000.f;
static float const collision_force = 1000.f;
static float const fixed_root_force = 1000.f;
static float const creature_lifetime = 9.5f;

struct hard_tissue
{};

struct soft_tissue
{};

struct leaf
{};

struct root
{
	bool fixed = false;
};

struct flower
{};

using cell_data = std::variant<hard_tissue, soft_tissue, leaf, root, flower>;

float spring_force(cell_data const & type)
{
	return std::visit(util::overload(
		[](hard_tissue const &){ return 5000.f; },
		[](soft_tissue const &){ return 2000.f; },
		[](leaf const &){ return 500.f; },
		[](root const &){ return 5000.f; },
		[](flower const &){ return 500.f; }
	), type);
}

float size(cell_data const & type)
{
	return std::visit(util::overload(
		[](auto const &){ return 1.f; }
	), type);
}

float lifetime(cell_data const & type)
{
	return std::visit(util::overload(
		[](hard_tissue const &){ return creature_lifetime; },
		[](soft_tissue const &){ return creature_lifetime; },
		[](leaf const &){ return creature_lifetime; },
		[](root const &){ return creature_lifetime; },
		[](flower const &){ return creature_lifetime; }
	), type);
}

float opacity(cell_data const & type)
{
	return std::visit(util::overload(
		[](hard_tissue const &){ return 1.f; },
		[](soft_tissue const &){ return 0.75f; },
		[](leaf const &){ return 0.25f; },
		[](root const &){ return 1.f; },
		[](flower const &){ return 0.5f; }
	), type);
}

gfx::color_rgba cell_color(cell_data type)
{
	return std::visit(util::overload(
		[](hard_tissue const &){ return gfx::color_rgba{127, 127, 127, 255}; },
		[](soft_tissue const &){ return gfx::color_rgba{255, 255, 255, 255}; },
		[](leaf const &){ return gfx::color_rgba{127, 255, 65, 255}; },
		[](root const &){ return gfx::color_rgba{63, 0, 0, 255}; },
		[](flower const &){ return gfx::color_rgba{255, 191, 63, 255}; }
	), type);
}

static math::vector<int, 2> const neighbours[4] =
{
	{-1,  0},
	{ 1,  0},
	{ 0, -1},
	{ 0,  1},
};

struct map
{
	struct wall
	{
		math::point<float, 2> origin;
		math::vector<float, 2> normal;

		bool contains(math::point<float, 2> const & p) const
		{
			return math::dot(p - origin, normal) <= 0.f;
		}
	};

	std::vector<wall> walls;

	std::vector<math::point<float, 2>> ground_points;

	std::optional<float> radius;
};

using cell_map = std::unordered_map<math::point<int, 2>, cell_data>;

struct genome
{
	cell_map cells;
};

struct creature
{
	struct cell
	{
		std::uint32_t indices[4];
		cell_data data;
		float lifetime = 0.f;
		float received_light = 0.f;
	};

	struct genome genome;
	int generation = 0;

	std::vector<math::point<float, 2>> positions;
	std::vector<math::vector<float, 2>> velocities;
	std::vector<bool> collided;
	std::vector<std::optional<math::point<float, 2>>> fixed;
	std::vector<cell> cells;

	float energy = 0.f;

	std::vector<math::segment<std::uint32_t>> outer_edges;

	math::point<float, 2> center() const;
	math::point<float, 2> cell_center(cell const & cell) const;
	math::vector<float, 2> center_velocity() const;
	void translate(math::vector<float, 2> const & delta);
	void push(math::vector<float, 2> const & delta_velocity);

	bool dead() const;

	std::vector<creature> update(float dt, random::generator & rng);
	std::optional<creature> create_offspring(cell const & cell, random::generator & rng);
	void collide(map const & map, float dt);

	void finalize_creation();
};

math::point<float, 2> creature::center() const
{
	math::vector<float, 2> sum{0.f, 0.f};
	for (int i = 1; i < positions.size(); ++i)
	{
		sum += positions[i] - positions[0];
	}
	return positions[0] + sum / (1.f * positions.size());
}

math::point<float, 2> creature::cell_center(cell const & cell) const
{
	math::point<float, 2> center{0.f, 0.f};
	for (auto idx : cell.indices)
		center += (positions[idx] - math::point{0.f, 0.f}) * 0.25f;
	return center;
}

math::vector<float, 2> creature::center_velocity() const
{
	math::vector<float, 2> sum{0.f, 0.f};
	for (int i = 1; i < velocities.size(); ++i)
	{
		sum += velocities[i];
	}
	return sum / (1.f * velocities.size());
}

void creature::translate(math::vector<float, 2> const & delta)
{
	for (auto & pos : positions)
		pos += delta;
}

void creature::push(math::vector<float, 2> const & delta_velocity)
{
	for (auto & vel : velocities)
		vel += delta_velocity;
}

bool creature::dead() const
{
	return cells.empty();
}

std::vector<creature> creature::update(float dt, random::generator & rng)
{
	for (int i = 0; i < velocities.size(); ++i)
	{
//		velocities[i] -= gravity * dt * math::normalized(positions[i] - math::point{0.f, 0.f});
		velocities[i][1] -= gravity * dt;
		if (fixed[i])
			velocities[i] += (*fixed[i] - positions[i]) * fixed_root_force * dt;
	}

	for (auto & vel : velocities)
	{
//		auto v = math::length(vel);
//		vel -= air_friction * v * vel * dt;
		vel *= std::exp(- air_friction * dt);
	}

	for (int i = 0; i < positions.size(); ++i)
		positions[i] += velocities[i] * dt;

	static math::vector<float, 2> const deltas[4]
	{
		{-0.5f, -0.5f},
		{ 0.5f, -0.5f},
		{ 0.5f,  0.5f},
		{-0.5f,  0.5f},
	};

	bool erased = false;

	float const reproduction_energy = genome.cells.size();
	float fixed_root_count = 0.f;

	for (int i = 0; i < cells.size(); ++i)
	{
		auto & cell = cells[i];

		std::visit(util::overload(
			[](auto const &){},
			[&](root const & root){
				if (root.fixed)
					fixed_root_count += 1.f;
			}
		), cell.data);
	}

	std::vector<creature> offspring;

	for (int i = 0; i < cells.size();)
	{
		auto & cell = cells[i];

		bool kill_cell = false;

		std::visit(util::overload(
			[](auto const &){},
			[&](leaf const &){
//				energy += dt * cell.received_light * fixed_root_count;
				energy += dt * cell.received_light;
			},
			[&](root const & root){
				if (root.fixed)
					energy += dt * 0.5f;
			},
			[&](flower const &){
				if (energy >= reproduction_energy)
				{
					energy -= reproduction_energy;
					if (auto child = create_offspring(cell, rng))
						offspring.push_back(std::move(*child));
				}
			}
		), cell.data);

		cell.lifetime += dt;

		if (cell.lifetime >= lifetime(cell.data))
			kill_cell = true;

		if (kill_cell)
		{
			cells.erase(cells.begin() + i);
			erased = true;
		}
		else
			++i;
	}

	if (erased)
		finalize_creation();

	for (auto & cell : cells)
	{
		float size = ::size(cell.data);

		auto center = cell_center(cell);

		float A = 0.f;
		float B = 0.f;

		for (int i = 0; i < 4; ++i)
		{
			auto const p = positions[cell.indices[i]] - center;
			auto const q = deltas[i] * size;

			A += math::dot(p, q);
			B += math::det(p, q);
		}

		float const angle = - std::atan2(B, A);

		for (int i = 0; i < 4; ++i)
		{
			auto const target = center + math::rotate(deltas[i] * size, angle);

			auto force = spring_force(cell.data) * (target - positions[cell.indices[i]]);
//			if (auto f = math::length(force); f > max_spring_force)
//				;
			velocities[cell.indices[i]] += force * dt;
		}

		auto cmvel = math::vector{0.f, 0.f};
		auto rotation = 0.f;
		for (auto idx : cell.indices)
		{
			cmvel += velocities[idx] * 0.25f;
			rotation += math::det(positions[idx] - center, velocities[idx]) * (0.25f / math::length_sqr(positions[idx] - center));
		}

		for (auto idx : cell.indices)
		{
			auto target_vel = cmvel + math::ort(positions[idx] - center) * rotation;

			velocities[idx] += (target_vel - velocities[idx]) * (1.f - std::exp(- spring_damping * dt));
		}
	}

	return offspring;
}

void creature::collide(map const & map, float dt)
{
	collided.assign(positions.size(), false);

	for (int i = 0; i < positions.size(); ++i)
	{
		if (map.radius)
		{
			auto delta = positions[i] - math::point{0.f, 0.f};
			auto dist = math::length(delta);
			auto normal = delta / dist;
			dist -= *map.radius;

			if (dist < 0.f)
			{
				positions[i] -= dist * normal;

				auto tangent = math::ort(normal);
				auto vn = math::dot(velocities[i], normal);
				auto vt = math::dot(velocities[i], tangent);

				vn = std::max(0.f, vn);
				vt *= std::exp(- dt * ground_friction);

				velocities[i] = normal * vn + tangent * vt;

				collided[i] = true;
			}
		}

		for (auto const & wall : map.walls)
		{
			auto delta = positions[i] - wall.origin;
			auto dist = math::dot(delta, wall.normal);
			if (dist < 0.f)
			{
				positions[i] -= dist * wall.normal;

				auto tangent = math::ort(wall.normal);
				auto vn = math::dot(velocities[i], wall.normal);
				auto vt = math::dot(velocities[i], tangent);

				vn = std::max(0.f, vn);
				vt *= std::exp(- dt * ground_friction);

				velocities[i] = wall.normal * vn + tangent * vt;

				collided[i] = true;
			}
		}

		auto it = std::upper_bound(map.ground_points.begin(), map.ground_points.end(), positions[i][0], [](float v, auto const & p){ return v < p[0]; });
		if (it != map.ground_points.begin() && it != map.ground_points.end())
		{
			auto j = (it - map.ground_points.begin()) - 1;

			auto n = math::normalized(math::ort(map.ground_points[j + 1] - map.ground_points[j]));
			float dist = math::dot(positions[i] - map.ground_points[j], n);

			if (dist < 0.f)
			{
				positions[i] -= dist * n;

				auto tangent = math::ort(n);
				auto vn = math::dot(velocities[i], n);
				auto vt = math::dot(velocities[i], tangent);

				vn = std::max(0.f, vn);
				vt *= std::exp(- dt * hills_friction);

				velocities[i] = n * vn + tangent * vt;
			}
		}
	}

	for (auto & cell : cells)
	{
		if (auto root = std::get_if<::root>(&cell.data))
		{
			for (auto idx : cell.indices)
				if (collided[idx])
				{
					root->fixed = true;
					if (!fixed[idx])
						fixed[idx] = positions[idx];
				}
		}
	}
}

void creature::finalize_creation()
{
	collided.assign(positions.size(), false);
	fixed.assign(positions.size(), std::nullopt);

	util::hash_set<math::segment<std::uint32_t>> edge_set;

	for (auto const & cell : cells)
	{
		for (int i = 0; i < 4; ++i)
		{
			math::segment<std::uint32_t> segment;
			segment[0] = cell.indices[i];
			segment[1] = cell.indices[(i + 1) % 4];
			edge_set.insert(segment);
		}
	}

	outer_edges.clear();
	for (auto const & edge : edge_set)
	{
		auto dual = edge;
		std::swap(dual[0], dual[1]);
		if (!edge_set.contains(dual))
			outer_edges.push_back(edge);
	}
}

void collide(std::vector<creature> & creatures, float dt)
{
	struct cell_data
	{
		int creature;
		int cell;
		math::point<float, 2> center;
		float radius;
	};

	util::hash_map<math::point<int, 2>, std::vector<cell_data>> bins;
	float bin_size = 1.f;

	for (int c = 0; c < creatures.size(); ++c)
	{
		for (int i = 0; i < creatures[c].cells.size(); ++i)
		{
			auto const & cell = creatures[c].cells[i];

			cell_data data{c, i, creatures[c].cell_center(cell), size(cell.data)};
			math::point<int, 2> bin_id{std::floor(data.center[0] / bin_size), std::floor(data.center[1] / bin_size)};
			bins[bin_id].push_back(data);
		}
	}

	auto collide_cells = [&](cell_data const & data1, cell_data const & data2)
	{
		auto delta = data2.center - data1.center;
		auto distance = math::length(delta);

		float min_distance = data1.radius + data2.radius;

		if (data1.creature == data2.creature)
			min_distance *= 0.5f;
		else
			min_distance *= 0.75f;

		if (0.f < distance && distance < min_distance)
		{
			auto impulse = delta * ((min_distance - distance) / distance * collision_force * dt);

			auto & creature1 = creatures[data1.creature];
			auto & creature2 = creatures[data2.creature];
			auto & cell1 = creature1.cells[data1.cell];
			auto & cell2 = creature2.cells[data2.cell];

			for (auto idx : cell1.indices)
				creature1.velocities[idx] -= impulse;

			for (auto idx : cell2.indices)
				creature2.velocities[idx] += impulse;
		}
	};

	for (auto const & bin : bins)
	{
		for (int i = 0; i < bin.second.size(); ++i)
			for (int j = i + 1; j < bin.second.size(); ++j)
				collide_cells(bin.second[i], bin.second[j]);

		for (int x = -1; x <= 1; ++x)
		{
			for (int y = -1; y <= 1; ++y)
			{
				if (x == 0 && y == 0) continue;

				auto nid = bin.first + math::vector{x, y};

				if (bin.first < nid) continue;

				if (auto it = bins.find(nid); it != bins.end())
					for (auto const & data1 : bin.second)
						for (auto const & data2 : it->second)
							collide_cells(data1, data2);
			}
		}
	}
}

void enlighten(std::vector<creature> & creatures)
{
	struct cell_data
	{
		int creature;
		int cell;
		math::point<float, 2> center;
		float radius;
	};

	util::hash_map<int, std::vector<cell_data>> bins;
	float bin_size = 1.f;

	for (int c = 0; c < creatures.size(); ++c)
	{
		for (int i = 0; i < creatures[c].cells.size(); ++i)
		{
			auto & cell = creatures[c].cells[i];
			cell.received_light = 0.f;

			float radius = size(cell.data) * 0.5f;

			cell_data data{c, i, creatures[c].cell_center(cell), radius};
			int bin_min = std::floor((data.center[0] - radius) / bin_size);
			int bin_max = std::floor((data.center[0] + radius) / bin_size);
			for (int bin_id = bin_min; bin_id <= bin_max; ++bin_id)
				bins[bin_id].push_back(data);
		}
	}

	for (auto & bin : bins)
	{
		std::sort(bin.second.begin(), bin.second.end(), [](cell_data const & d1, cell_data const & d2){
			return std::tie(d1.center[1], d1.center[0]) < std::tie(d2.center[1], d2.center[0]);
		});

		math::interval<float> bin_extent{bin.first * bin_size, (bin.first + 1) * bin_size};

		float received_light = 1.f;
		for (int i = bin.second.size(); i --> 0;)
		{
			auto const & data = bin.second[i];
			auto & cell = creatures[data.creature].cells[data.cell];
			math::interval cell_extent{data.center[0] - data.radius, data.center[0] + data.radius};

			auto portion = std::min(1.f, (cell_extent & bin_extent).length() / cell_extent.length());

			cell.received_light += received_light * portion;

			// Opacity, Portion -> Factor
			// 0, 0 -> 1
			// 0, 1 -> 1
			// 1, 0 -> 1
			// 1, 1 -> 0
			received_light *= 1.f - opacity(cell.data) * portion;
		}
	}
}

void draw(gfx::painter & painter, creature const & creature, float lag)
{
	auto point = [&](auto idx){
		return creature.positions[idx] + creature.velocities[idx] * lag;
	};

	for (auto const & cell : creature.cells)
	{
		math::point<float, 2> center{0.f, 0.f};
		for (auto idx : cell.indices)
			center += 0.25f * (creature.positions[idx] - math::point{0.f, 0.f});

		gfx::color_rgba const color = gfx::dark(cell_color(cell.data), 0.75f * (1.f - cell.received_light));
		gfx::color_rgba const bgcolor = gfx::dark(color, 0.25f);

		math::point<float, 2> ps[4];
		for (int i = 0; i < 4; ++i)
			ps[i] = point(cell.indices[i]);

		painter.triangle(ps[0], ps[1], ps[2], bgcolor);
		painter.triangle(ps[2], ps[0], ps[3], bgcolor);

		for (int i = 0; i < 4; ++i)
			ps[i] = math::lerp(ps[i], center, 0.25f);

		painter.triangle(ps[0], ps[1], ps[2], color);
		painter.triangle(ps[2], ps[0], ps[3], color);
	}

	for (auto const & edge : creature.outer_edges)
	{
		gfx::color_rgba const color{0, 0, 0, 255};
		float const width = 0.125f;
		painter.line(point(edge.points[0]), point(edge.points[1]), width, color, false);
	}
}

struct creature_builder
{
	creature_builder() = default;

	creature_builder(genome genome)
		: genome_(std::move(genome))
	{}

	void add(math::point<int, 2> const position, cell_data const & data)
	{
		genome_.cells[position] = data;
	}

	bool contains(math::point<int, 2> const & position) const
	{
		return genome_.cells.contains(position);
	}

	creature build(int generation)
	{
		static math::vector<int, 2> const vertex_delta[4]
		{
			{0, 0},
			{1, 0},
			{1, 1},
			{0, 1},
		};

		creature result;
		result.generation = generation;

		util::hash_map<math::point<int, 2>, std::uint32_t> vertex_id;

		for (auto const & cell : genome_.cells)
		{
			auto & cell_out = result.cells.emplace_back();
			cell_out.data = cell.second;
			for (int i = 0; i < 4; ++i)
			{
				math::point<int, 2> vertex = cell.first + vertex_delta[i];
				if (auto it = vertex_id.find(vertex); it != vertex_id.end())
				{
					cell_out.indices[i] = it->second;
				}
				else
				{
					cell_out.indices[i] = (vertex_id[vertex] = result.positions.size());
					result.positions.push_back(math::cast<float>(vertex));
					result.velocities.push_back(math::vector<float, 2>::zero());
				}
			}
		}

		result.genome = std::move(genome_);
		result.finalize_creation();
		return result;
	}

	bool connected() const
	{
		if (genome_.cells.empty())
			return false;

		util::hash_set<math::point<int, 2>> visited;

		std::deque<math::point<int, 2>> queue;
		queue.push_back(genome_.cells.begin()->first);
		visited.insert(queue.back());

		while (!queue.empty())
		{
			auto cur = queue.front();
			queue.pop_front();

			for (auto n : neighbours)
			{
				auto nn = cur + n;
				if (genome_.cells.contains(nn) && !visited.contains(nn))
				{
					visited.insert(nn);
					queue.push_back(nn);
				}
			}
		}

		return visited.size() == genome_.cells.size();
	}

private:
	genome genome_;
};

cell_data random_cell(random::generator & rng)
{
	if (auto t = random::uniform(rng, 0, 4); t == 0)
		return hard_tissue{};
	else if (t == 1)
		return soft_tissue{};
	else if (t == 2)
		return leaf{};
	else if (t == 3)
		return root{};
	else
		return flower{};
}

void mutate(genome & genome, random::generator & rng)
{
	float const change_type_probability = 1.f / 32.f;
	float const erase_probability = 1.f / 64.f;
	float const grow_probability = 1.f / 64.f;

	for (auto & cell : genome.cells)
		if (random::uniform<float>(rng) < change_type_probability)
			cell.second = random_cell(rng);

	std::vector<math::point<int, 2>> erase_cells;
	for (auto const & cell : genome.cells)
		if (random::uniform<float>(rng) < erase_probability)
			erase_cells.push_back(cell.first);

	for (auto const & cell : erase_cells)
		genome.cells.erase(cell);

	std::vector<std::pair<math::point<int, 2>, cell_data>> grow_cells;
	for (auto const & cell : genome.cells)
		for (auto n : neighbours)
		{
			auto ncell = cell.first + n;
			if (!genome.cells.contains(ncell) && random::uniform<float>(rng) < grow_probability)
				grow_cells.push_back({ncell, random_cell(rng)});
		}

	for (auto const & cell : grow_cells)
		genome.cells.insert(cell);
}

std::optional<creature> creature::create_offspring(cell const & cell, random::generator & rng)
{
	auto genome = this->genome;
	mutate(genome, rng);

	creature_builder builder(std::move(genome));
	if (!builder.connected())
		return std::nullopt;
	auto result = builder.build(generation + 1);
	result.translate(cell_center(cell) - result.center());

	auto center = result.center();
	auto angle = random::uniform_angle<float>(rng);
	for (auto & position : result.positions)
		position = center + math::rotate(position - center, angle);

	auto push = random::uniform_hemisphere_vector_distribution<float, 2>({0.f, 1.f})(rng);
	result.translate(push * 1.f);
//	this->translate(-push * 1.f);
//	result.push(10.f * push);

	return result;
}

struct soft_creatures_2d_app
	: app::application_base
{
	soft_creatures_2d_app(options const &, context const &)
	{
//		map_.ground_points.push_back({5.f, 0.f});
//		for (int x = 10; x <= 200; x += 1)
//			map_.ground_points.push_back({x / 2.f, random::uniform(rng, 0.f, std::min(x, 200) / 200.f * 4.f)});
//			map_.ground_points.push_back({x, std::min(2.f, math::sqr(x - 10) * 0.25f)});
//			map_.ground_points.push_back({x, random::uniform(rng, 0.f, 4.f)});

		map_.walls.push_back({{0.f, 0.f}, {0.f, 1.f}});
//		map_.walls.push_back({{-40.f, 0.f}, {1.f, 0.f}});
//		map_.walls.push_back({{40.f, 0.f}, {-1.f, 0.f}});
		map_.walls.push_back({{-20.f, 0.f}, math::normalized(math::vector{1.f, 1.f})});
		map_.walls.push_back({{20.f, 0.f}, math::normalized(math::vector{-1.f, 1.f})});

//		map_.radius = 30.f;

		int initial_population_size = 1;

		for (int c = 0; c < initial_population_size; ++c)
		{
			while (true)
			{
				int x_size = random::uniform(rng_, 2, 4);
				int y_size = random::uniform(rng_, 2, 4);

				x_size = 2;
				y_size = 1;

				creature_builder builder;

//				builder.add({0, 0}, root{});
				builder.add({0, 1}, flower{});
				builder.add({0, 2}, leaf{});

				if(false)
				for (int x = 0; x < x_size; ++x)
				{
					for (int y = 0; y < y_size; ++y)
					{
						if (random::uniform<float>(rng_) > 0.75f)
							continue;

						builder.add({x, y}, random_cell(rng_));
					}
				}

				if (builder.connected())
				{
					creatures_.push_back(builder.build(0));
					creatures_.back().translate({0.f, 5.f});
//					creatures_.back().translate({0.f, map_.radius + 5.f});
					break;
				}
			}
		}

		enlighten(creatures_);
	}

	void on_event(app::key_event const & event) override
	{
		app::application_base::on_event(event);

		if (event.down && event.key == app::keycode::SPACE)
			paused_ ^= true;
	}

	void update() override
	{
		if (state().key_down.contains(app::keycode::ESCAPE))
			stop();

		float const frame_dt = frame_clock_.restart().count();

		if (!paused_) physics_lag_ += frame_dt;

		while (physics_lag_ >= sim_dt)
		{
			physics_lag_ -= sim_dt;
			simulation_time_ += sim_dt;

			std::vector<creature> alive_creatures;

			enlighten(creatures_);

			for (auto & creature : creatures_)
			{
				auto children = creature.update(sim_dt, rng_);

				for (auto child : children)
					if (!child.dead())
						alive_creatures.push_back(std::move(child));

				creature.collide(map_, sim_dt);

				if (!creature.dead())
					alive_creatures.push_back(std::move(creature));
			}

			creatures_ = std::move(alive_creatures);

			collide(creatures_, sim_dt);
		}

		if (state().key_down.contains(app::keycode::LEFT))
			view_center_tgt_[0] -= 50.f * frame_dt;

		if (state().key_down.contains(app::keycode::RIGHT))
			view_center_tgt_[0] += 50.f * frame_dt;

		if (state().key_down.contains(app::keycode::UP))
			view_center_tgt_[1] += 50.f * frame_dt;

		if (state().key_down.contains(app::keycode::DOWN))
			view_center_tgt_[1] -= 50.f * frame_dt;

		view_center_ += (view_center_tgt_ - view_center_) * (1.f - std::exp(- 20.f * frame_dt));
	}

	void present() override
	{
		gl::ClearColor(0.5f, 0.6f, 0.8f, 0.f);
		gl::Clear(gl::COLOR_BUFFER_BIT);

		float aspect_ratio = state().size[0] * 1.f / state().size[1];
		math::box<float, 2> view_box = {{{0.f, 0.f}, {0.f, 0.f}}};
		view_box[0] = {-50.f, 50.f};
		view_box[1] = {0.f, view_box[0].length() / aspect_ratio};
		view_box[1] -= view_box[1].length() / 2.f;
		view_box[0] += view_center_[0];
		view_box[1] += view_center_[1];

		gfx::color_rgba ground_color{127, 91, 65, 255};

		if (map_.radius)
			painter_.circle({0.f, 0.f}, *map_.radius, ground_color, 72);

		for (auto const & wall : map_.walls)
		{
			std::vector<math::point<float, 2>> points;
			for (float x = 0; x <= 1; ++x)
			{
				for (float y = 0; y <= 1; ++y)
				{
					auto p = view_box.corner(x, y);
					if (wall.contains(p))
						points.push_back(p);
				}
			}

			for (int d = 0; d < 2; ++d)
			{
				for (int i = 0; i < 2; ++i)
				{
					auto p0 = (d == 0) ? view_box.corner(0.f, i) : view_box.corner(i, 0.f);
					auto p1 = (d == 0) ? view_box.corner(1.f, i) : view_box.corner(i, 1.f);

					// (p0 + t * dp - o) * n = 0
					// t (dp*n) + (p0-o)*n = 0
					float a = math::dot(p1 - p0, wall.normal);
					if (std::abs(a) < 1e-4f)
						continue;

					float t = - math::dot(p0 - wall.origin, wall.normal) / a;

					if (t < 0.f || t > 1.f)
						continue;

					points.push_back(p0 + (p1 - p0) * t);
				}
			}

			std::vector<std::vector<math::point<float, 2>>::iterator> hull;
			if (!points.empty())
				cg::graham_convex_hull(points.begin(), points.end(), std::back_inserter(hull));

			for (int i = 1; i + 1 < hull.size(); ++i)
				painter_.triangle(*hull[0], *hull[i], *hull[i + 1], ground_color);
		}

		{
			gfx::color_rgba hills_color{91, 127, 65, 255};
			for (int i = 0; i + 1 < map_.ground_points.size(); ++i)
			{
				float x0 = map_.ground_points[i    ][0];
				float x1 = map_.ground_points[i + 1][0];

				float y0 = map_.ground_points[i    ][1];
				float y1 = map_.ground_points[i + 1][1];

				painter_.triangle({x0, 0.f}, {x1, 0.f}, {x1, y1}, hills_color);
				painter_.triangle({x0, 0.f}, {x1, y1}, {x0, y0}, hills_color);
			}
		}

		for (auto const & creature : creatures_)
			draw(painter_, creature, physics_lag_);

		painter_.render(math::orthographic_camera(view_box).transform());

		int text_row = 0;
		auto put_line = [&](std::string const & line)
		{
			painter_.text({13.f, 10.f + text_row * 24.f}, line, {.scale = {2.f, 2.f}, .x = gfx::painter::x_align::left, .y = gfx::painter::y_align::top, .c = {0, 0, 0, 255}});
			painter_.text({12.f,  9.f + text_row * 24.f}, line, {.scale = {2.f, 2.f}, .x = gfx::painter::x_align::left, .y = gfx::painter::y_align::top, .c = {255, 255, 255, 255}});
			++text_row;
		};

		int cells = 0;
		for (auto const & creature : creatures_)
			cells += creature.cells.size();

		put_line(util::to_string("Time: ", simulation_time_));
		put_line(util::to_string("Creatures: ", creatures_.size()));
		put_line(util::to_string("Cells: ", cells));
		put_line(util::to_string("Cell/cr.: ", cells * 1.f / creatures_.size()));

		painter_.render(math::window_camera(state().size[0], state().size[1]).transform());
	}

private:
	gfx::painter painter_;

	util::clock<> frame_clock_;

	math::point<float, 2> view_center_{0.f, 20.f};
	math::point<float, 2> view_center_tgt_ = view_center_;

	random::generator rng_{random::device{}};

	map map_;

	std::vector<creature> creatures_;

	float simulation_time_ = 0.f;
	float physics_lag_ = 0.f;
	bool paused_ = false;
};

namespace psemek::app
{

	std::unique_ptr<application::factory> make_application_factory()
	{
		return default_application_factory<soft_creatures_2d_app>({.name = "Soft-body creatures", .multisampling = 4});
	}

}
