|
eidiot掛帥出征，攜令牌一枚，率人馬若干，編制如下：
* 尋路元帥
尋路總指揮，執(zhí)“行動(dòng)令牌”一枚和“開啟士兵名錄”、“關(guān)閉將軍名錄”各一冊(cè)。憑“行動(dòng)令牌”調(diào)兵遣將。
* 預(yù)備士兵
由元帥或預(yù)備將軍派往未探索區(qū)域，完成探索任務(wù)后授“開啟”軍銜，晉為“開啟士兵”。發(fā)令派其出者為其“父將”。
* 開啟士兵
前線待命。接到“行動(dòng)令牌”后晉為“預(yù)備將軍”執(zhí)行探索任務(wù)。
* 預(yù)備將軍
憑“行動(dòng)令牌”派出預(yù)備士兵至周圍未探索區(qū)域，并考察周圍“開啟士兵”狀態(tài)，以“父將”之名節(jié)制所派士兵。歸還“行動(dòng)令牌”后授“關(guān)閉”軍銜，晉為“關(guān)閉將軍”。
* 關(guān)閉將軍
后方待命。到達(dá)終點(diǎn)后依次報(bào)告“父將”直至元帥，尋路任務(wù)完成。
為協(xié)調(diào)行動(dòng)，特頒軍令如下：
* “預(yù)備士兵”只能由起點(diǎn)或“父將”所在格橫、豎或斜向移動(dòng)一格，直向（橫、豎）移動(dòng)一格走10步，斜向一格14步（斜向是直向1.414倍，取整數(shù)），抵達(dá)后不得再移動(dòng)。
* 所有人員需記下派出自己的“父將”、從起點(diǎn)到所在位置所走步數(shù)（G）、預(yù)計(jì)到達(dá)終點(diǎn)共需步數(shù)（F）。其中 F = G + H ，F(xiàn) 是從起點(diǎn)經(jīng)過該點(diǎn)到終點(diǎn)的總路程，G 為起點(diǎn)到該點(diǎn)的“已走路程”，H 為該點(diǎn)到終點(diǎn)的“預(yù)計(jì)路程”。G 的計(jì)算是“父將”的 G 值加上“父將”位置到該位置所走步數(shù)，H 的計(jì)算是該點(diǎn)到終點(diǎn)“只走直路”所需路程。
看看戰(zhàn)圖更容易理解，從紅色方格出發(fā)越過黃色障礙到達(dá)藍(lán)色方格：
圖例：
由圖可形象看出何謂“開啟士兵”、“關(guān)閉將軍”：外圍的綠色方格為“開啟士兵”，“前線待命”，隨時(shí)可向外繼續(xù)探索。內(nèi)圍的紫色方格是“關(guān)閉將軍”，從終點(diǎn)開始沿箭頭尋其“父將”直至起點(diǎn)即得最終路徑。
戰(zhàn)前會(huì)議結(jié)束，拔營(yíng)出征。
* 首先派出編號(hào)為0的“預(yù)備士兵”偵查起點(diǎn)，然后升其為“開啟士兵”，列入“開啟士兵名錄”。
* 檢查“開啟士兵名錄”，找出F值最低的“開啟士兵”（只有一名人員，當(dāng)然是0號(hào)），發(fā)出“行動(dòng)令牌”派其執(zhí)行探索任務(wù)。
* 0號(hào)“開啟士兵”接到“行動(dòng)令牌”，晉為“預(yù)備將軍”，探索周圍格子。
* 向周圍8個(gè)格子分別派出編號(hào)為1到8的“預(yù)備士兵”，成為這八名“預(yù)備士兵”的“父將”。
* 八名“預(yù)備士兵”到達(dá)方格后計(jì)算G值和F值，報(bào)告0號(hào)“父將”，晉為“開啟士兵”。
* 0號(hào)“預(yù)備將軍”收到八名“開啟士兵”的報(bào)告，歸還“行動(dòng)令牌”，晉為“關(guān)閉將軍”。
* 元帥收回“行動(dòng)令牌”，將0號(hào)加入“關(guān)閉將軍名錄”，1到8號(hào)加入“開啟士兵名錄”。
此過程結(jié)果如下（方格右上角數(shù)字是人員編號(hào)，左下角是G，右下角是H，左上角是F）：
第一輪探索任務(wù)完成，元帥開始檢查“開啟士兵名錄”。此時(shí)名錄中有8名人員，其中1號(hào)F值最低為40（起點(diǎn)右移一格，G值為10，到終點(diǎn)平移3格，H值為30，F(xiàn) = G + H = 40），向其發(fā)出“行動(dòng)令牌”。
* 1號(hào)“開啟士兵”接到“行動(dòng)令牌”，晉為“預(yù)備將軍”，探索周圍格子。
* 周圍8個(gè)格子中有3格障礙，跳過。一格是“關(guān)閉將軍”，跳過。其余四格是“開啟士兵”，檢查如果從該位置過去G值是否更低。以2號(hào)為例，如果從1 號(hào)過去G值為 10 + 14 = 24 （1號(hào)的G值加上1號(hào)到2號(hào)的步數(shù)）,而2號(hào)原來的G值是10，不做處理（如果此時(shí)發(fā)現(xiàn)新的G值更低，則更新2號(hào)的G值，并改2號(hào)的“父將”為1號(hào)）。其他類推。
* 1號(hào)檢測(cè)完周圍的方格，不需做任何處理，歸還“行動(dòng)令牌”，晉為“關(guān)閉將軍”。
* 元帥收回“行動(dòng)令牌”，將1號(hào)加入“關(guān)閉將軍名錄”。
此過程結(jié)果如下：
第二輪結(jié)束，元帥再次檢查“開啟士兵名錄”。此時(shí)還有7名“開啟士兵”，5號(hào)和8號(hào)的F值都為最低的54，選擇不同尋路的結(jié)果也將不同。元帥選擇了最后加入的8號(hào)“開啟士兵”發(fā)出“行動(dòng)令牌”，過程同上，不贅述，結(jié)果如下：
重復(fù)這個(gè)過程直到某位“關(guān)閉將軍”站到了終點(diǎn)上（或者“開啟士兵”探測(cè)到了終點(diǎn)，這樣更快捷，但某些情況找到的路徑不夠短），亦即找到了路徑；或是“開啟士兵名錄”已空，無法到達(dá)終點(diǎn)。
下面整理一下全過程并翻譯成“標(biāo)準(zhǔn)語言”，首先是各名詞：
* “開啟士兵名錄” - 開啟列表 - open list
* “關(guān)閉將軍名錄” - 關(guān)閉列表 - closed list
* “父將” - 父節(jié)點(diǎn) - parent square
* F - 路徑評(píng)分
* G - 起點(diǎn)到該點(diǎn)移動(dòng)損耗
* H - 該點(diǎn)到終點(diǎn)（啟發(fā)式）預(yù)計(jì)移動(dòng)損耗
尋路過程：
* 1, 將起點(diǎn)放入開啟列表
* 2, 尋找開放列表中F值最低的節(jié)點(diǎn)作為當(dāng)前節(jié)點(diǎn)
* 3, 將當(dāng)前節(jié)節(jié)點(diǎn)切換到關(guān)閉列表
* 4, 如果當(dāng)前節(jié)點(diǎn)是終點(diǎn)則路徑被找到，尋路結(jié)束
* 5, 對(duì)于其周圍8個(gè)節(jié)點(diǎn):
o 如果不可通過或已在關(guān)閉列表，跳過，否則：
o 如果已在開放列表中，檢查新路徑是否更好。如果新G值更低則更新其G值并改當(dāng)前節(jié)點(diǎn)為其父節(jié)點(diǎn)，否則跳過
o 如果是可通過區(qū)域則放入開啟列表，計(jì)算這一點(diǎn)的F、G、H值，并記當(dāng)前節(jié)點(diǎn)為其父節(jié)點(diǎn)
* 6, 如果開啟列表空了，則無法到達(dá)目標(biāo)，路徑不存在。否則回到2
再翻譯成“編程語言”？請(qǐng)看第三部分，鋒芒畢露 - AS3代碼和示例。
經(jīng)典論壇討論:
http://bbs.blueidea.com/thread-2738527-1-1.html
出處：藍(lán)色理想
責(zé)任編輯：elesa
上一頁 A*尋路,二叉堆優(yōu)化及AS3實(shí)現(xiàn) 下一頁 如虎添翼 - 使用二叉堆優(yōu)化
◎進(jìn)入論壇Flash專欄版塊參加討論
|
第 1 頁 
第 2 頁 牛刀小試 - A*尋路算法簡(jiǎn)介
