Why does my A* implementation overflow the stack?

Question

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
        gValues.Add(10);
    }
    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
        gValues.Add(14);
    }
    if (grid.PTileArray[(int)Start.x, (int)Start.y + 1].CurrentType.Passable == 1)
    {
        OpenList.Add(new Vector2(Start.x, Start.y + 1)); //TOP
        gValues.Add(10);
    }
    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
        gValues.Add(14);
    }
    if (grid.PTileArray[(int)Start.x + 1, (int)Start.y].CurrentType.Passable == 1)
    {
        OpenList.Add(new Vector2(Start.x + 1, Start.y)); //RIGHT
        gValues.Add(10);
    }
    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
        gValues.Add(14);
    }
    if (grid.PTileArray[(int)Start.x, (int)Start.y - 1].CurrentType.Passable == 1)
    {
        OpenList.Add(new Vector2(Start.x, Start.y - 1)); //BOTTOM
        gValues.Add(10);
    }
    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
        gValues.Add(14);
    }

    //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);
            hValues.Add((int)final);
        }

    //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;
        fValues.Add(final); 
        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
    ClosedList.Add(OpenList[reference]);

    //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.

Answer 1

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.

Answer 2

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.