/ 猿问

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

2019-07-31 10:28:15

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

let search-done? false

let search-path []

let current-node 0

set list-open []

set list-closed []

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

[

if parent-node != 0[

]

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 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 ]

[

[

set color red

]

## 3 回答

• 你可以看到花了~23ms

• 没有多线程（AMD 3.2GHz）

• C ++ 32位应用程序（如果你愿意，可以使用BDS2006 Turbo C ++或Borland C ++ builder 2006）

• 我找到的最慢路径是~44ms（几乎填满整个地图）

//---------------------------------------------------------------------------

//---------------------------------------------------------------------------

//---------------------------------------------------------------------------

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;

}

}

//---------------------------------------------------------------------------

//---------------------------------------------------------------------------

//---------------------------------------------------------------------------

// init

A_star map;

Graphics::TBitmap *maze=new Graphics::TBitmap;

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的算法和贪婪搜索。Djikstra的算法搜索最短路径。贪婪搜索寻找最便宜的路径。Djikstra的算法非常慢，因为它没有冒险。将贪婪搜索的效果倍增以承担更多风险。

`Greedy Search = distance from endDjikstra's Algorithm = distance from start`

RISEBY

• 3 回答
• 0 关注
• 186 浏览

0/150