趣說游戲AI開發：對狀態機的褒揚和批判

如題目所示，本文要來聊一聊在游戲開發中經常會涉及到的話題——游戲AI。設計游戲AI的目標之一是要找到一種便於使用並容易拓展的的方案，常見的一些游戲AI方案包括了有限狀態機(FSM)、分層有限狀態機（HFSM）、面向目標的動作規劃（GOAP）以及分層任務網路（HTN）和行為樹（BT）等等。下麵我們就來...

0x00 前言

因為臨近年關工作繁忙，已經有一段時間沒有更新博客了。到了元旦終於有時間來寫點東西，既是積累也是分享。如題目所示，本文要來聊一聊在游戲開發中經常會涉及到的話題——游戲AI。設計游戲AI的目標之一是要找到一種便於使用並容易拓展的的方案，常見的一些游戲AI方案包括了有限狀態機(FSM)、分層有限狀態機（HFSM）、面向目標的動作規劃（GOAP）以及分層任務網路（HTN）和行為樹（BT）等等。下麵我們就來聊一聊比較有代表性的游戲AI方案——狀態機。

0x01 有限狀態機(FSM)

有限狀態自動機 (Finite State Machine，FSM)是表示有限多個狀態以及在這些狀態（State）之間轉移（Transition）和動作（Action）的數學模型。有限狀態機的模型體現了兩點：

狀態首先是離散的：某一時刻只能處於某種狀態之下，且需要滿足某種條件才能從一種狀態轉移到另一種狀態。
然後狀態總數是有限的。

從它的定義，我們可以看到有限狀態機的幾個重要概念：

狀態（State）：表示對象的某種形態，在當前形態下可能會擁有不同的行為和屬性。
轉移（Transition）：表示狀態變更，並且必須滿足確使轉移發生的條件來執行。
動作（Action）：表示在給定時刻要進行的活動。
事件（Event）：事件通常會引起狀態的變遷，促使狀態機從一種狀態切換到另一種狀態。

而狀態機便是用來控制對象狀態的管理器。在滿足了某種條件或者說在某個特定的事件被觸發之後，對象的狀態便會通過轉換來變成另外一種狀態，而對象在不同的狀態之下也有可能會有不同的行為和屬性。
當然，有限狀態機的應用範圍很廣，但是顯然游戲開發是有限狀態機最為成功的應用領域之一。除了游戲AI的實現可以依靠有限狀態機之外，游戲邏輯以及動作切換都可以藉助有限狀態機來實現。因此游戲中的每個角色或者器件或者邏輯都有可能內嵌一個狀態機。

0x02 HFSM分層有限狀態機

如果我們仔細觀察一個有限狀態機的話，可以發現它在邏輯結構上是沒有層次的，如果和行為樹來做對比的話可以發現這一點十分明顯。在行為樹中，節點是有層次（Hierarchical）的，子節點由其父節點來控制。例如行為樹中有一種節點叫做“序列（Sequence）節點”，它的作用是順序執行所有子節點（如果某個子節點失敗返回失敗，否則返回成功）。而將行為樹的這個優勢應用到有限狀態機上，分層有限狀態機HFSM便誕生了。

分層的好處

那麼引入了分層之後的HFSM到底帶來了什麼好處呢？
最大的好處便是在一定程度上規範了狀態機的狀態轉換，從而有效地減少了狀態之間的轉換。
舉一個簡單的小例子：例如RTS游戲中計程車兵。如果邏輯沒有層次上的劃分，那麼我們對士兵所定義的若幹狀態，例如前進、尋敵、攻擊、防禦、逃跑等等，就需要在這些狀態之間定義轉移，因為它們是平級的，因此我們需要考慮每一組狀態的關係，並維護一大堆沒有側重點的轉移。
如果在邏輯上是分層的，我們就可以將士兵的這些狀態進行一個分類，把幾個低級的狀態歸併到一個高級的狀態中，並且狀態的轉移只發生在同級的狀態中。
例如高級狀態包括戰鬥、撤退，而戰鬥狀態中又包括了尋敵、攻擊等幾個小狀態；撤退狀態中又包括了防禦、逃跑這幾個小狀態。

總而言之，分層狀態機HFSM從某種程度上規範了狀態機的狀態轉移，而且狀態內的子狀態不需要關心外部狀態的跳轉，這樣也做到了無關狀態間的隔離。

0x03 有限狀態機的實現

那麼到底如何實現一個有限狀態機呢？主要有兩種方式來實現，即集中管理控制以及模塊化管理。具體來說，這兩種方式的實現如下：

使用switch語句：所有的狀態之間的轉移邏輯全都寫在一個部分，需要根據不同的分支來判斷轉移條件是否符合。
使用狀態模式（State Pattern）：一種常見的設計模式。在狀態模式中，我們為每個狀態創建與之對應的類，這樣就將狀態轉移的邏輯從臃腫的switch語句中分散到了各個類中。

瞭解了有限狀態機大體上可以分為這兩種實現方式，那麼接下來我們就具體來看一看這兩種方式是如何實現的。

switch語句

在實現有限狀態機時，使用switch語句是最簡單同時也是最直接的一種方式。這種方式的基本思路是為狀態機中的每一種狀態都設置一個case分支，專門用來對該狀態進行控制。
此處輸入圖片的描述
上圖是一個具體的使用有限狀態機實現游戲AI的場景，描述的是一個游戲單位的AI，下麵我們就使用switch語句來實現圖中的狀態機。

switch (state)  
{
  // 處理狀態Waiting的分支
  case State.Waiting: 
    // 執行等待
    wait();
    // 檢查是否有可以攻擊
    if (canAttack()){
      // 當前狀態轉換為Attacking
      changeState(State.Attacking);
    }
    // 若不可攻擊，則檢查是否有可以移動
    else if (canMove()) { 
      // 當前狀態轉換為Moving
      changeState(State.Moving)
    }
    break;
  // 處理狀態Moving的分支
  case State.Moving: 
    // 執行動作move
    move();
    // 檢查是否可以攻擊敵人
    if (canAttack()) {
      // 當前狀態轉換為Attacking
      changeState(State.Attacking);
    }
    // 若不可攻擊，則檢查是否可以等待
    else if (canWait()) {
      // 當前狀態轉換為Waiting
      changeState(State.Waiting);
    }
    break;
  // 處理狀態Attacking的分支
  case State.Attacking: 
    // 執行攻擊attack
    attack();
    // 檢查是否可以等待
    if (canWait()) {
      // 當前狀態轉換為Waiting
      changeState(State.Waiting);
    }
    break;
}

通過這個小例子，我們可以看到使用switch語句實現的有限狀態機的確可以很好的運行。不過我們還可以發現這種方式在實現狀態之間的轉換時，1.檢查轉換條件以及2.進行狀態轉換的代碼都是混雜在當前的狀態分支中來完成的，這樣就會導致代碼的可讀性降低甚至會增加日後的維護成本。
這是因為在每個具體的狀態下，都需要檢查多個具體的轉換條件，對符合條件的還需要轉移到新的具體的狀態，這樣的代碼是難以維護的，因為它們需要在具體的情況下處理具體的事物。即便我們將檢查轉換條件和進行狀態轉換的代碼分別封裝成兩個專門的函數FuncA（檢查轉換條件）和FuncB（進行狀態轉換），switch語句中各個具體狀態的代碼可能會更加清晰。但是隨著邏輯複雜度的增加，FuncA和FuncB這兩個函數本身的複雜度可能也會增加，甚至最後變得臃腫不堪。

狀態模式

當控制一個對象狀態轉換的條件表達式過於複雜時，把狀態的判斷邏輯轉移到一系列類當中，可以把複雜的邏輯判斷簡單化。因此，使用狀態模式來實現狀態機雖然不如直接使用switch語句來的直接，但是對於狀態更易維護也更易拓展。下麵我們就來看一看狀態模式中的角色：

　　1. 上下文環境（Context）：它定義了客戶程式需要的介面並維護一個具體狀態的實例，將與狀態相關的操作（1.檢查轉換條件；2.進行狀態轉換）交給當前的具體狀態對象來處理。
　　2. 抽象狀態（State）：定義一個介面以封裝使用上下文環境的的一個特定狀態相關的行為。
　　3. 具體狀態（Concrete State）：實現抽象狀態定義的介面。
下麵，我們就按照這三個角色來實現上一小節圖中的狀態機吧。
context類：

public class Context
{
    private State state;

    public Context(State state)
    {
        this.state = state;
    }

    public void Do()
    {
        state.CheckAndTran(this);
    }
}

抽象狀態類：

public abstract class State
{
    public abstract void CheckAndTran(Context context);
}

具體狀態類

public class WaitingState : State
{
    public override void CheckAndTran(Context context)
    {
        //執行等待動作
        Wait();
        //檢查是否可以攻擊敵人
        if (canAttack()){
            // 當前狀態轉換為Attacking
            context.State = new AttackingState();
        }
        // 若不可攻擊，則檢查是否有可以移動
        else if (canMove()) { 
            // 當前狀態轉換為Moving
            context.State = new MovingState();
        }
    }
}
...

雖然看似狀態模式緩解了使用switch語句那種代碼臃腫、可讀性維護性差的問題，但是狀態模式並非沒有自己的缺點。可以看出狀態模式的使用必然會增加類和對象的個數，如果使用不當將導致程式結構和代碼的混亂。

0x04 褒揚和批判

在游戲開發中使用狀態機顯然不失為一種不錯的選擇，首先它的概念並不複雜，其次它的實現也十分簡單而直接。但它的缺點卻也十分明顯，例如難以復用，因為它往往需要根據具體的情況來做出反應，當然當狀態機的模型複雜到一定的程度之後，也會帶來實現和維護上的困難。如何選擇，可能就是一個仁者見仁智者見智的問題了。