前言

伴隨著2021年以來元宇宙的異軍突起，相關(guān)研究得到了學(xué)術(shù)界和工業(yè)界的廣泛關(guān)注，迅速成為各界關(guān)注的焦點(diǎn)話題。

作為游戲人工智能中不可缺少的一個環(huán)節(jié)，尋路已經(jīng)成為影響游戲最終效果的一大重要因素。另一方面，在游戲的設(shè)計環(huán)節(jié)中，難度設(shè)置是否合理對于游戲的用戶體驗起著至關(guān)重要的作用。

蒙特卡洛樹

蒙特卡洛方法是一種基于概率的數(shù)值計算方法，又被稱作計算機(jī)隨機(jī)模擬方法，強(qiáng)化學(xué)習(xí)是機(jī)器學(xué)習(xí)的一種重要方法，蒙特卡洛樹搜索作為強(qiáng)化學(xué)習(xí)中一種常見算法。

它通過不斷在決策空間中選取隨機(jī)樣本來構(gòu)建和更新搜索樹，選擇：蒙特卡洛樹在進(jìn)行節(jié)點(diǎn)選擇時利用UCB選取需要訪問的節(jié)點(diǎn)。擴(kuò)展：當(dāng)訪問節(jié)點(diǎn)為葉節(jié)點(diǎn)時，會判斷當(dāng)前節(jié)點(diǎn)是否已被訪問過，如果已被訪問過，則將當(dāng)前節(jié)點(diǎn)接下來所有可能的動作列為當(dāng)前節(jié)點(diǎn)的子節(jié)點(diǎn)。

在完成以上全部環(huán)節(jié)后，蒙特卡洛樹會通過計算概率的方式判斷節(jié)點(diǎn)的好壞，并在選擇時優(yōu)先選擇勝率較高的節(jié)點(diǎn)。

2015年，DeepMind設(shè)計了基于MCTS和CNN的AlphaGo算法[35]，隨后在比賽中擊敗了人類頂級玩家。從邏輯上，蒙特卡洛搜索樹的搜索過程十分簡單，通過不斷地模擬、反向傳播來構(gòu)建生成搜索樹。

從游戲類型上，蒙特卡洛樹適用于像圍棋，迷宮這樣的在有限步數(shù)內(nèi)可以解決的問題，進(jìn)行路徑搜索，其中f(n)代表從路徑起點(diǎn)到達(dá)路徑終點(diǎn)的預(yù)計總消耗g(n)代表從路徑起點(diǎn)到達(dá)人物當(dāng)前位置的路徑消耗，曼哈頓距離是標(biāo)準(zhǔn)A*算法中最常被使用到的距離表示方法之一。

假設(shè)地圖中相鄰兩個網(wǎng)格的距離為1，曼哈頓距離規(guī)定。

在本文中，我們用歐氏距離來代表距離。人工勢場法是一種基于勢場的局部尋路算法，常用在機(jī)器人尋路及避障中。

人工勢場法存在目標(biāo)點(diǎn)不可達(dá)的問題。在人工勢場中通常障礙物位置的分布并不均勻，可能會存在目標(biāo)點(diǎn)的旁邊分布有障礙物的情況。

針對這個問題，可以采用當(dāng)游戲智能體接近目標(biāo)點(diǎn)時，改變游戲智能體所受斥力函數(shù)，使智能體所受斥力小于引力的方式加以解決。

基于A*算法的改進(jìn)版路徑生成算法

A*尋路算法作為啟發(fā)式尋路算法的代表雖然整體尋路效率相較以往傳統(tǒng)的盲目式尋路得到了較大提升，對于OpenList列表的操作。尋路路徑過于機(jī)械。

由于A*算法尋路的結(jié)果是以節(jié)點(diǎn)為單位的，由于A*尋路算法每輪訪問時都需要遍歷OpenList，從Openlist中選取F值最小的節(jié)點(diǎn)進(jìn)行遍歷并將該節(jié)點(diǎn)從中刪除。A*尋路算法每輪選擇需要遍歷的節(jié)點(diǎn)時都要訪問Openlist，在進(jìn)行節(jié)點(diǎn)插入時，每次會根據(jù)插入節(jié)點(diǎn)值的大小從根節(jié)點(diǎn)開始向下尋找其應(yīng)該處于的位置并插入該節(jié)點(diǎn)。

而在進(jìn)行節(jié)點(diǎn)刪除時，由于在使用Openlist時，我們僅需要距離值最小的節(jié)點(diǎn)作為每次訪問節(jié)點(diǎn)，為了檢驗改進(jìn)存儲結(jié)構(gòu)后的A*算法尋路效果，我們在一張由20*20個節(jié)點(diǎn)組成的地圖上對其進(jìn)行了驗證。

針對上述尋路路徑過于機(jī)械的問題，本文通過將A*算法同人工勢場法結(jié)合的方式進(jìn)行改進(jìn)。將改進(jìn)后的人工勢場法同A*算法結(jié)合后，可以通過由A*算法事先計算所得的全局路徑為其提供全局指引，由于A*算法在整體路徑搜索過程中起到的作用是提供一條全局路徑作為指引。

因此首先應(yīng)用A*尋路算法進(jìn)行全局尋路，在計算全局路徑給尋路體帶來的引力時，首先找到從當(dāng)前節(jié)點(diǎn)到全局路徑最近的位置，具體做法是從全局路徑的初始節(jié)點(diǎn)開始迭代。

值得一提的是，上述算法在真實游戲環(huán)境中運(yùn)行時不同于測試環(huán)境的重要一點(diǎn)在于，在測試環(huán)境中進(jìn)行測試時，我們只會進(jìn)行一次全局路徑搜索并用此結(jié)果為尋路提供指引。

此外，在一些即時策略類游戲如皇室戰(zhàn)爭中，不同卡牌角色對于尋路的要求會有所不同，如像“巨人”角色一旦確定目標(biāo)就不會改變。

此外，在一些即時策略類游戲如皇室戰(zhàn)爭中，不同卡牌角色對于尋路的要求會有所不同，如像“巨人”角色一旦確定目標(biāo)就不會改變，標(biāo)準(zhǔn)A*算法以節(jié)點(diǎn)為單位進(jìn)行尋路，其找到的路徑雖然是所有節(jié)點(diǎn)路徑中最快的一條。

我們還將改進(jìn)后的算法同標(biāo)準(zhǔn)人工勢場法進(jìn)行了對比，我們同樣在一張31*31的二維平面中進(jìn)行實驗，用藍(lán)色線條代表改進(jìn)后的算法路徑，紅色線條代表標(biāo)準(zhǔn)人工勢場法的路徑。

從上述實驗結(jié)果可以發(fā)現(xiàn)，結(jié)合A*算法和人工勢場法之后的算法相較單純的A*算法和人工勢場法尋路效果均得到了明顯提升。

從上述實驗結(jié)果可以發(fā)現(xiàn)，結(jié)合A*算法和人工勢場法之后的算法相較單純的A*算法和人工勢場法尋路效果均得到了明顯提升。在游戲未發(fā)布階段由于要對游戲難度進(jìn)行分析，往往需要提前預(yù)測難度。

鑒于機(jī)器學(xué)習(xí)在游戲領(lǐng)域的良好運(yùn)用，我們以迷宮游戲為例對蒙特卡洛樹在具體游戲中的應(yīng)用加以分析。在迷宮類游戲中，尋路點(diǎn)到終點(diǎn)的距離是影響最終模擬效果的一大重要因素。

我們以迷宮游戲為例對蒙特卡洛樹在具體游戲中的應(yīng)用加以分析。在迷宮類游戲中，尋路點(diǎn)到終點(diǎn)的距離是影響最終模擬效果的一大重要因素，針對改進(jìn)版蒙特卡洛算法，本文通過一個迷宮游戲驗證其能否提高游戲智能體在模擬時的成功率。

第一階段實驗分為障礙物數(shù)量較多及較少兩種情況進(jìn)行。每次實驗重新選擇起點(diǎn)和終點(diǎn)然后分別在兩種情況下各自進(jìn)行實驗并對比成功率。通過本階段實驗數(shù)據(jù)可以得到，在障礙物較少的情況下，UCB改進(jìn)效果較好，有九次模擬成功率優(yōu)于未改進(jìn)之前。

通過本階段實驗可以得到，在尋路距離較近的情況下，UCB改進(jìn)效果較好，有七次模擬成功率優(yōu)于未改進(jìn)之前。

實驗結(jié)束后，我們對產(chǎn)生上述結(jié)果的原因進(jìn)行了分析。從結(jié)論可以看出，改進(jìn)后蒙特卡洛樹的整體模擬效率相較改進(jìn)之前有所提升，為驗證改進(jìn)MCTS后數(shù)據(jù)是否有效，本文將經(jīng)上述過程得到的數(shù)據(jù)通過卷積神經(jīng)網(wǎng)絡(luò)進(jìn)行了訓(xùn)練，其中黑色節(jié)點(diǎn)代表障礙物，黃色代表起點(diǎn)，綠色代表終點(diǎn)。

在使用訓(xùn)練集完成訓(xùn)練后，利用訓(xùn)練好的模型對預(yù)測集中圖像進(jìn)行預(yù)測。在制作訓(xùn)練集時，將同一張地圖看作一個訓(xùn)練集。本章針對在游戲未發(fā)布階段分析游戲難度過程中，采用卷積神經(jīng)網(wǎng)絡(luò)進(jìn)行難度分析時，由MCTS模擬所得訓(xùn)練數(shù)據(jù)成功率較低。

三維游戲場景動態(tài)實現(xiàn)

闖關(guān)迷宮游戲是一款基于Unity3D引擎設(shè)計與實現(xiàn)的單機(jī)游戲，使用C#進(jìn)行游戲開發(fā)，由于本游戲中玩家在不同關(guān)卡面對的游戲地圖都不相同，因此在游戲開始之初需要對各關(guān)卡難度進(jìn)行衡量，方便后續(xù)關(guān)卡設(shè)置。

玩家在游戲中的視角如下圖所示，游戲界面由三部分構(gòu)成，分別是墻體、障礙物以及普通地面，其中墻體中包含一個特殊的節(jié)點(diǎn)，為終點(diǎn)位置。游戲的規(guī)則是每輪游戲玩家需要從起點(diǎn)出發(fā)，在規(guī)定的時間內(nèi)獲得足夠的積分并找到迷宮的出口方能取得勝利。

該迷宮游戲共分為兩種模式，分別是傳統(tǒng)模式及闖關(guān)模式。在傳統(tǒng)模式中，玩家每局的積分都從零開始，玩家在一局比賽失敗后可以選擇重新開始本局游戲。

除以上常規(guī)設(shè)置外，本文還在游戲中設(shè)置了一些道具用于增加游戲的趣味性。游戲中設(shè)置了一些精美的工具，例如能量獲取瓶可以增加玩家的血量，為了更好地提升游戲效果，本文在多處運(yùn)用到了動畫系統(tǒng)。在敵人動畫上，敵人包括多個狀態(tài)，在尋路方面，本迷宮游戲中共包含兩種角色，玩家角色及敵人角色。

玩家角色通過玩家使用鍵盤控制前后左右移動，鼠標(biāo)控制轉(zhuǎn)向，P鍵及空格鍵控制下蹲及跳躍。

“迷宮闖關(guān)”游戲的游戲規(guī)則看似簡單，但在游戲進(jìn)入到高關(guān)卡階段時往往會有很強(qiáng)大的boss出現(xiàn)，一旦玩家陷入到同boss的爭斗中難以擺脫，本章使用Unity3D開發(fā)工具作為引擎，設(shè)計出一個適合檢驗改進(jìn)后算法的迷宮游戲，對前兩章提出的改進(jìn)版A*尋路算法及難度分析算法加以使用。

總結(jié)

游戲難度的設(shè)置是否合理對于玩家的游戲體驗起著至關(guān)重要的作用。過高或過低的難度設(shè)置很有可能會導(dǎo)致玩家在游戲過程中感到沮喪或是無聊，進(jìn)而導(dǎo)致玩家因不好的用戶體驗而退出游戲。

作為游戲人工智能中不可缺少的一大重要環(huán)節(jié)，尋路已經(jīng)成為影響游戲最終效果的一大重要因素，提出了一種基于傳統(tǒng)A*算法的改進(jìn)版游戲路徑生成算法。