2D Pathfinding causes Stack Overflow

Archived Forums Questions & Answers
1

I have been working on my first ever attempt at 2D Pathfinding (Still fairly new to gamedev) using the A* Algorithm as detailed here - http://www.policyalmanac.org/games/aStarTutorial.htm

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). Upon further investigation it would appear that at some point in the path the algorithm is switching back and forth between two tiles and I cannot seem to work out why.

Any help or nudges in the right direction would be greatly appreciated.
The code probably isn’t the best way to do things but this is my first attempt so apologies if it offends anyone :stuck_out_tongue:

33430-question.png
33430-question.png935×718 61.4 KB 

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);
    }
2

It’s a bit hard to see exactly where the infinite loop is happening from just looking at your code. But, I have an idea:

//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);
    }
}

Here, you’re removing the parent node from the open list. This means that the H-value for this node is not calculated. The g-value, though, were added when you looked at the parent node.

As far as I can tell, this means that gValues should have one more value than hValues, and your calculation will probably be thrown off by that - every gValue after your parent node will be off by one. Try modifying the bit I quoted above like this:

if (OpenList[n] == ClosedList[ClosedList.Count - 1])
{
    OpenList.RemoveAt(n);
    gValues.RemoveAt(n);
}

I’m not sure that this will fix the problem, but it definitely looks weird that you’re not removing the g-value of the parent node.