# Why does my A* implementation overflow the stack?

I'm fairly new to game dev and working on my first ever attempt at 2D pathfinding. I'm using the A* algorithm as detailed here.

For the most part, it seems to be working correctly and as intended. However upon attempting to wrap my path around a building in the map, a stack overflow is caused in ClosedList (the list storing coordinates of the path). It appears that at some point in the path, the algorithm is switching back and forth between two tiles, but I cannot work out why.

The code probably isn't the best way to do things but this is my first attempt. Apologies if it offends anyone. :P

void CheckSquare(Vector2 Start, Vector2 End)
{
//Check for Invalid Start/End Points
if (Start == End ||
grid.PTileArray[(int)Start.x, (int)Start.y].CurrentType.Passable == 0 ||
grid.PTileArray[(int)End.x, (int)End.y].CurrentType.Passable == 0)
{
return;
}

//Check which adjacent tiles are passable
if (grid.PTileArray[(int)Start.x - 1, (int)Start.y].CurrentType.Passable == 1)
{
OpenList.Add(new Vector2(Start.x - 1, Start.y)); //LEFT
}
if (grid.PTileArray[(int)Start.x - 1, (int)Start.y + 1].CurrentType.Passable == 1)
{
OpenList.Add(new Vector2(Start.x - 1, Start.y + 1)); //TOP LEFT
}
if (grid.PTileArray[(int)Start.x, (int)Start.y + 1].CurrentType.Passable == 1)
{
OpenList.Add(new Vector2(Start.x, Start.y + 1)); //TOP
}
if (grid.PTileArray[(int)Start.x + 1, (int)Start.y + 1].CurrentType.Passable == 1)
{
OpenList.Add(new Vector2(Start.x + 1, Start.y + 1)); //TOP RIGHT
}
if (grid.PTileArray[(int)Start.x + 1, (int)Start.y].CurrentType.Passable == 1)
{
OpenList.Add(new Vector2(Start.x + 1, Start.y)); //RIGHT
}
if (grid.PTileArray[(int)Start.x + 1, (int)Start.y - 1].CurrentType.Passable == 1)
{
OpenList.Add(new Vector2(Start.x + 1, Start.y - 1)); //BOTTOM RIGHT
}
if (grid.PTileArray[(int)Start.x, (int)Start.y - 1].CurrentType.Passable == 1)
{
OpenList.Add(new Vector2(Start.x, Start.y - 1)); //BOTTOM
}
if (grid.PTileArray[(int)Start.x - 1, (int)Start.y - 1].CurrentType.Passable == 1)
{
OpenList.Add(new Vector2(Start.x - 1, Start.y - 1)); //BOTTOM LEFT
}

//Remove the parent from the Possible choices
for (int n = 0; n < OpenList.Count; n++)
{
if (OpenList[n] == ClosedList[ClosedList.Count - 1])
{
OpenList.RemoveAt(n);
}
}

//Calculate H Values
for (int n = 0; n < OpenList.Count; n++)
{
float x = Mathf.Abs(End.x - OpenList[n].x);
float y = Mathf.Abs(End.y - OpenList[n].y);
float final = 10 * (x + y);
}

//Calculate F Values
int lowest = 10000;
int reference = 0;
for (int n = 0; n < OpenList.Count; n++)
{
int g = gValues[n];
int h = hValues[n];
int final = g + h;
if (fValues[n] < lowest)
{
lowest = fValues[n];
reference = n;
}
}

//Add the square with the lowest F Value to the closed list as part of the path

//Clear Lists
OpenList.Clear();
gValues.Clear();
hValues.Clear();
fValues.Clear();

//If the final Location in ClosedList is not the end then continue
if (ClosedList[ClosedList.Count - 1] != End)
CheckSquare(ClosedList[ClosedList.Count - 1], End);
}


Help or nudges in the right direction would be greatly appreciated.

• Pedantically speaking, it's not your pathfinding algo causing a stack overflow (at least not with only 400 nodes, unless your stack is ridiculously tiny for some reason), it's a bug in your pathfinding algo that's causing infinite recursion, which is almost always the proximal cause of a stack overflow. Oct 9, 2014 at 2:41

A typical implementation of A* will use a loop instead of recursion. Change the if (ClosedList[ClosedList.Count - 1] != End) CheckSquare(...) into a while loop.

However, I suspect the code won't work correctly even with that change, because you're clearing all the data after you check just one square. A* needs all that data (OpenList, gValues, etc.) so you don't want to clear it before you're finished finding the path. You're going to need to change more to make it work.

If you're looking for some sample code, see my article. I try to keep the sample code as simple as I can.

Your best bet is to attach the debugger and see where things are going wrong. If you're getting a stackoverflow it means you're recursing too far into your CheckSquare method. That either means your map is too large, or you're checking the same tiles multiple times. I'd bet on the latter given your screenshot.

Depending on the IDE you're using, you can cause the debugger to break after the line you're targeting has been reached a certain number of times. That means you can place a break point at the beginning of your CheckSquare method and set it to break after 50 or so iterations.

It could be that you're adding squares to your open list that are on your closed list. Which can result in you going in circles when the path is not straight forward.

You might want to switch to an iterative approach to more easily track down your problems.