Custom Pathfinding Gets Stuck

[Sashilove123 (Bizzy)]

You can write your topic however you want, but you need to answer these questions:
Goal - stop my pathfinding NPC from getting stuck when it is forced to explore paths that make it temporarily go further away from its target.

2. What is the issue? Include screenshots / videos if possible!
   Below is a screenshot of the grid setup that I have for pathfinding and item placement in my game:
   
   

When the NPC is given a path with obstructions that do not require much moving from the desired path, like below, then the NPC does very well.

However, when there is more of a U shape blockade for the NPC, as seen below, the code freezes the game because it loops so many times trying to find a path but doesn’t.

I think the issue has something to do with the NPC not being willing to explore paths that initially take it away from its target. Keep in mind in all these screenshots the target is in the top left corner of the grid.

3. What solutions have you tried so far? Did you look for solutions on the Developer Hub?

So far, I have attempted numerous adjustments to the weighting of the heuristic values (I am using the a* algo). I have implemented a revisit penalty so the algo is disinsentived to return to already explored squares, thus making it harder for it to get stuck, but that doesn’t seem to work either.

Below is the main function that handles the pathfinding

--both goal and start are 3 element tables, containing the plotnumber, 2d row index for the grid, and 2d --column index for the grid.
function Algorithms.AStar(start, goal, grid)
	local baseHeuristicWeight = 1  -- Base weight for the heuristic
	local heuristicWeight = baseHeuristicWeight
	local dynamicWeightAdjustment = 0.05  -- Amount to adjust the weight
	local maxIterationsBeforeAdjustment = 750  -- Iterations before adjusting weight
	local iterations = 0
	local Frontier = PriorityQueue.new()
	local Explored = {}
	local gScore = {}  -- Actual path cost from start to current node
	local visitCount = {}  -- Revisit penalty tracker
	local revisitPenalty = 0  -- Penalty for revisiting a node

	Frontier:Push(start, 0)
	gScore[start] = 0

	while not Frontier:isEmpty() do
		iterations += 1
		if iterations % maxIterationsBeforeAdjustment == 0 then
			heuristicWeight = math.max(heuristicWeight - dynamicWeightAdjustment, 0.1)
			warn("HeuristicWeight has been adjusted! " .. heuristicWeight)
		end

		local current = Frontier:Pop()

		-- Check if goal is reached
		if current.row == goal.row and current.column == goal.column and current.plotNumber == goal.plotNumber then
			-- Goal reached, reconstruct path
			local path = {}
			local temp = current
			while temp do
				table.insert(path, 1, {temp.row, temp.column})
				temp = Explored[temp]
			end
			return path
		end

		local neighbors = GetNeighbors(current, grid)
		for _, neighbor in ipairs(neighbors) do
			local nextNode = neighbor
			local newGScore = gScore[current] + Heuristic(current, nextNode) + (visitCount[nextNode] or 0) * revisitPenalty

			if not gScore[nextNode] or newGScore < gScore[nextNode] then
				gScore[nextNode] = newGScore
				Explored[nextNode] = current
				local hScore = Heuristic(goal, nextNode) * heuristicWeight
				local priority = newGScore + hScore
				Frontier:Push(nextNode, priority)
				visitCount[nextNode] = (visitCount[nextNode] or 0) + 1
			end
		end
	end
	return nil  -- No path found
end

Please do not hesitate to ask more questions if you believe that would help you help me

Thanks - Sasha

[Sashilove123 (Bizzy)]

This is for anyone encountering the same issue in the future. I resolved the problem by using a priority queue system, and a very high node revisit cost. After that was implemented, I saw a great leap in the performance of the code and now I can’t find a situation the code can’t handle.