- Home /
Unity2D Grid A* pathfinding freezing for a few seconds
My A* pathfinding function can reach the endpoint but it often freezes for a few seconds and I am testing it using one object only.
I am using a grid based tilemap.
The construction of the path works fine but it is the path finding that is not working as intended. When it is a simple straight line to the goal, it works without freezing.
I have used the wiki pseudocode as a reference
EDIT: I think I have found the source of the problem but I am unsure of how to solve it. I ran the profiler and I narrowed down the problem but I do not know how to fix it. Any guidance would be appreciated!
Behavior.update takes 99% total with 837ms. Under behavior update, EventSystem.update() with 98.9% total and a time MS of 836.65. Under EventSystem.update(), the main problem seem to be LogStringToConsole, with its child
StackTraceUtility.PostprocessStacktrace() and StackTraceUtility.ExtractStackTrace()
void startPathfinding(Vector3 startPoint, Vector3 endPoint, Transform someObject,bool Hint) {
var initialPosition = tileMap.getTileCoordinates(startPoint);
endPosition = tileMap.getTileCoordinates(endPoint);
openList.Clear();
closedList.Clear();
Node initialPostionStep = new Node();
initialPostionStep.position = initialPosition;
addIntoOpenList(initialPostionStep); // adds the node into the open list and sorts it by the lowest fScore
do {
var currentStep = openList[0];
openList.RemoveAt(0);
closedList.Add(currentStep);
if (currentStep.position == endPosition) {
// not relevant to problem
}
var adjacentTiles = WalkableAdjacentTiles(currentStep);
foreach (Node adjacentNode in adjacentTiles) {
var moveCost = 1;
var tentativeGScore = currentStep.gScore + moveCost;
var inOpenList = FindInOpenList(adjacentNode);
if (FindInClosedList(adjacentNode) != null) {
print ("In ClosedList");
continue;
}
if (inOpenList == null || tentativeGScore < adjacentNode.gScore) {
adjacentNode.parent = currentStep;
adjacentNode.gScore = tentativeGScore;
adjacentNode.hScore = computeHScore(adjacentNode.position,endPosition);
addIntoOpenList(adjacentNode);
} else {
addIntoOpenList(adjacentNode);
}
}
}while (openList.Count > 0);
}
public bool isValidTile(int x, int y) {
if (x > 17 || y > 9 ) {
// Debug.Log("Not a valid Tile " + "x value: " +x + " y value: "+y);
return false;
}
Transform tile = getTileAt(x,y);
if (x < 0 || y < 0 || tile.gameObject.name == "filled") {
return false; }
if (tile == null) {
print ("tile is null for some reason?");
return false;
}
//print ((x) + " value " + (y) + " value");
return true;
}
Answer by zach-r-d · Jun 27, 2015 at 11:25 PM
There's nothing wrong with the A* implementation per se, it's just that A* can be really slow sometimes. Try messing around with this interactive pathfinding visualizer to see how (try putting a sideways-U-shaped wall around the destination so that the path has to go around the back and see how long it takes versus a straight path).
The solution will involve either using a different algorithm that performs better for whatever particular maps you have, or potentially using a background thread to perform pathfinding the way NavMeshAgents do.
That's strange because I am porting my iOS spritekit game to Unity and I am using the exact same implementation of the code which has no lag but in Unity it freezes for a few seconds. Perhaps I am doing something wrong with Unity? I am confused
The grid map is also really small, about 18x15
Oh, if the grid size is only 18x15 then it must be something completely different indeed. Have you tried running the game with the profiler to see if it can narrow down where so much time is spent?
I ran the profiler and I narrowed down the problem but I do not know how to fix it. Any guidance would be appreciated!
Behavior.update takes 99% total with 837ms. Under behavior update, EventSystem.update() with 98.9% total and a time $$anonymous$$S of 836.65.
Under EventSystem.update(), the main problem seem to be LogStringToConsole, with its child
StackTraceUtility.PostprocessStacktrace() and StackTraceUtility.ExtractStackTrace()
Huh. Are there a lot of errors or debug logs in the console? That would slow things down significantly.
Also, if you want finer/custom samples to show up in the profiler, insert some Profiler.BeginSample/Profiler.EndSample calls around bits of code you suspect to be causing performance problems (they can be nested, too).