[發(fā)明專(zhuān)利]面向虛擬對(duì)象的路徑規(guī)劃方法、裝置以及計(jì)算機(jī)設(shè)備

在審

• 申請(qǐng)?zhí)枺?/td>: 201910747688.2
• 申請(qǐng)日: 2019-08-14
• 公開(kāi)（公告）號(hào): CN112386914A
• 公開(kāi)（公告）日: 2021-02-23
• 發(fā)明（設(shè)計(jì)）人: 王山月;劉子源
• 申請(qǐng)（專(zhuān)利權(quán)）人: 上海幻電信息科技有限公司
• 主分類(lèi)號(hào): A63F13/56
• 分類(lèi)號(hào): A63F13/56;A63F13/573
• 代理公司: 北京英特普羅知識(shí)產(chǎn)權(quán)代理有限公司 11015
• 代理人: 王勇

本發(fā)明公開(kāi)了一種面向虛擬對(duì)象的路徑規(guī)劃方法，該方法包括：接收尋路請(qǐng)求；獲取虛擬對(duì)象的當(dāng)前位置點(diǎn)的第一位置信息以及目標(biāo)位置點(diǎn)的第二位置信息；根據(jù)所述第一位置信息和第二位置信息中的區(qū)域網(wǎng)格信息標(biāo)記出所述當(dāng)前位置點(diǎn)尋路到所述目標(biāo)位置點(diǎn)的連通區(qū)域的網(wǎng)格地圖，并對(duì)所述連通區(qū)域的網(wǎng)格地圖中的網(wǎng)格進(jìn)行網(wǎng)格合并，得到已合并網(wǎng)格的網(wǎng)格地圖；對(duì)所述已合并網(wǎng)格的網(wǎng)格地圖進(jìn)行路徑打點(diǎn)得到路徑網(wǎng)格點(diǎn)，并繪制成尋路路徑。本發(fā)明還提供一種面向虛擬對(duì)象的路徑規(guī)劃裝置、計(jì)算機(jī)設(shè)備以及計(jì)算機(jī)可讀存儲(chǔ)介質(zhì)。本發(fā)明通過(guò)對(duì)連通區(qū)域的地圖網(wǎng)格進(jìn)行網(wǎng)格合并后進(jìn)行路徑規(guī)劃，從而降低了路徑規(guī)劃過(guò)程的計(jì)算量，提升了尋路效率。

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

本發(fā)明涉及虛擬現(xiàn)實(shí)中路徑規(guī)劃的技術(shù)領(lǐng)域，尤其涉及一種面向虛擬對(duì)象的路徑規(guī)劃方法、裝置、計(jì)算機(jī)設(shè)備及計(jì)算機(jī)可讀存儲(chǔ)介質(zhì)。

背景技術(shù)

隨著游戲技術(shù)的發(fā)展，游戲設(shè)計(jì)過(guò)程中的人工智能也是重要的組成部分，尋路算法是人工智能應(yīng)用于游戲中的最基本問(wèn)題，一個(gè)流暢高效的尋路實(shí)現(xiàn)能夠帶給玩家更好的用戶(hù)體驗(yàn)。

目前絕大部分游戲中的尋路都是采用A*(A-Star)算法來(lái)計(jì)算的，A*算法是一種靜態(tài)路網(wǎng)中求解最短路徑最有效的直接搜索方法，能夠計(jì)算出從一個(gè)點(diǎn)到另一個(gè)點(diǎn)的路線。然而該算法的計(jì)算速度與使用的場(chǎng)景大小有非常大的關(guān)系，場(chǎng)景非常大并且尋路距離非常遠(yuǎn)的情況下，計(jì)算速度也會(huì)急劇下降，因此會(huì)給用戶(hù)一種游戲畫(huà)面卡頓的不良體驗(yàn)。

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

有鑒于此，本發(fā)明提出一種面向虛擬對(duì)象的路徑規(guī)劃方法、裝置、計(jì)算機(jī)設(shè)備及計(jì)算機(jī)可讀存儲(chǔ)介質(zhì)，用于解決游戲大場(chǎng)景地圖且尋路距離非常遠(yuǎn)的情況下執(zhí)行尋路時(shí)因運(yùn)算量大而引起的耗時(shí)嚴(yán)重問(wèn)題。

首先，為實(shí)現(xiàn)上述目的，本發(fā)明提供一種面向虛擬對(duì)象的路徑規(guī)劃方法，所述方法包括：

接收尋路請(qǐng)求；獲取所述尋路請(qǐng)求對(duì)應(yīng)的虛擬對(duì)象的當(dāng)前位置點(diǎn)的第一位置信息以及所述尋路請(qǐng)求中的目標(biāo)位置點(diǎn)的第二位置信息，其中，所述第一位置信息與所述第二位置信息均包括區(qū)域網(wǎng)格信息；根據(jù)所述第一位置信息和第二位置信息中的區(qū)域網(wǎng)格信息標(biāo)記出所述當(dāng)前位置點(diǎn)尋路到所述目標(biāo)位置點(diǎn)的連通區(qū)域的網(wǎng)格地圖；對(duì)所述連通區(qū)域的網(wǎng)格地圖中的網(wǎng)格進(jìn)行網(wǎng)格合并，得到已合并網(wǎng)格的網(wǎng)格地圖；對(duì)所述已合并網(wǎng)格的網(wǎng)格地圖進(jìn)行路徑打點(diǎn)，得到所述當(dāng)前位置點(diǎn)到所述目標(biāo)位置點(diǎn)的路徑網(wǎng)格點(diǎn)，將路徑網(wǎng)格點(diǎn)繪制成尋路路徑。

優(yōu)選地，所述標(biāo)記出所述當(dāng)前位置點(diǎn)尋路到所述目標(biāo)位置點(diǎn)的連通區(qū)域的網(wǎng)格地圖包括：獲取包括所述當(dāng)前位置點(diǎn)和所述目標(biāo)位置點(diǎn)、且所述當(dāng)前位置點(diǎn)到所述目標(biāo)位置點(diǎn)之間未被障礙物完全遮擋的區(qū)域的地圖區(qū)域，并作為所述連通區(qū)域；將所述連通區(qū)域進(jìn)行網(wǎng)格化，并標(biāo)記為所述連通區(qū)域的網(wǎng)格地圖。

優(yōu)選地，所述對(duì)所述連通區(qū)域的網(wǎng)格地圖的網(wǎng)格進(jìn)行網(wǎng)格合并包括：對(duì)所述連通區(qū)域的網(wǎng)格地圖中的未進(jìn)行網(wǎng)格合并的網(wǎng)格進(jìn)行多模式網(wǎng)格合并，從而獲得所有網(wǎng)格都參與網(wǎng)格合并的已合并網(wǎng)格地圖。

優(yōu)選地，所述多模式網(wǎng)格合并包括：對(duì)所述連通區(qū)域的網(wǎng)格地圖先進(jìn)行M*N模式的第一合并操作，以及對(duì)未參與第一合并操作的網(wǎng)格進(jìn)行Q*P模式的第二合并操作。

優(yōu)選地，所述對(duì)所述已合并網(wǎng)格的網(wǎng)格地圖進(jìn)行路徑打點(diǎn)，得到所述當(dāng)前位置點(diǎn)到所述目標(biāo)位置點(diǎn)的路徑網(wǎng)格點(diǎn)包括：分別獲取所述已合并網(wǎng)格的網(wǎng)格地圖上所有的合并網(wǎng)格的代表網(wǎng)格點(diǎn)；采用A*算法對(duì)所述當(dāng)前位置點(diǎn)到所述目標(biāo)位置點(diǎn)之間的所有合并網(wǎng)格的代表網(wǎng)格點(diǎn)進(jìn)行路徑規(guī)劃，從而得到所述當(dāng)前位置點(diǎn)到所述目標(biāo)位置點(diǎn)的路徑網(wǎng)格點(diǎn)。

優(yōu)選地，在所述采用A*算法對(duì)所述當(dāng)前位置點(diǎn)到所述目標(biāo)位置點(diǎn)之間的所有合并網(wǎng)格的代表網(wǎng)格點(diǎn)進(jìn)行路徑規(guī)劃之前，所述方法還包括：通過(guò)方向特性對(duì)每一個(gè)合并網(wǎng)格進(jìn)行相鄰網(wǎng)格標(biāo)記。

優(yōu)選地，通過(guò)相同合并模式執(zhí)行合并操作的合并網(wǎng)格的代表網(wǎng)格點(diǎn)位于所述合并網(wǎng)格的相同部位。

此外，為實(shí)現(xiàn)上述目的，本發(fā)明還提供一種面向虛擬對(duì)象的路徑規(guī)劃裝置，所述裝置包括：