A* PathFinding Poor Performance

Question

After debugging for a few hours, the algorithm seems to be working. Right now to check if it works I'm checking the end node position to the currentNode position when the while loop quits. So far the values look correct. The problem is, the farther I get from the NPC, who is current stationery, the worse the performance gets. It gets to a point where the game is unplayable less than 10 fps. My current PathGraph is 2500 nodes, which I believe is pretty small, right? Any ideas on how to improve performance?

struct Node

{

    bool walkable;      //Whether this node is blocked or open

    vect2 position;     //The tile's position on the map in pixels

    int xIndex, yIndex; //The index values of the tile in the array

    Node*[4] connections; //An array of pointers to nodes this current node connects to

    Node* parent;

    int gScore;

    int hScore;

    int fScore;

}

class AStar

{

    private:

    SList!Node openList;    //List of nodes who have been visited, with F scores but not processed

    SList!Node closedList;  //List of nodes who have had their connections processed

    //Node*[4] connections;     //The connections of the current node;

    Node currentNode;           //The current node being processed

    Node[] Path;        //The path found;

    const int connectionCost = 10;

    Node start, end;

//////////////////////////////////////////////////////////

    void AddToList(ref SList!Node list, ref Node node )

    {

        list.insert( node );

    }

    void RemoveFrom(ref SList!Node list, ref Node node )

    {

        foreach( elem; list )

        {

            if( node.xIndex == elem.xIndex && node.yIndex == elem.yIndex )

            {

                auto a = find( list[] , elem );

                list.linearRemove( take(a, 1 ) );

            }

        }

    }

 

    bool IsInList( SList!Node list, ref Node node )

    {

        foreach( elem; list )

        {

            if( node.xIndex == elem.xIndex && node.yIndex == elem.yIndex )

                return true;

        }

        return false;

    }

    void ClearList( SList!Node list )

    {

        list.clear;

    }

    void SetParentNode( ref Node parent, ref Node child )

    {

        child.parent = &parent;

    }

    void SetStartAndEndNode( vect2 vStart, vect2 vEnd, Node[] PathGraph )

    {

        int startXIndex, startYIndex;

        int endXIndex, endYIndex;

        startXIndex = cast(int)( vStart.x / 32 );

        startYIndex = cast(int)( vStart.y / 32 );

        endXIndex = cast(int)( vEnd.x / 32 );

        endYIndex = cast(int)( vEnd.y / 32 );

        foreach( node; PathGraph )

        {

            if( node.xIndex == startXIndex && node.yIndex == startYIndex )

            {

                start = node;

            }

            if( node.xIndex == endXIndex && node.yIndex == endYIndex )

            {

                end = node;

            }

        }

    }

    void SetStartScores( ref Node start )

    {

        start.gScore = 0;

        start.hScore = CalculateHScore( start, end );

        start.fScore = CalculateFScore( start );

    }

    Node GetLowestFScore()

    {

        Node lowest;

        lowest.fScore = 10000;

        foreach( elem; openList )

        {

            if( elem.fScore < lowest.fScore )

                lowest = elem;

        }

        return lowest;

    }

    //This function current sets the program into an infinite loop

    //I still need to debug to figure out why the parent nodes aren't correct

    void GeneratePath()

    {

        while( currentNode.position != start.position )

        {

            Path ~= currentNode;

            currentNode = *currentNode.parent;

        }

    }

    void ReversePath()

    {

        Node[] temp;

        for(int i = Path.length - 1; i >= 0; i-- )

        {

            temp ~= Path[i];

        }

        Path = temp.dup;

    }

    public:

    //@FIXME It seems to find the path, but now performance is terrible

    void FindPath( vect2 vStart, vect2 vEnd, Node[] PathGraph )

    {

        openList.clear;

        closedList.clear;

        SetStartAndEndNode( vStart, vEnd, PathGraph );

        SetStartScores( start );

        AddToList( openList, start );

        while( currentNode.position != end.position )

        {

            currentNode = GetLowestFScore();

            if( currentNode.position == end.position )

                break;

            else

            {

                RemoveFrom( openList, currentNode );

                AddToList( closedList, currentNode );

                for( int i = 0; i < currentNode.connections.length; i++ )

                {

                    if( currentNode.connections[i] is null )

                        continue;

                    else

                    {

                        if( IsInList( closedList, *currentNode.connections[i] ) 

                           && currentNode.gScore < currentNode.connections[i].gScore )

                        {

                            currentNode.connections[i].gScore = currentNode.gScore + connectionCost;

                                 currentNode.connections[i].hScore = abs( currentNode.connections[i].xIndex - end.xIndex ) 

                            + abs(     currentNode.connections[i].yIndex - end.yIndex );

                            currentNode.connections[i].fScore =     currentNode.connections[i].gScore + currentNode.connections[i].hScore;

                            currentNode.connections[i].parent = &currentNode;

                        }

                        else if( IsInList( openList, *currentNode.connections[i] ) 

                                && currentNode.gScore < currentNode.connections[i].gScore )

                        {

                            currentNode.connections[i].gScore = currentNode.gScore + connectionCost;

                            currentNode.connections[i].hScore = abs( currentNode.connections[i].xIndex - end.xIndex ) 

                            + abs(     currentNode.connections[i].yIndex - end.yIndex );

                            currentNode.connections[i].fScore = currentNode.connections[i].gScore + currentNode.connections[i].hScore;

                            currentNode.connections[i].parent = &currentNode;

                        }

                        else

                        {

                            currentNode.connections[i].gScore = currentNode.gScore + connectionCost;

                            currentNode.connections[i].hScore = abs( currentNode.connections[i].xIndex - end.xIndex ) 

                            + abs( currentNode.connections[i].yIndex - end.yIndex );

                             currentNode.connections[i].fScore = currentNode.connections[i].gScore +     currentNode.connections[i].hScore;

                            currentNode.connections[i].parent = &currentNode;

                            AddToList( openList, *currentNode.connections[i] );

                        }

                    }   

                }

            }

        }

        writeln( "Current Node Position: ", currentNode.position );

        writeln( "End Node Position: ", end.position );

        if( currentNode.position == end.position )

        {

            writeln( "Current Node Parent: ", currentNode.parent );

           //GeneratePath();

           //ReversePath();

        }

    }

    Node[] GetPath()

    {

        return Path;

    }

}

Answer 1

Actually, you're using singly-linked lists for both the "open list" and the "closed list", which leads to unnecessary linear-time operations.

The above code should include a priority queue (heap), while the latter is best implemented as a hash table.

You have to use the associative array as a set, there are only keys, no values. Use the components you're now storing in your list as keys and use a dummy value, e.g. true.