[發(fā)明專利]一種2D網(wǎng)格尋路方法、裝置及存儲(chǔ)介質(zhì)

在審

• 申請(qǐng)?zhí)枺?/td>: 201711316317.6
• 申請(qǐng)日: 2017-12-12
• 公開（公告）號(hào): CN108090155A
• 公開（公告）日: 2018-05-29
• 發(fā)明（設(shè)計(jì)）人: 劉禮葵;陸利民
• 申請(qǐng)（專利權(quán)）人: 蘇州蝸牛數(shù)字科技股份有限公司
• 主分類號(hào): G06F17/30
• 分類號(hào): G06F17/30;G06Q10/04
• 代理公司: 北京德崇智捷知識(shí)產(chǎn)權(quán)代理有限公司 11467
• 代理人: 王金雙

一種2D網(wǎng)格尋路方法、裝置及存儲(chǔ)介質(zhì)，所述方法包括步驟：根據(jù)指定的分辨率對(duì)2D網(wǎng)格進(jìn)行規(guī)則區(qū)塊的劃分；基于碰撞大小，構(gòu)建單個(gè)規(guī)則區(qū)塊內(nèi)的區(qū)域并確定鄰接規(guī)則區(qū)塊內(nèi)區(qū)域的連通關(guān)系；基于區(qū)域的連通關(guān)系，在區(qū)域之間進(jìn)行分級(jí)分段尋路。本發(fā)明的2D網(wǎng)格尋路方法、裝置及存儲(chǔ)介質(zhì)，相對(duì)于沒有層次劃分的普通A星算法，在大規(guī)模地圖下，采用層次劃分從而極大地降低尋路響應(yīng)時(shí)間（從秒級(jí)降低到毫秒級(jí)），使尋路可用于實(shí)時(shí)環(huán)境中。而相對(duì)于采用普通的層次劃分的尋路方法，本發(fā)明2D網(wǎng)格尋路方法、裝置及存儲(chǔ)介質(zhì)，還支持動(dòng)態(tài)場(chǎng)景修改以及不同碰撞大小的尋路需求，并且規(guī)劃出來的路徑更自然。

技術(shù)領(lǐng)域

本發(fā)明涉及2D網(wǎng)格尋路技術(shù)領(lǐng)域，特別是涉及一種適用于層次劃分且支持動(dòng)態(tài)場(chǎng)景修改以及不同碰撞大小的2D網(wǎng)格尋路方法、裝置及存儲(chǔ)介質(zhì)。

背景技術(shù)

2D網(wǎng)格及導(dǎo)航網(wǎng)格（NavMesh）是目前游戲業(yè)內(nèi)場(chǎng)景尋路時(shí)常用的數(shù)據(jù)組織方法。其中，2D網(wǎng)格結(jié)構(gòu)簡(jiǎn)單，主要用于平面游戲中；導(dǎo)航網(wǎng)格則常用于不需要支持角色碰撞或者3D尋路的系統(tǒng)中。

尋路過程中常用的搜尋算法為A*算法（俗稱A星算法），A星算法既可用于2D網(wǎng)格的尋路中，也可用于導(dǎo)航網(wǎng)格的尋路中。A星算法應(yīng)用于2D網(wǎng)格中時(shí)，由于其內(nèi)部需要進(jìn)行排序，當(dāng)搜索范圍增大時(shí)，其搜索性能會(huì)急劇下降，導(dǎo)致其不可用于實(shí)時(shí)環(huán)境。

尋路時(shí)，業(yè)內(nèi)一般會(huì)將2D網(wǎng)格劃分為多級(jí)的結(jié)構(gòu)（即層次劃分），層次劃分時(shí)，最精細(xì)的級(jí)別為原始網(wǎng)格信息，往上劃分時(shí)逐漸降低分辨率，同時(shí)維護(hù)新的級(jí)別之間各個(gè)節(jié)點(diǎn)的連通關(guān)系。但是基于層次劃分的方法，很難支持動(dòng)態(tài)場(chǎng)景修改以及不同碰撞大小的尋路需求。

因此，目前亟需一種適用于層次劃分且支持動(dòng)態(tài)場(chǎng)景修改以及不同碰撞大小的2D網(wǎng)格尋路方法。

發(fā)明內(nèi)容

為了解決現(xiàn)有技術(shù)存在的不足，本發(fā)明的目的在于提供一種2D網(wǎng)格尋路方法、裝置及存儲(chǔ)介質(zhì)，可以適用于層次劃分且支持動(dòng)態(tài)場(chǎng)景修改以及不同碰撞大小。

為實(shí)現(xiàn)上述目的，本發(fā)明提供的2D網(wǎng)格尋路方法，包括以下步驟：

根據(jù)指定的分辨率對(duì)2D網(wǎng)格進(jìn)行規(guī)則區(qū)塊的劃分；

基于碰撞大小，構(gòu)建單個(gè)規(guī)則區(qū)塊內(nèi)的區(qū)域并確定鄰接規(guī)則區(qū)塊內(nèi)區(qū)域的連通關(guān)系；

基于區(qū)域的連通關(guān)系，在區(qū)域之間進(jìn)行分級(jí)分段尋路。

進(jìn)一步地，所述基于碰撞大小，構(gòu)建單個(gè)規(guī)則區(qū)塊內(nèi)的區(qū)域的步驟是：

依次遍歷規(guī)則區(qū)塊內(nèi)的格子，若某一格子滿足碰撞大小，則查找與所述某一格子直接相鄰的相同碰撞大小的格子是否已經(jīng)屬于某個(gè)區(qū)域，是則將所述某一格子加入所述某個(gè)區(qū)域，否則新建一個(gè)區(qū)域并將所述某一格子加入新建的區(qū)域。

進(jìn)一步地，以某一格子為中心，若其周圍的N×N個(gè)格子都可行走，則所述某一格子滿足規(guī)定的碰撞大小，其中，規(guī)定的碰撞大小為N×N個(gè)格子，N為正整數(shù)。

進(jìn)一步地，所述確定鄰接規(guī)則區(qū)塊內(nèi)區(qū)域的連通關(guān)系的步驟是：

搜索規(guī)則區(qū)塊邊緣滿足碰撞大小的格子與臨接的規(guī)則區(qū)塊內(nèi)的區(qū)域是否連通，是則格子所在區(qū)域與臨接的規(guī)則區(qū)塊內(nèi)的區(qū)域連通。

進(jìn)一步地，所述基于區(qū)域的連通關(guān)系，在區(qū)域之間進(jìn)行分級(jí)分段尋路的步驟包括以下步驟：

根據(jù)區(qū)域的連通關(guān)系，在區(qū)域之間進(jìn)行粗糙級(jí)別的區(qū)域?qū)ぢ?；根?jù)區(qū)域?qū)ぢ返慕Y(jié)果，分次地對(duì)每段區(qū)域路線進(jìn)行細(xì)化尋路。

進(jìn)一步地，所述的2D網(wǎng)格尋路方法，還包括步驟：

若修改的格子導(dǎo)致兩個(gè)區(qū)域之間連通，則將所述兩個(gè)區(qū)域合并，合并前所述兩個(gè)區(qū)域與臨接的規(guī)則區(qū)塊內(nèi)的區(qū)域的連通關(guān)系也進(jìn)行合并。