如何在大空间尺度上加速A*算法？

Question

在http://ccl.northwestern.edu/netlogo/models/community/Astardemo中，我使用网络中的节点来定义最小成本路径，从而编写了一个A*算法。代码似乎可以工作，但当我在大空间中使用它时，它太慢了。scales.My景观的范围是1000个补丁x 1000个补丁，1个补丁=1个像素。即使我在400补丁x 400补丁和1个补丁=1像素的情况下减少它，它仍然太慢(我不能修改我的景观低于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

不幸的是，我不知道如何加速这段代码。有没有在大空间尺度上快速计算最小成本路径的解决方案？

非常感谢你的帮助。

Answer 1

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

迷宫1280 x 800 x 32位像素

​

​

如您所见，

• 耗时约23ms
• 非多线程(AMD3.2 the)
• C++ 32位应用程序(BDS2006 Turbo C++或Borland C++ builder 2006，如果您喜欢)
• 我找到的最慢路径约为44ms(几乎填满整个地图)

<代码>F212

我觉得这已经够快了..。

下面是我的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样式。他们只是从bitmap加载map，并将计算出的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

Answer 2

A*是两个启发式算法；Dijkstra算法和贪婪搜索。Dijkstra的算法搜索最短路径。贪婪的搜索寻找最便宜的路径。Dijkstra的算法非常慢，因为它不承担风险。乘以贪婪搜索的效果来承担更多的风险。

例如，如果为A* = Dijkstra + Greedy，则为更快的A* = Dijkstra + 1.1 * Greedy。无论您对内存访问或代码进行了多大程度的优化，都不会修复解决问题的糟糕方法。让你的A*更加贪婪，它会专注于寻找一个解决方案，而不是一个完美的解决方案。

注意：

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

在标准A*中，它将寻求完美的解决方案，直到到达障碍。This video展示了不同的搜索启发式；注意贪婪搜索可以有多快(跳到A*的2:22，贪婪的4:40 )。当我第一次开始使用A*时，我自己也遇到了类似的问题，上面修改后的A* I大纲提高了我的性能。故事的寓意；为工作使用正确的工具。

Answer 3

TL;DR:在您的节点列表(图)中仅包含重要的补丁程序(或代理)！

加快速度的一种方法是不在每个网格空间中搜索。A*是一种图搜索，但似乎大多数程序员只是将网格中的每个点都转储到图中。这不是必需的。使用稀疏搜索图，而不是搜索屏幕上的每个点，可以加快速度。

即使在复杂的迷宫中，您也可以通过在图形中只包含角和交叉点来加快速度。不要将走廊网格添加到开放列表中--向前寻找下一个拐角或交叉口。这是对屏幕/网格/地图进行预处理以构建搜索图的地方，可以在以后节省时间。

从我在turtlezero.com上的(相当低效的) A*模型的图像中可以看到，一种简单的方法会创建很多额外的步骤。在长而直的道路中创建的任何开放节点都将被浪费：

​

​

通过从图表中删除这些步骤，可以将找到解决方案的速度提高数百倍。

另一种稀疏图形技术是使用密度逐渐降低的图形，该图形距离步行者越远。也就是说，使您的搜索空间在步行器附近细化，并在离步行器较远的地方稀疏(节点较少，关于障碍物的准确性较低)。当步行者在地图上移动通过正在变化的详细地形或朝向正在移动的目标，并且无论如何都必须重新计算路线时，这一点特别有用。

例如，在道路可能变得拥堵或发生事故的交通模拟中。同样，一个智能体在不断变化的环境中追求另一个智能体的模拟。在这些情况下，只需精确绘制接下来的几个步骤。到达目的地的一般路线可以是近似值。

实现这一点的一种简单方法是随着路径变长而逐渐增加步行器的步长。忽略障碍物，或者进行快速的线相交或切线测试。这为步行者提供了一个大致的去向。

改进的路径可以通过每一步重新计算，或者周期性地重新计算，或者在遇到障碍时重新计算。

它可能只节省了几毫秒，但在即将改变的道路末端浪费的几毫秒可以更好地用于为更多的步行者提供大脑，或者更好的图形，或者更多的时间与家人在一起。

有关不同密度的稀疏图的示例，请参阅David Wallace Croft所著的Advanced Java Programming的第8章，网址为APress：http://www.apress.com/game-programming/java/9781590591239

他在一个演示坦克游戏中使用了一个循环图来增加稀疏性，并使用a*算法来驱动敌人的坦克。

另一种稀疏图方法是仅使用兴趣点填充图。例如，要绘制一条穿过建筑物组成的简单校园的路线，只有入口、出口和角落才是重要的。沿建筑物侧面或建筑之间空地上的点并不重要，可以从搜索图形中省略这些点。更详细的地图可能需要更多的路点--比如喷泉或雕像周围的一圈节点，或者铺好的小路相交的地方。

这是一个示意图，显示了两个航点之间的路径。

​

​

这是由我在turtlezero.com上创建的校园建筑路径图模型生成的：http://www.turtlezero.com/models/view.php?model=campus-buildings-path-graph

它使用简单的netlogo补丁查询来查找兴趣点，如外部和内部角落。我确信一个更复杂的查询集可以处理像对角线墙这样的事情。但即使没有这种奇特的进一步优化，A*搜索空间也会减少几个数量级。

不幸的是，由于现在的Java1.7不允许未签名的applet，所以你不能在不调整Java安全设置的情况下在网页中运行该模型。真对不起。但请阅读描述。