本系列為筆者初學(xué)c/c++和游戲AI開發(fā)的學(xué)習(xí)過程，算法為主，不涉及到具體的游戲開發(fā)軟件學(xué)習(xí)(如unity，虛幻4等),若有錯(cuò)誤請(qǐng)?jiān)谠u(píng)論區(qū)留下批評(píng)意見。

• 語言：c/c++ (11及以上)

• 平臺(tái)：macOS mojave

• 編譯器：vs Code / g++

圖與路徑規(guī)劃

一、圖

1.1 圖的定義

圖(Graph)是由頂點(diǎn)和連接頂點(diǎn)的邊構(gòu)成的離散結(jié)構(gòu)。在游戲中，圖則常常被用來表示點(diǎn)和點(diǎn)之間的路徑。

? 如圖1，路徑點(diǎn)稱為節(jié)點(diǎn)（node，頂點(diǎn)），連接節(jié)點(diǎn)的路線稱為邊（edge），或弧（arc）。

? 通過游戲角色運(yùn)動(dòng)的路徑表示為圖，我們就可以通過各種圖算法來計(jì)算出兩點(diǎn)之間的最短路徑（或其他條件），然后驅(qū)動(dòng)游戲角色沿著計(jì)算好的路勁剛移動(dòng)。

? 一個(gè)圖G能被規(guī)范化的定義為，通過邊的集合E進(jìn)行連接的節(jié)點(diǎn)（或頂點(diǎn)）的集合N。

G = {N，E}

1.2?圖的性質(zhì)

? 圖的基本性質(zhì)：

• 有向圖：只能從一個(gè)節(jié)點(diǎn)到另一個(gè)節(jié)點(diǎn)，這兩個(gè)節(jié)點(diǎn)稱作有序?qū)Γ∣rdered pair），用來? ? ? ? ? ? ? ? 表示邊的方向?？杀硎緸閺脑垂?jié)點(diǎn)（source node）到目標(biāo)節(jié)點(diǎn)（destination? ? ? ? ? ? ? ? ? ? node）。

• 無向圖：兩個(gè)點(diǎn)之間可以來回運(yùn)動(dòng)，沒有方向限制。

• 加權(quán)圖：點(diǎn)和點(diǎn)之間的邊是有重要性區(qū)別的，若把每個(gè)點(diǎn)看做一件事，那邊的權(quán)重意味著? ? ? ? ? ? ? ? 完成這件事的重要性。

• 有/無環(huán)圖：環(huán)是針對(duì)有向圖而言的，有環(huán)就是從一個(gè)點(diǎn)出發(fā)，一定能夠找到一條路徑回? ? ? ? ? ? ? ? ??到這個(gè)點(diǎn)；反之若找不到，則是無環(huán)圖。

• 連通圖：無向圖中每一對(duì)不同的頂點(diǎn)之間都有路徑。如果這個(gè)條件在有向圖里也成立，那? ? ? ? ? ? ? ? 么就是強(qiáng)連通的。

• 圖密度：邊與節(jié)點(diǎn)的比率決定了一個(gè)圖是稀疏的還是致密的。
  

1.3 圖的數(shù)據(jù)結(jié)構(gòu)

??在計(jì)算機(jī)中，圖主要由兩種數(shù)據(jù)結(jié)構(gòu)來表示：

• 鄰接矩陣：用一個(gè)二維矩陣來表示圖的連接關(guān)系，通常用0來表示兩個(gè)點(diǎn)之間沒有連接。? ? ? ? ? ? ? ? 可以高效的查找兩個(gè)節(jié)點(diǎn)間是否有連接，但對(duì)稀疏圖會(huì)消耗大量的內(nèi)存空間。

• 鄰接表：對(duì)于每一個(gè)當(dāng)前節(jié)點(diǎn)，一個(gè)鄰接表圖存儲(chǔ)一個(gè)鏈表以包含所有它的鄰邊。鄰接表? ? ? ? ? ? ?存儲(chǔ)稀疏圖可以節(jié)省內(nèi)存空間，但每次查找都需要遍歷一次鏈表，產(chǎn)生額外開銷。

1.4?圖在游戲中的應(yīng)用

1.4.1 導(dǎo)航圖??

? 導(dǎo)航圖（Navgraph）是這樣一種抽象結(jié)構(gòu)，它包含了在一個(gè)游戲環(huán)境中智能體可能訪問的所有的位置和這些位置之間的所有連接。

? 導(dǎo)航圖的每一個(gè)節(jié)點(diǎn)通常都表示一個(gè)關(guān)鍵區(qū)域的位置，或一個(gè)環(huán)境的對(duì)象，每條邊代表這些點(diǎn)之間的連接，且邊通常是有權(quán)重的。

1.4.2?依賴圖

??在含有資源管理系統(tǒng)的游戲類型中，依賴圖發(fā)揮著重要作用，它被用來描述玩家可以利用的不同的資源之間的依賴關(guān)系，即完成每種資源所必須的先決條件。

? 舉個(gè)例子，在游戲中，玩家必須先制造武器庫，然后他才能制造武器。這里的武器庫和武器就是兩種不同的資源，武器資源依賴于武器庫資源。

? 除此之外，用依賴圖設(shè)計(jì)的游戲人工智能，如即時(shí)戰(zhàn)略游戲中，電腦可以根據(jù)玩家目前建造的資源而決定下一步驟的決策行為，設(shè)計(jì)出具有針對(duì)性的策略行動(dòng)。

? 比如玩家建造了步兵軍營(yíng)，電腦就會(huì)從克制步兵的資源中選取一樣或幾樣來建造，設(shè)計(jì)出針對(duì)性的克制玩家的策略。

? 但是我們要注意的一點(diǎn)是，游戲人工智能設(shè)計(jì)，并不是要設(shè)計(jì)出能百分百完勝玩家的超級(jí)智能，而是要設(shè)計(jì)出一個(gè)可供玩家挑戰(zhàn)并戰(zhàn)勝的陪玩。

? 戰(zhàn)勝玩家并不是我們的目的，這太容易辦到了。難的是如何在勝利和失敗之間取得平衡，讓玩家永遠(yuǎn)處于躍躍欲試的興奮狀態(tài)中，讓他們能從游戲中獲得滿足感，并渴望去挑戰(zhàn)更高的難度。

? 這點(diǎn)在Sim Hui Tee的論文《DEVELOPING PARALLEL DEPENDENCY GRAPH IN IMPROVING GAME BALANCING》里有了很好的體現(xiàn)，他解釋了依賴圖在游戲平衡中的應(yīng)用。

1.4.2 狀態(tài)圖

? 狀態(tài)圖用在表示一個(gè)系統(tǒng)的每一個(gè)可能的狀態(tài)以及狀態(tài)之間的轉(zhuǎn)換。一個(gè)系統(tǒng)潛在的狀態(tài)的集合被叫做狀態(tài)空間。

? 在這里，有狀圖知識(shí)點(diǎn)的講解和應(yīng)用。

??

參考：

• 《游戲人工智能編程案例精粹》

• 《算法導(dǎo)論》

• 相關(guān)代碼下載? ??https://github.com/linpeijie/GameToy