A星算法求解最短路徑

1、A*算法求解最短路徑時(shí)間:2010-03-29 20:00來(lái)源:未知 作者:admin 點(diǎn)擊: 2940次關(guān)于A*算法求解最短路徑的問(wèn)題介紹, 給出了一個(gè)搜索最短路徑的程序。近來(lái)不少的朋友問(wèn)我關(guān)于 A* 算法的問(wèn)題, 目的是寫(xiě)一個(gè)搜索最短路徑的程序. 這個(gè)在鼠標(biāo)控制精靈運(yùn)動(dòng)的游戲中(不算智冠出的那些用鼠標(biāo)充當(dāng)鍵盤(pán)方向鍵的弱智 RPG) 大量使用,尤其是即時(shí)戰(zhàn)略類的. 但是我個(gè)人認(rèn)為 A* 算法只適合處理靜態(tài)路徑求解, 對(duì)即時(shí)戰(zhàn)略游戲中大量對(duì)象堵塞過(guò)道時(shí),疏通交通很難實(shí)現(xiàn)(也不是不能實(shí)現(xiàn), 這需要一個(gè)相當(dāng)好的估價(jià)函數(shù),且不能一次搜索路徑) 我奇怪的是, A* 算法應(yīng)該是算法課的基礎(chǔ)知識(shí)了, 任何

2、一個(gè)系統(tǒng)學(xué)習(xí)過(guò)算法的人都應(yīng)該了解, 本不應(yīng)該我在這里亂寫(xiě)一通, 大家隨意翻本將計(jì)算機(jī)算法的書(shū), 就應(yīng)該看的到. (講 AI 的書(shū)了更是少不了) 不過(guò)既然許多朋友問(wèn)起, 在各個(gè)討論組, BBS 等地方也屢次見(jiàn)人提到, 特花一下午時(shí)間完成本文和附帶的程序, 滿足我們廣大業(yè)余游戲制作愛(ài)好者的求知欲, 專業(yè)人士免看, 以免班門(mén)弄斧 _ 不過(guò)如有錯(cuò)誤一定指出喲. 在介紹 A* 算法前,先提一下廣度優(yōu)先搜索,廣度優(yōu)先搜索就是每次將當(dāng)前狀態(tài)可能發(fā)展的策略逐層展開(kāi),比如一個(gè)地圖中,對(duì)象允許向四個(gè)方向移動(dòng), 那么,就將地點(diǎn)處,對(duì)象向上下左右各移動(dòng)一步, 將四個(gè)狀態(tài)都保存在內(nèi)存中, 然后再?gòu)倪@四個(gè)出發(fā)點(diǎn)向各自的四

3、個(gè)方向再移動(dòng)一步. (當(dāng)然這里可以剔除不合理的移動(dòng)方法,比如不準(zhǔn)向回移動(dòng)) 實(shí)際上, 整個(gè)搜索好似一個(gè)圓形向外展開(kāi),直到到達(dá)目的地,很明顯這樣求解一定能找到最優(yōu)解,但節(jié)點(diǎn)展開(kāi)的數(shù)量是和距離成級(jí)數(shù)增加的, 真的用在游戲中, 玩家會(huì)抱怨內(nèi)存 128M 也不夠用了 _ 而且伴隨待處理節(jié)點(diǎn)數(shù)的增加, 處理速度也會(huì)迅速減慢. 可以說(shuō)這個(gè)算法并不實(shí)用 而 A* 算法實(shí)際是一種啟發(fā)式搜索, 所謂啟發(fā)式搜索,就是利用一個(gè)估價(jià)函數(shù)評(píng)估每次的的決策的價(jià)值, 決定先嘗試哪一種方案. 這樣可以極大的優(yōu)化普通的廣度優(yōu)先搜索. 一般來(lái)說(shuō), 從出發(fā)點(diǎn)(A)到目的地(B)的最短距離是固定的,我們可以寫(xiě)一個(gè)函數(shù) judge()

4、 估計(jì) A 到 B 的最短距離, 如果程序已經(jīng)嘗試著從出發(fā)點(diǎn)(A) 沿著某條路線移動(dòng)到了 C 點(diǎn), 那么我們認(rèn)為這個(gè)方案的 A B 間的估計(jì)距離為 A 到 C 實(shí)際已經(jīng)行走了的距離 H 加上用 judge() 估計(jì)出的 C 到 B 的距離. 如此, 無(wú)論我們的程序搜索展開(kāi)到哪一步, 都會(huì)算出一個(gè)評(píng)估值, 每一次決策后, 將評(píng)估值和等待處理的方案一起排序, 然后挑出待處理的各個(gè)方案中最有可能是最短路線的一部分的方案展開(kāi)到下一步, 一直循環(huán)到對(duì)象移動(dòng)到目的地, 或所有方案都嘗試過(guò)卻沒(méi)有找到一條通向目的地的路徑則結(jié)束. (通常在游戲里還要設(shè)置超時(shí)控制的代碼,當(dāng)內(nèi)存消耗過(guò)大或用時(shí)過(guò)久就退出搜索) 完了

5、? 沒(méi)有.怎么寫(xiě)這個(gè)算法中的估價(jià)函數(shù)非常的重要,如何保證一定能找到最短路徑呢? 充要條件是, 你的估價(jià)函數(shù)算出的兩點(diǎn)間的距離必須小于等于實(shí)際距離. 這個(gè)可以從數(shù)學(xué)上嚴(yán)格證明,有興趣可以自己去查閱相關(guān)資料. 如果你的估價(jià)函數(shù)不滿足這點(diǎn), 就只能叫做 A 算法, 并不能保證最后的結(jié)果是最優(yōu)的,但它可能速度非常的快. 而游戲中我們也不一定非要得到最優(yōu)解的. 但無(wú)疑, 滿足那個(gè)條件的 A* 算法中, 估計(jì)值越接近真實(shí)值的估價(jià)函數(shù)就做的越好, 下面給出的程序,我只使用了一個(gè)相當(dāng)簡(jiǎn)單的估價(jià)函數(shù): 求出兩點(diǎn)中,若無(wú)障礙物的情況下的最短路徑. 如果您想寫(xiě)出快速的尋路算法, 請(qǐng)自己尋找好的估價(jià)函數(shù)吧,有時(shí)間的時(shí)

6、候,我會(huì)對(duì)此另文敘述 ;-) 下面附的程序我已經(jīng)花時(shí)間注釋過(guò)了, 并且調(diào)試通過(guò).如果你經(jīng)過(guò)思索后還是有不懂的地方, 可以來(lái) E-mail 到 cloudwu ;-) 1 /* 云風(fēng)的求解最短路徑代碼 (Cloud Wu's Pathfinding code) 2 * 1999 年 1月 8 日 (1999, Jan 8) 3 * 這段代碼沒(méi)有進(jìn)行任何優(yōu)化(包括算法上的), 但不意味我不知道該怎樣優(yōu)化它， 4 * 它是為教學(xué)目的而做,旨在用易于理解和簡(jiǎn)潔的代碼描述出 A* 算法在求最段路 5 * 徑中的運(yùn)用. 由于很久沒(méi)有摸算法書(shū), 本程序不能保證是純正的 A* 算法 ;-) 6 * 你

7、可以在理解了這段程序的基礎(chǔ)上,按自己的理解寫(xiě)出類似的代碼. 但是簡(jiǎn)單的 7 * 復(fù)制它到你的程序中是不允許的,如果你真要這樣干,請(qǐng)?jiān)谥苯邮褂盟能浖?8 * 文檔中,寫(xiě)上我的名字 ;-) 9 * 有任何的問(wèn)題,或建議請(qǐng) E-mail 到 cloudwu 10 * 歡迎參觀我的主頁(yè) (云風(fēng)工作室) 11 * (你可以在上面找到一些有關(guān)這個(gè)問(wèn)題的討論,和有關(guān)游戲設(shè)計(jì)的其它大量資料) 12 * 13 * 本程序附帶有一個(gè)數(shù)據(jù)文件 map.dat, 保存有地圖的數(shù)據(jù) 14 */ 15 16 / #define NDEBUG 17 #include <stdio.h> 18 #includ

8、e <conio.h> 19 #include <assert.h> 20 #include <stdlib.h> 21 #define MAPMAXSIZE 100 /地圖面積最大為 100x100 22 #define MAXINT 8192 /定義一個(gè)最大整數(shù), 地圖上任意兩點(diǎn)距離不會(huì)超過(guò)它 23 #define STACKSIZE 65536 /保存搜索節(jié)點(diǎn)的堆棧大小 24 25 #define tile_num(x,y) (y)*map_w+(x) /將 x,y 坐標(biāo)轉(zhuǎn)換為地圖上塊的編號(hào) 26 #define tile_x(n) (n)%map_w

9、) /由塊編號(hào)得出 x,y 坐標(biāo) 27 #define tile_y(n) (n)/map_w) 28 29 / 樹(shù)結(jié)構(gòu), 比較特殊, 是從葉節(jié)點(diǎn)向根節(jié)點(diǎn)反向鏈接 30 typedef struct node *TREE; 31 32 struct node 33 int h; 34 int tile; 35 TREE father; 36 ; 37 38 typedef struct node2 *LINK; 39 40 struct node2 41 TREE node; 42 int f; 43 LINK next; 44 ; 45 46 LINK queue; / 保存沒(méi)有處理的行走方

10、法的節(jié)點(diǎn) 47 TREE stackSTACKSIZE; / 保存已經(jīng)處理過(guò)的節(jié)點(diǎn) (搜索完后釋放) 48 int stacktop; 49 unsigned char mapMAPMAXSIZEMAPMAXSIZE; /地圖數(shù)據(jù) 50 int dis_mapMAPMAXSIZEMAPMAXSIZE; /保存搜索路徑時(shí),中間目標(biāo)地最優(yōu)解 51 52 int map_w,map_h; /地圖寬和高 53 int start_x,start_y,end_x,end_y; /地點(diǎn),終點(diǎn)坐標(biāo) 54 55 / 初始化隊(duì)列 56 void init_queue() 57 58 queue=(LINK)ma

11、lloc(sizeof(*queue); 59 queue->node=NULL; 60 queue->f=-1; 61 queue->next=(LINK)malloc(sizeof(*queue); 62 queue->next->f=MAXINT; 63 queue->next->node=NULL; 64 queue->next->next=NULL; 65 66 67 / 待處理節(jié)點(diǎn)入隊(duì)列, 依靠對(duì)目的地估價(jià)距離插入排序 68 void enter_queue(TREE node,int f) 69 70 LINK p=queue

12、,father,q; 71 while(f>p->f) 72 father=p; 73 p=p->next; 74 assert(p); 75 76 q=(LINK)malloc(sizeof(*q); 77 assert(queue); 78 q->f=f,q->node=node,q->next=p; 79 father->next=q; 80 81 82 / 將離目的地估計(jì)最近的方案出隊(duì)列 83 TREE get_from_queue() 84 85 TREE bestchoice=queue->next->node; 86 LINK

13、 next=queue->next->next; 87 free(queue->next); 88 queue->next=next; 89 stackstacktop+=bestchoice; 90 assert(stacktop<STACKSIZE); 91 return bestchoice; 92 93 94 / 釋放棧頂節(jié)點(diǎn) 95 void pop_stack() 96 97 free(stack-stacktop); 98 99 100 / 釋放申請(qǐng)過(guò)的所有節(jié)點(diǎn) 101 void freetree() 102 103 int i; 104 LINK p

14、; 105 for (i=0;i<stacktop;i+) 106 free(stacki); 107 while (queue) 108 p=queue; 109 free(p->node); 110 queue=queue->next; 111 free(p); 112 113 114 115 / 估價(jià)函數(shù),估價(jià) x,y 到目的地的距離,估計(jì)值必須保證比實(shí)際值小 116 int judge(int x,int y) 117 118 int distance; 119 distance=abs(end_x-x)+abs(end_y-y); 120 return distan

15、ce; 121 122 123 / 嘗試下一步移動(dòng)到 x,y 可行否 124 int trytile(int x,int y,TREE father) 125 126 TREE p=father; 127 int h; 128 if (mapyx!=' ') return 1; / 如果 (x,y) 處是障礙,失敗 129 while (p) 130 if (x=tile_x(p->tile) && y=tile_y(p->tile) return 1; /如果 (x,y) 曾經(jīng)經(jīng)過(guò),失敗 131 p=p->father; 132 133 h=

16、father->h+1; 134 if (h>=dis_mapyx) return 1; / 如果曾經(jīng)有更好的方案移動(dòng)到 (x,y) 失敗 135 dis_mapyx=h; / 記錄這次到 (x,y) 的距離為歷史最佳距離 136 137 / 將這步方案記入待處理隊(duì)列 138 p=(TREE)malloc(sizeof(*p); 139 p->father=father; 140 p->h=father->h+1; 141 p->tile=tile_num(x,y); 142 enter_queue(p,p->h+judge(x,y); 143 ret

17、urn 0; 144 145 146 / 路徑尋找主函數(shù) 147 void findpath(int *path) 148 149 TREE root; 150 int i,j; 151 stacktop=0; 152 for (i=0;i<map_h;i+) 153 for (j=0;j<map_w;j+) 154 dis_mapij=MAXINT; 155 init_queue(); 156 root=(TREE)malloc(sizeof(*root); 157 root->tile=tile_num(start_x,start_y); 158 root->h=0

18、; 159 root->father=NULL; 160 enter_queue(root,judge(start_x,start_y); 161 for (;) 162 int x,y,child; 163 TREE p; 164 root=get_from_queue(); 165 if (root=NULL) 166 *path=-1; 167 return; 168 169 x=tile_x(root->tile); 170 y=tile_y(root->tile); 171 if (x=end_x && y=end_y) break; / 達(dá)到目的地

19、成功返回 172 173 child=trytile(x,y-1,root); /嘗試向上移動(dòng) 174 child&=trytile(x,y+1,root); /嘗試向下移動(dòng) 175 child&=trytile(x-1,y,root); /嘗試向左移動(dòng) 176 child&=trytile(x+1,y,root); /嘗試向右移動(dòng) 177 if (child!=0) 178 pop_stack(); / 如果四個(gè)方向均不能移動(dòng),釋放這個(gè)死節(jié)點(diǎn) 179 180 181 / 回溯樹(shù)，將求出的最佳路徑保存在 path 中 182 for (i=0;root;i+) 183

20、pathi=root->tile; 184 root=root->father; 185 186 pathi=-1; 187 freetree(); 188 189 190 void printpath(int *path) 191 192 int i; 193 for (i=0;pathi>=0;i+) 194 gotoxy(tile_x(pathi)+1,tile_y(pathi)+1); 195 cprintf("xfe"); 196 197 198 199 int readmap() 200 201 FILE *f; 202 int i,j; 203 f=fopen("map.dat","r"); 204 assert(f); 205 fscanf(f,"%d,%dn",&map_w,&map_h); 206 for (i=0;i<map_h;i+) 207 fgets(&mapi0,map_w+1,f); 208 fclose(f); 209 start_x=-1,end_x=-1; 210 for (i=0;i<map_h;i+) 211 for (j=0;j<map_w;j+) 212