# Why is my A* algorithm slow?

I made an A* algorithm, but running it is unbearably slow, even on a 40 x 40 test arena with few obstacles. I've tried changing the unexplored array to exclude nodes in the open list, and although it runs a lot faster, this creates a bug where it doesn't always select the best path.

What am I doing wrong? For what it's worth, I'm running Visual Studio.

Coordinate* Map::astar(int x1, int y1, int x2, int y2, int size)
{
Coordinate* return_path;

if (!passable[x2/24000][y2/24000])
{
// return with blank path if target is not passable
return_path = new Coordinate[1];
return_path[0].x = -1;
return_path[0].y = -1;
return return_path;
}

std::vector<Node> open_list;
std::vector<Node> closed_list;
Node current_node;
Coordinate destination;
Coordinate directions[8];
directions[0].x = -1;
directions[0].y = -1;
directions[1].x = -1;
directions[1].y = 1;
directions[2].x = 1;
directions[2].y = -1;
directions[3].x = 1;
directions[3].y = 1; // diagonal directions
directions[4].x = -1;
directions[4].y = 0;
directions[5].x = 0;
directions[5].y = -1;
directions[6].x = 0;
directions[6].y = 1;
directions[7].x = 1;
directions[7].y = 0; // straight directions

// set up unexplored array to quickly sift through explored nodes
bool** unexplored;
unexplored = new bool*[xmax];

for (int i = 0; i < xmax; i++)
{
unexplored[i] = new bool[ymax];

for (int j = 0; j < ymax; j++)
{
unexplored[i][j] = true;
}
}

// set starting node and add it to open list
current_node.loc.x = x1 / 24000;
current_node.loc.y = y1 / 24000;
current_node.exactloc.x = x1;
current_node.exactloc.y = y1;
current_node.parent.x = current_node.loc.x;
current_node.parent.y = current_node.loc.y;
current_node.cost = 0;
current_node.steps = 1;
destination.x = x2 / 24000;
destination.y = y2 / 24000;
open_list.push_back(current_node);

// Main loop
while (!open_list.empty())
{
// select the open node with lowest cost + distance
int best_node;
int best_cost = -1;

for (unsigned int i = 0; i < open_list.size(); i++)
{
int dx = abs(destination.x - open_list[i].loc.x);
int dy = abs(destination.y - open_list[i].loc.y);
int min = (dx > dy) ? dy : dx;
int distance = (dx + dy) * 1000 - min * 586;
int total_cost = open_list[i].cost + distance;

if (total_cost < best_cost || best_cost < 0)
{
best_cost = total_cost;
best_node = i;
}
}

current_node = open_list[best_node];

// if we are at the destination, construct a path to it
if (current_node.loc.x == destination.x && current_node.loc.y == destination.y)
{
// Path found: add current node to the closed list
closed_list.push_back(current_node);
return_path = new Coordinate[current_node.steps + 2];
return_path[current_node.steps+1].x = -1;
return_path[current_node.steps+1].y = -1;
return_path[current_node.steps].x = x2;
return_path[current_node.steps].y = y2;

for (int i = current_node.steps - 1; i >= 0; i--)
{
unsigned int j;

for (j = 0; j < closed_list.size(); j++)
{
if (current_node.exactloc.x == closed_list[j].exactloc.x &&
current_node.exactloc.y == closed_list[j].exactloc.y)
{
break;
}
}

return_path[i] = current_node.exactloc;
current_node.exactloc = closed_list[j].parent;
}

// clean up unexplored array
for (int i = 0; i < xmax; i++)
{
delete[] unexplored[i];
}

delete[] unexplored;
return return_path;
}

// remove current node from open list and add to closed
open_list.erase(open_list.begin() + best_node);
closed_list.push_back(current_node);
unexplored[current_node.loc.x][current_node.loc.y] = false;

// add neighboring nodes to open list
for (char i = 0; i < 8; i++)
{
Node n;
n.loc.x = current_node.loc.x + directions[i].x;
n.loc.y = current_node.loc.y + directions[i].y;

if (i<=3)
{
n.cost = current_node.cost + 1414;
}
else
{
n.cost = current_node.cost + 1000;
}

n.steps = current_node.steps + 1;
n.exactloc.x = n.loc.x * 24000;
n.exactloc.y = n.loc.y * 24000;
n.parent = current_node.exactloc;

// check if both coordinates are positive and below maximum
// check if location is a passable node
// check if location has already been considered
if (n.loc.x >= 0 && n.loc.y >= 0 && n.loc.x < xmax && n.loc.y < ymax)
{
// check if location is a passable node
if (passable[n.loc.x][n.loc.y] && unexplored[n.loc.x][n.loc.y])
{
// for diagonals, check if the adjacent straight nodes are passable.
// if neither is passable, abort movement.
if ((i <= 3 && (passable[current_node.loc.x][n.loc.y] ||
passable[n.loc.x][current_node.loc.y])) || i > 3)
{
// add the neighbor to the open list
open_list.push_back(n);
}
}
}
}
}

// no path found
// clean up unexplored array
for (int i = 0; i < xmax; i++)
{
delete[] unexplored[i];
}

delete[] unexplored;

// return with blank path
return_path = new Coordinate[1];
return_path[0].x = -1;
return_path[0].y = -1;
return return_path;
}

• Create more functions and run the profiler that comes with Visual Studio on your code... Jan 18, 2017 at 2:25
• This might be better suited to the code review StackExchange Jan 18, 2017 at 7:30
• @DMGregory definitely more suited for there. Also, it's a general enough algorithm and a general enough language that there will be a lot more people to help there. Jan 18, 2017 at 10:50

Thanks guys. I think I got it. What I did was change the unexplored array into a cost array that stores the cost to travel to that node. If the pathfinder travels over a node that requires more cost that the lowest recorded cost, it is not added to the open list. Now my algorithm returns quick results and doesn't make unwanted detours. There are still lots of things I can do for speed improvements like binary heap, but I already know how to implement that.

• You should also turn your Open List into a Heap. Greatly increases look up times May 2, 2017 at 20:19

One problem may be the way you use the open list, At the start of each loop you do a linear scan over the entire open_list, use erase to remove the lowest cost node and then add all not-closed neighbours to the open_list which leads to duplicate nodes in the list. You also don't have a way to avoid exploring a node twice.

If you track how large the open_list gets during the algorithm you'll see it gets massive. Combine this with the 2 O(n) operations on the list and it'll be no surprise that the runtime gets massive.

During the linear scan over the open_list you should flush the explored nodes. You can replace erase with a swap with back and pop_back sequence.

for (unsigned int i = 0; i < open_list.size(); i++)
{
while(i < open_list.size() &&
explored[open_list[i].loc.x][open_list[i].loc.y]){
// flush explored nodes
swap(open_list[i], open_list.back());
open_list.pop_back();
}
if(i >= open_list.size()) break;

int dx = abs(destination.x - open_list[i].loc.x);
int dy = abs(destination.y - open_list[i].loc.y);
int min = (dx > dy) ? dy : dx;
int distance = (dx + dy) * 1000 - min * 586;
int total_cost = open_list[i].cost + distance;

if (total_cost < best_cost || best_cost < 0)
{
best_cost = total_cost;
best_node = i;
}
}


Though it would be better if you updated the elements in the open_list in place instead of simply adding the neighbours.