Method findShortestPath

game/state/tilemap/pathfinding.cpp:133–412

} // anonymous namespace

std::list<Vec3<int>> TileMap::findShortestPath(Vec3<int> origin, Vec3<int> destinationStart,
                                               Vec3<int> destinationEnd, int iterationLimit,
                                               const CanEnterTileHelper &canEnterTileHelper,
                                               bool approachOnly, bool ignoreStaticUnits,
                                               bool ignoreMovingUnits, bool ignoreAllUnits,
                                               float *cost, float maxCost)
{
#ifdef PATHFINDING_DEBUG
	for (auto &t : tiles)
		t.pathfindingDebugFlag = false;
#endif

	maxCost /= canEnterTileHelper.pathOverheadAlloawnce();
	// Faster than looking up in a set
	std::vector<bool> visitedTiles = std::vector<bool>(size.x * size.y * size.z, false);
	int strideZ = size.x * size.y;
	int strideY = size.x;
	std::list<PathNode *> nodesToDelete;
	std::list<PathNode *> fringe;
	Vec3<float> goalPositionStart;
	Vec3<float> goalPositionEnd;
	bool destinationIsSingleTile = destinationStart == destinationEnd - Vec3<int>{1, 1, 1};
	int iterationCount = 0;

	// Approach Only makes no sense with pathing into a block, but we'll fix it anyway
	if (approachOnly && !destinationIsSingleTile)
	{
		LogWarning("Trying to route from %s to %s-%s in approachOnly mode? Extending destination's "
		           "xy boundaries by 1.",
		           origin, destinationStart, destinationEnd);
		approachOnly = false;
		destinationStart -=
		    Vec3<int>(destinationStart.x > 0 ? 1 : 0, destinationStart.y > 0 ? 1 : 0, 0);
		destinationEnd +=
		    Vec3<int>(destinationEnd.x < size.x ? 1 : 0, destinationEnd.y < size.y ? 1 : 0, 0);
	}

	if (destinationIsSingleTile)
	{
		LogInfo("Trying to route from %s to %s", origin, destinationStart);
	}
	else
	{
		LogInfo("Trying to route from %s to %s-%s", origin, destinationStart, destinationEnd);
	}

	if (!tileIsValid(origin))
	{
		LogError("Bad origin %s", origin);
		return {};
	}
	if (!tileIsValid(destinationStart))
	{
		LogError("Bad destinationStart %s", destinationStart);
		return {};
	}
	if (destinationEnd.x <= destinationStart.x || destinationEnd.x > this->size.x ||
	    destinationEnd.y <= destinationStart.y || destinationEnd.y > this->size.y ||