Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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.

share|improve this question
    
check my answer here: maybe you get an idea what's wrong :gamedev.stackexchange.com/questions/26512/… –  Ali.S Apr 2 '12 at 7:04
8  
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
3  
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. –  Daniel Apr 3 '12 at 7:15
3  
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
1  
@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

1 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.

share|improve this answer
    
Good advices. Also, if performance is still an issue after all this, an idea could be to do the pathfinding in a separate thread. –  Laurent Couvidou Apr 18 '12 at 19:37

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.