[發明專利]基于二叉堆節點排序的A星尋路方法及系統在審
| 申請號： | 201410531309.3 | 申請日： | 2014-10-10 |
| 公開（公告）號： | CN104268420A | 公開（公告）日： | 2015-01-07 |
| 發明（設計）人： | 熊仕勇;林金朝;周敏;潘豪;田航;李沁翰;唐浩;張喜平;聶婧;譚世雨;李楊 | 申請（專利權）人： | 重慶郵電大學 |
| 主分類號： | G06F19/00 | 分類號： | G06F19/00 |
| 代理公司： | 北京眾合誠成知識產權代理有限公司 11246 | 代理人： | 裴娜 |
| 地址： | 400065 重*** | 國省代碼： | 重慶;85 |
| 權利要求書： | 查看更多 | 說明書： | 查看更多 |
| 摘要： | |||
| 搜索關鍵詞： | 基于 二叉 節點 排序 星尋路 方法 系統 | ||
技術領域
本發明涉及一種游戲技術領域，特別涉及一種基于二叉堆節點排序的A星尋路方法及系統。?
背景技術
游戲在業界被稱為第九藝術，成功的游戲更會受到全球玩家推崇。隨著移動互聯網技術的應用以及和中國移動網絡3G、4G增值等業務迅速發展，手機游戲已經展露鋒芒。在游戲軟件中，人工智能是一個重要而又復雜的模塊，而尋路算法是人工智能運用于電子游戲中的最基本問題之一。物體按照某種指定目的地的方式移動其就要求程序必須能夠找到一條從起點到目標點的最佳路徑，這條路徑應該是繞過障礙物并且到達目的地的最短的路徑，完成這個任務最常用的算法就是A星算法。A星作為一種高性價比的尋路算法一直被游戲行業所廣泛使用，很多客戶端游戲和大型網頁游戲中的尋路算法都基于A星算法如：英雄聯盟，魔獸世界，夢幻飛仙等。但是由于手機游戲運行軟件條件和硬件不佳等原因，傳統的A星算法也急需改進，以此提高尋路效率。傳統A星算法需要頻繁維護OPEN和CLOSE表，并且每次都需要對OPEN表中的節點進行排序，而采用冒泡排序的A星算法的平均時間復雜為O(n^2)，執行的效率相當的緩慢，特別是當地圖更大時，反復搜索這么大的列表會嚴重拖慢整個過程。這顯然無法滿足游戲實時性要求較高的特點。?
發明內容
有鑒于此，本發明所要解決的技術問題是提供一種基于二叉堆節點排序的A星尋路方法及系統。?
本發明的目的之一是提出一種基于二叉堆節點排序的A星尋路方法；本發明的目的之二是提出一種基于二叉堆節點排序的A星尋路系統。?
本發明的目的之一是通過以下技術方案來實現的：?
本發明提供的基于二叉堆節點排序的A星尋路方法，包括以下步驟：?
S1：初始化OPEN表、CLOSE表和目標點A，將起始結點S放入OPEN表，CLOSE表置空；?
S2：判斷OPEN表是否為空，如果否，則從OPEN表的表頭取一個結點n；如果是，則結束算法過程；?
S3：判斷結點n是否為目標解A，如果是，則輸出結點n；如果否，則轉入步驟S4；所述目標解是最終要尋找的目標點A；?
S4：將結點n的所有后繼結點展開形成直接關聯子結點，判斷子結點是否在CLOSE表中，如果否，則將子結點放入OPEN表；?
S5：把已經判斷的結點n放入CLOSE表，同時采用以下公式計算結點n的每一個后繼結點的估價值f′(n)；?
f′(n)＝g′(n)+h′(n)；?
其中，f′(n)是估價函數，g′(n)是起始結點到結點n的最短路徑值，h′(n)是結點n到目標的最短路經的啟發值；?
S6：將OPEN表按估價值f′(x)進行堆排序，將估價值f′(x)最小的結點放在OPEN表的表頭，返回步驟S2重復循環。?
進一步，所述OPEN表，用于存儲欲遍歷的下個節點；?
所述CLOSE表，用于存儲已經找到的路徑。?
進一步，所述堆排序采用二叉堆進行排序；?
所述二叉堆是通過以下方式進行的：?
首先獲取OPEN表中節點的估價值f′(x)，將估價值f′(x)最小的節點放置在堆頂端；?
然后從剩余的節點中選擇出估價值最小和次小的節點作為上一個節點的兩個子節點；?
最后分別重復為兩個子節點選擇出估價值最小和次小的節點作為上一個節點的兩個子節點；直到將所有OPEN表中節點排列完成。?
進一步，所述堆排序采用二叉堆進行排序；所述二叉堆是通過以下方式進行的：?
首先獲取OPEN表中節點的估價值f′(x)，將估價值f′(x)最小的節點存儲在一維數組的第一個元素存儲地址中；然后將剩余的節點中的估價值f′(x)最小的節點存儲在一維數組的第二個元素存儲地址中，最后直到完成OPEN表中所有節點的排序。?
本發明的目的之二是通過以下技術方案來實現的：?
本發明提供的基于二叉堆節點排序的A星尋路系統，包括初始化模塊、OPEN表判斷模塊、結點判斷模塊、關聯子結點模塊、結點估價值計算模塊、堆排序模塊；?
所述初始化模塊，用于初始化OPEN表、CLOSE表和目標點A，將起始結點S放入OPEN表，CLOSE表置空；?
所述OPEN表判斷模塊，用于判斷OPEN表是否為空，如果否，則從OPEN表的表頭取一個?結點n；如果是，則結束算法過程；?
所述結點判斷模塊，用于判斷結點n是否為目標解A，如果是，則輸出結點n；如果否，則轉入步驟S4；所述目標解是最終要尋找的目標點A，即從起點找到一條路徑到達目標點；?
該專利技術資料僅供研究查看技術是否侵權等信息，商用須獲得專利權人授權。該專利全部權利屬于重慶郵電大學，未經重慶郵電大學許可，擅自商用是侵權行為。如果您想購買此專利、獲得商業授權和技術合作，請聯系【客服】
本文鏈接：http://www.szxzyx.cn/pat/books/201410531309.3/2.html，轉載請聲明來源鉆瓜專利網。
- 上一篇：噴藥機機架調節機構
- 下一篇：一種連鎖故障多階段動態博弈防御方法
- 同類專利
- 專利分類
G06F 電數字數據處理
G06F19-00 專門適用于特定應用的數字計算或數據處理的設備或方法
G06F19-10 .生物信息學，即計算分子生物學中的遺傳或蛋白質相關的數據處理方法或系統
G06F19-12 ..用于系統生物學的建?；蚍抡妫纾焊怕誓Ｐ突騽討B模型，遺傳基因管理網絡，蛋白質交互作用網絡或新陳代謝作用網絡
G06F19-14 ..用于發展或進化的，例如：進化的保存區域決定或進化樹結構
G06F19-16 ..用于分子結構的，例如：結構排序，結構或功能關系，蛋白質折疊，結構域拓撲，用結構數據的藥靶，涉及二維或三維結構的
G06F19-18 ..用于功能性基因組學或蛋白質組學的，例如：基因型–表型關聯，不均衡連接，種群遺傳學，結合位置鑒定，變異發生，基因型或染色體組的注釋，蛋白質相互作用或蛋白質核酸的相互作用
