Function SearchLOT_DijkstraAStar

TombEngine/Game/control/box.cpp:1891–2036

* @brief Cost-based path search (Dijkstra / A*) for pathfinding through boxes. * * This function expands the search using a priority queue ordered by accumulated * path cost. It builds a "flow field" where each box's exitBox points toward the * target, preferring lower-cost paths. When A* is selected, a heuristic is added * to guide the search toward the creature's source box. * * ALGORITHM

 * @return true if more boxes remain to expand, false if search exhausted.
 */
bool SearchLOT_DijkstraAStar(LOTInfo* LOT, int depth, PathfindingMode mode)
{
	PathQueue queue = {};
	auto& zone = g_Level.Zones[(int)LOT->Zone][(int)FlipStatus];

	// Determine whether A* heuristic should be applied.
	bool useHeuristic = (mode == PathfindingMode::AStar && LOT->SourceBox != NO_VALUE);

	// A* heuristic target (creature's source box center).
	auto sourceCenter = useHeuristic ? GetBoxCenter(LOT->SourceBox) : Vector3::Zero;

	// Move legacy Head/Tail expansion list into priority queue.
	int currentBox = LOT->Head;
	while (currentBox != NO_VALUE)
	{
		auto* node = &LOT->Node[currentBox];

		int next = node->nextExpansion;
		node->nextExpansion = NO_VALUE;

		float pathCost = node->cost;
		float heuristicCost = useHeuristic ? Vector3::Distance(GetBoxCenter(currentBox), sourceCenter) : 0.0f;

		queue.push({ pathCost + heuristicCost, pathCost, currentBox });

		currentBox = next;
	}

	// Reset legacy queue; it will be rebuilt from remaining PQ entries.
	LOT->Head = NO_VALUE;
	LOT->Tail = NO_VALUE;

	int expansions = 0;

	// Main Dijkstra / A* expansion loop.
	while (expansions < depth && !queue.empty())
	{
		auto [currentEstimatedCost, currentPathCost, headBox] = queue.top();
		queue.pop();

		auto* box = &g_Level.PathfindingBoxes[headBox];
		auto* node = &LOT->Node[headBox];

		// Skip stale queue entries superseded by a cheaper path.
		if (currentPathCost > node->cost)
			continue;

		expansions++;

		int index = box->overlapIndex;
		int searchZone = zone[headBox];

		auto currentCenter = GetBoxCenter(headBox);
		bool done = false;

		// Iterate through all overlapping neighbor boxes.
		if (index >= 0)
		{