[發(fā)明專利]一種尋路網(wǎng)格的多線程更新方法

有效

• 申請?zhí)枺?/td>: 202011205490.0
• 申請日: 2020-11-02
• 公開（公告）號: CN112295225B
• 公開（公告）日: 2021-08-10
• 發(fā)明（設(shè)計）人: 劉沐寒
• 申請（專利權(quán)）人: 不鳴科技（杭州）有限公司
• 主分類號: A63F13/5378
• 分類號: A63F13/5378;A63F13/35
• 代理公司: 杭州快知知識產(chǎn)權(quán)代理事務(wù)所(特殊普通合伙) 33293
• 代理人: 楊冬玲

本發(fā)明公開了一種尋路網(wǎng)格的多線程更新方法，包括獲取尋路網(wǎng)格塊信息，所述尋路網(wǎng)格塊信息包括尋路網(wǎng)格塊坐標(biāo)、高度場數(shù)據(jù)；基于所述尋路網(wǎng)格塊坐標(biāo)向N個子線程發(fā)起更新任務(wù)流程，N為大于1的整數(shù)，本發(fā)明彌補了單線程中只有上一尋路網(wǎng)格塊整合入尋路網(wǎng)格之后才開始下一尋路網(wǎng)格塊的計算，在現(xiàn)今計算機多線程計算架構(gòu)已經(jīng)普及的情況下，采用多線程更新方法大大提升了效率，從而能夠有效緩解單線程延時過高的問題。

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

本發(fā)明涉及尋路技術(shù)領(lǐng)域，尤其涉及一種尋路網(wǎng)格的多線程更新方法。

背景技術(shù)

隨著電子游戲的發(fā)展，為了使用戶有更好的游戲體驗，內(nèi)容越來越豐富，游戲地圖越來越大，因此游戲當(dāng)中每一幀的變化的延遲性變越來越重要，游戲中的實時尋路業(yè)務(wù)因其地圖面積的增大，則需要對其延遲性提出一個很高的要求。

一個導(dǎo)航網(wǎng)格是由多個凸多邊形組成的，以網(wǎng)格為單位，在地圖中的兩個點，在忽略地圖高度的情況下，可以直線到達(dá)；但是如果兩個位于不同高度的空間，那么將會利用導(dǎo)航網(wǎng)絡(luò)和尋路算法算出需要經(jīng)過的網(wǎng)格，再算出具體路徑。

目前，現(xiàn)有技術(shù)中尋路技術(shù)通常以單線程更新的方式躲避障礙物，并且修改局部網(wǎng)格塊需要重新生成整片尋路網(wǎng)格，此方式就會對延遲性造成很大的影響，不能及時更新突發(fā)情況帶來的地圖的變化。

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

本發(fā)明提供的一種尋路網(wǎng)格的多線程更新方法，旨在解決現(xiàn)有技術(shù)中采用單線程更新尋路網(wǎng)格而導(dǎo)致延時過高的問題。

為實現(xiàn)上述目的，本發(fā)明采用以下技術(shù)方案：

本發(fā)明的一種尋路網(wǎng)格的多線程更新方法，包括以下步驟：

獲取尋路網(wǎng)格塊信息，所述尋路網(wǎng)格塊信息包括尋路網(wǎng)格塊坐標(biāo)；

基于所述尋路網(wǎng)格塊坐標(biāo)向N個子線程發(fā)起更新任務(wù)流程，N為大于1的整數(shù)。

首先定義尋路生成交換信息，包括：尋路網(wǎng)格塊坐標(biāo)、高度場數(shù)據(jù)、成功信號。我們的方法流程為：根據(jù)多線程計算架構(gòu)線程數(shù)提前分配對應(yīng)的尋路生成交換信息。主線程收集障礙物影響的尋路網(wǎng)格塊坐標(biāo)至對應(yīng)的尋路生成交換信息中。向N個子線程上發(fā)起尋路網(wǎng)格更新任務(wù)流程，并等待N個子線程完成信號。各線程根據(jù)分配的尋路生成交換信息中的尋路網(wǎng)格塊坐標(biāo)，分別解壓對應(yīng)坐標(biāo)的壓縮高度場數(shù)據(jù)，在壓縮高度場上標(biāo)記障礙物，計算生成新的尋路網(wǎng)格塊存回尋路生成交換信息，發(fā)送完成信號，主線程收到所有子線程的完成信號后，依次將成功生成的尋路網(wǎng)格塊整合進(jìn)尋路網(wǎng)格。

作為優(yōu)選，獲取尋路網(wǎng)格塊信息，所述尋路網(wǎng)格塊信息包括尋路網(wǎng)格塊坐標(biāo)，包括：

獲取障礙物信息，所述障礙物信息包括障礙物位置和幾何信息；

根據(jù)所述障礙物信息，獲取與所述障礙物信息有重疊的所述尋路網(wǎng)格塊信息，所述尋路網(wǎng)格塊信息還包括高度場數(shù)據(jù)和完成信號，其中，所述高度場數(shù)據(jù)是由多個體素構(gòu)成。

作為優(yōu)選，基于所述尋路網(wǎng)格塊坐標(biāo)向N個子線程發(fā)起更新任務(wù)流程，N為大于1的整數(shù)，包括：

基于所述高度場數(shù)據(jù)，標(biāo)記障礙物覆蓋區(qū)域，所述障礙物覆蓋區(qū)域用于表示不可通行的體素；

在子線程中，根據(jù)所述障礙物覆蓋區(qū)域，計算生成新的尋路網(wǎng)格塊，并向主線程發(fā)送完成信號；

主線程接收完所述N個子線程的完成信號后，依次將所述新的尋路網(wǎng)格塊整合進(jìn)所述尋路網(wǎng)格塊信息。

作為優(yōu)選，所述高度場數(shù)據(jù)，包括：

根據(jù)可通行條件標(biāo)記場景高度場獲得高度場數(shù)據(jù)，所述可通行條件包括人物高度、半徑、可跨越臺階高度。

一種尋路網(wǎng)格的多線程更新裝置，包括：

獲取模塊：用于獲取尋路網(wǎng)格塊信息，所述尋路網(wǎng)格塊信息包括尋路網(wǎng)格塊坐標(biāo)；