[發明專利]一種2D網格尋路方法、裝置及存儲介質

在審

• 申請號: 201711316317.6
• 申請日: 2017-12-12
• 公開（公告）號: CN108090155A
• 公開（公告）日: 2018-05-29
• 發明（設計）人: 劉禮葵;陸利民
• 申請（專利權）人: 蘇州蝸牛數字科技股份有限公司
• 主分類號: G06F17/30
• 分類號: G06F17/30;G06Q10/04
• 代理公司: 北京德崇智捷知識產權代理有限公司 11467
• 代理人: 王金雙

1.一種2D網格尋路方法，其特征在于，包括以下步驟：

根據指定的分辨率對2D網格進行規則區塊的劃分；

基于碰撞大小，構建單個規則區塊內的區域并確定鄰接規則區塊內區域的連通關系；

基于區域的連通關系，在區域之間進行分級分段尋路。

2.根據權利要求1所述的2D網格尋路方法，其特征在于，所述基于碰撞大小，構建單個規則區塊內的區域的步驟是：

依次遍歷規則區塊內的格子，若某一格子滿足碰撞大小，則查找與所述某一格子直接相鄰的相同碰撞大小的格子是否已經屬于某個區域，是則將所述某一格子加入所述某個區域，否則新建一個區域并將所述某一格子加入新建的區域。

3.根據權利要求2所述的2D網格尋路方法，其特征在于，進一步包括，

以某一格子為中心，若其周圍的N×N個格子都可行走，則所述某一格子滿足規定的碰撞大小，其中，規定的碰撞大小為N×N個格子，N為正整數。

4.根據權利要求1所述的2D網格尋路方法，其特征在于，所述確定鄰接規則區塊內區域的連通關系的步驟是：

搜索規則區塊邊緣滿足碰撞大小的格子與臨接的規則區塊內的區域是否連通，是則格子所在區域與臨接的規則區塊內的區域連通。

5.根據權利要求1所述的2D網格尋路方法，其特征在于，所述基于區域的連通關系，在區域之間進行分級分段尋路的步驟包括以下步驟：

根據區域的連通關系，在區域之間進行粗糙級別的區域尋路；根據區域尋路的結果，分次地對每段區域路線進行細化尋路。

6.根據權利要求1所述的2D網格尋路方法，其特征在于，還包括步驟：

若修改的格子導致兩個區域之間連通，則將所述兩個區域合并，合并前所述兩個區域與臨接的規則區塊內的區域的連通關系也進行合并。

7.一種計算機可讀存儲介質，其上存儲有計算機程序，其特征在于，該程序被處理器執行時實現權利要求1-6中任一項所述2D網格尋路方法的步驟。

8.一種2D網格尋路裝置，包括存儲器、處理器及存儲在存儲器上并可在處理器上運行的計算機程序，其特征在于，所述處理器執行所述程序時實現權利要求1-6中任一項所述2D網格尋路方法的步驟。