<commit_before>#include "library/sp.h"
#include "game/tileview/tile.h"
#include "framework/framework.h"
#include "game/tileview/tileobject_projectile.h"
#include "game/city/projectile.h"
#include "game/tileview/tileobject_vehicle.h"
#include "game/city/vehicle.h"
#include "game/tileview/tileobject_scenery.h"
#include "game/city/scenery.h"
#include "game/tileview/tileobject_doodad.h"
#include "game/city/doodad.h"

#include <unordered_map>

namespace OpenApoc
{

TileMap::TileMap(Framework &fw, Vec3<int> size) : fw(fw), size(size)
{
	tiles.reserve(size.z * size.y * size.z);
	for (int z = 0; z < size.z; z++)
	{
		for (int y = 0; y < size.y; y++)
		{
			for (int x = 0; x < size.x; x++)
			{
				tiles.emplace_back(*this, Vec3<int>{x, y, z});
			}
		}
	}
}

Tile *TileMap::getTile(int x, int y, int z)
{
	if (x >= size.x || y >= size.y || z >= size.z)
	{
		LogError("Requesting tile {%d,%d,%d} in map of size {%d,%d,%d}", x, y, z, size.x, size.y,
		         size.z);
		return nullptr;
	}
	return &this->tiles[z * size.x * size.y + y * size.x + x];
}

Tile *TileMap::getTile(Vec3<int> pos) { return getTile(pos.x, pos.y, pos.z); }

Tile *TileMap::getTile(Vec3<float> pos) { return getTile(pos.x, pos.y, pos.z); }

TileMap::~TileMap() {}

Tile::Tile(TileMap &map, Vec3<int> position) : map(map), position(position) {}

namespace
{
class PathNode
{
  public:
	PathNode(float costToGetHere, Tile *parentTile, Tile *thisTile, const Vec3<float> &goal)
	    : costToGetHere(costToGetHere), parentTile(parentTile), thisTile(thisTile)
	{
		Vec3<float> thisPosition{(float)thisTile->position.x, (float)thisTile->position.y,
		                         (float)thisTile->position.z};
		Vec3<float> vectorToGoal = (goal - thisPosition);
		this->distanceToGoal = glm::length(vectorToGoal);
	}
	float costToGetHere;
	Tile *parentTile;
	Tile *thisTile;

	float distanceToGoal;
};

class PathNodeComparer
{
  public:
	bool operator()(const PathNode &p1, const PathNode &p2)
	{
		return (p1.costToGetHere + p1.distanceToGoal) < (p2.costToGetHere + p2.distanceToGoal);
	}
};

} // anonymous namespace

static std::list<Tile *> getPathToNode(std::unordered_map<Tile *, PathNode> nodes, PathNode &end)
{
	std::list<Tile *> path;
	path.push_back(end.thisTile);
	Tile *t = end.parentTile;
	while (t)
	{
		path.push_front(t);
		auto nextNodeIt = nodes.find(t);
		if (nextNodeIt == nodes.end())
		{
			LogError("Trying to expand unvisited node?");
			return {};
		}
		auto &nextNode = nextNodeIt->second;
		if (nextNode.thisTile != t)
		{
			LogError("Unexpected parentTile pointer");
			return {};
		}
		t = nextNode.parentTile;
	}

	return path;
}

std::list<Tile *> TileMap::findShortestPath(Vec3<int> origin, Vec3<int> destination,
                                            unsigned int iterationLimit,
                                            const CanEnterTileHelper &canEnterTile)
{
	PathNodeComparer c;
	std::unordered_map<Tile *, PathNode> visitedTiles;
	std::set<PathNode, PathNodeComparer> fringe(c);
	Vec3<float> goalPosition;
	unsigned int iterationCount = 0;

	LogInfo("Trying to route from {%d,%d,%d} to {%d,%d,%d}", origin.x, origin.y, origin.z,
	        destination.x, destination.y, destination.z);

	if (origin.x < 0 || origin.x >= this->size.x || origin.y < 0 || origin.y >= this->size.y ||
	    origin.z < 0 || origin.z >= this->size.z)
	{
		LogError("Bad origin {%d,%d,%d}", origin.x, origin.y, origin.z);
		return {};
	}
	if (destination.x < 0 || destination.x >= this->size.x || destination.y < 0 ||
	    destination.y >= this->size.y || destination.z < 0 || destination.z >= this->size.z)
	{
		LogError("Bad destination {%d,%d,%d}", destination.x, destination.y, destination.z);
		return {};
	}

	if (origin == destination)
	{
		LogError("Destination == origin {%d,%d,%d}", destination.x, destination.y, destination.z);
		return {};
	}

	goalPosition = {destination.x, destination.y, destination.z};

	Tile *goalTile = this->getTile(destination);
	if (!goalTile)
	{
		LogError("Failed to get destination tile at {%d,%d,%d}", destination.x, destination.y,
		         destination.z);
		return {};
	}
	Tile *startTile = this->getTile(origin);
	if (!startTile)
	{
		LogError("Failed to get origin tile at {%d,%d,%d}", origin.x, origin.y, origin.z);
		return {};
	}

	PathNode startNode(0.0f, nullptr, startTile, goalPosition);
	fringe.emplace(startNode);
	visitedTiles.emplace(startTile, startNode);

	auto closestNodeSoFar = *fringe.begin();

	while (iterationCount++ < iterationLimit)
	{
		auto first = fringe.begin();
		if (first == fringe.end())
		{
			LogInfo("No more tiles to expand after %d iterations", iterationCount);
			return {};
		}
		auto nodeToExpand = *first;
		fringe.erase(first);

		Vec3<int> currentPosition = nodeToExpand.thisTile->position;
		if (currentPosition == destination)
			return getPathToNode(visitedTiles, nodeToExpand);<commit_msg>Pathing: Allow origin==dest and always move at least one tile if routing fails<commit_after>#include "library/sp.h"
#include "game/tileview/tile.h"
#include "framework/framework.h"
#include "game/tileview/tileobject_projectile.h"
#include "game/city/projectile.h"
#include "game/tileview/tileobject_vehicle.h"
#include "game/city/vehicle.h"
#include "game/tileview/tileobject_scenery.h"
#include "game/city/scenery.h"
#include "game/tileview/tileobject_doodad.h"
#include "game/city/doodad.h"

#include <unordered_map>

namespace OpenApoc
{

TileMap::TileMap(Framework &fw, Vec3<int> size) : fw(fw), size(size)
{
	tiles.reserve(size.z * size.y * size.z);
	for (int z = 0; z < size.z; z++)
	{
		for (int y = 0; y < size.y; y++)
		{
			for (int x = 0; x < size.x; x++)
			{
				tiles.emplace_back(*this, Vec3<int>{x, y, z});
			}
		}
	}
}

Tile *TileMap::getTile(int x, int y, int z)
{
	if (x >= size.x || y >= size.y || z >= size.z)
	{
		LogError("Requesting tile {%d,%d,%d} in map of size {%d,%d,%d}", x, y, z, size.x, size.y,
		         size.z);
		return nullptr;
	}
	return &this->tiles[z * size.x * size.y + y * size.x + x];
}

Tile *TileMap::getTile(Vec3<int> pos) { return getTile(pos.x, pos.y, pos.z); }

Tile *TileMap::getTile(Vec3<float> pos) { return getTile(pos.x, pos.y, pos.z); }

TileMap::~TileMap() {}

Tile::Tile(TileMap &map, Vec3<int> position) : map(map), position(position) {}

namespace
{
class PathNode
{
  public:
	PathNode(float costToGetHere, Tile *parentTile, Tile *thisTile, const Vec3<float> &goal)
	    : costToGetHere(costToGetHere), parentTile(parentTile), thisTile(thisTile)
	{
		Vec3<float> thisPosition{(float)thisTile->position.x, (float)thisTile->position.y,
		                         (float)thisTile->position.z};
		Vec3<float> vectorToGoal = (goal - thisPosition);
		this->distanceToGoal = glm::length(vectorToGoal);
	}
	float costToGetHere;
	Tile *parentTile;
	Tile *thisTile;

	float distanceToGoal;
};

class PathNodeComparer
{
  public:
	bool operator()(const PathNode &p1, const PathNode &p2)
	{
		return (p1.costToGetHere + p1.distanceToGoal) < (p2.costToGetHere + p2.distanceToGoal);
	}
};

} // anonymous namespace

static std::list<Tile *> getPathToNode(std::unordered_map<Tile *, PathNode> nodes, PathNode &end)
{
	std::list<Tile *> path;
	path.push_back(end.thisTile);
	Tile *t = end.parentTile;
	while (t)
	{
		path.push_front(t);
		auto nextNodeIt = nodes.find(t);
		if (nextNodeIt == nodes.end())
		{
			LogError("Trying to expand unvisited node?");
			return {};
		}
		auto &nextNode = nextNodeIt->second;
		if (nextNode.thisTile != t)
		{
			LogError("Unexpected parentTile pointer");
			return {};
		}
		t = nextNode.parentTile;
	}

	return path;
}

std::list<Tile *> TileMap::findShortestPath(Vec3<int> origin, Vec3<int> destination,
                                            unsigned int iterationLimit,
                                            const CanEnterTileHelper &canEnterTile)
{
	PathNodeComparer c;
	std::unordered_map<Tile *, PathNode> visitedTiles;
	std::set<PathNode, PathNodeComparer> fringe(c);
	Vec3<float> goalPosition;
	unsigned int iterationCount = 0;

	LogInfo("Trying to route from {%d,%d,%d} to {%d,%d,%d}", origin.x, origin.y, origin.z,
	        destination.x, destination.y, destination.z);

	if (origin.x < 0 || origin.x >= this->size.x || origin.y < 0 || origin.y >= this->size.y ||
	    origin.z < 0 || origin.z >= this->size.z)
	{
		LogError("Bad origin {%d,%d,%d}", origin.x, origin.y, origin.z);
		return {};
	}
	if (destination.x < 0 || destination.x >= this->size.x || destination.y < 0 ||
	    destination.y >= this->size.y || destination.z < 0 || destination.z >= this->size.z)
	{
		LogError("Bad destination {%d,%d,%d}", destination.x, destination.y, destination.z);
		return {};
	}

	goalPosition = {destination.x, destination.y, destination.z};
	Tile *goalTile = this->getTile(destination);

	if (!goalTile)
	{
		LogError("Failed to get destination tile at {%d,%d,%d}", destination.x, destination.y,
		         destination.z);
		return {};
	}
	Tile *startTile = this->getTile(origin);
	if (!startTile)
	{
		LogError("Failed to get origin tile at {%d,%d,%d}", origin.x, origin.y, origin.z);
		return {};
	}

	if (origin == destination)
	{
		LogInfo("Destination == origin {%d,%d,%d}", destination.x, destination.y, destination.z);
		return {goalTile};
	}

	PathNode startNode(0.0f, nullptr, startTile, goalPosition);
	fringe.emplace(startNode);
	visitedTiles.emplace(startTile, startNode);

	auto closestNodeSoFar = *fringe.begin();

	while (iterationCount++ < iterationLimit)
	{
		auto first = fringe.begin();
		if (first == fringe.end())
		{
			LogInfo("No more tiles to expand after %d iterations", iterationCount);
			return {};
		}
		auto nodeToExpand = *first;
		fringe.erase(first);

		// Make it so we always try to move at least one tile
		if (closestNodeSoFar.parentTile == nullptr)
			closestNodeSoFar = nodeToExpand;

		Vec3<int> currentPosition = nodeToExpand.thisTile->position;
		if (currentPosition == destination)
			return getPathToNode(visitedTiles, nodeToExpand);
{'fraction_non_alphanumeric': 0.16544376319228063, 'fraction_numerical': 0.006030756859985928, 'mean_word_length': 3.872673849167483, 'pattern_counts': {'":': 0, '<': 63, '<?xml version=': 0, '>': 89, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 8, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4786052', 'n_tokens_mistral': 3856, 'n_tokens_neox': 3583, 'n_words': 785}