一. 人工智能的定義

人工智能（AI, Artificial Intelligent）,指的是通過算法編程使計(jì)算機(jī)模仿人完成一些像人一樣的任務(wù)，同時(shí)在執(zhí)行任務(wù)時(shí)模仿人的思維和智慧，甚至通過大量學(xué)習(xí)訓(xùn)練積累學(xué)習(xí)經(jīng)驗(yàn)，提高自身解決問題的智慧和效率。人工應(yīng)用廣泛，像智能交通，人工智能機(jī)器人，智能家電等，通過模仿人的智慧代替人類完成一些重復(fù)性工作。人工智能目前依舊在人工的階段，即計(jì)算機(jī)的智能仍然在人類人工下可控可預(yù)見的范圍內(nèi)運(yùn)行，人工智能實(shí)際上是在大量的邏輯運(yùn)算和大量的數(shù)據(jù)輸入處理基礎(chǔ)上進(jìn)行實(shí)現(xiàn)，人工智能需要大量的數(shù)據(jù)輸入訓(xùn)練才能使其更加智能化。典型的近日谷歌的人工智能Alpha狗即進(jìn)行了成千上萬(wàn)次的圍棋棋局訓(xùn)練才得以打敗世界圍棋冠軍李世石。與人類智能不同的是人工智能依賴自身的強(qiáng)大計(jì)算速度大量的學(xué)習(xí)而智能化，人類智能則可通過少量學(xué)習(xí)而理解更多相關(guān)的事物。在目前人類對(duì)自身智能了解仍舊不夠充分的情況下，人工智能依舊依賴于人工處理上。

二. 游戲中的AI

游戲中尤其是虛擬現(xiàn)實(shí)游戲追求創(chuàng)建一個(gè)盡可能真實(shí)的虛擬世界環(huán)境，虛擬世界中需要設(shè)置很多NPC（Non-Player Character）人物與玩家交互互動(dòng)，這需要NPC人物具有智能與玩家更自然真實(shí)的交流，幫助玩家順利進(jìn)行游戲，提高游戲真實(shí)性體驗(yàn)。NPC的智能動(dòng)作是一系列的有限狀態(tài)集合，其連貫合理的狀態(tài)的改變實(shí)現(xiàn)與玩家交互。NPC和玩家共同組成游戲中的角色群體。

另一方面，游戲中AI技術(shù)的一個(gè)核心的內(nèi)容是游戲中角色的智能尋路，人物能夠像人一樣避開障礙物選擇合理的路徑從起點(diǎn)到達(dá)目的地，或者引導(dǎo)玩家到達(dá)虛擬場(chǎng)景中的指定地點(diǎn)。游戲中的尋路算法主要分盲目式搜索和啟發(fā)式搜索兩種，同圖論中的最短路徑問題相聯(lián)系，在圖論的數(shù)據(jù)結(jié)構(gòu)上進(jìn)行實(shí)現(xiàn)。游戲?qū)ぢ匪惴ㄖ凶罨咀畛墒斓氖茿 Start啟發(fā)式函數(shù)尋路算法，市面上有大量RPG角色游戲以及戰(zhàn)略游戲等當(dāng)中的智能尋路皆使用到基于A Star算法或者其變種優(yōu)化算法以及與其他算法結(jié)合的混合算法。另外在應(yīng)用中開發(fā)者們利用物理中的電勢(shì)原理設(shè)計(jì)了基于電勢(shì)矩陣的負(fù)電荷自動(dòng)被吸引尋路算法，是一種新興的創(chuàng)意性思路。圖論中的深度優(yōu)先搜索算法（DFS）和廣度優(yōu)先搜索算法以及Dijksrta單源最短路徑貪心算法都是典型的盲目式搜索算法。除以上目的點(diǎn)明確的路徑尋路以外游戲中還需要一種隨機(jī)尋路算法，主要應(yīng)用于怪物在某個(gè)區(qū)域毫無目的的盲目閑游，使怪物顯得自然化、動(dòng)態(tài)化。

2.1 有限狀態(tài)機(jī)

Unity中有限狀態(tài)機(jī)(FSM, FiniteState Machine)的一個(gè)重要應(yīng)用是控制一個(gè)角色的動(dòng)畫系統(tǒng)連續(xù)性切換：

有限狀態(tài)機(jī)動(dòng)畫是將一個(gè)游戲人物角色的活動(dòng)分割為有限個(gè)狀態(tài)的集合，通過條件觸發(fā)狀態(tài)的轉(zhuǎn)換使角色產(chǎn)生一系列連續(xù)的動(dòng)作，狀態(tài)之間的方向箭頭代表狀態(tài)轉(zhuǎn)換的方向和轉(zhuǎn)換的條件，如圖中展示一個(gè)最簡(jiǎn)單的有限狀態(tài)機(jī)動(dòng)畫系統(tǒng)，通過條件觸發(fā)人物休息、行走、跳躍等動(dòng)作狀態(tài)的連續(xù)變換。有限狀態(tài)機(jī)動(dòng)畫在游戲中的NPC中應(yīng)用最多，但有限狀態(tài)機(jī)動(dòng)畫的AI性能較差，動(dòng)作有限很容易被玩家預(yù)測(cè)而顯得生硬，真實(shí)感被很大程度上限制。

2.2 尋路導(dǎo)航圖

游戲中進(jìn)行尋路前需要將地形中的可行走區(qū)域與障礙不可行走區(qū)域分開，同要對(duì)可行走區(qū)域進(jìn)行不同方法的分割，分割成結(jié)點(diǎn)從而可以轉(zhuǎn)化成算法和數(shù)據(jù)結(jié)構(gòu)可以處理的對(duì)象，行走區(qū)域的分割有以下幾種類型：

1.刪格化導(dǎo)航圖

類似于光柵圖像，將地圖用等間距的方格分割，表示成一個(gè)柵格矩陣，每個(gè)柵格代表一個(gè)位置點(diǎn)，同時(shí)這個(gè)點(diǎn)作為矩陣的一個(gè)值可以通過加權(quán)重來表示該點(diǎn)是否是障礙物，如果不是障礙物又是哪些不同的地形等等。柵格化導(dǎo)航圖相對(duì)其他類型的導(dǎo)航圖劃分更精細(xì)準(zhǔn)確，同時(shí)會(huì)占用大量?jī)?nèi)存。

2.多邊形導(dǎo)航圖

多邊形導(dǎo)航圖是將可行走地形用凸多邊形來分割填充，分割的原則是相鄰的兩個(gè)多邊形之間可以無障礙的直接通過。針對(duì)不同的地形可以選擇不同的多邊形。

3.可視點(diǎn)導(dǎo)航圖

用一系列有代表性的關(guān)鍵點(diǎn)來全面覆蓋可行走地形的核心框架，這樣使地形大大簡(jiǎn)化，地圖的搜索空間被大程度的瘦身，有利于提高搜索效率,但是在這種地圖中生成的路徑會(huì)出現(xiàn)使角色走“Z”字形的缺陷。WayPoint尋路法即基于此種導(dǎo)航圖。

三. 游戲AI尋路算法

3.1 A Star尋路算法

A Star算法又形象的稱為A*算法，是一種啟發(fā)式函數(shù)路徑計(jì)算搜索算法，算法中通過設(shè)計(jì)合理的啟發(fā)函數(shù)可以大大減少尋路過程中的計(jì)算量，提高計(jì)算效率，而估計(jì)不精確是啟發(fā)式函數(shù)的特點(diǎn)，因此使用A*算法計(jì)算的路徑可能不是人所理解的最優(yōu)路徑，但A*可以高效的提供一種在游戲中相對(duì)合理的路徑，在游戲?qū)ぢ分袘?yīng)用廣泛。

1. A*中的結(jié)點(diǎn)（Node）

結(jié)點(diǎn)是A*算法計(jì)算的基本單位。由于A*算法可應(yīng)用于多種導(dǎo)航圖，在不同的導(dǎo)航圖中結(jié)點(diǎn)的表示各不相同，在多邊形導(dǎo)航圖中一個(gè)多邊形為一個(gè)A*結(jié)點(diǎn)，可視點(diǎn)導(dǎo)航圖中每一個(gè)可視點(diǎn)為一個(gè)A*結(jié)點(diǎn)，刪格化導(dǎo)航圖中每一個(gè)矩形格子為一個(gè)A*結(jié)點(diǎn)。

2. 估價(jià)函數(shù)

估價(jià)函數(shù)用于評(píng)價(jià)一個(gè)結(jié)點(diǎn)被選做路徑點(diǎn)的概率，其利用了結(jié)點(diǎn)自身與起始點(diǎn)位置關(guān)系的信息，啟發(fā)算法搜索較合理的路徑，路徑即相鄰結(jié)點(diǎn)的集合序列，估價(jià)函數(shù)表達(dá)式如下：

F(N) = G(n) + H(n)

公式中的F(n)表示第n個(gè)結(jié)點(diǎn)的估價(jià)值，G(n)表示結(jié)點(diǎn)按照某種距離規(guī)則到起點(diǎn)的距離值，H(n)表示結(jié)點(diǎn)按照某種距離規(guī)則到終點(diǎn)的距離值，因此估價(jià)值F(n)越小，代表路徑行走消耗越少，則被選為路徑點(diǎn)的概率越大。

距離計(jì)算規(guī)則主要有曼哈頓距離、歐幾里得距離和對(duì)角線距離三種。曼哈頓距離指的是兩點(diǎn)之間水平距離與豎直距離之和，歐幾里得距離指的是兩點(diǎn)之間的幾何距離，對(duì)角線距離指的是水平距離和豎直距離中的較大者。

在P1、P2兩點(diǎn)之間構(gòu)成的直角三角形中，假設(shè)水平直角邊長(zhǎng)度為A，豎直直角邊長(zhǎng)度為B，斜邊距離為C，則：

曼哈頓距離： D1 = A + B

歐幾里得距離：D2 = C

對(duì)角線距離： D3 = max{A,B}

在算法的實(shí)際應(yīng)用中，根據(jù)[13]沈健的研究結(jié)論歐幾里得距離在尋路計(jì)算效率上表現(xiàn)更佳，具體根據(jù)不同情形常常進(jìn)行混合應(yīng)用以更好提高計(jì)算效率和算法適應(yīng)性。

3. A*算法的執(zhí)行過程

算法維護(hù)Open表和Closed表兩個(gè)表，前者存放可能的待訪問的結(jié)點(diǎn)，后者不斷加入估價(jià)計(jì)算后的結(jié)點(diǎn)。

(1) 算法初始將起點(diǎn)加入Closed表，其估價(jià)函數(shù)值：F(0) =H(0), 其中G(0) = 0,為其到自身的距離。

(2) 然后將所有與當(dāng)前點(diǎn)(暫時(shí)是起點(diǎn))相鄰的結(jié)點(diǎn)加入Open表，如果已經(jīng)加入則不操作。在當(dāng)前結(jié)點(diǎn)估價(jià)函數(shù)值的基礎(chǔ)上，累加計(jì)算所有相鄰結(jié)點(diǎn)的F、G、H值，如果已在Closed表中的結(jié)點(diǎn)的新的估價(jià)值比之前的小，則更新為更小的值，將F值最小的結(jié)點(diǎn)選為新路徑點(diǎn)，設(shè)置成當(dāng)前結(jié)點(diǎn)的子節(jié)點(diǎn)，新路徑點(diǎn)繼續(xù)做為當(dāng)前結(jié)點(diǎn)繼續(xù)遍歷相鄰的結(jié)點(diǎn)。

(3) 重復(fù)(2)的操作當(dāng)終點(diǎn)加入Closed表時(shí)，算法結(jié)束，根據(jù)父子結(jié)點(diǎn)的關(guān)系可得到最終路徑，如果Open表為空時(shí)終點(diǎn)依舊不在Closed表中，則搜索失敗。

(4) 以上算法執(zhí)行過程中障礙物結(jié)點(diǎn)不加入Open表中計(jì)算。

A*算法最簡(jiǎn)單的應(yīng)用是在經(jīng)典的磚塊地圖（Tile）中，每一個(gè)方格看做一個(gè)結(jié)點(diǎn)，從當(dāng)前方格結(jié)點(diǎn)可以往上、下、左、右、左上、右上、左下、右下八個(gè)方向到下一個(gè)相鄰結(jié)點(diǎn)，實(shí)際開發(fā)中需要考慮結(jié)點(diǎn)單元的大小，即貼圖方格的密度。典型的《坦克大戰(zhàn)》游戲即基于磚塊地圖。地圖中的方格分為可行走（Moveable）和不可行走（Not Moveable）兩種，不可行走的結(jié)點(diǎn)算法中會(huì)忽略跳過不加入計(jì)算。在磚塊地圖中，為了計(jì)算簡(jiǎn)便，的計(jì)算常采用歐幾里得距離，的計(jì)算采用曼哈頓距離。

4. 拐點(diǎn)法優(yōu)化A*路徑

在可視點(diǎn)導(dǎo)航圖中可視關(guān)鍵點(diǎn)即算法的結(jié)點(diǎn)。這樣設(shè)置結(jié)點(diǎn)的好處是結(jié)點(diǎn)的設(shè)置自由靈活，可以通過權(quán)衡減少A*結(jié)點(diǎn)的數(shù)量，減少計(jì)算量，也可以根據(jù)設(shè)計(jì)師的要求快速調(diào)整。問題是在大地圖中，如果設(shè)置的結(jié)點(diǎn)比較稀疏，得到的路徑會(huì)顯得死板生硬，造成不自然的視覺體驗(yàn)。在導(dǎo)航網(wǎng)格（Navigation Mesh，又稱Navmesh）也就是多邊形導(dǎo)航圖中可以很大程度上避免以上問題。

在多邊形導(dǎo)航圖中，使用凸多邊形作為結(jié)點(diǎn)，一方面可以大大減少結(jié)點(diǎn)的數(shù)量，另一方面可以更好的覆蓋整個(gè)地形。此外，通過計(jì)算起點(diǎn)和終點(diǎn)之間直線與多邊形導(dǎo)航網(wǎng)格相鄰點(diǎn)的位置關(guān)系可以得出可否直接無障礙通過，基于此優(yōu)化后，可避免像可視導(dǎo)航點(diǎn)搜索路徑那樣出現(xiàn)折返“Z”型路線，使角色產(chǎn)生多余的繞行。

使用A*算法在NavMesh中搜索的路徑是一系列相鄰的多邊形組成的通路，事實(shí)上在很多情況下多個(gè)多邊形組成的行走區(qū)域是可以直接通過的，此時(shí)可將這些多邊形合并，形成直線路徑，只在必須拐彎的拐點(diǎn)處使路徑轉(zhuǎn)折，多邊形的合并和拐點(diǎn)的尋找方法如下。

按照多邊形導(dǎo)航圖的生成規(guī)格，相鄰的兩個(gè)多邊形之間只有一條共同邊，共同邊上有兩個(gè)可能作為拐點(diǎn)的端點(diǎn)，從一個(gè)多邊形到另一個(gè)多邊形兩個(gè)端點(diǎn)可記為左端點(diǎn)、右端點(diǎn)，結(jié)點(diǎn)到兩個(gè)端點(diǎn)的方向向量記為左向量Vleft、右向量Vright。根據(jù)多邊形結(jié)點(diǎn)的代表點(diǎn)與兩個(gè)端點(diǎn)的坐標(biāo)可以計(jì)算出左右向量，另外根據(jù)目的地坐標(biāo)可以計(jì)算一個(gè)目的方向向量Vd，因此一個(gè)結(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)可設(shè)計(jì)如下：

算法執(zhí)行過程如下：

(1) 算法維護(hù)一個(gè)拐點(diǎn)表P，表示優(yōu)化后路徑的關(guān)鍵點(diǎn)，作為算法的運(yùn)算結(jié)果；

(2) 算法初始將起點(diǎn)結(jié)點(diǎn)的代表點(diǎn)設(shè)置為多邊形中心點(diǎn)，并加入拐點(diǎn)表P，然后計(jì)算到下一個(gè)結(jié)點(diǎn)的左右向量與目的方向向量的夾角，夾角較小方向上的端點(diǎn)設(shè)置為下一個(gè)結(jié)點(diǎn)的代表點(diǎn)；

(3) 根據(jù)下一個(gè)結(jié)點(diǎn)的代表點(diǎn)和左右端點(diǎn)計(jì)算左右向量，如果向量都不為零，執(zhí)行和

起點(diǎn)結(jié)點(diǎn)相同操作；如果左向量為零，說明代表點(diǎn)和左端點(diǎn)重合，將左端點(diǎn)記為一個(gè)拐點(diǎn)加入拐點(diǎn)表P；

(4) 直到到達(dá)終點(diǎn)所在的結(jié)點(diǎn)時(shí)，將當(dāng)前代表點(diǎn)和終點(diǎn)先后一起加入拐點(diǎn)表P，算法結(jié)束。

A*路徑經(jīng)拐點(diǎn)法優(yōu)化后會(huì)出現(xiàn)沿導(dǎo)航圖邊界行走的情況，只要設(shè)置游戲角色的自身半徑作為offset校正即可實(shí)現(xiàn)與導(dǎo)航圖邊界保持一定距離行進(jìn)，避免與邊界的碰撞卡頓。

3.2電勢(shì)矩陣尋路算法

電勢(shì)矩陣尋路算法將移動(dòng)的物體也就是Unity中的NavAgent看做一個(gè)負(fù)電荷，模擬電勢(shì)場(chǎng)中負(fù)電荷向電勢(shì)高的地方移動(dòng)的特點(diǎn)，通過改變電勢(shì)場(chǎng)來引導(dǎo)負(fù)電荷沿著電勢(shì)場(chǎng)線向目的地尋路移動(dòng)?；陔妱?shì)場(chǎng)的設(shè)置方法此算法最好應(yīng)用在柵格化的導(dǎo)航圖中，以更精確的描述電勢(shì)場(chǎng)的細(xì)節(jié)，并且算法使用一個(gè)地圖矩陣來存儲(chǔ)地形每個(gè)點(diǎn)的電勢(shì)整數(shù)值。

設(shè)置目的點(diǎn)的方法即建立一個(gè)新的目的矩陣將目的點(diǎn)的電勢(shì)設(shè)置成一個(gè)極大值，然后以圓形或者矩形向四周遞減散播開來，離目的點(diǎn)越遠(yuǎn)電勢(shì)值越小，直到0為止，然后將目的矩陣與原地圖矩陣相加，改變電勢(shì)分布，從而使負(fù)電荷沿著電勢(shì)場(chǎng)分布向目的點(diǎn)移動(dòng)。

此算法本質(zhì)上是一種貪心算法（GreedyAlgorithm），缺點(diǎn)是不保證一定能找到正確路徑，可能計(jì)算無解。此算法可在一些比較規(guī)則的、簡(jiǎn)單的地形中完成尋路計(jì)算任務(wù)。

3.3群體行為（Flocking Behavior）尋路

有些游戲中會(huì)需要角色群體的共同尋路功能，如果對(duì)每一個(gè)個(gè)體都進(jìn)行單獨(dú)尋路計(jì)算，會(huì)造成計(jì)算量膨脹，造成大量不必要的重復(fù)。因此角色單位的移動(dòng)可采用行為控制（SteeringBehavior）來實(shí)現(xiàn)，即選擇群體中的一個(gè)角色單位作為群體的領(lǐng)導(dǎo)者（Leader），對(duì)齊使用尋路算法進(jìn)行尋路計(jì)算，然后其他的群體成員按照一定的Flocking規(guī)則對(duì)Leader進(jìn)行跟隨移動(dòng)。

Flocking規(guī)則的設(shè)計(jì)主要考慮以下三個(gè)方面：

(1) 一致性：

即群體成員的的移動(dòng)方向要同整體的移動(dòng)方向（此即Leader的移動(dòng)方向）保持一致；

(2) 分離性：

即每個(gè)群體成員需要與其他成員保持一定距離，避免重合在一起，這個(gè)可參照SterringBehavior的碰撞避免（Collision Avoidance）算法來類似實(shí)現(xiàn)；

(3) 聚合性：

即群體的成員向群體成員整體的平均位置靠近，使群體的整體尋路前進(jìn)效果更真實(shí)。

3.4碰撞避免（Collision Avoidance）

如圖中綠色方塊為游戲角色，紅色方塊為目的地，移動(dòng)方向向量Vd根據(jù)角色當(dāng)前位置和目的地位置不斷更新，使其總是趨向于指向目的地，碰撞檢測(cè)向量為角色位置指向最近的障礙物的向量，向量的模為到障礙物的距離，當(dāng)距離小于一定值時(shí)開始避讓障礙物，避讓的方法為將移動(dòng)方向向量與碰撞檢測(cè)向量的反向量Vc'相加得到校正的移動(dòng)方向向量Vd':

Vd' = Vd + Vc'

Vd = Vd'

校正的瞬間角色的移動(dòng)方向向量設(shè)置為Vd'，使其避開當(dāng)前最近的障礙物，之后更新調(diào)整繼續(xù)向目的地移動(dòng)。

圖論算法將地圖結(jié)點(diǎn)和結(jié)點(diǎn)之間的通路信息用有向或者無向鄰接矩陣來進(jìn)行存儲(chǔ)，鄰接矩陣中相連的兩點(diǎn)對(duì)應(yīng)值為1，不相連的對(duì)應(yīng)值為0，同一個(gè)圖中可以有多種深度優(yōu)先序列和廣度優(yōu)先序列。在路徑搜尋中可以將相鄰兩點(diǎn)的對(duì)應(yīng)值設(shè)置為兩者的距離權(quán)重值，在算法搜索結(jié)束后選擇距離最短的路徑分支，從而確定一條算法上最優(yōu)的路徑序列。

深度優(yōu)先搜索(DFS, Depth First Search)和廣度優(yōu)先搜索(BFS, Breadth First Search)都是按照一定規(guī)則進(jìn)行的盲目搜索。

深度優(yōu)先搜索的邏輯規(guī)則為從起點(diǎn)開始，尋找訪問下一個(gè)連通的結(jié)點(diǎn)，直到?jīng)]有未訪問的連通結(jié)點(diǎn)后，回溯到起點(diǎn)并從其他的分支繼續(xù)尋找深度連通路徑，直到所有的結(jié)點(diǎn)都被訪問到為止。

假設(shè)圖3-9中無向圖的起點(diǎn)為V1，則有以下幾種深度優(yōu)先序列：

V1, V3, V5, V4, V2;

V1, V4, V5, V3;

V1, V4, V2;

V1, V2, V4, V5, V3;

根據(jù)確定的目的結(jié)點(diǎn)以及連線的權(quán)值和可從序列中截取選擇最短路徑；

廣度優(yōu)先搜索的搜索邏輯為從起點(diǎn)開始，遍歷所有相連的結(jié)點(diǎn)并設(shè)置為起點(diǎn)的子結(jié)點(diǎn)，之后在子節(jié)點(diǎn)進(jìn)行同樣的遞歸操作，直到所有結(jié)點(diǎn)都加入以起點(diǎn)為根結(jié)點(diǎn)的樹中。

假設(shè)圖3-10中有向圖的起點(diǎn)依舊為V1，其中一個(gè)廣度優(yōu)先搜索序列為：

V1, V3, V4, V2, V5

如圖3-11中所示的兩棵廣度優(yōu)先搜索樹，從第二層開始，樹的一層代表一次廣度優(yōu)先搜索。

3.6Dijkstra單源最短路徑搜索算法

Dijkstra算法是A start算法的無啟發(fā)函數(shù)版,同時(shí)是一種典型的貪心算法。算法沒有利用結(jié)點(diǎn)本身與起點(diǎn)和目的點(diǎn)的距離信息進(jìn)行引導(dǎo)，在整個(gè)地圖的所有結(jié)點(diǎn)中進(jìn)行搜索，體現(xiàn)其盲目性，效率自然比A*算法低。算法的本質(zhì)搜索思想是對(duì)于A和B兩個(gè)結(jié)點(diǎn)，如果從整個(gè)地圖中添加某些中間結(jié)點(diǎn)可以使A和B之間的加權(quán)路徑長(zhǎng)度更短，則加入中間結(jié)點(diǎn)構(gòu)成A和B之間更短的加權(quán)路徑，直到?jīng)]有中間結(jié)點(diǎn)可以使A、B兩點(diǎn)之間路徑更短為止。

算法初始化時(shí)計(jì)算各結(jié)點(diǎn)到其他結(jié)點(diǎn)的直接距離表，結(jié)點(diǎn)之間相連的距離為結(jié)點(diǎn)連線的權(quán)重值，不相連的距離設(shè)置為無窮大。構(gòu)建一個(gè)S表，表示計(jì)算完成的結(jié)點(diǎn)的集合，算法開始時(shí)將起點(diǎn)加入S表，然后搜索與起點(diǎn)距離最近的點(diǎn)加入S表，并以新加入的結(jié)點(diǎn)為中間結(jié)點(diǎn)，計(jì)算起點(diǎn)到其他結(jié)點(diǎn)的相對(duì)更近距離，更新起點(diǎn)的距離表，直到所有的結(jié)點(diǎn)都加入S表。起點(diǎn)最終的距離表中的距離值即起點(diǎn)到其他各結(jié)點(diǎn)之間的最短路徑距離。當(dāng)終點(diǎn)確定時(shí)，記錄在算法運(yùn)行過程中起始點(diǎn)之間加入了那些中間結(jié)點(diǎn)，即可找出相應(yīng)的最短路線。

假設(shè)圖3-10有向圖中的起點(diǎn)為V1，則Dijkstra算法初始化的距離表如表3-1所示：

算法的執(zhí)行過程可用表3-2表示如下，共六個(gè)結(jié)點(diǎn)執(zhí)行五次循環(huán)將所有結(jié)點(diǎn)加入S表，w為新加入結(jié)點(diǎn)，D[Vi]表示起點(diǎn)到結(jié)點(diǎn)Vi的最短距離。

3.7隨機(jī)尋路算法

游戲中的怪物在玩家還未靠近時(shí)要有自己自然的隨機(jī)動(dòng)作，以一個(gè)隨機(jī)的方向和隨機(jī)的速率進(jìn)行移動(dòng)，使其看上去是活躍的。當(dāng)玩家靠近進(jìn)入怪物的“境界區(qū)域”時(shí)，怪物會(huì)主動(dòng)尋路靠近玩家，當(dāng)玩家與怪物足夠近進(jìn)入怪物的“攻擊區(qū)域”時(shí)，怪物開始攻擊玩家。

隨機(jī)尋路算法的實(shí)現(xiàn)是設(shè)計(jì)一種隨機(jī)移動(dòng)規(guī)則，使游戲角色不斷產(chǎn)生不規(guī)則、不可預(yù)見的行動(dòng)，從而使角色在游戲中自行保持活躍狀態(tài)，提高游戲真實(shí)感。尋路的隨機(jī)主要是角色行進(jìn)的方向和行進(jìn)速度的隨機(jī)。方向的表示可用一個(gè)隨機(jī)目的地位置表示，或用一個(gè)單位方向向量表示。速度的改變可以通過控制更新的頻率或者每次移動(dòng)的距離實(shí)現(xiàn)。

比如可以用一個(gè)向量的方向表示當(dāng)前行進(jìn)的方向，的模的大小來表示行進(jìn)的速度，按照一定周期隨機(jī)更新的方向和模的大小實(shí)現(xiàn)隨機(jī)移動(dòng)，同時(shí)使用碰撞避免算法來校正尋路，防止游戲角色出現(xiàn)在障礙物處長(zhǎng)時(shí)間卡頓徘徊的現(xiàn)象。