Method findLosBlockPath

game/state/tilemap/pathfinding.cpp:730–847

FIXME: This can be improved with caching of results, though I am not sure if it would be worth it. The way to improve is as follows: After we find a path, we know for sure that this path is optimal for all the subpaths in it. For example, if optimal path from A to D is A->B->C->D, then the optimal path from B to D would certainly be B->C->D, and from A to C will be A->B->C etc. Additionally, sin

//
// Obviously, when any update of the LOS block pathfinding happens, this would have to be cleared.
std::list<int> Battle::findLosBlockPath(int origin, int destination, BattleUnitType type,
                                        int iterationLimit)
{
	int lbCount = losBlocks.size();
	std::vector<bool> visitedBlocks = std::vector<bool>(lbCount, false);
	std::list<LosNode *> nodesToDelete;
	std::list<LosNode *> fringe;
	int iterationCount = 0;

	LogInfo("Trying to route from lb %d to lb %d", origin, destination);

	if (origin == destination)
	{
		LogInfo("Origin is destination!");
		return {destination};
	}

	if (!blockAvailable[type][origin])
	{
		LogInfo("Origin unavailable!");
		return {};
	}

	if (!blockAvailable[type][destination])
	{
		LogInfo("Destination unavailable!");
		return {};
	}

	auto startNode =
	    new LosNode(0.0f,
	                BattleUnitTileHelper::getDistanceStatic(blockCenterPos[type][origin],
	                                                        blockCenterPos[type][destination]),
	                nullptr, origin);
	nodesToDelete.push_back(startNode);
	fringe.emplace_back(startNode);

	auto closestNodeSoFar = *fringe.begin();

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

		// Skip if we've already expanded this
		if (visitedBlocks[nodeToExpand->block])
		{
			iterationCount--;
			continue;
		}
		visitedBlocks[nodeToExpand->block] = true;