Suggestion for Pathfinder: set a limit on the number of paths per frame + temporarily restrict prepass until the open list algorithm itself is replaced during A*

[diqezit]

Let's say that if we have many units requesting a path at the same time, all paths are counted as one frame. Even if each path is short, 50 paths at a time cause lag. Before A*, a prepass (beam to the target) is launched. On long paths, this is expensive and useless, as the beam almost always hits a wall.

I suggest adding MAX_PATHFINDS_PER_FRAME = 3 and an additional condition to the processPathfindQueue() loop.

Then it turns out that unprocessed requests will remain in the queue and will be executed in the following frames. With a large cluster of units, some of them will start moving with a delay of several frames.

And PREPASS_MAX_MANHATTAN = 32

In theory it will only be called when the distance from the current cell to the target does not exceed the threshold.

---

Add new constants:

constexpr const Int MAX_PATHFINDS_PER_FRAME = 3;
constexpr const Int PREPASS_MAX_MANHATTAN = 32;
constexpr const Int GROUND_PATH_CELL_LIMIT = 2500;

---

File GameEngine/Source/GameLogic/AI/AIPathfind.cpp

---

Pathfinder::processPathfindQueue()

Add MAX_PATHFINDS_PER_FRAME condition to the loop. Unprocessed requests remain in the queue and will be executed in the following frames.

	m_cumulativeCellsAllocated = 0;
#ifdef DEBUG_QPF
	Int pathsFound = 0;
#endif

	Int pathsThisFrame = 0;

	while (m_cumulativeCellsAllocated < PATHFIND_CELLS_PER_FRAME &&
		m_queuePRTail!=m_queuePRHead &&
		pathsThisFrame < MAX_PATHFINDS_PER_FRAME) {

		Object *obj = TheGameLogic->findObjectByID(m_queuedPathfindRequests[m_queuePRHead]);
		m_queuedPathfindRequests[m_queuePRHead] = INVALID_ID;
		if (obj) {
			AIUpdateInterface *ai = obj->getAIUpdateInterface();
			if (ai) {
				ai->doPathfind(this);
				pathsThisFrame++;
#ifdef DEBUG_QPF
				pathsFound++;
#endif
			}
		}
		m_queuePRHead = m_queuePRHead+1;
		if (m_queuePRHead >= PATHFIND_QUEUE_LEN) {
			m_queuePRHead = 0;
		}
	}

processPathfindQueue() full click to open

void Pathfinder::processPathfindQueue()
{
	//USE_PERF_TIMER(processPathfindQueue)
	if (!m_isMapReady) {
		return;
	}
#ifdef DEBUG_QPF
#ifdef DEBUG_LOGGING
	Int startTimeMS = ::GetTickCount();
	__int64 startTime64;
	double timeToUpdate=0.0f;
	__int64 endTime64,freq64;
	QueryPerformanceFrequency((LARGE_INTEGER *)&freq64);
	QueryPerformanceCounter((LARGE_INTEGER *)&startTime64);
#endif
#endif

	if (m_zoneManager.needToCalculateZones()) {
		m_zoneManager.calculateZones(m_map, m_layers, m_extent);
		return;
	}

	// Get the current logical extent.
	Region3D terrainExtent;
	TheTerrainLogic->getExtent( &terrainExtent );
	IRegion2D bounds;
	bounds.lo.x = REAL_TO_INT_FLOOR(terrainExtent.lo.x / PATHFIND_CELL_SIZE_F);
	bounds.hi.x = REAL_TO_INT_FLOOR(terrainExtent.hi.x / PATHFIND_CELL_SIZE_F);
	bounds.lo.y = REAL_TO_INT_FLOOR(terrainExtent.lo.y / PATHFIND_CELL_SIZE_F);
	bounds.hi.y = REAL_TO_INT_FLOOR(terrainExtent.hi.y / PATHFIND_CELL_SIZE_F);
	bounds.hi.x--;
	bounds.hi.y--;
	m_logicalExtent = bounds;

	m_cumulativeCellsAllocated = 0;	// Number of pathfind cells examined.
#ifdef DEBUG_QPF
	Int pathsFound = 0;
#endif

	Int pathsThisFrame = 0;

	while (m_cumulativeCellsAllocated < PATHFIND_CELLS_PER_FRAME &&
		m_queuePRTail!=m_queuePRHead &&
		pathsThisFrame < MAX_PATHFINDS_PER_FRAME) {
		Object *obj = TheGameLogic->findObjectByID(m_queuedPathfindRequests[m_queuePRHead]);
		m_queuedPathfindRequests[m_queuePRHead] = INVALID_ID;
		if (obj) {
			AIUpdateInterface *ai = obj->getAIUpdateInterface();
			if (ai) {
				ai->doPathfind(this);
				pathsThisFrame++;
#ifdef DEBUG_QPF
				pathsFound++;
#endif
			}
		}
		m_queuePRHead = m_queuePRHead+1;
		if (m_queuePRHead >= PATHFIND_QUEUE_LEN) {
			m_queuePRHead = 0;
		}
	}
#ifdef DEBUG_QPF
	if (pathsFound>0) {
#ifdef DEBUG_LOGGING
		QueryPerformanceCounter((LARGE_INTEGER *)&endTime64);
		timeToUpdate = ((double)(endTime64-startTime64) / (double)(freq64));
		if (timeToUpdate>0.01f)
		{
			DEBUG_LOG(("%d Pathfind queue: %d paths, %d cells --", TheGameLogic->getFrame(), pathsFound, m_cumulativeCellsAllocated));
			DEBUG_LOG(("time %f (%f)", timeToUpdate, (::GetTickCount()-startTimeMS)/1000.0f));
		}
#endif
	}	
#endif
#if defined(RTS_DEBUG)
	doDebugIcons();
#endif

}

---

2. Pathfinder::examineNeighboringCells()

Add Manhattan distance check before prepass. Prepass will only be called when the distance from the current cell to the target does not exceed the threshold.

		if (attackDistance==NO_ATTACK && !m_isTunneling && !locomotorSet.isDownhillOnly() && goalCell) {
			ExamineCellsStruct info;
			info.thePathfinder = this;
			info.theLoco = &locomotorSet;
			info.centerInCell = centerInCell;
			info.radius = radius;
			info.obj = obj;
			info.isHuman = isHuman;
			info.goalCell = goalCell;
			ICoord2D start, end;
			start.x = parentCell->getXIndex();
			start.y = parentCell->getYIndex();
			end.x = goalCell->getXIndex();
			end.y = goalCell->getYIndex();

			Int manhattan = IABS(start.x - end.x) + IABS(start.y - end.y);
			if (manhattan <= PREPASS_MAX_MANHATTAN) {
				iterateCellsAlongLine(start, end, parentCell->getLayer(), examineCellsCallback, &info);
			}
		}

examineNeighboringCells() full click to open

Int Pathfinder::examineNeighboringCells(PathfindCell *parentCell, PathfindCell *goalCell, const LocomotorSet& locomotorSet,
																				 Bool isHuman, Bool centerInCell, Int radius, const ICoord2D &startCellNdx,
																				 const Object *obj, Int attackDistance)
{
		Bool canPathThroughUnits = false;
		if (obj && obj->getAIUpdateInterface()) {
			canPathThroughUnits = obj->getAIUpdateInterface()->canPathThroughUnits();
		}
		Bool isCrusher = obj ? obj->getCrusherLevel() > 0 : false;
		if (attackDistance==NO_ATTACK && !m_isTunneling && !locomotorSet.isDownhillOnly() && goalCell) {
			ExamineCellsStruct info;
			info.thePathfinder = this;
			info.theLoco = &locomotorSet;
			info.centerInCell = centerInCell;
			info.radius = radius;
			info.obj = obj;
			info.isHuman = isHuman;
			info.goalCell = goalCell;
			ICoord2D start, end;
			start.x = parentCell->getXIndex();
			start.y = parentCell->getYIndex();
			end.x = goalCell->getXIndex();
			end.y = goalCell->getYIndex();

			Int manhattan = IABS(start.x - end.x) + IABS(start.y - end.y);
			if (manhattan <= PREPASS_MAX_MANHATTAN) {
				iterateCellsAlongLine(start, end, parentCell->getLayer(), examineCellsCallback, &info);
			}
		}

		Int cellCount = 0;
		// expand search to neighboring orthogonal cells
		static ICoord2D delta[] =
		{
			{ 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 },
			{ 1, 1 }, { -1, 1 }, { -1, -1 }, { 1, -1 }
		};
		const Int numNeighbors = 8;
		const Int firstDiagonal = 4;
		ICoord2D newCellCoord;
		PathfindCell *newCell;
		const Int adjacent[5] = {0, 1, 2, 3, 0};
		Bool neighborFlags[8] = { 0 };

		UnsignedInt newCostSoFar = 0;

		for( int i=0; i<numNeighbors; i++ )
		{
			neighborFlags[i] = false;
			// determine neighbor cell to try
			newCellCoord.x = parentCell->getXIndex() + delta[i].x;
			newCellCoord.y = parentCell->getYIndex() + delta[i].y;

			// get the neighboring cell
			newCell = getCell(parentCell->getLayer(), newCellCoord.x, newCellCoord.y );

			// check if cell is on the map
			if (!newCell)
				continue;

			Bool notZonePassable = false;
			if ((newCell->getLayer()==LAYER_GROUND) && !m_zoneManager.isPassable(newCellCoord.x, newCellCoord.y)) {
				notZonePassable = true;
			}

			// check if new cell is in logical map.	(computer can move off logical map)
			if (isHuman && checkCellOutsideExtents(newCellCoord))
				continue;

			// check if this neighbor cell is already on the open (waiting to be tried)
			// or closed (already tried) lists
			if ( newCell->hasInfo() && (newCell->getOpen() || newCell->getClosed()) )
				continue;

			if (i>=firstDiagonal) {
				// make sure one of the adjacent sides is open.
				if (!neighborFlags[adjacent[i-4]] && !neighborFlags[adjacent[i-3]]) {
					continue;
				}
			}

			// do the gravity check here
			if ( locomotorSet.isDownhillOnly() )
			{
				Coord3D fromPos;
				fromPos.x = parentCell->getXIndex() * PATHFIND_CELL_SIZE_F ;
				fromPos.y = parentCell->getYIndex() * PATHFIND_CELL_SIZE_F ;
				fromPos.z = TheTerrainLogic->getGroundHeight(fromPos.x , fromPos.y);

				Coord3D toPos;
				toPos.x = newCellCoord.x * PATHFIND_CELL_SIZE_F ;
				toPos.y = newCellCoord.y * PATHFIND_CELL_SIZE_F ;
				toPos.z = TheTerrainLogic->getGroundHeight(toPos.x , toPos.y);

				if ( fromPos.z < toPos.z )
					continue;
			}

			Bool movementValid = validMovementPosition(isCrusher, locomotorSet.getValidSurfaces(), newCell, parentCell);
			Bool dozerHack = false;
			if (!movementValid && obj->isKindOf(KINDOF_DOZER) && newCell->getType() == PathfindCell::CELL_OBSTACLE) {
				Object* obstacle = TheGameLogic->findObjectByID(newCell->getObstacleID());
				if (obstacle && !(obj->getRelationship(obstacle) == ENEMIES)) {
					movementValid = true;
					dozerHack = true;
				}
			}

			if (!movementValid && !m_isTunneling) {
				continue;
			}

			if (!dozerHack)
				neighborFlags[i] = true;

			TCheckMovementInfo info;
			info.cell = newCellCoord;
			info.layer = parentCell->getLayer();
			info.centerInCell = centerInCell;
			info.radius = radius;
			info.considerTransient = false;
			info.acceptableSurfaces = locomotorSet.getValidSurfaces();
			Int dx = newCellCoord.x-startCellNdx.x;
			Int dy = newCellCoord.y-startCellNdx.y;
			if (dx<0) dx = -dx;
			if (dy<0) dy = -dy;
			if (dx>1+radius) info.considerTransient = false;
			if (dy>1+radius) info.considerTransient = false;
			if (!checkForMovement(obj, info) || info.enemyFixed) {
				if (!m_isTunneling) {
					continue;
				}
				movementValid = false;
			}

			if (movementValid && !newCell->getPinched()) {
				//Note to self - only turn off tunneling after check for movement.jba.
				m_isTunneling = false;
			}

			if (!newCell->hasInfo()) {
				if (!newCell->allocateInfo(newCellCoord)) {
					// Out of cells for pathing...
 					return cellCount;
				}
				cellCount++;
			}

			newCostSoFar = newCell->costSoFar( parentCell );
			if (info.allyMoving && dx<10 && dy<10) {
				newCostSoFar += 3*COST_DIAGONAL;
			}

			if (newCell->getType() == PathfindCell::CELL_CLIFF && !newCell->getPinched() ) {
				Coord3D fromPos;
				fromPos.x = parentCell->getXIndex() * PATHFIND_CELL_SIZE_F ;
				fromPos.y = parentCell->getYIndex() * PATHFIND_CELL_SIZE_F ;
				fromPos.z = TheTerrainLogic->getGroundHeight(fromPos.x , fromPos.y);

				Coord3D toPos;
				toPos.x = newCellCoord.x * PATHFIND_CELL_SIZE_F ;
				toPos.y = newCellCoord.y * PATHFIND_CELL_SIZE_F ;
				toPos.z = TheTerrainLogic->getGroundHeight(toPos.x , toPos.y);

				if ( fabs(fromPos.z - toPos.z)<PATHFIND_CELL_SIZE_F) {
					newCostSoFar += 7*COST_DIAGONAL;
				}
			} else if (newCell->getPinched()) {
				newCostSoFar += COST_ORTHOGONAL;
			}

			newCell->setBlockedByAlly(false);
			if (info.allyFixedCount>0) {
#if RTS_GENERALS && RETAIL_COMPATIBLE_PATHFINDING
				newCostSoFar += 3*COST_DIAGONAL*info.allyFixedCount;
#else
				newCostSoFar += 3*COST_DIAGONAL;
#endif
				if (!canPathThroughUnits)
					newCell->setBlockedByAlly(true);
			}

			Int costRemaining = 0;
			if (goalCell) {
				if (attackDistance == NO_ATTACK)  {
					costRemaining = newCell->costToGoal( goalCell );
				}	else {
					dx = newCellCoord.x - goalCell->getXIndex();
					dy = newCellCoord.y - goalCell->getYIndex();
					costRemaining = COST_ORTHOGONAL*sqrt(dx*dx + dy*dy);
					costRemaining -= attackDistance/2;
					if (costRemaining<0)
						costRemaining=0;
					if (info.allyGoal) {
						if (obj->isKindOf(KINDOF_VEHICLE)) {
							newCostSoFar += 3*COST_ORTHOGONAL;
						}	else {
							// Infantry can pass through infantry.
							newCostSoFar += COST_ORTHOGONAL;
						}
					}
				}
			}

			if (notZonePassable) {
				newCostSoFar += 100*COST_ORTHOGONAL;
			}

			if (newCell->getType()==PathfindCell::CELL_OBSTACLE) {
				newCostSoFar += 100*COST_ORTHOGONAL;
			}

			if (m_isTunneling) {
				if (!validMovementPosition( isCrusher, locomotorSet.getValidSurfaces(), newCell, parentCell )) {
					newCostSoFar += 10*COST_ORTHOGONAL;
				}
			}

			newCell->setCostSoFar(newCostSoFar);
			// keep track of path we're building - point back to cell we moved here from
			newCell->setParentCell(parentCell) ;
			if (m_isTunneling) {
				costRemaining = 0; // find the closest valid cell.
			}
			newCell->setTotalCost(newCell->getCostSoFar() + costRemaining) ;

			// if newCell was on closed list, remove it from the list
			if (newCell->getClosed())
				newCell->removeFromClosedList( m_closedList );

			// if the newCell was already on the open list, remove it so it can be re-inserted in order
			if (newCell->getOpen())
				newCell->removeFromOpenList( m_openList );

			// insert newCell in open list such that open list is sorted, smallest total path cost first
			newCell->putOnSortedOpenList( m_openList );
		}
	return cellCount;
}

---

3. Pathfinder::findGroundPath()

Two changes inside the main A* loop:

Cell limit placed after goalCell check so that a ready path is never discarded

		// take head cell off of open list - it has lowest estimated total path cost
		parentCell = m_openList.getHead();
		parentCell->removeFromOpenList(m_openList);

		if (parentCell == goalCell)
		{
			// success - found a path to the goal
			// ... (unchanged) ...
			return path;
		}

		// limin number of cells explored to prevent frame spikes
		if (cellCount >= GROUND_PATH_CELL_LIMIT) {
			parentCell->releaseInfo();
			break;
		}

		// put parent cell onto closed list - its evaluation is finished
		parentCell->putOnClosedList( m_closedList );

Manhattan check on prepass same logic as in examineNeighboringCells

		ICoord2D start, end;
		start.x = parentCell->getXIndex();
		start.y = parentCell->getYIndex();
		end.x = goalCell->getXIndex();
		end.y = goalCell->getYIndex();

		// Only run prepass when goal is nearby
		Int manhattan = IABS(start.x - end.x) + IABS(start.y - end.y);
		if (manhattan <= PREPASS_MAX_MANHATTAN) {
			iterateCellsAlongLine(start, end, parentCell->getLayer(), groundCellsCallback, &info);
		}

findGroundPath() full click to open

Path *Pathfinder::findGroundPath( const Coord3D *from,
													 const Coord3D *rawTo, Int pathDiameter, Bool crusher)
{
	//CRCDEBUG_LOG(("Pathfinder::findGroundPath()"));
#ifdef DEBUG_LOGGING
	Int startTimeMS = ::GetTickCount();
#endif
#ifdef INTENSE_DEBUG
	DEBUG_LOG(("Find ground path..."));
#endif
	Bool centerInCell = false;

	m_zoneManager.clearPassableFlags();
	Bool isHuman = true;

	Path *hPat = internal_findHierarchicalPath(isHuman, LOCOMOTORSURFACE_GROUND, from, rawTo, false, false);
	if (hPat) {
		deleteInstance(hPat);
	}	else {
		m_zoneManager.setAllPassable();
	}

	if (rawTo->x == 0.0f && rawTo->y == 0.0f) {
		DEBUG_LOG(("Attempting pathfind to 0,0, generally a bug."));
		return nullptr;
	}
	DEBUG_ASSERTCRASH(m_openList.empty() && m_closedList.empty(), ("Dangling lists."));
	if (m_isMapReady == false) {
		return nullptr;
	}

	Coord3D adjustTo = *rawTo;
	Coord3D *to = &adjustTo;
	Coord3D clipFrom = *from;
	clip(&clipFrom, &adjustTo);

	m_isTunneling = false;

	PathfindLayerEnum destinationLayer = TheTerrainLogic->getLayerForDestination(to);

	ICoord2D cell;
	worldToCell( to, &cell );

	if (pathDiameter!=clearCellForDiameter(crusher, cell.x, cell.y, destinationLayer, pathDiameter)) {
		Int offset=1;
		ICoord2D newCell;
		const Int MAX_OFFSET = 8;
		while (offset<MAX_OFFSET) {
			newCell = cell;
			cell.x += offset;
			if (clearCellForDiameter(crusher, cell.x, cell.y, destinationLayer, pathDiameter)==pathDiameter) break;
			cell.y += offset;
			if (clearCellForDiameter(crusher, cell.x, cell.y, destinationLayer, pathDiameter)==pathDiameter) break;
			cell.x -= offset;
			if (clearCellForDiameter(crusher, cell.x, cell.y, destinationLayer, pathDiameter)==pathDiameter) break;
			cell.x -= offset;
			if (clearCellForDiameter(crusher, cell.x, cell.y, destinationLayer, pathDiameter)==pathDiameter) break;
			cell.y -= offset;
			if (clearCellForDiameter(crusher, cell.x, cell.y, destinationLayer, pathDiameter)==pathDiameter) break;
			cell.y -= offset;
			if (clearCellForDiameter(crusher, cell.x, cell.y, destinationLayer, pathDiameter)==pathDiameter) break;
			cell.x += offset;
			if (clearCellForDiameter(crusher, cell.x, cell.y, destinationLayer, pathDiameter)==pathDiameter) break;
			cell.x += offset;
			if (clearCellForDiameter(crusher, cell.x, cell.y, destinationLayer, pathDiameter)==pathDiameter) break;
			offset++;
			cell = newCell;
		}
		if (offset >= MAX_OFFSET) {
			return nullptr;
		}
	}

	// determine goal cell
	PathfindCell *goalCell = getCell( destinationLayer, cell.x, cell.y );
	if (goalCell == nullptr) {
		return nullptr;
	}
	if (!goalCell->allocateInfo(cell)) {
		return nullptr;
	}

	// determine start cell
	ICoord2D startCellNdx;
	PathfindLayerEnum layer = TheTerrainLogic->getLayerForDestination(from);
	PathfindCell *parentCell = getClippedCell( layer,&clipFrom );
	if (parentCell == nullptr) {
#if RETAIL_COMPATIBLE_PATHFINDING
		if (s_useFixedPathfinding)
#endif
		{
			goalCell->releaseInfo();
		}
		return nullptr;
	}
	if (parentCell!=goalCell) {
		worldToCell(&clipFrom, &startCellNdx);
		if (!parentCell->allocateInfo(startCellNdx)) {
			goalCell->releaseInfo();
			return nullptr;
		}
	}


	Int zone1, zone2;
	// m_isCrusher = false;
	zone1 = m_zoneManager.getEffectiveZone(LOCOMOTORSURFACE_GROUND, false, parentCell->getZone());
	zone2 =  m_zoneManager.getEffectiveZone(LOCOMOTORSURFACE_GROUND, false, goalCell->getZone());

	//DEBUG_LOG(("Zones %d to %d", zone1, zone2));

	if ( zone1 != zone2) {
		goalCell->releaseInfo();
		parentCell->releaseInfo();
		return nullptr;
	}
	parentCell->startPathfind(goalCell);

	// initialize "open" list to contain start cell
#if RETAIL_COMPATIBLE_PATHFINDING
	if (!s_useFixedPathfinding) {
		m_openList.reset(parentCell);
	}
	else
#endif
	{
		m_openList.reset();
		parentCell->putOnSortedOpenList(m_openList);
	}

	// "closed" list is initially empty
	m_closedList.reset();

	// TheSuperHackers @fix helmutbuhler This was originally uninitialized and in the loop below.
#if RETAIL_COMPATIBLE_CRC
	UnsignedInt newCostSoFar = 0;
#endif

	//
	// Continue search until "open" list is empty, or
	// until goal is found.
	//
	Int cellCount = 0;
	while( !m_openList.empty() )
	{
		// take head cell off of open list - it has lowest estimated total path cost
		parentCell = m_openList.getHead();
		parentCell->removeFromOpenList(m_openList);

		if (parentCell == goalCell)
		{
			// success - found a path to the goal
#ifdef INTENSE_DEBUG
	DEBUG_LOG((" time %d msec %d cells", (::GetTickCount()-startTimeMS), cellCount));
	DEBUG_LOG((" SUCCESS"));
#endif
#if defined(RTS_DEBUG)
			Bool show = TheGlobalData->m_debugAI==AI_DEBUG_GROUND_PATHS;
			if (show)
				debugShowSearch(true);
#endif
			m_isTunneling = false;
			// construct and return path
			Path *path =  buildGroundPath(crusher, from, goalCell, centerInCell, pathDiameter );
#if RETAIL_COMPATIBLE_PATHFINDING
			if (!s_useFixedPathfinding)
			{
				parentCell->releaseInfo();
				cleanOpenAndClosedLists();
			}
			else
#endif
			{
				cleanOpenAndClosedLists();
				parentCell->releaseInfo();
			}
			return path;
		}

		if (cellCount >= GROUND_PATH_CELL_LIMIT) {
			parentCell->releaseInfo();
			break;
		}

		// put parent cell onto closed list - its evaluation is finished
		parentCell->putOnClosedList( m_closedList );

		// Check to see if we can change layers in this cell.
		checkChangeLayers(parentCell);

		GroundCellsStruct info;
		info.thePathfinder = this;
		info.centerInCell = centerInCell;
		info.pathDiameter = pathDiameter;
		info.goalCell = goalCell;
		info.crusher = crusher;
		ICoord2D start, end;
		start.x = parentCell->getXIndex();
		start.y = parentCell->getYIndex();
		end.x = goalCell->getXIndex();
		end.y = goalCell->getYIndex();

		Int manhattan = IABS(start.x - end.x) + IABS(start.y - end.y);
		if (manhattan <= PREPASS_MAX_MANHATTAN) {
			iterateCellsAlongLine(start, end, parentCell->getLayer(), groundCellsCallback, &info);
		}

		// expand search to neighboring orthogonal cells
		static ICoord2D delta[] =
		{
			{ 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 },
			{ 1, 1 }, { -1, 1 }, { -1, -1 }, { 1, -1 }
		};
		const Int numNeighbors = 8;
		const Int firstDiagonal = 4;
		ICoord2D newCellCoord;
		PathfindCell *newCell;
		const Int adjacent[5] = {0, 1, 2, 3, 0};
		Bool neighborFlags[8] = { 0 };

		// TheSuperHackers @fix Mauller 23/05/2025 Fixes uninitialized variable.
#if RETAIL_COMPATIBLE_CRC
		// newCostSoFar defined in outer block.
#else
		UnsignedInt newCostSoFar = 0;
#endif

		for( int i=0; i<numNeighbors; i++ )
		{
			neighborFlags[i] = false;
			// determine neighbor cell to try
			newCellCoord.x = parentCell->getXIndex() + delta[i].x;
			newCellCoord.y = parentCell->getYIndex() + delta[i].y;

			// get the neighboring cell
			newCell = getCell(parentCell->getLayer(), newCellCoord.x, newCellCoord.y );

			// check if cell is on the map
			if (newCell == nullptr)
				continue;

			if ((newCell->getLayer()==LAYER_GROUND) && !m_zoneManager.isPassable(newCellCoord.x, newCellCoord.y)) {
				// check if we are within 3.
				Bool passable = false;
				if (m_zoneManager.clipIsPassable(newCellCoord.x+3, newCellCoord.y+3)) passable = true;
				if (m_zoneManager.clipIsPassable(newCellCoord.x-3, newCellCoord.y+3)) passable = true;
				if (m_zoneManager.clipIsPassable(newCellCoord.x+3, newCellCoord.y-3)) passable = true;
				if (m_zoneManager.clipIsPassable(newCellCoord.x-3, newCellCoord.y-3)) passable = true;
				if (!passable) continue;
			}

			// check if this neighbor cell is already on the open (waiting to be tried)
			// or closed (already tried) lists
			Bool onList = false;
			if (newCell->hasInfo()) {
				if (newCell->getOpen() || newCell->getClosed())
				{
					// already on one of the lists
					onList = true;
				}
			}
			Int clearDiameter = 0;
			if (newCell!=goalCell) {

				if (i>=firstDiagonal) {
					// make sure one of the adjacent sides is open.
					if (!neighborFlags[adjacent[i-4]] && !neighborFlags[adjacent[i-3]]) {
						continue;
					}
				}

				// See how wide the cell is.
				clearDiameter = clearCellForDiameter(crusher, newCellCoord.x, newCellCoord.y, newCell->getLayer(), pathDiameter);
				if (newCell->getType() != PathfindCell::CELL_CLEAR) {
					continue;
				}
				if (newCell->getPinched()) {
					continue;
				}
				neighborFlags[i] = true;

				if (!newCell->allocateInfo(newCellCoord)) {
					// Out of cells for pathing...
 					continue;
				}
				cellCount++;

#if RETAIL_COMPATIBLE_CRC
				// TheSuperHackers @fix helmutbuhler 11/06/2025 The indentation was wrong on retail here.
				newCostSoFar = newCell->costSoFar( parentCell );
				if (clearDiameter<pathDiameter) {
					int delta = pathDiameter-clearDiameter;
					newCostSoFar += 0.6f*(delta*COST_ORTHOGONAL);
				}
				newCell->setBlockedByAlly(false);
			}
#else
			}
			newCostSoFar = newCell->costSoFar( parentCell );
			if (clearDiameter<pathDiameter) {
				int delta = pathDiameter-clearDiameter;
				newCostSoFar += 0.6f*(delta*COST_ORTHOGONAL);
			}
			newCell->setBlockedByAlly(false);
#endif
			Int costRemaining = 0;
			costRemaining = newCell->costToGoal( goalCell );

			// check if this neighbor cell is already on the open (waiting to be tried)
			// or closed (already tried) lists
			if (onList)
			{
				// already on one of the lists - if existing costSoFar is less,
				// the new cell is on a longer path, so skip it
				if (newCell->getCostSoFar() <= newCostSoFar)
					continue;
			}
			newCell->setCostSoFar(newCostSoFar);
			// keep track of path we're building - point back to cell we moved here from
			newCell->setParentCell(parentCell) ;
			newCell->setTotalCost(newCell->getCostSoFar() + costRemaining) ;

			// if newCell was on closed list, remove it from the list
			if (newCell->getClosed())
				newCell->removeFromClosedList( m_closedList );

			// if the newCell was already on the open list, remove it so it can be re-inserted in order
			if (newCell->getOpen())
				newCell->removeFromOpenList( m_openList );

			// insert newCell in open list such that open list is sorted, smallest total path cost first
			newCell->putOnSortedOpenList( m_openList );
		}
	}
	// failure - goal cannot be reached
#ifdef INTENSE_DEBUG
	DEBUG_LOG((" FAILURE"));
#endif
#if defined(RTS_DEBUG)
	if (TheGlobalData->m_debugAI)
	{
		extern void addIcon(const Coord3D *pos, Real width, Int numFramesDuration, RGBColor color);
 		RGBColor color;
		color.blue = 0;
		color.red = color.green = 1;
		addIcon(nullptr, 0, 0, color);
		debugShowSearch(false);
		Coord3D pos;
		pos = *from;
		pos.z = TheTerrainLogic->getGroundHeight( pos.x, pos.y ) + 0.5f;
		addIcon(&pos, 3*PATHFIND_CELL_SIZE_F, 600, color);
		pos = *to;
		pos.z = TheTerrainLogic->getGroundHeight( pos.x, pos.y ) + 0.5f;
		addIcon(&pos, 3*PATHFIND_CELL_SIZE_F, 600, color);
		Real dx, dy;
		dx = from->x - to->x;
		dy = from->y - to->y;

		Int count = sqrt(dx*dx+dy*dy)/(PATHFIND_CELL_SIZE_F/2);
		if (count<2) count = 2;
		Int i;
		color.green = 0;
		for (i=1; i<count; i++) {
			pos.x = from->x + (to->x-from->x)*i/count;
			pos.y = from->y + (to->y-from->y)*i/count;
			pos.z = TheTerrainLogic->getGroundHeight( pos.x, pos.y ) + 0.5f;
			addIcon(&pos, PATHFIND_CELL_SIZE_F/2, 60, color);

		}
	}
#endif

	DEBUG_LOG(("%d FindGroundPath failed from (%f,%f) to (%f,%f) --", TheGameLogic->getFrame(), from->x, from->y, to->x, to->y));
	DEBUG_LOG(("time %f", (::GetTickCount()-startTimeMS)/1000.0f));

#ifdef DUMP_PERF_STATS
	TheGameLogic->incrementOverallFailedPathfinds();
#endif
	m_isTunneling = false;
#if RETAIL_COMPATIBLE_PATHFINDING
	if (!s_useFixedPathfinding)
	{
		goalCell->releaseInfo();
		cleanOpenAndClosedLists();
	}
	else
#endif
	{
		cleanOpenAndClosedLists();
		parentCell->releaseInfo();
		goalCell->releaseInfo();
	}
	return nullptr;
}

---

MAX_PATHFINDS_PER_FRAME requests which is unprocess will be stay in queue and execute next frame. Units start moving with a delay of several frames at most.
PREPASS_MAX_MANHATTAN is only a hint for A*. Without it finds the same path and just explores more cells.
GROUND_PATH_CELL_LIMIT is always checked before the limit so a found path is never discarded. This cell that triggered break is cleaned up with releaseInfo()

[diqezit]

After profiling, I can confirm that in almost every heavy frame of the game, the sum of cells by internal + closest approaches 30,000, and at the same time, searches do not stop due to a logical condition, and they literally exhaust the entire pool of PathfindCellInfo records. A small change to reduce binary iterations helped for open/closed cells putOnSortedOpenList removeFromOpenList etc., but that's not the main reason.
MiniLog.txt

---

After testing, there were changes that made pathfinding safer in terms of frame time.
The point is to prevent the queue from burning through all the frame time at once during a massive repath. This is done in processPathfindQueue

examineNeighboringCells weakens the expensive prepass on distant targets. That is, before the usual A* neighbor walk, there is no longer such an aggressive long check along the line to the target where it only inflates the search cost.

findClosestPath is also limited... That is, if the exact path is not found, the fallback search for the nearest reachable point should not grow uncontrollably either. But in some cases, for example, on the well-known twilling flame, Ai itself will strive to go close to the ravine, since the duration of the full path will be very long for a complete scan of the track.

findGroundPath has received separate protection for wide paths. This is necessary because wide ground paths used to require very heavy calculations. The long-range prepass was also weakened to avoid a huge wide search.

As a result, the time delays have been significantly reduced, but they have not yet completely disappeared.

AIPathfind.cpp
(rename from txt to cpp)
in full with all corrections (if haven't forgotten anything else)

---

Before the profiling changes were made, the pathfinding function heavily relied on internalFindPath, which often took 250 to 675 ms per search and explored 9-15k cells, while the findClosestPath function added another 20-60 ms. In the same frames, the checkForMovement function alone could consume 100-300+ ms, with hundreds of thousands or even more than a million calls and millions of cell checks... Damn.

After the changes, internalFindPath now often stops at around 3000 cells with budgetBreaks=1

findClosestPath is also limited when necessary

frame rates are typically around 8-18 ms instead of hundreds of milliseconds. .

And checkForMovement has been reduced from hundreds of milliseconds to approximately 0.1-5 ms in selected frames
Visually now can see a slight improvement in responsiveness and global FPS by 4-5 points in some cases.
MiniLog.txt

---

Next, it is MANDATORY to close

#2430
#2425

Since by the time of the repeat request, the path had already been delivered and traversed.
From the point of view of dedup guard, this is a new legitimate request.
Guard protects against duplicates in the queue, not against repeat requests after receiving the result.

The same pair of coordinates, one object, 14 times in 85 frames.

f7662: obj=905 from=(4117,3195) to=(3835,1265) internal=cap closest=ok
f7682: obj=905 from=(4117,3194) to=(3835,1265) internal=cap closest=ok
f7698: obj=905 from=(4105,3197) to=(3835,1265) internal=cap closest=ok
f7709: obj=905 from=(4105,3197) to=(3835,1265) internal=cap closest=ok
f7716: obj=905 from=(4105,3197) to=(3835,1265) internal=cap closest=ok
f7721: obj=905 from=(4105,3197) to=(3835,1265) internal=cap closest=ok
f7724: obj=905 from=(4105,3197) to=(3835,1265) internal=cap closest=ok
f7727: obj=905 from=(4105,3197) to=(3835,1265) internal=cap closest=ok
f7731: obj=905 from=(4104,3197) to=(3835,1265) internal=cap closest=ok
f7734: obj=905 from=(4104,3197) to=(3835,1265) internal=cap closest=ok
f7737: obj=905 from=(4104,3196) to=(3835,1265) internal=cap closest=ok
f7741: obj=905 from=(4104,3196) to=(3835,1265) internal=cap closest=ok
f7744: obj=905 from=(4103,3196) to=(3835,1265) internal=cap closest=ok
f7747: obj=905 from=(4103,3196) to=(3835,1265) internal=cap closest=ok

[diqezit]

Additional changes related to #2430 and #2425 for related logic

So here is the add some logic in doPathfind() when after attack path failure

when if computeAttackPath() failed - could continue execution and reach for computePath(pathfinder, &m_requestedDestination)
always triggered an extra normal-path search (exact+fallback) which caused a heavy drawdown

AIUpdate.cpp part

/* Called by the pathfinder when it processes the pathfind queue.  Basically, it's our turn
to call use the PathfindServicesInterface to do a pathfind operation.  This shouldn't be called
(and in fact is very hard to do because PathfindServicesInterace is private to the pathfinder)
except by the pathfinder during pathfind queue processing.  jba */
//-------------------------------------------------------------------------------------------------
void AIUpdateInterface::doPathfind( PathfindServicesInterface *pathfinder )
{
	if (!m_waitingForPath) {
		return;
	}
	//CRCDEBUG_LOG(("AIUpdateInterface::doPathfind() for object %d", getObject()->getID()));
	m_waitingForPath = FALSE;
	if (m_isSafePath) {
		destroyPath();
		Coord3D pos1, pos2;
		pos1.set(-1000,-1000,0);
		Object *repulsor = TheGameLogic->findObjectByID(m_repulsor1);
		if (repulsor) {
			pos1 = *repulsor->getPosition();
		}
		pos2 = pos1;
		repulsor = TheGameLogic->findObjectByID(m_repulsor2);
		if (repulsor) {
			pos2 = *repulsor->getPosition();
		}
		m_path = pathfinder->findSafePath(getObject(), m_locomotorSet,
			getObject()->getPosition(),
			&pos1, 	&pos2,
			getObject()->getVisionRange() + TheAI->getAiData()->m_repulsedDistance);
		return;
	}
	if (m_isApproachPath && !isDoingGroundMovement()) {
		m_isApproachPath = false;
	}
	if (m_isApproachPath) {
		destroyPath();
		m_path = pathfinder->findClosestPath(getObject(), m_locomotorSet, getObject()->getPosition(),
			&m_requestedDestination, m_isBlockedAndStuck, 0.2f, FALSE );
		if (isDoingGroundMovement() && getPath()) {
			TheAI->pathfinder()->updateGoal(getObject(), getPath()->getLastNode()->getPosition(),
				getPath()->getLastNode()->getLayer());
		}
		return;
	}
	if (m_isAttackPath) {
		Object *victim = nullptr;
		if (m_requestedVictimID != INVALID_ID) {
			victim = TheGameLogic->findObjectByID(m_requestedVictimID);
		}
		if (computeAttackPath(pathfinder, victim, &m_requestedDestination))	{
			if (getPath()) {
				TheAI->pathfinder()->updateGoal(getObject(), getPath()->getLastNode()->getPosition(),
					getPath()->getLastNode()->getLayer());
			}
			//CRCDEBUG_LOG(("AIUpdateInterface::doPathfind() - m_isAttackPath = TRUE after computeAttackPath"));
			m_isAttackPath = TRUE;
			return;
		}
		//CRCDEBUG_LOG(("AIUpdateInterface::doPathfind() - m_isAttackPath = FALSE after computeAttackPath()"));
		m_isAttackPath = FALSE;
		if (victim) {
			m_requestedDestination = *victim->getPosition();
			/* find a pathable destination near the victim.*/
			TheAI->pathfinder()->adjustToPossibleDestination(getObject(), getLocomotorSet(), &m_requestedDestination);
			ignoreObstacle(victim);

			// Prevents expensive attack -> internalFindPath -> findClosestPath.
			destroyPath();
			m_path = pathfinder->findClosestPath(getObject(), m_locomotorSet, getObject()->getPosition(),
				&m_requestedDestination, m_isBlockedAndStuck, 0.2f, FALSE );
			if (isDoingGroundMovement() && getPath()) {
				TheAI->pathfinder()->updateGoal(getObject(), getPath()->getLastNode()->getPosition(),
					getPath()->getLastNode()->getLayer());
			}
			return;
		}
	}
	computePath(pathfinder, &m_requestedDestination);
	if (m_isFinalGoal && isDoingGroundMovement() && getPath()) {
		TheAI->pathfinder()->updateGoal(getObject(), getPath()->getLastNode()->getPosition(),
			getPath()->getLastNode()->getLayer());
	}
	if (m_queueForPathFrame > TheGameLogic->getFrame()) {
		m_waitingForPath = TRUE;
	}
#ifdef SLEEPY_AI
	// if we're no longer waiting for a path, make sure we wake up right away!
	if (!m_waitingForPath)
	{
		wakeUpNow();
	}
#endif
}

//-------------------------------------------------------------------------------------------------
// checks whether the given destination is effectively the same as the currently requested destination
// dedup guards to avoid requeueing pathfinding while already waiting
void AIUpdateInterface::SamePosCoordinate(Coord3D* destination, bool& retFlag) const
{
	retFlag = true;
	Real dx = m_requestedDestination.x - destination->x;
	Real dy = m_requestedDestination.y - destination->y;
	Real dz = m_requestedDestination.z - destination->z;
	Real distSqr = sqr(dx) + sqr(dy) + sqr(dz);
	if (distSqr <= 1.0f) return;
	retFlag = false;
}

/* Requests a path to be found.  Note that if it is possible to do it without having to use the
pathfinder (air units just move point to point) it generates the path immediately.  Otherwise the path
will be processed when we get to the front of the pathfind queue. jba */
//-------------------------------------------------------------------------------------------------
void AIUpdateInterface::requestPath( Coord3D *destination, Bool isFinalGoal )
{

	if (m_locomotorSet.getValidSurfaces() == 0) {
		DEBUG_CRASH(("Attempting to path immobile unit."));
	}

	// do not requeue - we are already waiting for the exact same safe path request!
	if (m_waitingForPath &&
		m_requestedVictimID == INVALID_ID &&
		!m_isAttackPath &&
		!m_isApproachPath &&
		!m_isSafePath &&
		m_isFinalGoal == isFinalGoal)
	{

		bool retFlag;
		SamePosCoordinate(destination, retFlag);
		if (retFlag) return;
	}

	//DEBUG_LOG(("Request Frame %d, obj %s %x", TheGameLogic->getFrame(), getObject()->getTemplate()->getName().str(), getObject()));
	m_requestedDestination = *destination;
	m_isFinalGoal = isFinalGoal;
	CRCDEBUG_LOG(("AIUpdateInterface::requestPath() - m_isAttackPath = FALSE for object %d", getObject()->getID()));
	m_isAttackPath = FALSE;
	m_requestedVictimID = INVALID_ID;
	m_isApproachPath = FALSE;
	m_isSafePath = FALSE;
	if (canComputeQuickPath()) {
		computeQuickPath(destination);
		return;
	}
	m_waitingForPath = TRUE;
	if (m_pathTimestamp > TheGameLogic->getFrame()-3) {
		/* Requesting path very quickly.  Can cause a spin. */
		//DEBUG_LOG(("%d Pathfind - repathing in less than 3 frames.  Waiting 1 second",
			//TheGameLogic->getFrame()));
		setQueueForPathTime(LOGICFRAMES_PER_SECOND);
		// See if it has been too soon.
		// jba intense debug
		//DEBUG_LOG(("Info - RePathing very quickly %d, %d.", m_pathTimestamp, TheGameLogic->getFrame()));
		if (m_path && m_isBlockedAndStuck) {
			setIgnoreCollisionTime(2*LOGICFRAMES_PER_SECOND);
			m_blockedFrames = 0;
			m_isBlocked = FALSE;
			m_isBlockedAndStuck = FALSE;
		}
		return;
	}
	TheAI->pathfinder()->queueForPath(getObject()->getID());

}

//-------------------------------------------------------------------------------------------------
void AIUpdateInterface::requestAttackPath( ObjectID victimID, const Coord3D* victimPos )
{
	if (m_locomotorSet.getValidSurfaces() == 0) {
		DEBUG_CRASH(("Attempting to path immobile unit."));
	}

	// do not requeue - we are already waiting for the exact same attack path request!
	if (m_waitingForPath &&
		m_isAttackPath &&
		!m_isApproachPath &&
		!m_isSafePath &&
		m_requestedVictimID == victimID &&
		victimPos != nullptr)
	{
		Real dx = m_requestedDestination.x - victimPos->x;
		Real dy = m_requestedDestination.y - victimPos->y;
		Real dz = m_requestedDestination.z - victimPos->z;
		Real distSqr = sqr(dx) + sqr(dy) + sqr(dz);
		if (distSqr <= 1.0f) return;
	}

	CRCDEBUG_LOG(("AIUpdateInterface::requestAttackPath() - m_isAttackPath = TRUE for object %d", getObject()->getID()));
	m_requestedDestination = *victimPos;
	m_requestedVictimID = victimID;
	m_isAttackPath = TRUE;
	m_isApproachPath = FALSE;
	m_isSafePath = FALSE;
	m_waitingForPath = TRUE;
	if (m_pathTimestamp > TheGameLogic->getFrame()-3) {
		/* Requesting path very quickly.  Can cause a spin. */
		//DEBUG_LOG(("%d Pathfind - repathing in less than 3 frames.  Waiting 2 second",TheGameLogic->getFrame()));
		setQueueForPathTime(2*LOGICFRAMES_PER_SECOND);
		setLocomotorGoalNone();
		return;
	}
	TheAI->pathfinder()->queueForPath(getObject()->getID());
}

//-------------------------------------------------------------------------------------------------
void AIUpdateInterface::requestApproachPath( Coord3D *destination )
{
	if (m_locomotorSet.getValidSurfaces() == 0) {
		DEBUG_CRASH(("Attempting to path immobile unit."));
	}

	// do not requeue - we are already waiting for the exact same safe path request!
	if (m_waitingForPath &&
		!m_isAttackPath &&
		m_isApproachPath &&
		!m_isSafePath)
	{
		bool retFlag;
		SamePosCoordinate(destination, retFlag);
		if (retFlag) return;
	}

	m_requestedDestination = *destination;
	m_isFinalGoal = TRUE;
	CRCDEBUG_LOG(("AIUpdateInterface::requestApproachPath() - m_isAttackPath = FALSE for object %d", getObject()->getID()));
	m_isAttackPath = FALSE;
	m_requestedVictimID = INVALID_ID;
	m_isApproachPath = TRUE;
	m_isSafePath = FALSE;
	m_waitingForPath = TRUE;
	if (m_pathTimestamp > TheGameLogic->getFrame()-3) {
		/* Requesting path very quickly.  Can cause a spin. */
		//DEBUG_LOG(("%d Pathfind - repathing in less than 3 frames.  Waiting 2 second",TheGameLogic->getFrame()));
		setQueueForPathTime(2*LOGICFRAMES_PER_SECOND);
		return;
	}
	TheAI->pathfinder()->queueForPath(getObject()->getID());
}

//-------------------------------------------------------------------------------------------------
// Requests a safe path away from the repulsor.
void AIUpdateInterface::requestSafePath( ObjectID repulsor )
{
	// do not requeue - we are already waiting for the exact same safe path request!
	if (m_waitingForPath &&
		!m_isAttackPath &&
		!m_isApproachPath &&
		m_isSafePath &&
		m_repulsor1 == repulsor)
	{
		return;
	}

	if (repulsor != m_repulsor1) {
		m_repulsor2 = m_repulsor1; // save the prior repulsor.
	}
	m_repulsor1 = repulsor;
	m_isFinalGoal = FALSE;
	CRCDEBUG_LOG(("AIUpdateInterface::requestSafePath() - m_isAttackPath = FALSE for object %d", getObject()->getID()));
	m_isAttackPath = FALSE;
	m_requestedVictimID = INVALID_ID;
	m_isApproachPath = FALSE;
	m_isSafePath = TRUE;
	m_waitingForPath = TRUE;
	if (m_pathTimestamp > TheGameLogic->getFrame()-3) {
		/* Requesting path very quickly.  Can cause a spin. */
		//DEBUG_LOG(("%d Pathfind - repathing in less than 3 frames.  Waiting 2 second",TheGameLogic->getFrame()));
		setQueueForPathTime(2*LOGICFRAMES_PER_SECOND);
		return;
	}
	TheAI->pathfinder()->queueForPath(getObject()->getID());
}

---

UPDATE.

Additionally, I can take further measurements - in the computePointOnPath function, there are frame-by-frame delays within 4-5 ms for each frame, which is not so noticeable; it can be reduced to a threshold of less than 0.5 ms per frame - for this, I made such decisions as
adding two fields to the Path header class itself and then simply reusing them in this function

That is, I added the following to the path class

Click me to show more

UnsignedInt m_cpopEvalFrame;
ICoord2D m_cpopEvalCell;

then initializing this data in the constructor

Path::Path():
m_path(nullptr),
m_pathTail(nullptr),
m_isOptimized(FALSE),
m_blockedByAlly(FALSE),
m_cpopRecentStart(nullptr),
m_cpopCountdown(MAX_CPOP),
m_cpopValid(FALSE),
m_cpopEvalFrame(0xFFFFFFFF)
{
    m_cpopIn.zero();
	m_cpopOut.distAlongPath=0;
    m_cpopOut.layer = LAYER_GROUND;
    m_cpopOut.posOnPath.zero();
    m_cpopEvalCell.x = -999999;
    m_cpopEvalCell.y = -999999;
}

Next, I made some changes to the computePointOnPath function
After checking for null, add a comparison and exit if we are in the current cell.

	if (m_path == nullptr)
	{
		m_cpopValid = false;
		return;
	}
	out.layer = m_path->getLayer();

	ICoord2D curCell = {
			REAL_TO_INT_FLOOR(pos.x / PATHFIND_CELL_SIZE_F),
			REAL_TO_INT_FLOOR(pos.y / PATHFIND_CELL_SIZE_F)
	};
	UnsignedInt curFrame = TheGameLogic ? TheGameLogic->getFrame() : 0;

	if (m_cpopValid
		&& curCell.x == m_cpopEvalCell.x
		&& curCell.y == m_cpopEvalCell.y
		&& (curFrame == m_cpopEvalFrame || curFrame == m_cpopEvalFrame + 1))
	{
		Coord2D delta = { pos.x - m_cpopIn.x, pos.y - m_cpopIn.y };

		if (delta.lengthSqr() <= sqr(PATHFIND_CELL_SIZE_F * 0.20f))
		{
			out = m_cpopOut;
			return;
		}
	}

Further on, be sure to call at the very end of the function

    m_cpopIn = pos;
    m_cpopOut = out;
    m_cpopValid = true;
    m_cpopEvalFrame = curFrame;
    m_cpopEvalCell = curCell;
    CRCDEBUG_LOG((“Path::computePointOnPath() end”));

So, in the end, it turned out to be less than 0.5 ms, somewhere closer to 0.1-0.2 ms.
Roughly speaking, without it, it gives the same path calculations for the same result, just a little more expensive.

Additionally, add a check with break after
cellCount += examineNeighboringCells(``` in the getMoveAwayFromPath`
function:

if (cellCount >= CELL_LIMIT) break;

Here's what ended up with

PFProf.txt

---

So, what do I have after all this.

In adjustDestination, the cost does not depend on a single expensive path search; it already depends on sending cells via checkForAdjust during batch frames.
Most of the time is spent on tightenPath and repeated quick path checks.
It's like forming mass orders for movement, changing the start of a firefight, etc.

Quick-path checks are like availability tests based on clientSafeQuickDoesPathExist(), but they don't build a complete path.
They only answer whether it is worth trying the starting point or the adjusted one.
One call is cheap, but there are many repeated calls in one frame.

That is, if you reduce the number of neighboring cells being checked
since almost every cell falls into checkForAdjust
inside checkForAdjust, they are called again and again... So either don't call directly for each one for the same path check and don't count each path again and on't use the expensive branch but use the expensive one only for very long distances.
That is, either add some kind of cheap filter can't say for sure...

---

UPD 2

here some small edits in adjustDestination

Click me to show more

Bool Pathfinder::adjustDestination(Object *obj, const LocomotorSet& locomotorSet, Coord3D *dest, const Coord3D *groupDest)
{
	if( obj->isKindOf(KINDOF_PROJECTILE) )
	{
		return true; // missiles can go wherever they want to. jba.
	}

	Bool isHuman = true;
	if (obj && obj->getControllingPlayer() && (obj->getControllingPlayer()->getPlayerType()==PLAYER_COMPUTER)) {
		isHuman = false; // computer gets to cheat.
	}
	Int iRadius;
	Bool center;
	getRadiusAndCenter(obj, iRadius, center);
	ICoord2D cell;
	Coord3D adjustDest = *dest;
	if (!center) {
		adjustDest.x += PATHFIND_CELL_SIZE_F/2;
		adjustDest.y += PATHFIND_CELL_SIZE_F/2;
	}
	worldToCell( &adjustDest, &cell );
	PathfindLayerEnum layer = TheTerrainLogic->getLayerForDestination(dest);
	if (groupDest) {
		layer = TheTerrainLogic->getLayerForDestination(groupDest);
	}

	Int limit = MAX_ADJUSTMENT_CELL_COUNT;

	const Int SOLO_LIMIT = 128;
	const Int GROUP_LIMIT = 150;
	const Int maxLimit = (groupDest != nullptr) ? GROUP_LIMIT : SOLO_LIMIT;

	if (limit > maxLimit) {
		limit = maxLimit;
	}

	Int i, j;
	i = cell.x;
	j = cell.y;
	if (checkForAdjust(obj, locomotorSet, isHuman, i,j, layer, iRadius, center, dest, groupDest)) {
		return true;
	}

	Int delta=1;
	Int count;
	while (limit>0) {
		for (count = delta; count>0; count--) {
			i++;
			limit--;
			if (checkForAdjust(obj, locomotorSet, isHuman, i,j, layer, iRadius, center, dest, groupDest)) {
				return true;
			}
			if (limit <= 0) {
				break;
			}
		}
		if (limit <= 0) {
			break;
		}
		for (count = delta; count>0; count--) {
			j++;
			limit--;
			if (checkForAdjust(obj, locomotorSet, isHuman, i,j, layer, iRadius, center, dest, groupDest)) {
				return true;
			}
			if (limit <= 0) {
				break;
			}
		}
		if (limit <= 0) {
			break;
		}
		delta++;
		for (count = delta; count>0; count--) {
			i--;
			limit--;
			if (checkForAdjust(obj, locomotorSet, isHuman, i,j, layer, iRadius, center, dest, groupDest)) {
				return true;
			}
			if (limit <= 0) {
				break;
			}
		}
		if (limit <= 0) {
			break;
		}
		for (count = delta; count>0; count--) {
			j--;
			limit--;
			if (checkForAdjust(obj, locomotorSet, isHuman, i,j, layer, iRadius, center, dest, groupDest)) {
				return true;
			}
			if (limit <= 0) {
				break;
			}
		}
		delta++;
	}
	if (groupDest) {
		// Didn't work, so just do simple adjust.
		return(adjustDestination(obj, locomotorSet, dest, nullptr));
	}
	return false;
}

adjustDestination now dropped from roughly 42 ms burst to about 2-5 ms

Then made some changes here to limit the number of requests for medium distances (and short distances too). As a result, the number of requests decreased from 2,500 to 200-300, and the average delay decreased slightly from 2.68 ms to 0.41 ms.

checkForAdjust click to show

Bool Pathfinder::checkForAdjust(Object *obj, const LocomotorSet& locomotorSet, Bool isHuman,
																Int cellX, Int cellY, PathfindLayerEnum layer,
																Int iRadius, Bool center, Coord3D *dest, const Coord3D *groupDest)
{
	Coord3D adjustDest;
	PathfindCell *cellP = getCell(layer, cellX, cellY);
	if (cellP==nullptr) return false;
	if (cellP && cellP->getType() == PathfindCell::CELL_CLIFF) {
		return false;  // no final destinations on cliffs.
	}
	if (isHuman) {
		// check if new cell is in logical map.	(computer can move off logical map)
		if (cellX < m_logicalExtent.lo.x ||
				cellY < m_logicalExtent.lo.y ||
				cellX > m_logicalExtent.hi.x ||
				cellY > m_logicalExtent.hi.y) return false;
	}
	if (checkDestination(obj, cellX, cellY, layer, iRadius, center)) {
		adjustCoordToCell(cellX, cellY,  center, adjustDest, cellP->getLayer());
		Bool pathExists;
		Bool adjustedPathExists;
		if (obj->isKindOf(KINDOF_AIRCRAFT)) {
			pathExists = true;
			adjustedPathExists = true;
		}	else {
			pathExists = clientSafeQuickDoesPathExist( locomotorSet, obj->getPosition(), dest);
			adjustedPathExists = clientSafeQuickDoesPathExist( locomotorSet, obj->getPosition(), &adjustDest);
			if (!pathExists) {
				if (clientSafeQuickDoesPathExist( locomotorSet, dest, &adjustDest))	{
 					adjustedPathExists = true;
				}
			}
		}
		if ( adjustedPathExists	) {
			if (groupDest) {
				tightenPath(obj, locomotorSet, &adjustDest, groupDest);

				Real dx = (Real)fabs(groupDest->x - adjustDest.x);
				Real dy = (Real)fabs(groupDest->y - adjustDest.y);

				// diqezot 
				// avoid expensive A for close and medium-distance
				if (dx + dy <= 8.0f * PATHFIND_CELL_SIZE_F) {
					*dest = adjustDest;
					return true;
				}

				// Check to see if it is a long way to get to the adjusted destination.
				Int cost = checkPathCost(obj, locomotorSet, groupDest, &adjustDest);
				if (1.4f*(dx+dy)<cost) {
					return false;
				}
			}
			*dest = adjustDest;
			return true;
		}
	}
	return false;
}

PFProf.txt

---

UPD 3

The attack state machine (AIAttackApproachTargetState) holds the movement target and always requests a path directly to the victim. When A* with a budget of 3000 cannot find a way around a long barrier, it returns a partial path to the wall. The unit moves toward the wall. The state re-queries, and this triggers a loop.
If we consider the problem after the exceptions.

Following my changes to the ISSUE description, I can assume that AIAttackApproachTargetState::computePath() needs to be fixed at the point where the attack state decides WHERE to go.

https://ibb.co/vvmxTHNw

Units do not switch to attack and movement waypoints at a distance, and they remain stuck in an idle/attack state

---

So, my final changes led to a modification of this function

checkForAdjust click to show Pathfinder::findPath

/**
 * Find a short, valid path between given locations.
 * Uses A* algorithm.
 */
Path *Pathfinder::findPath( Object *obj, const LocomotorSet& locomotorSet, const Coord3D *from,
													 const Coord3D *rawTo)
{
	if (!clientSafeQuickDoesPathExist(locomotorSet, from, rawTo)) {
		return nullptr;
	}
	Bool isHuman = true;
	if (obj && obj->getControllingPlayer() && (obj->getControllingPlayer()->getPlayerType()==PLAYER_COMPUTER)) {
		isHuman = false; // computer gets to cheat.
	}

	m_zoneManager.clearPassableFlags();
	Path *hPat = findHierarchicalPath(isHuman, locomotorSet, from, rawTo, false);
	if (hPat) {
		deleteInstance(hPat);
	}	else {
		m_zoneManager.setAllPassable();
	}

	Path *pat = internalFindPath(obj, locomotorSet, from, rawTo);
	if (pat!=nullptr) {
		return pat;
	}

	// reroute toward nearest labeled waypoint when A* cannot reach the goal
	// removes zone penalties so A* can explore detour routes freely
	m_zoneManager.setAllPassable();

	Waypoint *bestWp = nullptr;
	Real bestDist = 1e30f;

	for (Waypoint *wp = TheTerrainLogic->getFirstWaypoint(); wp; wp = wp->getNext())
	{
		if (wp->getPathLabel1().isEmpty()
			&& wp->getPathLabel2().isEmpty()
			&& wp->getPathLabel3().isEmpty())
			continue;

		Coord2D delta;
		delta.x = wp->getLocation()->x - from->x;
		delta.y = wp->getLocation()->y - from->y;
		Real dist = delta.length();

		if (dist > 3.0f * PATHFIND_CELL_SIZE_F && dist < bestDist)
		{
			bestDist = dist;
			bestWp = wp;
		}
	}

	if (bestWp)
	{
		Coord3D wpPos = *bestWp->getLocation();
		wpPos.z = TheTerrainLogic->getGroundHeight(wpPos.x, wpPos.y);

		pat = internalFindPath(obj, locomotorSet, from, &wpPos);
		if (!pat)
			pat = findClosestPath(obj, locomotorSet, from, &wpPos, false, 0.0f, false);
	}

	return pat;
}

When attacking, units would run into impassable terrain and stand there indefinitely instead of looking for a detour. This is because the internal zone system applies a ×100 penalty to all cells outside the direct route, and the search algorithm exhausts its entire budget along the wall without reaching the detour.
Since marked waypoints for attack routes (BackDoor, Flank, Center) have already been set.
If a direct path isn’t found, we simply remove all zone penalties and plot a path to the nearest such waypoint.
Those same stuck units start moving across passable terrain instead of getting stuck by the wall.
Instead of nullptr now we return an A* path to the nearest marked waypoint with penalties removed

If there were no marked waypoints on the map, then in theory bestWp remains nullptr, and the block is skipped; findPath returns nullptr as before.
And computePath falls back to findClosestPath to the destination, as before.

But this needs to be tested in longer gameplay sessions.
On the other hand, in some cases this edit in Pathfinder::findPath (for thiss issue story) disrupts the navigation behavior; units will head toward the nearest waypoint destination rather than the optimal one. hope this is helpful to someone

---

[Mauller]

Hi there bud, thanks for taking a look over this too.

At the moment i have a change in the works that more than doubles the performance of the pathfinder without changing the overall functionality of it. In some cases it also triples the performance.

Exaustion of pathfind cells is also a known issue and is the reason why units cannot traverse the ravine in Twilight Flame as the pathfinder simply runs out of resources before it can find a way across.
I also have another change in the pipeline that removes dynamic allocation of pathfinding information within the pathfinder, it resolves this issue and other pathfind issues due to resource exaustion on large maps.

We are currently maintaining retail compatibility so cannot easily make significant changes without gating them, but it is worthshile investigating some of your recommendations further to see how they affect the game.

Limiting pathfind calls per frame is a good one to consider to help balance the load and reduce stalls in the engine. But we still need to be careful as what to set as the limit as there will be a balance between pathfinder queue size and how many things can pathfind per frame.