[發明專利]虛擬空間導航圖自動生成方法與系統及其尋路方法與系統

無效

• 申請號: 201110253549.8
• 申請日: 2011-08-30
• 公開（公告）號: CN102306106A
• 公開（公告）日: 2012-01-04
• 發明（設計）人: 任立群;丁振
• 申請（專利權）人: 盛趣信息技術（上海）有限公司
• 主分類號: G06F9/44
• 分類號: G06F9/44;G09B29/00
• 代理公司: 上海思微知識產權代理事務所(普通合伙) 31237
• 代理人: 菅秀君

技術領域

本發明涉及自動尋路技術，特別是涉及一種虛擬空間導航圖自動生成方法與系統及其尋路方法與系統。

背景技術

在虛擬場景中，從起始點到目標點之間為角色尋找一條最優路徑(尋路)的問題是游戲開發、虛擬現實系統、機器人研究、地理信息系統等領域的基本問題。實時戰略游戲與動作游戲中的尋路方法，一般先根據地形生成一張導航圖，它實際上是一個抽象的圖結構，然后用搜索算法在該圖上搜索得到路徑。在對角色的智能要求較高的游戲客戶端軟件中，目前采用較多的方法是由關卡設計師手工放置路點，然后由計算機根據這些路點和場景的阻擋信息，自動生成連接這些路點的網絡，最后在該網絡上采用搜索算法尋找到一條路徑。

因此，尋路問題的關鍵在于生成這個導航圖，有了這個圖，可以采用人工智能中的經典算法，如A^*算法、Dijkstra算法搜索該圖，從而尋找到一條路徑，而導航圖的生成的關鍵在于路點的設置。

虛擬場景是由地形和空間物體模型構成，以往由關卡設計師手動擺放路點的方案中，在地形擺放路點這個步驟已經可以由計算機來自動完成了。具體，只要控制一個表示路點疏密的因子，這些路點完全可以由計算機均勻的分布到地形上，因為純地形的場景是很簡單的，用二維(2D)網格圖的方法就可以處理，即把地形劃分成二維網格，如四方網格或者六方網格，在每個網格中心放置一個路點即可。而對于空間物體的路點設置，計算機就很難自動生成，這是因為空間物體的屬性是三維的，例如樓梯、橋梁、建筑物等，其很難用網格的方法進行處理，因而，目前采用的方法仍然是人工放置路點的方法。

然而這種人工放置路點的方法存在一定的缺陷，尤其是對于場景巨大而且復雜的情況，人工放置的方法很難及時準確的生成導航圖，而且很容易出錯。

為此，隨著游戲場景的日益絢爛，復雜度日益增加，如何在三維虛擬場景利用計算機自動生成路點，已經成為業界亟待解決的重要問題。

發明內容

有鑒于此，本發明提供一種自動尋路方法與系統及其導航圖自動生成方法與系統，以解決現有三維虛擬場景中導航圖自動生成困難的問題。

為解決以上技術問題，本發明提供一種虛擬空間導航圖自動生成方法，包括：在建立虛擬空間的物體模型的同時，標記該物體模型的屬性；讀取所標記的屬性信息，并利用該屬性信息自動生成導航圖。

進一步的，所述物體模型的屬性包括幾何屬性和物理屬性。

進一步的，所述自動生成導航圖的步驟包括導航圖頂點的生成與導航圖邊的生成步驟。

進一步的，導航圖頂點包括基礎頂點和采樣頂點，基礎頂點直接從所標記的屬性信息中讀取，采樣頂點通過在每兩個可見基礎頂點之間進行采樣獲得。

進一步的，所述采樣頂點通過對每兩個可見基礎頂點的中點進行采樣獲得。

進一步的，所述導航圖邊的生成步驟根據之前生成的導航圖頂點，利用不規則三角網生成導航圖的邊。

本發明另提供一種虛擬空間導航圖自動生成系統，其包括：存儲裝置，其內存儲有虛擬空間的物體模型屬性標記文件；導航圖生成裝置，讀取存儲裝置內的物體模型屬性標記文件，并根據該文件自動生成導航圖。

進一步的，所述物體模型屬性標記文件中包括物體模型的幾何屬性和物理屬性。

進一步的，所述導航圖生成裝置包括頂點生成單元和邊生成單元。

進一步的，所述頂點生成單元包括：頂點集合，其內存儲有從物體模型屬性標記文件中讀取的基礎頂點；采樣單元，在每兩個可見基礎頂點之間進行采樣獲得采樣頂點，并將采樣頂點添加入頂點集合。

進一步的，所述采樣頂點為對應的兩個可見基礎頂點之間的中點。

進一步的，所述邊生成單元讀取頂點集合內的頂點，利用不規則三角網生成導航圖的邊。

本發明還提供一種虛擬空間自動尋路方法，包括：在建立虛擬空間的物體模型的同時，標記該物體模型的屬性；讀取所標記的屬性信息，并利用該屬性信息自動生成導航圖；依據所標記的屬性信息，確定尋路函數，在所生成的導航圖上自動尋路。

進一步的，所述物體模型的屬性包括幾何屬性和物理屬性。

進一步的，所述自動生成導航圖的步驟包括導航圖頂點的生成與導航圖邊的生成步驟。

進一步的，導航圖頂點包括基礎頂點和采樣頂點，基礎頂點直接從所標記的屬性信息中讀取，采樣頂點通過在每兩個可見基礎頂點之間進行采樣獲得。

進一步的，所述采樣頂點通過對每兩個可見基礎頂點的中點進行采樣獲得。