CODEWITHSUNDEEP
c++performancealgorithmmaze
Jake Runzer
Jake Runzer

Reputation: 1007

A* pathfinding slow

I am currently working on a A* search algorithm. The algorithm would just be solving text file mazes. I know that the A* algorithm is supposed to be very quick in finding the finish. Mine seems to take 6 seconds to find the path in a 20x20 maze with no walls. It does find the finish with the correct path it just takes forever to do so.

If I knew which part of code was the problem I would just post that but I really have no idea what is going wrong. So here is the algorithm that I use...

 while(!openList.empty()) {  
    visitedList.push_back(openList[index]);
    openList.erase(openList.begin() + index);

    if(currentCell->x_coor == goalCell->x_coor && currentCell->y_coor == goalCell->y_coor)          
    }
        FindBestPath(currentCell);
        break;
    }

    if(map[currentCell->x_coor+1][currentCell->y_coor] != wall)
    {
    openList.push_back(new SearchCell(currentCell->x_coor+1,currentCell->y_coor,currentCell));
    }
    if(map[currentCell->x_coor-1][currentCell->y_coor] != wall) 
    {
        openList.push_back(new SearchCell(currentCell->x_coor-1,currentCell->y_coor,currentCell));
    }
    if(map[currentCell->x_coor][currentCell->y_coor+1] != wall) 
    {
        openList.push_back(new SearchCell(currentCell->x_coor,currentCell->y_coor+1,currentCell));
    }
    if(map[currentCell->x_coor][currentCell->y_coor-1] != wall) 
    {
        openList.push_back(new SearchCell(currentCell->x_coor,currentCell->y_coor-1,currentCell));
    }

    for(int i=0;i<openList.size();i++) {
        openList[i]->G = openList[i]->parent->G + 1;
        openList[i]->H = openList[i]->ManHattenDistance(goalCell);
    }

    float bestF = 999999;
    index = -1;

    for(int i=0;i<openList.size();i++) {
        if(openList[i]->GetF() < bestF) {
            for(int n=0;n<visitedList.size();n++) {
                if(CheckVisited(openList[i])) {
                    bestF = openList[i]->GetF();
                    index = i;
                }
            }
        }
    }
    if(index >= 0) {
        currentCell = openList[index];
    }
}

I know this code is messy and not the most efficient way to do things but I think it should still be faster then what it is. Any help would be greatly appreciated.

Thanks.

Upvotes: 0

Views: 1175

Answers (4)

BlueRaja - Danny Pflughoeft
BlueRaja - Danny Pflughoeft

Reputation: 85996

openList.erase is O(n), and the for-loop beginning with for(int i=0;i<openList.size();i++) is O(n^2) due to the call to CheckVisited - these are called every iteration, making your overall algorithm O(n^3). A* should be O(n log n).

Try changing openList to a priority-queue like it's supposed to be, and visitedList to a hash table. The entire for loop can then be replaced by a dequeue - make sure you check if visitedList.Contains(node) before enqueuing!

Also, there is no need to recalculate the ManHattenDistance for every node every iteration, since it never changes.

Upvotes: 1

btilly
btilly

Reputation: 46409

Here is a big hint.

If ever you find two paths to the same cell, you can always throw away the longer one. If there is a tie, you can throw away the second one to get there.

If you implement that, with no other optimizations, the search would become more than acceptably fast.

Secondly the A* algorithm should only bother backtracking if the length to the current cell plus the heuristic exceeds the length to the current cell plus the heuristic for any other node. If you implement that, then it should directly find a path and stop. To facilitate that you need to store paths in a priority queue (typically implemented with a heap), not a vector.

Upvotes: 1

rlinden
rlinden

Reputation: 2041

Aren't you constantly backtracking?

The A* algorithm backtracks when the current best solution becomes worse than another previously visited route. In your case, since there are no walls, all routes are good and never die (and as MSalters correctly pointed, there are several of them). When you take a step, your route becomes worse than all the others that are one step shorter.

If that is true, this may account for the time taken by your algorithm.

Upvotes: 0

MSalters
MSalters

Reputation: 179809

Your 20x20 maze has no walls, and therefore many, many routes which are all the same length. I'd estimate trillions of equivalent routes, in fact. It doesn't seem so bad when you take that into account.

Of course, since your heuristic looks perfect, you should get a big benefit from excluding routes that are heuristically predicted to be precisely as long as the best route known so far. (This is safe if your heuristic is correct, i.e. never overestimates the remaining distance).

Upvotes: 1

Related Questions