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

有效

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

1.一種基于六邊形動態尋路的方法，其特征在于，該方法包括：

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

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

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

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

2.根據權利要求1所述的方法，其特征在于，所述在AABB區域內繪制相鄰、且中心點均處于AABB區域內的多個六邊形，并投影各個六邊形到所述導航模型包括：

步驟1，繪制AABBMIN和AABBMAX在X-Z軸上圍成的圖形，記為AABB矩形；

步驟2，以AABB矩形中最小X值、最小Z值組成的坐標點AABBmin為中心、半徑為設定值r繪制一個六邊形，將該六邊形的六個頂點進行Y方向投影，以投影至所述導航模型；之后以所述六邊形作為當前六邊形，執行步驟3；

步驟3，判斷AABB矩形內是否還能繪制與當前六邊形相鄰、中心點處于AABB區域內、且半徑為r的六邊形，是則執行步驟4，否則執行步驟5；

步驟4，在僅能繪制一個與當前六邊形相鄰、中心點處于AABB區域內、且半徑為r的六邊形時，繪制與當前六邊形相鄰、中心點處于AABB區域內、且半徑為r的六邊形，將該繪制的六邊形的六個頂點進行Y方向投影，以投影至所述導航模型，并以該繪制的六邊形作為當前六邊形，返回步驟3；在僅能繪制兩個以上與當前六邊形相鄰、中心點處于AABB區域內、且半徑為r的六邊形時，繪制該兩個以上與當前六邊形相鄰、中心點處于AABB區域內、且半徑為r的六邊形，將該繪制的每一六邊形的六個頂點進行Y方向投影，以投影至所述導航模型，并以該繪制的每一六邊形作為當前六邊形，返回步驟3；

步驟5，結束繪制與當前六邊形相鄰、中心點處于AABB區域內、且半徑為r的六邊形，判斷AABB矩形內是否還能繪制與已繪制的任一六邊形相鄰、中心點處于AABB區域內、且半徑為r的六邊形，如果是，以該六邊形為當前六邊形，返回步驟4，如果否，結束流程。

3.根據權利要求1或2所述的方法，其特征在于，所述N為大于等于3，且小于等于6的正整數。

4.根據權利要求1所述的方法，其特征在于，所述基于該新的導航模型進行尋路包括：

針對記錄的每一六邊形設置權重；

基于新的導航模型中每一六邊形設置的權重進行A*尋路。

5.根據權利要求4所述的方法，其特征在于，該方法進一步包括：

當需要占用某一位置時，在所述新的導航模型中查找包含該位置的六邊形；

調節該查找到的六邊形的權重，以使該位置被占用，拒絕玩家從該位置經過。

6.一種基于六邊形動態尋路的裝置，其特征在于，該裝置包括：

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

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

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

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