How to speed up A* algorithm at large spatial scales?

Question

From http://ccl.northwestern.edu/netlogo/models/community/Astardemo, I coded an A* algorithm by using nodes in a network to define least-cost paths. The code seems to work but it is much too slow when I use it at large spatial scales.My landscape has an extent of 1000 patches x 1000 patches with 1 patch = 1 pixel. Even if I reduce it at 400 patches x 400 patches with 1 patch = 1 pixel, it is yet too slow (I can't modify my landscape below 400 patches x 400 patches). Here is the code:

to find-path [ source-node destination-node] 

let search-done? false
let search-path []
let current-node 0
set list-open []
set list-closed []  
let list-links-with-nodes-in-list-closed []
let list-links []

set list-open lput source-node list-open
while [ search-done? != true]
[    
ifelse length list-open != 0
[
  set list-open sort-by [[f] of ?1 < [f] of ?2] list-open 
  set current-node item 0 list-open 
  set list-open remove-item 0 list-open 
  set list-closed lput current-node list-closed
  ask current-node
  [  
    if parent-node != 0[
    set list-links-with-nodes-in-list-closed lput link-with parent-node list-links-with-nodes-in-list-closed 
    ]
    ifelse any? (nodes-on neighbors4) with [ (xcor = [ xcor ] of destination-node) and (ycor = [ycor] of destination-node)]
    [
      set search-done? true 
    ]
    [        
      ask (nodes-on neighbors4) with [ (not member? self list-closed) and (self != parent-node) ]  
      [  
        if not member? self list-open and self != source-node and self != destination-node
        [
          set list-open lput self list-open
          set parent-node current-node
          set list-links sentence (list-links-with-nodes-in-list-closed) (link-with parent-node)
          set g sum (map [ [link-cost] of ? ] list-links)
          set h distance destination-node 
          set f (g + h)
        ]
      ]
    ]
  ]
]

[
  user-message( "A path from the source to the destination does not exist." )
  report []
 ]
]
set search-path lput current-node search-path
let temp first search-path
while [ temp != source-node ]
[
 ask temp
[
  set color red
]
set search-path lput [parent-node] of temp search-path 
set temp [parent-node] of temp 
]
set search-path fput destination-node search-path
set search-path reverse search-path  
print search-path
end

Unfortunately, I don't know how to speed up this code. Is there a solution to calculate rapidly least-cost paths at large spatial scales ?

Thanks very much for your help.

Mickelson

I don't know this language at all, but you sort-by the list-open every iteration, I don't know if that's adding overhead. Also the setting of g could be the "cost of current path +1", which might give you a minescule boost. I don't know the language well enough to suggest anything further, but it has several characteristics that strike me as common in slower languages. – Nimiety

The code looks fine to me. If there's any efficiency mistakes in it, I'm not spotting them. Perhaps the amount of computation you're trying to do is simply too great, and you need to figure out a way to solve your problem in a manner requiring less computation. How about using heuristics that don't necessarily find the best path, but tend to choose reasonably good paths? – Candicandia

Answer 1

Was curious so I tested mine A* and here is mine result

Maze 1280 x 800 x 32 bit pixels

• as you can see it took ~23ms
• no multithreading (AMD 3.2GHz)
• C++ 32bit app (BDS2006 Turbo C++ or Borland C++ builder 2006 if you like)
• the slowest path I found was ~44ms (fill almost whole map)

I think that is fast enough ...

Here is source for mine A* class:

//---------------------------------------------------------------------------
//---------------------------------------------------------------------------
//---------------------------------------------------------------------------
const DWORD A_star_space=0xFFFFFFFF;
const DWORD A_star_wall =0xFFFFFFFE;
//---------------------------------------------------------------------------
class A_star
    {
public:
    // variables
    DWORD **map;        // map[ys][xs]
    int xs,ys;          // map esolution   xs*ys<0xFFFFFFFE !!!
    int *px,*py,ps;     // output points px[ps],py[ps] after compute()

    // internals
    A_star();
    ~A_star();
    void _freemap();                                    // release map memory
    void _freepnt();                                    // release px,py memory

    // inteface
    void resize(int _xs,int _ys);                       // realloc map to new resolution
    void set(Graphics::TBitmap *bmp,DWORD col_wall);    // copy bitmap to map
    void get(Graphics::TBitmap *bmp);                   // draw map to bitmap for debuging
    void compute(int x0,int y0,int x1,int y1);          // compute path from x0,y0 to x1,y1 output to px,py
    };
//---------------------------------------------------------------------------
     A_star::A_star()   { map=NULL; xs=0; ys=0; px=NULL; py=NULL; ps=0; }
     A_star::~A_star()  { _freemap(); _freepnt(); }
void A_star::_freemap() { if (map) delete[] map; map=NULL; xs=0; ys=0; }
void A_star::_freepnt() { if (px) delete[] px; px=NULL; if (py) delete[] py; py=NULL; ps=0; }
//---------------------------------------------------------------------------
void A_star::resize(int _xs,int _ys)
    {
    if ((xs==_xs)&&(ys==_ys)) return;
    _freemap();
    xs=_xs; ys=_ys;
    map=new DWORD*[ys];
    for (int y=0;y<ys;y++)
     map[y]=new DWORD[xs];
    }
//---------------------------------------------------------------------------
void A_star::set(Graphics::TBitmap *bmp,DWORD col_wall)
    {
    int x,y;
    DWORD *p,c;
    resize(bmp->Width,bmp->Height);
    for (y=0;y<ys;y++)
     for (p=(DWORD*)bmp->ScanLine[y],x=0;x<xs;x++)
        {
        c=A_star_space;
        if (p[x]==col_wall) c=A_star_wall;
        map[y][x]=c;
        }
    }
//---------------------------------------------------------------------------
void A_star::get(Graphics::TBitmap *bmp)
    {
    int x,y;
    DWORD *p,c;
    bmp->SetSize(xs,ys);
    for (y=0;y<ys;y++)
     for (p=(DWORD*)bmp->ScanLine[y],x=0;x<xs;x++)
        {
        c=map[y][x];
             if (c==A_star_wall ) c=0x00000000;
        else if (c==A_star_space) c=0x00FFFFFF;
        else                      c=((c>>1)&0x7F)+0x00404040;
        p[x]=c;
        }
    }
//---------------------------------------------------------------------------
void A_star::compute(int x0,int y0,int x1,int y1)
    {
    int x,y,xmin,xmax,ymin,ymax,xx,yy;
    DWORD i,j,e;
    // [clear previous paths]
    for (y=0;y<ys;y++)
     for (x=0;x<xs;x++)
      if (map[y][x]!=A_star_wall)
       map[y][x]=A_star_space;
/*
    // [A* no-optimizatims]
    xmin=x0; xmax=x0; ymin=y0; ymax=y0;
    if (map[y0][x0]==A_star_space)
     for (i=0,j=1,e=1,map[y0][x0]=i;(e)&&(map[y1][x1]==A_star_space);i++,j++)
      for (e=0,y=ymin;y<=ymax;y++)
       for (   x=xmin;x<=xmax;x++)
        if (map[y][x]==i)
        {
        yy=y-1; xx=x; if ((yy>=0)&&(map[yy][xx]==A_star_space)){ map[yy][xx]=j; e=1; if (ymin>yy) ymin=yy; }
        yy=y+1; xx=x; if ((yy<ys)&&(map[yy][xx]==A_star_space)){ map[yy][xx]=j; e=1; if (ymax<yy) ymax=yy; }
        yy=y; xx=x-1; if ((xx>=0)&&(map[yy][xx]==A_star_space)){ map[yy][xx]=j; e=1; if (xmin>xx) xmin=xx; }
        yy=y; xx=x+1; if ((xx<xs)&&(map[yy][xx]==A_star_space)){ map[yy][xx]=j; e=1; if (xmax<xx) xmax=xx; }
        }
*/
    // [A* changed points list]
    // init space for 2 points list
    _freepnt();
    int i0=0,i1=xs*ys,n0=0,n1=0,ii;
    px=new int[i1*2];
    py=new int[i1*2];
    // if start is not on space then stop
    if (map[y0][x0]==A_star_space)
        {
        // init start position to first point list
        px[i0+n0]=x0; py[i0+n0]=y0; n0++; map[y0][x0]=0;
        // search until hit the destination (swap point lists after each iteration and clear the second one)
        for (j=1,e=1;(e)&&(map[y1][x1]==A_star_space);j++,ii=i0,i0=i1,i1=ii,n0=n1,n1=0)
         // test neibours of all points in first list and add valid new points to second one
         for (e=0,ii=i0;ii<i0+n0;ii++)
            {
            x=px[ii]; y=py[ii];
            yy=y-1; xx=x; if ((yy>=0)&&(map[yy][xx]==A_star_space)){ map[yy][xx]=j; e=1; px[i1+n1]=xx; py[i1+n1]=yy; n1++; map[yy][xx]=j; }
            yy=y+1; xx=x; if ((yy<ys)&&(map[yy][xx]==A_star_space)){ map[yy][xx]=j; e=1; px[i1+n1]=xx; py[i1+n1]=yy; n1++; map[yy][xx]=j; }
            yy=y; xx=x-1; if ((xx>=0)&&(map[yy][xx]==A_star_space)){ map[yy][xx]=j; e=1; px[i1+n1]=xx; py[i1+n1]=yy; n1++; map[yy][xx]=j; }
            yy=y; xx=x+1; if ((xx<xs)&&(map[yy][xx]==A_star_space)){ map[yy][xx]=j; e=1; px[i1+n1]=xx; py[i1+n1]=yy; n1++; map[yy][xx]=j; }
            }
        }
    // [reconstruct path]
    _freepnt();
    if (map[y1][x1]==A_star_space) return;
    if (map[y1][x1]==A_star_wall) return;
    ps=map[y1][x1]+1;
    px=new int[ps];
    py=new int[ps];
    for (i=0;i<ps;i++) { px[i]=x0; py[i]=y0; }
    for (x=x1,y=y1,i=ps-1,j=i-1;i>=0;i--,j--)
        {
        px[i]=x;
        py[i]=y;
        if ((y>   0)&&(map[y-1][x]==j)) { y--; continue; }
        if ((y<ys-1)&&(map[y+1][x]==j)) { y++; continue; }
        if ((x>   1)&&(map[y][x-1]==j)) { x--; continue; }
        if ((x<xs-0)&&(map[y][x+1]==j)) { x++; continue; }
        break;
        }
    }
//---------------------------------------------------------------------------
//---------------------------------------------------------------------------
//---------------------------------------------------------------------------

I know it is a bit too much code but it is complete. The important stuff is in member function compute so search for [A* changed points list]. The unoptimized A* (rem-ed) is about 100 times slower.

Code use bitmap from Borland VCL so if you do not have it ignore functions get,set and rewrite them to your input/output gfx style. They just load map from bitmap and draw computed map back to bitmap

Usage:

// init
A_star map;
Graphics::TBitmap *maze=new Graphics::TBitmap;
maze->LoadFromFile("maze.bmp");
maze->HandleType=bmDIB;
maze->PixelFormat=pf32bit;
map.set(maze,0); // walls are 0x00000000 (black)
// this can be called repetitive without another init
map.compute(x0,y0,x1,y1); // map.px[map.ps],map.py[map.ps] holds the path
map.get(maze,0); // this is just for drawing the result map back to bitmap for viewing

for more info about A* see Backtracking in A star

Robillard

this can be speeded up <= 2 times if you cast the path from both start and endpoint until the path joins. but it need bigger points list and slight different coding for path ... The speed up is dependent on the map and added overhead (sometimes can even slow things down)... – Robillard

Thanks very much Spektre. As I never used the language C++, I don't know how to compile and execute the code. I tried with the compiler dev-C++ but I obtain several messages (e.g. DWORD does not name a type). Thanks in advance for your help. – Mickelson

@Mickelson DWORD is 32 bit unsigned int you can use any integer type but if you use signed numbers then you have to change A_star_space and A_star_wall constants from 0xFFFFFFF? to 0x7FFFFFF? ... In your case I would just add typedef unsigned int DWORD; at the start of the source code. Also you will have to rewrite get,set functions to your environment (I use bitmap from borland VCL so just change it to your data type you use...). Also you can try to rewrite this from C++ to your language (I do not recognize it at all...) – Robillard

How does this answer relate to the question? What's the point of this? – Sweeney

@Sweeney it is an example for comparison to rule out that the resolution is too big to still be computed fast. As the OP lacks information on the HW and the runtimes this way it can be seen this can be dome in a relatively short time. So the speed problems are for other reasons. – Robillard

Answer 2

TL;DR: Include in your node list (graph) only the patches (or agents) that are important!

One way to speed things up is to not search over every grid space. A* is a graph search, but seems like most coders just dump every point in the grid into the graph. That's not required. Using a sparse search graph, rather than searching every point on the screen, can speed things up.

Even in a complex maze, you can speed up by only including corners and junctions in the graph. Don't add hallway grids to the open list--seek ahead to find the next corner or junction. This is where pre-processing the screen/grid/map to construct the search graph can save time later.

As you can see in this image from my (rather inefficient) A* model on turtlezero.com, a naive approach creates a lot of extra steps. Any open nodes created in a long straight corridor are wasted:

By eliminating these steps from the graph, the solution could be found hundreds of times faster.

Another sparse graph technique is to use a graph that is gradually less dense the further from the walker. That is, make your search space detailed near the walker, and sparse (fewer nodes, less accurate regarding obstacles) away from the walker. This is especially useful where the walker is moving through detailed terrain on a map that is changing or towards a target that is moving and the route has to be recalculated anyway.

For example, in a traffic simulation where roads may become gridlocked, or accidents occur. Likewise, a simulation where one agent is pursuing another agent on a changing landscape. In these cases, only the next few steps need to be exactly plotted. The general route to the destination can be approximate.

One simple way to implement this is to gradually increase the step size of the walker as the path becomes longer. Disregard obstacles or do a quick line-intersection or tangent test. This gives the walker a general idea of where to go.

An improved path can be recalculated with each step, or periodically, or when an obstacle is encountered.

It may only be milliseconds saved, but milliseconds wasted on the soon-to-change end of the path could be better used providing brains for more walkers, or better graphics, or more time with your family.

For an example of a sparse graph of varying density, see chapter 8 of Advanced Java Programming By David Wallace Croft from APress: http://www.apress.com/game-programming/java/9781590591239

He uses a circular graph of increasing sparseness in a demo tank game with an a* algorithm driving the enemy tanks.

Another sparse graph approach is to populate the graph with only way-points of interest. For example, to plot a route across a simple campus of buildings, only entrances, exits, and corners are important. Points along the side of a building or in the open space between are not important, and can be omitted from the search graph. A more detailed map might need more way-points--such as a circle of nodes around a fountain or statue, or where paved paths intersect.

Here's a diagram showing the paths between waypoints.

This was generated by the campus-buildings-path-graph model by me on turtlezero.com: http://www.turtlezero.com/models/view.php?model=campus-buildings-path-graph

It uses simple netlogo patch queries to find points of interest, like outside and inside corners. I'm sure a somewhat more sophisticated set of queries could deal with things like diagonal walls. But even without such fancy further optimization, the A* search space would be reduced by orders of magnitude.

Unfortunately, since now Java 1.7 won't allow unsigned applets, you can't run the model in the webpage without tweaking your java security settings. Sorry about that. But read the description.

Naaman

Answer 3

A* is two heuristics; Dijkstra's Algorithm & Greedy Search. Dijkstra's Algorithm searches for the shortest path. The Greedy Search looks for the cheapest path. Dijkstra's algorithm is extraordinarily slow because it doesn't take risks. Multiply the effect of the Greedy Search to take more risks.

For example, if A* = Dijkstra + Greedy, then a faster A* = Dijkstra + 1.1 * Greedy. No matter how much you optimize your memory access or your code, it will not fix a bad approach to solving the problem. Make your A* more greedy and it will focus on finding a solution, rather than a perfect solution.

NOTE:

Greedy Search = distance from end
Dijkstra's Algorithm = distance from start

in standard A*, it will seek perfect solutions until reaching an obstacle. This video shows the different search heuristics in action; notice how fast a greedy search can be (skip to 2:22 for A*, 4:40 for Greedy). I myself had a similar issue when I first began with A* and the modified A* I outline above improved my performance exponentially. Moral of the story; use the right tool for the job.

Dictatorial

Answer 4

If you plan to reuse the same map multiple times, some form of pre-processing is usually optimal. Effectively, you work out the shortest distances between some common points, and add them to the graphs as edges, this will typically help a* find a solution more quickly. Although its more difficult to implement.

E.g. you might do this for all motorway routes in a map of the UK, so the search algorithm only has to find a route to a motorway, and from the motorway junctions to its destination.

Velarium

Answer 5

I can't tell what the actual cause of the observed slowlyness might be. Maybe it's just due to shortcomings in efficiency imposed by the programming language at hand. How did you measure your performance? How can we reproduce it?

Besides that, the heuristic (distance metric) being used has a large influence on the amount of exploration that is done in order to find the optimal path and thus also influences the perceived efficiency of the algorithm.

In theory you have to use an admissible heuristic, that is, one that never overestimates the remaining distance. In practice, depending on the complicatedness of the maze, a conservative choice for a 2d grid maze, like manhattan distance, might significantly underestimate the remaining distance. Therefore a lot of exploration is done in areas of the maze far away from the goal. This leads to a degree of exploration that resembles much rather that of an exhaustive search (e.g., Breadth-First Search), than what one would expect from an informed search algorithm.

This might be something to look into.

Also have a look at my related answer here:

• https://mcmap.net/q/107376/-representing-and-solving-a-maze-given-an-image

There I have compared different heuristics used with the basic A-Star algorithm and visualized the results. You might find it interesting.

Sweeney