http://ccl.northwestern.edu/netlogo/models/community/Astardemo中,我通过使用网络中的节点定义成本最低的路径对A *算法进行了编码。该代码似乎可以正常工作,但是当我在较大的空间比例下使用它时,它的速度太慢了。我的景观范围为1000个色块x 1000个色块,其中1个色块= 1像素。即使以1个色块= 1像素将其缩小为400个色块x 400个色块,它仍然太慢(我无法在400个色块x 400个色块以下修改我的景观)。这是代码:

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

不幸的是,我不知道如何加快这段代码的速度。是否有解决方案可以在大空间范围内快速计算成本最低的路径?

非常感谢您的帮助。

最佳答案

很好奇,所以我测试了我的A *,这是我的结果

迷宫1280 x 800 x 32位像素


您可以看到

  • 大约花了23毫秒
  • 无多线程(AMD 3.2GHz)
  • C++ 32位应用程序(如果愿意,可以使用BDS2006 Turbo C++或Borland C++ builder 2006)
  • 我发现的最慢路径是〜44ms(几乎填满整个 map )

  • 我认为这足够快...

    这是我的A *类的来源:

    //---------------------------------------------------------------------------
    //---------------------------------------------------------------------------
    //---------------------------------------------------------------------------
    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;
            }
        }
    //---------------------------------------------------------------------------
    //---------------------------------------------------------------------------
    //---------------------------------------------------------------------------
    

    我知道这是太多的代码,但它是完整的。重要的是成员函数compute中的内容,因此请搜索[A* changed points list]。未优化的A*(rem-ed)慢大约100倍。

    代码使用Borland VCL中的位图,因此如果没有位图,则忽略函数get,set并将其重写为输入/输出gfx样式。他们只是从map加载bitmap并将计算出的map绘制回bitmap
    用法:
    // 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
    

    有关A *的更多信息,请参见Backtracking in A star

    关于performance - 如何在大空间尺度上加速A *算法?,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/23705233/

    10-12 01:33
    查看更多