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 = ¤tNode;
}
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 = ¤tNode;
}
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 = ¤tNode;
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.