如何在大空间尺度上加速A *algorithm？
从http://ccl.northwestern.edu/netlogo/models/community/Astardemo ，我使用networking中的节点编码A *algorithm来定义成本最低的path。 该代码似乎工作，但它是太慢，当我在大的空间尺度使用它。我的景观有1000个补丁×1000个补丁的程度，1个补丁= 1个像素。 即使我减less400个修补程序×400个修补程序，1个修补程序= 1个像素，但它仍然太慢（我不能修改我的风景低于400个修补程序×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 不幸的是，我不知道如何加快这个代码。 有没有一个解决scheme来计算大型空间尺度上的成本最低的path？
非常感谢您的帮助。
很好奇，所以我testing了我的A *，这里是我的结果
迷宫1280 x 800 x 32位像素
- 你可以看到它花了23毫秒
- 没有multithreading（AMD 3.2GHz）
- C ++ 32位应用程序（如果你喜欢，BDS2006 Turbo C ++或Borland C ++ builder 2006）
- 我发现最慢的path是〜44ms（几乎填满整个地图）
我觉得那够快
这里是我的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所以search[A* changed points list] 。 未优化的A* （remdeed）大约慢了100倍。
代码使用来自Borland VCL的位图，所以如果你没有它，忽略函数get,set和重写它们到你的input/输出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 *是两个启发式; Djikstra的algorithm和贪婪search。 Djikstra的algorithmsearch最短path。 贪婪的search寻找最便宜的path。 Djikstra的algorithm非常缓慢，因为它不会冒险。 乘以贪婪search的效果，以承担更多的风险。
例如，如果A* = Djikstra + Greedy ，那么更快的A* = Djikstra + 1.1 * Greedy 。 不pipe你优化你的内存访问或你的代码多less，它都不能解决一个坏的方法来解决这个问题。 让你的A *更加贪婪，它将专注于find一个解决scheme，而不是一个完美的解决scheme。
注意：
Greedy Search = distance from end Djikstra's Algorithm = distance from start
在标准A *中，它将寻求完美的解决scheme，直到遇到障碍。 这个video显示了不同的search启发式在行动; 注意贪婪search的速度有多快（A *跳过2:22，贪婪跳到4:40）。 当我刚开始使用A *时，我自己也遇到过类似的问题，上面修改过的A * I概要以指数方式提高了我的性能。 故事的道德启示; 使用正确的工具来完成这项工作。
TL; DR：在节点列表（graphics）中只包含重要的补丁（或代理）！
加快速度的一个方法是不要search每个网格空间。 A *是一个图search，但似乎大多数编码器只是将网格中的每个点转储到图中。 这不是必需的。 使用稀疏的search图表，而不是search屏幕上的每一个点，都可以加快速度。
即使是在一个复杂的迷宫中，也可以通过在图中包含拐angular和交点来加速。 不要将走廊网格添加到公开列表中 – 向前寻找下一个angular落或路口。 这是预处理屏幕/网格/地图来构buildsearch图的地方，以后可以节省时间。
正如你可以从turtlezero.com上我的（相当低效的）A *模型的图片中看到的，一个天真的方法创造了很多额外的步骤。 在一条长长的走廊中创build的任何开放节点都将被浪费：
通过从图中消除这些步骤，解决scheme可以find几百倍的速度。
另一种稀疏graphics技术是使用一个随着步行者的进一步减小密度的graphics。 也就是说，请将您的search空间放在靠近步行者的位置，并且将远离步行者的部分稀疏（较less的节点，不太精确的障碍物）。 如果步行者在正在改变的地图上移动的细节地形，或正在移动的目标以及无论如何都必须重新计算的路线，这一点尤其有用。
例如，在道路可能发生堵塞的交通模拟中，或发生事故。 同样，模拟一个代理正在变化的景观追求另一个代理。 在这些情况下，只有接下来的几个步骤需要精确绘制。 到目的地的一般路线可以是近似的。
实现这一点的一个简单方法是随着path变长，逐步增加步行者的步长。 无视障碍或做一个快速的直线相交或相切testing。 这给了步行者一个总体思路。
每个步骤都可以重新计算一条改进的path，或者定期或者遇到障碍物。
它可能只有毫秒的节省，但在即将改变的path浪费了毫秒，可以更好地用于为更多的步行者提供头脑，或更好的graphics，或更多的时间与你的家人。
有关变化密度的稀疏图的示例，请参见Advanced Java Programming的第8章。来自APress的David Wallace Croft： http : //www.apress.com/game-programming/java/9781590591239
他用一个驾驶敌方坦克的a *algorithm在演示坦克游戏中使用增加稀疏性的圆形图。
另一种稀疏图的方法是只用感兴趣的方式填充图。 例如，要绘制穿过简单的build筑物校园的路线，只有入口，出口和拐angular很重要。 在build筑物的侧面或者在开放空间之间的点不重要，并且可以从search图中省略。 更详细的地图可能需要更多的方法点 – 例如喷泉或雕像周围的节点圆，或铺设的path相交的地方。
这是一个显示航点之间path的图表。
这是由我在turtlezero.com校园build筑物path图模型生成的： http ://www.turtlezero.com/models/view.php?model=campus-buildings-path-graph
它使用简单的netlogo补丁查询来查找兴趣点，如外部和内部angular落。 我相信一些更复杂的查询可以处理像对angular墙这样的事情。 但是，即使没有这样的幻想进一步的优化，A *search空间将会减less数量级。
不幸的是，由于现在Java 1.7不允许未经签名的小程序，所以无法在不调整Java安全设置的情况下在网页中运行模型。 对于那个很抱歉。 但请阅读说明。
如果您打算重复使用相同的地图，某种forms的预处理通常是最佳的。 实际上，您可以计算出一些常用点之间的最短距离，并将它们作为边添加到图中，这通常会帮助*更快地find解决scheme。 虽然实施起来比较困难。
例如，您可能会在英国的地图上为所有高速公路路线执行此操作，因此searchalgorithm只需find通往高速公路的路线，并从高速公路路口通往目的地。
我无法分辨所观察到的缓慢的实际原因可能是什么。 也许这只是由于手头的编程语言带来的效率方面的缺陷。 你如何衡量你的performance？ 我们如何重现呢？
除此之外，所使用的启发式（距离度量）对于为了find最优path而进行的探索量具有很大的影响，因此也影响了algorithm的感知效率。
从理论上说，你必须使用可接受的启发式，也就是说，永远不会高估剩余的距离。 在实践中，根据迷宫的复杂性，像曼哈顿距离这样的二维网格迷宫的保守select可能会显着低估剩余的距离。 因此在远离目标的迷宫地区进行了大量的探索。 这导致一定程度的探索，类似于穷尽search（例如，广度优先search），而不是从期望的知情searchalgorithm。
这可能是要看的东西。
也看看我的相关答案在这里：
在那里我比较了不同的启发式algorithm和基本的A-Staralgorithm，并将结果可视化。 你可能会觉得很有趣。
