久久青青草原精品国产软件,久久99国产精品久久久,亚洲欧美日韩精品久久亚洲区

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

轉：http://qinysong.iteye.com/blog/678941

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

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

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

2、自由的探索節點：
探索節點朝著目標前進，如果前方不是阻擋，探索節點可以繼續向前進入下一個地圖格子，這種探索節點我們稱為自由探索節點；

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

演示如下：

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

尋路次數比較（5秒鐘尋路次數）

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

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

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

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

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

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

只有注冊用戶登錄后才能發表評論。
【推薦】100%開源！大型工業跨平臺軟件C++源碼提供，建模，組態！

相關文章: C++中使用Lua腳本和lua中調用c的方法一種高效的尋路算法 - B*尋路算法魔獸世界私服trinitycore2的架構——世界對象游戲對象的實現號稱是目標軟件的服務器架構（轉載的，不關我事哦，圖片就不發了，懶）網絡游戲中的同步問題一種經典的服務器架構（和我的體會太接近了，不得不轉）從騰訊QQgame高性能服務器集群架構看“分而治之”與“自治”等分布式架構設計原則無縫世界網游服務器架構的設計思路（轉）網游服務器架構的設計

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

常用鏈接

留言簿(16)

隨筆分類(441)

隨筆檔案(379)

Linux

游戲開發

綜合

最新隨筆

搜索

最新隨筆

最新評論

閱讀排行榜

評論排行榜