久久人人爽人人,亚洲区免费影片,欧美日韩精品在线观看

一種高效的尋路算法 - B*尋路算法

轉(zhuǎn)：http://qinysong.iteye.com/blog/678941

在此把這個算法稱作B* 尋路算法（Branch Star 分支尋路算法，且與A*對應(yīng)），本算法適用于游戲中怪物的自動尋路，其效率遠(yuǎn)遠(yuǎn)超過A*算法，經(jīng)過測試，效率是普通A*算法的幾十上百倍。

通過引入該算法，一定程度上解決了游戲服務(wù)器端無法進(jìn)行常規(guī)尋路的效率問題，除非服務(wù)器端有獨(dú)立的AI處理線程，否則在服務(wù)器端無法允許可能消耗大量時間的尋路搜索，即使是業(yè)界普遍公認(rèn)的最佳的A*，所以普遍的折中做法是服務(wù)器端只做近距離的尋路，或通過導(dǎo)航站點(diǎn)縮短A*的范圍。

算法原理
本算法啟發(fā)于自然界中真實動物的尋路過程，并加以改善以解決各種阻擋問題。
前置定義：
1、探索節(jié)點(diǎn)：
為了敘述方便，我們定義在尋路過程中向前探索的節(jié)點(diǎn)（地圖格子）稱為探索節(jié)點(diǎn)，起始探索節(jié)點(diǎn)即為原點(diǎn)。（探索節(jié)點(diǎn)可以對應(yīng)為A*中的開放節(jié)點(diǎn)）

2、自由的探索節(jié)點(diǎn)：
探索節(jié)點(diǎn)朝著目標(biāo)前進(jìn)，如果前方不是阻擋，探索節(jié)點(diǎn)可以繼續(xù)向前進(jìn)入下一個地圖格子，這種探索節(jié)點(diǎn)我們稱為自由探索節(jié)點(diǎn)；

3、繞爬的探索節(jié)點(diǎn)：
探索節(jié)點(diǎn)朝著目標(biāo)前進(jìn)，如果前方是阻擋，探索節(jié)點(diǎn)將試圖繞過阻擋，繞行中的探索節(jié)點(diǎn)我們成為繞爬的探索節(jié)點(diǎn)；
算法過程
1、起始，探索節(jié)點(diǎn)為自由節(jié)點(diǎn)，從原點(diǎn)出發(fā)，向目標(biāo)前進(jìn)；
2、自由節(jié)點(diǎn)前進(jìn)過程中判斷前面是否為障礙，
a、不是障礙，向目標(biāo)前進(jìn)一步，仍為自由節(jié)點(diǎn)；
b、是障礙，以前方障礙為界，分出左右兩個分支，分別試圖繞過障礙，這兩個分支節(jié)點(diǎn)即成為兩個繞爬的探索節(jié)點(diǎn)；
3、繞爬的探索節(jié)點(diǎn)繞過障礙后，又成為自由節(jié)點(diǎn)，回到2）；
4、探索節(jié)點(diǎn)前進(jìn)后，判斷當(dāng)前地圖格子是否為目標(biāo)格子，如果是則尋路成功，根據(jù)尋路過程構(gòu)造完整路徑；
5、尋路過程中，如果探索節(jié)點(diǎn)沒有了，則尋路結(jié)束，表明沒有目標(biāo)格子不可達(dá)；

演示如下：

B*與A*算法的性能比較

尋路次數(shù)比較（5秒鐘尋路次數(shù)）

B*與A*性能比較實例
1、無障礙情況
此種情況，根據(jù)以上測試數(shù)據(jù)，B*算法效率是普通A*的44倍（左為A*，右為B*)

2、線形障礙
此種情況，根據(jù)以上測試數(shù)據(jù)，B*算法效率是普通A*的28倍（左為A*，右為B*)

3、環(huán)形障礙
此種情況，根據(jù)以上測試數(shù)據(jù)，B*算法效率是普通A*的132倍（左為A*，右為B*)

4、封閉障礙（目標(biāo)不可達(dá)）
此種情況，根據(jù)以上測試數(shù)據(jù)，B*算法效率是普通A*的581倍（左為A*，右為B*)

衍生算法
通過以上封閉障礙，可以看出，這個方法在判斷地圖上的兩個點(diǎn)是否可達(dá)上，也是非常高效的，在不可達(dá)情況下，時間復(fù)雜度與封閉障礙的周長相當(dāng)，而不是整個地圖的面積。

posted on 2011-04-07 00:07 小王閱讀(4884) 評論(0) 編輯收藏引用所屬分類: 游戲服務(wù)器端開發(fā)

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

常用鏈接

留言簿(16)

隨筆分類(443)

隨筆檔案(381)

Linux

游戲開發(fā)

綜合

最新隨筆

搜索

最新隨筆

最新評論

閱讀排行榜

評論排行榜

只有注冊用戶登錄后才能發(fā)表評論。


相關(guān)文章: C++中使用Lua腳本和lua中調(diào)用c的方法一種高效的尋路算法 - B*尋路算法魔獸世界私服trinitycore2的架構(gòu)——世界對象游戲?qū)ο蟮膶崿F(xiàn) 號稱是目標(biāo)軟件的服務(wù)器架構(gòu)（轉(zhuǎn)載的，不關(guān)我事哦，圖片就不發(fā)了，懶）網(wǎng)絡(luò)游戲中的同步問題一種經(jīng)典的服務(wù)器架構(gòu)（和我的體會太接近了，不得不轉(zhuǎn)）從騰訊QQgame高性能服務(wù)器集群架構(gòu)看“分而治之”與“自治”等分布式架構(gòu)設(shè)計原則無縫世界網(wǎng)游服務(wù)器架構(gòu)的設(shè)計思路（轉(zhuǎn)）網(wǎng)游服務(wù)器架構(gòu)的設(shè)計

網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理