# A* PathFinding Poor Performance

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.

• check my answer here: maybe you get an idea what's wrong :gamedev.stackexchange.com/questions/26512/… – Ali1S232 Apr 2 '12 at 7:04
• Have you tried adding debugging code so you can see the paths that it's trying to make? Or stepped through your code with a debugger? – Tetrad Apr 2 '12 at 7:21
• Sounds like your learning a new language in a complex situation. I suggest you simplify the algorithm to its barebones and then debug it verbosely. – deceleratedcaviar Apr 3 '12 at 7:15
• Efficient A* must be done with data structures like priority queues and sets where low element removal and membership checks can be done in sub-linear time. Not simple lists. Until you do this, it's debatable whether it's even properly called A*. This is the #1 error I've seen in dozens of A* implementations over the past decade, and it's the same error here. (Among probably many others.) – user744 Apr 3 '12 at 16:10
• @RedShft I would have thought that the Manhattan heuristic would be fine for that size. For problems like this I'd benchmark portions of the code. – PhilCK Apr 4 '12 at 22:05