AI分為16、17兩節課講，大綱如下：

尋路/導航系統Navigation

• 基本思路：
  

Walkable Area

需要讓ai知道哪些部分可以通過（包含走路、跳、翻越攀爬、載具可過等不同情況，還要考慮物理碰撞）。

其表達方式有Waypoint Network、Grid、Navigation Mesh、Sparse Voxel Octree（空間八叉樹）等。每種方式都尤其優缺點，因此游戲經常使用多種方式結合。

Waypoint Network

早期游戲引擎用的多，通過設置道路關鍵點（如道路兩邊）并用算法插值關鍵點得到路網，尋路時先找到距離當前位置和目標位置最近的路網點，再通過路網連通（就像坐地鐵一樣），如下圖：

優點是好實現、效率高，缺點是不方便動態更新、總走路中間

Grid

地圖網格化，類似光柵化，如下圖：

優點是便于動態更新，缺點是精確度取決于格子大小、存儲空間浪費、效率比較低、難以表達層疊結構（比如橋）

Navigation Mesh（尋路網格）

現代游戲引擎最普遍的方法，即把地圖上所有可通行的區域連起來（用凸多邊形），主要用物理碰撞與預測路線，既可以解決路線僵硬問題，又能應對層疊結構

優點是支持3d、精確、靈活、動態，缺點是生成Navigation Mesh的算法非常復雜，并且只能“尋路”，不能飛機3d空間導航

• 怎么生成Navigation Mesh呢？
  現在基本都是自動生成，用一些開源庫如recast，voxelization后去計算可通行區域；然后再通過計算離邊緣最近的edge voxel，得到一個類似距離場的東西；
  
  再找到每個區域距離邊緣最遠的中心點，用洪水算法向外擴散，直到覆蓋所有區域，在通過進一步處理（比如連通區域變為凸多邊形之類，比較復雜），這就是我們的生成的Mesh了
  

• Polygon Flag
  通過地形標簽生成不同區域的mesh
  

• Tile
  那如果地圖在動態變化怎么辦，比如路障被用戶打掉了。可以使用Tile把地圖分塊，部分地圖更新后只需要重新計劃該塊tile即可
  
  把空間分成一個個Tile，當Tile改變時只需要更新這個Tile即可

• Off Mesh Link
  建立一些手動的連接點和連接線可以讓尋路變得更加復雜，增強拓展性
  

Sparse Voxel Octree

把空間體素化，通過求交導航。可以表達3d空間的導航，主要用于航空航天游戲。但缺點是存儲消耗大
通過八叉樹劃分空間

Path Finding

以上每種方式都可以把各個幾何元素的中心連接為點圖，只要找到最短路徑即可。

所謂尋路問題主要就是解決兩個問題：

1. 找到一條起點到終點的道路
2. 盡可能的少走彎路

這個過程也有幾種算法，比如經典的：

深度優先搜索（Depth-First Search）：找到一個分支一直走，如果沒有路就退回來，直到走到終點為止（時間換空間）

廣度優先搜索（Breadth-First Search）：每一個step都向全部子節點擴散一步，直到找到終點（空間換時間）
但以上兩種方式都比較費，并且不能計算加權最短路徑，所以還需要更多算法幫助：

Dijkstra Algorithm迪杰斯特拉算法

可以解決有權圖中最短路徑問題，參考這個大佬的文章：圖論：Dijkstra算法——最詳細的分析，圖文并茂，一次看懂！
截圖自大佬博客:

但是對于游戲來說，有時候并不需要真的“最優路徑”，只要按照大致方向走就行了，所以引入了下邊的A Star算法

A Star（A*算法）

用的最普遍，是一種啟發式算法，通過有選擇的節點搜索找到最短路徑，因此更快，常用于游戲或機器人導航。
原理是通過計算一個代價函數：f = g（從原點已經走過的路程的代價，一般累計路程距離） + h（到終點還有多遠的代價，一般用歐拉距離或x+y），來逐步尋找最優下一步的路徑（按照網格或mesh的劃分），原理有些類似梯度下降。

Path Smoothing

把無效的運動盡可能踢掉

Funnel Algorithm煙囪算法：類似于人走路時對道路的感知，如下圖：

從起始點看向下一個三角形，視野卡在三角形兩端，如果能全部在視野中，就繼續看下一個三角形，更新視野，直到某一個三角形被擋住一部分時，左邊被擋沿左視野邊走，右邊被擋沿右視野邊走；
走到被卡視野的遮擋點后，再重新進行上述過程；
如果迭代過程中發現終點就在視野里時則直接向終點走。

Steering系統

載具的移動受限于它們的移動能力：油門、剎車、轉向等，所以經常會在尋路中被障礙物卡死

steer behavior：

• Seek/Flee：包括 追蹤、巡邏、流場跟隨、路徑跟隨
• 速度匹配：快到目標點減速，減速到速度為0時剛好到達目標點，比如火箭發射會用到
• 一致性：角速度的加速和減速，比如npc看向主角
  

Crowd Simulation群體模擬

現在的游戲城市環境交互等越來越豐富，那群體模擬必不可少，比如一群鴿子突然飛走，一群npc四散逃跑等。群體模擬需要做到：避免碰撞、成群的來回移動（Swarming）、編隊運動（motion in formation）

群體模擬模型

群體模擬模型大致有三種：
微觀方法（Microscopic)：自底向上的定義每個個體的行為，合起來就組成了群體行為。
宏觀方法(Macroscopic)：定義群體宏觀的運動趨勢，所有個體按照該趨勢移動。
綜合方法(Mesoscopic)：將群體分組。既有宏觀的趨勢，也有微觀的個體行為。

微觀方法：基于規則的模型

比如動物的群體動力學，用簡單規則控制每個個體的運動：

• 分離（Separation）：避開自己的所有“鄰居”（斥力）
• 凝聚性（Cohesion：朝向群體的“質心”移動
• 一致性（Alignment）：和鄰近的對象朝向同一個方向移動

好處是規則簡單，壞處是宏觀上是不可控且不怎么受人影響。

宏觀方法

從宏觀的角度模擬人群的運動，通過設置可通行區域和有勢場或流體力學的控制運動，類似粒子系統運動？

綜合方法

結合了宏觀和微觀方法，把群體分為很多小組，每組分別運動，同時組里的個體也有一點自己的區別。比如紅警里圈出一群小兵運動時就是這樣。

避免碰撞

這部分如果給ai做效率非常低，所以需要用一個碰撞系統幫助ai決策

基于力的模型

相當于使用距離場給障礙物增加一個反向力

好處：可以被拓展去模擬更慌亂的人群的行為。
壞處：類似于物理模擬，模擬的步驟應該足夠小。

基于速度的模型–速度障礙法

類似人眼處理方式：當兩個物體在同一速度線上行走，就都靠左邊避讓一點。

當參與的對象不止兩個時，A 對 B 的避讓可能又會影響到 C。所有需要做一些優化：Optimal Reciprocal
Velocity Avoidance（ORVA）。其數學復雜度非常高，不過實際中也會用基于力的方式替代（結果沒那么絲滑但能用）

Sensing環境感知

對世界的感知是我們和ai決策的依據，感知分為內部和外部信息：

內部的信息包含位置、血量、護甲狀態、增益狀態、可以被自由獲取的東西等等；外部的信息包含靜態空間信息如Tactical Map戰術地圖、掩體等和動態信息如influenceMap人群熱力圖、視角圖、游戲物體等。

這些非常類似人類對世界的感知（并不是上帝視角），有視覺、聽覺并隨距離衰減，有活動范圍、視野等，但如果感知太多會影響性能，因此一般會取舍幾個，并范圍內共享信息

經典決策算法

經典決策算法有：
有限狀態機（Finite State Machine）
行為樹（Behavior Tree）：AI最核心的體系
層次任務網絡（Hierarchical Tasks Network)
目標驅動的行為計劃系統(Goal Oriented Action Planning)
蒙特卡洛搜索樹(Monte Carlo Tree Search)
深度學習（Deep Learning)

有限狀態機（Finite State Machine）

根據一些條件轉換（Transition）一個狀態到其他狀態

比如吃豆人的狀態機示例：

好處：容易執行、容易理解、對于簡單例子，應對起來非常快
壞處：可維護性差，特別是添加和移動狀態；重用性差，不能被應用于其他項目或角色；可擴展性差，很難去修改復雜的案例

層次有限狀態機（HFSM）

把狀態機分為很多層或模塊，每個狀態機之間有相互的接口，復雜度可控；雖然能部分解決上述問題，但是會造成一定的性能下降，難以跳模塊，反應速度也會下降。15年前的很多游戲就是這么做的，屬于“古老”的方法。

行為樹（Behavior Tree）

行為樹和人的思考類似，例如 人碰到一個敵人，會根據自己的狀態來選擇追擊還是撤退。（一些復雜的商業決策也有類似決策樹的邏輯）

可執行結點

分為條件節點和動作節點
條件結點可以立馬執行完，而行為結點有一定過程，例如追鬼，首先得有尋路系統，然后還需要轉向系統。行為也分為正在進行和失敗等幾種狀態。

控制結點

• Sequence 順序執行，&&：從左到右便利子節點，如果某個子節點返回 Failure 就停止整個行為，或者時所有子節點都成功執行，返回 Success，并執行該行為。
  

• Selector 條件執行，||： 根據條件嘗試所有子節點，一旦某個子節點 滿足條件，立馬作出該決策。
  

• Parallel并行執行 ：一個 AI 體可以同時進行多個行為，例如對于射擊游戲來說可以同時進行移動和射擊。

• Decorator裝飾節點：起修飾作用，例如循環執行、執行一次、計時器、定時等。
  

注意行為樹tick更新時要每一幀都從根節點開始判斷，這一點上也可以優化為正常從上一幀的節點繼續，但某些優先級高的event會更新整棵樹。

黑板（Blackboard）

用于記錄行為狀態，用于把數據與邏輯分離

• 行為樹的好處：
  模塊化、層級組織（每個子樹可以被看作是一個模塊）
  可讀性高
  容易維護，并且修改只會影響樹的一部分
  反應快，每個 tick 會快速的根據環境來改變行為
  容易 Debug，每個 tick 都是是一個完整的決策。

• 行為樹的壞處
  如果不優化，每個 tick 都從根節點觸發，會造成更大的開銷
  反應性越好，條件越多，每幀的花銷也越大

QA
行為樹和if else有什么區別：if else就是最簡單的行為樹，行為樹類似goto、jump等語言指令
ai如何從環境中提取數據（感知）：環境數據類型多數量多，其實很難讀取，可以用引擎中的反射等技術解決；ai提取數據時效率其實不高，需要對感知做規劃和指令
如何處理垂直鄰面的NavMesh生成？根據高度設置為斷開的懸崖或是可通過的障礙，如果可以攀爬另說

原文鏈接：