1
\$\begingroup\$

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;
}
\$\endgroup\$
3
  • 1
    \$\begingroup\$ Create more functions and run the profiler that comes with Visual Studio on your code... \$\endgroup\$
    – Vaillancourt
    Jan 18, 2017 at 2:25
  • 5
    \$\begingroup\$ This might be better suited to the code review StackExchange \$\endgroup\$
    – DMGregory
    Jan 18, 2017 at 7:30
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ Jan 18, 2017 at 10:50

2 Answers 2

1
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ You should also turn your Open List into a Heap. Greatly increases look up times \$\endgroup\$
    – Archmede
    May 2, 2017 at 20:19
1
\$\begingroup\$

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.

\$\endgroup\$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .