A* PathFinding Poor Performance

Question

I'm getting poor performance in-game due to my path-finding algorithm. The farther I get from my NPC, the worse the framerate gets.

Ok, I updated my code and implemented the openList as a min-heap and the closed list as an associative array. As far as I know, it's not possible to grow binary heaps in D so I had to allocate enough space on my openList so that my game wouldn't crash.

Unfortunately, when I fired up my game to test pathfinding, the performance was still bad, despite the openList being sorted by fScore.

I'm not entirely sure what i'm missing. As far as I've read, the main areas for performance are the data structures and the heuristic to an extent.

The heuristic i'm using is Manhattan distance, since my nodes are based upon tiles. My data structures are a min-heap, sorted by fScore, lowest at the front, and an associative array, which I believe is implemented as a hash table in D.

Where is all the performance going?

Are my data structures implemented and used right?

Would it help performance to implement tie breaking with Manhattan Distance?

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:
bool[Node] closedList;  

Node currentNode;           //The current node being processed

Node[] Path;        //The path found;

const int connectionCost = 10;

Node start, end;

//.... other functions omitted here//

public:
void FindPath( vect2 vStart, vect2 vEnd, Node[] PathGraph )
{
    Node[] a;
    a.length = 3000;
    auto openList = BinaryHeap!(Node[], "a.fScore > b.fScore")(a, 0);
    closedList.clear;

    SetStartAndEndNode( vStart, vEnd, PathGraph );
    SetStartScores( start );
    openList.insert( start );

    while( currentNode.position != end.position )
    {
        currentNode = openList.front();
        openList.removeFront();

        if( currentNode.position == end.position )
            break;
        else
        {
            closedList[currentNode] = false;

            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].fScore = currentNode.connections[i].gScore + currentNode.connections[i].hScore;
                        currentNode.connections[i].parent = &currentNode;
                    }
                    else if( IsInList( a, *currentNode.connections[i] ) 
                            && currentNode.gScore < currentNode.connections[i].gScore )
                    {
                        currentNode.connections[i].gScore = currentNode.gScore + connectionCost;
                        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;
                        openList.insert(  *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();
    //}
}

}

This is my first attempt at A* so any help would be greatly appreciated.

Answer 1

Like others have said, simplify your algorithm. It's ok to make a crude implementation and use interpolation to smooth it out later. Maybe also increase the size of each search block and if something is past a certain distance, don't pathfind. And it would probably be best if you cache your path unless your position changes and only recalc if the player moves away from the path.