[發明專利]基于六邊形動態尋路的方法和裝置

有效

• 申請號: 201310741056.8
• 申請日: 2013-12-27
• 公開（公告）號: CN103714253B
• 公開（公告）日: 2017-01-04
• 發明（設計）人: 藺甜甜
• 申請（專利權）人: 北京像素軟件科技股份有限公司
• 主分類號: G06F19/00
• 分類號: G06F19/00
• 代理公司: 北京德琦知識產權代理有限公司11018
• 代理人: 楊春香,宋志強

技術領域

本申請涉及計算機技術，特別涉及基于六邊形動態尋路的方法和裝置。

背景技術

為使本申請便于理解，下面先對本申請涉及的技術術語進行描述：

導航模型：其是由若干個三角形組成的模型，在該導航模型中，帶有一定的數據（比如三角形各個頂點的索引和位置坐標等），該數據能夠幫助一些NPC玩家可以獲得進行A*尋路算法的信息。這里，NPC玩家是指不受用戶控制的系統人物。

占地權重：導航模型中的每一個三角形都可以有自己的權重值。通常，玩家會選擇權重最低的三角形組成的路徑移動，而權重高的或者高于一定值得三角形組成的的路徑就會要求玩家繞道而行不準通過。

如圖1所示的由三角形組成的導航模型，每一個三角形都有自己的權重值（該權重值可以任意設定），且三角形的權重越高則表示越不能在該三角形區域通過。

目前，大多數游戲比如大型多人在線角色扮演（MMOPRG）都是基于A*算法在導航模型中尋路，具體實現時只能根據保存的各個三角形的權重去尋路，無法實時改變每一個三角形的權重值，也無法通過調節三角形的權重值可以改變尋路的結果。

所以，目前大多數游戲因為無法隨時改變尋路中的尋路權重而導致無法動態占地。基于此，一種動態尋路的方法是當前亟待解決的技術問題。

發明內容

本申請提供了基于六邊形動態尋路的方法和裝置，以實現隨時改變尋路中的尋路權重，實現動態占地。

本申請提供的技術方案包括：

一種基于六邊形動態尋路的方法，包括：

在導航模型中確定出AABB區域，所述AABB區域由三維X-Y-Z坐標系內的坐標點AABBMIN和坐標點AABBMAX圍成，所述AABBMIN為所述導航模型在X-Y-Z坐標系中的最小X值、最小Y值、最小Z值組成，所述AABBMAX為所述導航模型在X-Y-Z坐標系中的最大X值、最大Y值、最大Z值組成；

在所述AABB區域內繪制相鄰、且中心點均處于AABB區域內的多個六邊形，并投影各個六邊形到所述導航模型；

遍歷每一六邊形，如果該六邊形中有設定數量N個頂點在所述導航模型中存在對應的焦點，則記錄該六邊形；

將記錄的六邊形組成的圖形作為新的導航模型，基于該新的導航模型進行尋路。

一種基于六邊形動態尋路的裝置，包括：

確定單元，用于在導航模型中確定出AABB區域，所述AABB區域由三維X-Y-Z坐標系內的坐標點AABBMIN和坐標點AABBMAX圍成，所述AABBMIN為所述導航模型在X-Y-Z坐標系中的最小X值、最小Y值、最小Z值組成，所述AABBMAX為所述導航模型在X-Y-Z坐標系中的最大X值、最大Y值、最大Z值組成；

繪制單元，用于在所述AABB區域內繪制相鄰、且中心點均處于AABB區域內的多個六邊形，并投影各個六邊形到所述導航模型；

遍歷單元，用于遍歷每一六邊形，如果該六邊形中有設定數量N個頂點在所述導航模型中存在對應的焦點，則記錄該六邊形；

尋路單元，用于將記錄的六邊形組成的圖形作為新的導航模型，基于該新的導航模型進行尋路。

由以上技術方案可以看出，本發明在進行尋路時，不再基于原有的導航模型尋路，而是基于通過六邊形組成的新的導航模型進行尋路，因為該新的導航模型中的六邊形均有N個頂點在原有導航模型中存在對應的焦點，這就相當于該新的導航模型存在原有導航模型的連接關系，可以應用于尋路。并且，通過基于六邊形的導航模型尋路，能夠保證尋出的路徑比三角形平滑，更加智能。

進一步地，由于該基于六邊形的新導航模型相對于原有的導航模型，可以通過動態調節六邊形的權重修改尋路效果，實現隨時改變尋路中的尋路權重，實現動態占地。

附圖說明

圖1為導航模型示意圖；

圖2為本發明實施例提供的方法流程圖；

圖3為本發明實施例提供的步驟202實現流程圖；

圖4為本發明實施例提供的由六邊形組成的新導航模型示意圖；

圖5為本發明實施例提供的AABB矩形示意圖；

圖6為本發明實施例提供的裝置結構圖。

具體實施方式

為了使本發明的目的、技術方案和優點更加清楚，下面結合附圖和具體實施例對本發明進行詳細描述。

本發明提供的方法能夠實現隨時改變尋路中的尋路權重，實現動態占地。通過動態占地，能夠滿足實時可能更換占地的尋路模式。

下面對本發明提供的方法進行描述：