Method findShortestPathUsingLB

game/state/tilemap/pathfinding.cpp:598–710

}

std::list<Vec3<int>> Battle::findShortestPathUsingLB(Vec3<int> origin, Vec3<int> destination,
                                                     const BattleUnitTileHelper &canEnterTile,
                                                     bool approachOnly, bool ignoreStaticUnits,
                                                     bool ignoreMovingUnits, bool ignoreAllUnits,
                                                     float *cost, float maxCost)
{
	// How much attempts are given to the pathfinding until giving up and concluding that
	// there is no simple path between orig and dest. This is a multiplier for "distance", which is
	// a minimum number of iterations required to pathfind between two locations
	static const int PATH_ITERATION_LIMIT_MULTIPLIER = 2;

	// Same as PATH_ITERATION_LIMIT_MULTIPLIER but for when navigating to next los block
	static const int GRAPH_ITERATION_LIMIT_MULTIPLIER = 2;

	// Extra iterations allowed when pathing to a los block, because if we need
	// to find a door we can have a hard time doing so
	static const int GRAPH_ITERATION_LIMIT_EXTRA = 50;

	int distance = canEnterTile.getDistance(origin, destination) / 4.0f;
	std::list<Vec3<int>> result;

	// Pathfind on graphs of los blocks
	int startLB = getLosBlockID(origin.x, origin.y, origin.z);
	int destLB = getLosBlockID(destination.x, destination.y, destination.z);
	auto pathLB = findLosBlockPath(startLB, destLB, canEnterTile.getType());

	// If pathfinding on graphs failed - return short part of the path towards target
	if ((*pathLB.rbegin()) != destLB)
	{
		if (!result.empty())
		{
			return result;
		}
		else
		{
			return map->findShortestPath(
			    origin, destination, distance * PATH_ITERATION_LIMIT_MULTIPLIER, canEnterTile,
			    approachOnly, ignoreStaticUnits, ignoreMovingUnits, ignoreAllUnits, cost, maxCost);
		}
	}

	// Step 01: Pathfind using path among blocks

	result.clear();
	result.push_back(origin);
	if (cost)
	{
		*cost = 0.0f;
	}
	float curMaxCost = maxCost;
	while (!pathLB.empty())
	{
		auto curOrigin = *result.rbegin();
		float curCost = 0.0f;
		auto lbID = pathLB.front();
		pathLB.pop_front();
		auto &lb = *losBlocks[lbID];
		auto distToNext = canEnterTile.getDistance(curOrigin, (lb.start + lb.end) / 2) / 4.0f;