A* Pathfinding: Debugging Special Cases – Steven Lilley

December 19, 2019

A* Pathfinding

Debugging Special Cases

ISSUES

Getting an Index Out of Bounds Error in EnemyBasicMovement Script

Error happening on this line:

Vector3 direction = (path.lookPoints[0] – transform.position).normalized;

Suggests that the very first point in a path does not exist, so somehow empty paths are being passed through the system.

Test 1: Increase A* Grid Size to Cover Entire Play Area and Spawn Points

Some of the spawn points are a bit off of the normal play area, so I made sure to cover anywhere the units could possibly exist with the A* grid so they always had a node to latch onto (even though I believe the clamping should cover this error). This did not end up being the issue as the error persisted.

Test 2: Increase Size of Walkable Plane Over Entire Play Area

Similar to the logic of Test 1, I just wanted to make sure the nodes were not not being created because the units were missing some usual piece of information they would have to make them. Turns out this was not the issue either.

Test 3: Make Sure Target is Set Before Instantiating the Enemy

I thought maybe a path was being created before the unit had a target, which could make sense for creating a path with size 0. I did this by having the pathing script disabled initially, and making sure the spawner passed in the target information BEFORE it activated the script. The error continued though.

Test 4: Do Not Move the Target to See if Error Exists

It seemed like most spawns didn’t get errors if the player did not move, so I moved the one spawn that basically did not have to move to reach the player’s x position and tested what happened without the player moving (The X position counted as “very close” to the player at this time since I still had some of the issues with converting between 3D and 2D coordinates). There were no errors at all when not moving the target during the game.

DETERMINED ISSUE

Something about the paths updating later in the units’ lives was creating these size 0 paths.

Test 5: Is Spawning Causing the Issue

I was not sure if spawning the units was somehow causing the problems still, so I just placed 4 of the unit prefabs randomly about into the scene initially and stopped the spawners. This did not get rid of the error, and had the units return to moving in big circles still.

Further Info

This was giving me a lot of trouble, so I went back to following the path of logic to see why it would be producing these 0 count paths.

OnPathFound method in EnemyBasicMovement is being passed an empty array of Vector3[] waypoints
PathRequestManager class calls this method through its own FinishedProcessingPath method
OnPathFound is the method assigned to the callback Action for the PathRequest object
PathFindingHeap is creating an empty waypoints array somehow

The zero count path is being created in PathFindingHeap somehow. This should be impossible as every path should at the very least have the start node and the target node, which would be a count of 2.

RetracePath takes in a startNode and endNode to create the entire path of nodes between them
In the problem case, a new path has been created when the target is only a single node away from the pathfinding unit’s current position
there is a while loop that runs until it hits the startNode, so in this case, it only runs a single time (since the only nodes are the startNode and the endNode), creating a single waypoint
this creates a path with a count of 1
then the SimplifyPath method takes in this path
SimplifyPath creates a new List of Vector3 to fill with only necessary waypoints
it does this by taking points from the passed in path, but it looks through this with a for loop which starts at i = 1 and ends at i < path.Count, because it needs a previous point to compare to since it is doing a directional check
since the path.Count is only 1 here, the for loop never runs, and we return an empty set of waypoints
Can possibly solve with a special case since a path of 1 node is also a most simplified case

Test 6: Add Case In Simplify Path to Deal with Receiving One Node

I just added a check case before the normal logic that if the input path for SimplifyPath was only 1 node, it would just use that node as the path. This reduces the number of errors significantly, but there are cases where even the base path passed into SimplifyPath has 0 nodes.

DETERMINED ISSUE

The PathFindingHeap RetracePath method is creating paths with 0 nodes when Unit is close to target. As a result, SimplifyPath also makes 0 count paths. The only way this can be the case is if the startNode == endNode, so this must be happening when a new path is being created even though the unit and its target are already considered to be on the same node. This leads me to believe it is an issue with the difference between the node size and the distance the target has to move before looking for a new path (pathUpdateMoveThreshold in EnemyBasicMovement).

Test 7: Reduce NodeRadius to Half (or Less) of Update Path Threshold

Originally the values for pathUpdateMoveThreshold and the nodeRadius were both 0.5, which lead to a overall node size (nodeDiamater) of 1.0. I reduced the nodeRadius to 0.25 (which gives them a total nodeDiameter of 0.5), so this was at or below the threshold.

SOLVED

This completely removed the errors from happening (I add mostly because I am unsure if there exists a case where having the nodeDiameter exactly equal the threshold could cause an error).

SUMMARY

There was a lot of going back and forth to figure out where this error was coming from, and it was even harder since I was having some other issues since I had not fully converted the 3D system to the 2D system. As far as I can tell, this should cover most of the strange cases the pathing should run into even with an updating target (which should mostly be extra for my purposes anyway). I should add a check between the node size and the update threshold to make sure that issue does not happen again.