?? 新建 文本文檔 (2).txt
字號:
A**尋路算法簡介
閱讀本文以前，可能大家已經接觸過A*算法，如果沒有，那也沒關系。想了解A*算法的更多內容，可以去http://articles.gameres.com/搜索A*，那里有足夠的文章讓您理解A*算法的基本思路。
一、A**算法的基本思想
參考A*算法的文章《A* Pathfinding for Beginners》，我同樣使用這個例題作為開頭：
0 1 2 3 4 5 6
0
圖1.1
1
2
3
4
如圖，綠色是起點，紅色是終點，藍色是障礙物，這樣的地圖可以在內存中表示成一個二維數組：
0 0 0 0 0 0 0
0 0 0 1 0 0 0
0 0 0 1 0 0 0
0 0 0 1 0 0 0
0 0 0 0 0 0 0
x1=1 y1=2
x2=5 y2=2
暫時限定不允許出界。允許橫走、直走和斜走，求最短的到達目標的路徑。A**算法的基本思路就是：首先求出每一點到達終點的最短路徑的長度（下面簡稱值），然后本著總是往值更少的位置走的原則，則走過的一定是最短路徑。
首先，我們設置Value數組，用于記錄每點的值。在未計算之前，全部標志為-1，就得到如下的數組：
-1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1
毫無疑問，終點離終點的距離是0，所以(5,2)的值可以置為0。因此值數組內容變成這樣：
-1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 0 -1
-1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1
這樣，又由于它周圍的點距離終點的距離不會超過它離終點距離+1，因此值數組變成這樣：
-1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 1 1 1
-1 -1 -1 -1 1 0 1
-1 -1 -1 -1 1 1 1
-1 -1 -1 -1 -1 -1 -1
-1 -1 -1 2 2 2 2
-1 -1 -1 -1 1 1 1
-1 -1 -1 -1 1 0 1
-1 -1 -1 -1 1 1 1
-1 -1 -1 2 2 2 2
要注意到，(3,1)、(3,2)、(3,3)三個點，雖然在點(4,2)周圍，但是由于這三個點不可到達，所以搜索時不應改變他們的值。
-1 -1 3 2 2 2 2
-1 -1 3 -1 1 1 1
-1 -1 -1 -1 1 0 1
-1 -1 3 -1 1 1 1
-1 -1 3 2 2 2 2
-1 4 3 2 2 2 2
-1 4 3 -1 1 1 1
-1 4 4 -1 1 0 1
-1 4 3 -1 1 1 1
-1 4 3 2 2 2 2
5 4 3 2 2 2 2
5 4 3 -1 1 1 1
5 4 4 -1 1 0 1
5 4 3 -1 1 1 1
5 4 3 2 2 2 2
這樣，我們得到起點(1,2)到達目標需要4步，又由于(1,2)-(2,1)-(3,0)-(4,1)-(5,2)是一條值遞減的路徑，因此它也是從(1,2)點到達(5,2)點的最短路徑。
換句話說，由于(1,2)點的值為4，(2,1)點的值為3，因此(1,2)點走到終點比(2,1)多需要一步，所以(1,2)點走向(2,1)點一定是更接近而不是更遠離終點，這樣走完全可以成為最短路徑的一步。接下來每一步都保證值遞減，也就是說經過了4步之后，到達的地點值一定為0，而地圖上唯一值為0的位置就是終點，即4步后到達終點。
以上算法仍然屬于廣度優先算法，但它和經典廣度優先算法的區別在于，經典廣度優先算法運用結點的方式記錄每個點的坐標，和走到這個點的父結點的坐標，而這個算法僅僅記錄每點到終點的距離。當找到目標時，經典廣度優先尋找終點結點的祖先結點并依次記錄下來，而以上算法則不斷在當前點周圍尋找比當前點更接近終點的點，并且移動到該點。
：）當然，到目前為止，還沒有看出我所謂A**算法有任何優勢，但我可以用這樣一種非廣度優先方法來實現程序：
反復按順序搜索整個數組，如果發現有已求值的點，它周圍有未求值或者已知值但不如經過當前點的路線，則用新值覆蓋下該點。知道找不到這樣的點為止代碼如下：
#define p(a,x,y) *(a+(x)+(y)*Width) //為了更直觀
int Width,Height,Size; //寬、高、總大小
char *MAP; //儲存地圖信息的數組
int *Value; //儲存搜索信息的數組
int x1,y1,x2,y2;
void WORK_TDZL1()
{
int i,j,
b; //用于標記
for (i=0;i<Size;i++)
*(Value+i)=-1; //搜索前把所有位置標志為-1
p(Value,x2,y2)=0; //把終點標記為0
b=1;
while (b)
{
b=0;
for (i=0;i<Width;i++)
for (j=0;j<Height;j++)
if (p(Value,i,j)>-1)
{
int x,y,k;
for (k=0;k<8;k++)
{
x=i;y=j;
switch (k)
{
case 0:x++;break;
case 1:x--;break;
case 2:y++;break;
case 3:y--;break;
case 4:x++;y++;break;
case 5:x++;y--;break;
case 6:x--;y++;break;
case 7:x--;y--;break;
default:break;
}
if ((x<0)||(y<0)||(x>Width)||(y>Height)) continue;
if ((p(MAP,x,y)==0)&&((p(Value,x,y)==-1)||(p(Value,x,y)>p(Value,i,j)+1)))
{
p(Value,x,y)=p(Value,i,j)+1;
b=1;
}
}
}
}
if (p(Value,x1,y1)>-1) //輸出結果
{
int x,y,k;
printf("Total %d step\n",p(Value,x1,y1));
i=x1;j=y1;
while ((i!=x2)||(j!=y2))
{
for (k=0;k<8;k++)
{
x=i;y=j;
switch (k)
{
case 0:x++;break;
case 1:x--;break;
case 2:y++;break;
case 3:y--;break;
case 4:x++;y++;break;
case 5:x++;y--;break;
case 6:x--;y++;break;
case 7:x--;y--;break;
default:break;
}
if ((x<0)||(y<0)||(x>Width)||(y>Height)) continue;
if (p(Value,x,y)==p(Value,i,j)-1)
{
i=x;j=y;break;
}
}
//每次在這里取i和j的值
}
return;
}
printf("No answer!\n");
}
這段程序的意思是：首先，我們知道終點到終點的距離為0，然后不斷掃描整幅地圖，如果發現某點A的值已知，而它周圍的某點B值未知且非障礙物，或者它B的值大于A的值+1，則將B的值設為A的值+1。因為A點可達，且B點非障礙物，因此B點一定可達并且值不會大于A點的值+1，因為由A點到B點為一可行策略。
然而，運行如上程序時我們會發現，它對付從左上到右下的路徑非常在行，但是對于含由U型路徑或回型路徑甚至僅僅是從右下到左上的路徑，它會變得非常緩慢。于是將程序優化如下：
void WORK_TDZL3()
{
int i,j,
b; //用于標記
for (i=0;i<Size;i++)
*(Value+i)=-1;
p(Value,x2,y2)=0;
b=1;
while (b)
{
b=0;
for (i=0;i<Width;i++)
for (j=0;j<Height;j++)
if (p(Value,i,j)>-1)
{
int x,y,k;
for (k=0;k<3;k++)
{
x=i;y=j;
switch (k)
{
case 0:y++;break;
case 1:x++;y++;break;
default:break;
}
if ((x<0)||(y<0)||(x>Width)||(y>Height)) continue;
if ((p(MAP,x,y)==0)&&((p(Value,x,y)==-1)||(p(Value,x,y)>p(Value,i,j)+1)))
{
p(Value,x,y)=p(Value,i,j)+1;
b=1;
}
}
}
for (i=0;i<Width;i++)
for (j=Height-1;j>=0;j--)
if (p(Value,i,j)>-1)
{
int x,y,k;
for (k=0;k<3;k++)
{
x=i;y=j;
switch (k)
{
case 0:x++;break;
case 1:x++;y--;break;
default:break;
}
if ((x<0)||(y<0)||(x>Width)||(y>Height)) continue;
if ((p(MAP,x,y)==0)&&((p(Value,x,y)==-1)||(p(Value,x,y)>p(Value,i,j)+1)))
{
p(Value,x,y)=p(Value,i,j)+1;
b=1;
}
}
}
for (i=Width-1;i>=0;i--)
for (j=0;j<Height;j++)
if (p(Value,i,j)>-1)
{
int x,y,k;
for (k=0;k<3;k++)
{
x=i;y=j;
switch (k)
{
case 0:x--;break;
case 1:x--;y++;break;
default:break;
}
if ((x<0)||(y<0)||(x>Width)||(y>Height)) continue;
if ((p(MAP,x,y)==0)&&((p(Value,x,y)==-1)||(p(Value,x,y)>p(Value,i,j)+1)))
{
p(Value,x,y)=p(Value,i,j)+1;
b=1;
}
}
}
for (i=Width-1;i>=0;i--)
for (j=Height-1;j>=0;j--)
if (p(Value,i,j)>-1)
{
int x,y,k;
for (k=0;k<3;k++)
{
x=i;y=j;
switch (k)
{
case 0:y--;break;
case 1:x--;y--;break;
default:break;
}
if ((x<0)||(y<0)||(x>Width)||(y>Height)) continue;
if ((p(MAP,x,y)==0)&&((p(Value,x,y)==-1)||(p(Value,x,y)>p(Value,i,j)+1)))
{
p(Value,x,y)=p(Value,i,j)+1;
b=1;
}
}
}
}
if (p(Value,x1,y1)>-1)
{
//輸出結果
int x,y,k;
printf("Total %d step\n",p(Value,x1,y1));
i=x1;j=y1;
while ((i!=x2)||(j!=y2))
{
for (k=0;k<8;k++)
{
x=i;y=j;
switch (k)
{
case 0:x++;break;
case 1:x--;break;
case 2:y++;break;
case 3:y--;break;
case 4:x++;y++;break;
case 5:x++;y--;break;
case 6:x--;y++;break;
case 7:x--;y--;break;
default:break;
}
if ((x<0)||(y<0)||(x>Width)||(y>Height)) continue;
if (p(Value,x,y)==p(Value,i,j)-1)
{
i=x;j=y;break;
}
}
//每次在這里取i和j的值
}
return;
}
printf("No answer!\n");
}
：）由于時間關系在此不再詳述，測試程序、代碼及測試數據將在近期上傳，比A*算法究竟好上幾百倍大家自己體會吧，這可是即時對戰游戲設計者夢寐以求的算法哦。本算法的特點是不怕地圖大，不怕回形路，另外，本算法還有一個最大好處，就是對目標的一次計算，地圖上所有點到達目標的路徑都可以很方便的求出。當然具體運用時還得修改不少地方，但相信我的這篇文章你對你有所幫助。
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -