有限狀態機 FSM

    雖然我現在已很少使用基礎的有限狀態機（FSM）實現，多使用我的行爲樹（通用任務樹）來代替，但基礎的 FSM 還是有必要講一講，有兩個原因：

1. 有限狀態機（FSM）永遠是你最有用的工具之一，雖然形式上可能有差別，但內核是不變的。

2. 我們需要了解 FSM 的優缺點，才能更好的使用它，以及知道什麼時候放棄它。

在開始之前，我提醒幾點：

1. 每個人對 FSM 的理解可能是不同的，分享的側重點也是不同的，建議大家多查查資料，集思廣益。

2. 一定要閱讀《遊戲人工智能編程案例精粹》中關於 FSM 的內容，因爲遊戲 AI 中的 FSM 和基礎的 FSM 實現稍有不同，而作者講得非常好；珠玉在前，我就不再重複了。

3. 本文不會詳細解釋狀態模式，但狀態模式是 FSM 的基礎。

我與狀態機的初識

    我的第一個項目是 MMORPG 項目，由於我對遊戲的 AI 和戰鬥部分非常感興趣，因此在系統功能開發方面遊刃有餘後，在空閒的時間就開始研究項目中的 AI 和戰鬥實現，而 Npc 的 AI 便是狀態機實現的 —— 和《遊戲人工智能編程案例精粹》中的實現大致相同。

    那時的我還是一個小菜鳥，因此研究得津津有味，在自覺研究明白以後，還偷摸 “優化” 了寵物的 AI —— 然後產生了一些 bug（客戶端不同步），然後被 Leader 叫去談話，讓我不要輕易動場景中的代碼（技能、AI）。我此後一段時間雖沒有修改代碼，但並沒有停止研究，以致後面沒有人比我更熟悉 AI 和技能的代碼，所以後面這兩塊的維護工作就落到了我身上。

    PS：以我自身的成長經歷來看，場景內的 AI、技能這些東西，確實不是一個工作 1~2 年的遊戲程序員能駕馭的，這涉及到非常多的問題，但研究這方面的實現可以讓人快速成長。

有限狀態機和狀態模式的關係？

    維基百科對 FSM 的解釋：

    有限狀態機（英語：finite-state machine，縮寫：FSM）又稱有限狀態自動機（英語：finite-state automaton，縮寫：FSA），簡稱狀態機，是表示有限個狀態以及在這些狀態之間的轉移和動作等行爲的數學計算模型。

    不知道大家看完這條解釋，能 get 到多少東西。我看完的感受是：聽君一席話，如聽一席話。FSM 的內核我是理解的，但總有一種只可意會不可言傳的感覺，因此我無法給出更好的易於理解的解釋。對於這些抽象的東西，我不建議大家摳文字，而是多在實踐中學習和理解，多看他人優秀的代碼，通過外在理解本質。

    維基百科對狀態模式的解釋：

    狀態模式是一種行爲類型的軟件設計模式，它可以讓物件在其內部狀態有變化時，改爲其行爲。這種模式有點像有限狀態機的概念。狀態模式可以被當成成一種策略模式，它能夠在調用模式界面中所定義的方法來切換策略。

    計算機編程中，狀態模式用於，當同一物件基於其內部狀態而有不同行爲，將其行爲進行封裝。對於物件來說，這可以是一種更爲簡潔方式，可以在運行時更改其行爲而無需訴諸條件語句，從而提高可維護性。

    對於狀態模式，我補充一個解釋：

    狀態模式是 將該狀態相關的數據和行爲封裝爲狀態對象，通過切換狀態對象，實現行爲的切換。它與策略模式的區別是：狀態可以通過上下文發起狀態切換請求，因此狀態對象之間通常是互相瞭解的；而策略對象不能發起切換策略請求，因此策略之間互不瞭解。

    如果按照百科對 FSM 的解釋，FSM 和狀態模式其實沒太大關係，看下面這段代碼：

// 計算從1加到5的和
public int func() {
    int r = 0;
    for(int i = 1; i <= 5; i++) {
        r += i;
    }
    return r;
}

    這段代碼和狀態模式有關係嗎？一點關係也沒有。那這段代碼和 FSM 有關係嗎？這就是個有限狀態機。

    這裏的核心在於：狀態是普遍的，有數據就狀態，但狀態模式是侷限與 OOP 的。

    不過，我們日常說的 FSM，並不是廣義上的 FSM，而是一種對狀態模式的封裝（也可以看做一種模式），它仍然是符合廣義 FSM 定義的。

FSM 核心要素

1. 上下文（Context）—— 上下文總是核心要素。

2. 委託，對象將一部分邏輯委託給當前狀態（State）。

3. 事件驅動，狀態切換多基於事件（含輸入）。

4. 狀態轉移表（狀態遷移表）

狀態機的基礎實現

    下面給出基礎的狀態和狀態機抽象，然後基於這個基礎實現，來討論常見的狀態機實現中的一些問題。

狀態抽象：

public interface IState<E> {
    // 進入狀態時調用
    void enter(E entity);
    // 每幀調用
    void execute(E entity); 
    // 退出狀態調用
    void exit(E entity); 
    // 收到外部事件
    void onEvent(E entity, Object event);
}

基礎狀態機實現：

public class StateMachine<E, S extends IState> {
    private E entity; // 實體，或者說上下文
    private S curState; // 當前狀態
    public E getEntity() {
        return entity;
    }
    public void setEntity(E entity) {
        this.entity = entity;
    }
    // 獲取當前狀態
    public S getCurState() {
        return curState;
    }
    // 是否在指定狀態
    public boolean isInState(Class<?> type) {
        // 注意：通常不使用instanceof測試
        return curState != null && curState.getClass() == type;
    }
    // 每幀調用，驅動當前狀態運行
    public void update() {
        if (curState != null) {
            curState.execute(entity);
        }
    }
    // 請求切換到新狀態
    public void changeState(S newState) {
        if (curState != null) {
            curState.exit(entity);
        }
        curState = newState;
        if (newState != null) {
            newState.enter(entity);
        }
    }
    // 收到外部事件 -- 接口與具體需求有關
    public void onEvent(Object event) {
        if (curState != null) {
            curState.onEvent(entity, event);
        }
    }
}

Entity 誤區

    在遊戲開發中，我們實現 FSM 時，通常將 State 的依賴（入參）命名 Entity。這種做法，可能會對新手程序員形成誤導，認爲狀態的依賴是實體（Entity） —— 一些寫 FSM 框架的程序員的也有這樣的誤解。

    實際上，狀態依賴的是上下文（Context），而不是實體（Entity）。我們在日常的編碼中很少定義額外的 Context 類，是因爲多數情況下不需要爲對象封裝額外的數據和功能；另外，在遊戲開發中，我們通常是針對 GameObject 編碼，而我們又習慣稱 GameObject 這類對象爲 Entity（實體），久而久之，遊戲開發中的 FSM 和 State 的參數都變成了 Entity —— 所以，這一誤解在遊戲開發中較爲常見。

下面這種基於 Context 的狀態模式實現，纔是更爲通用的組織方式。

public class Context {
    IState curState;
    // Context的其它數據    
    public void changeState(IState newState) {
        if (curState != null) {
            curState.exit(this);
        }
        curState = newState;
        if (newState != null) {
            newState.enter(this);
        }
    }
    public void onEvent(Object event) {
        curState.onEvent(this, event);
    }
}

單例狀態

    我發現許多書籍在講解狀態模式時，都談到了單例狀態，但依據我個人的編程經驗，我認爲單例狀態的適用性過於狹窄 —— 許多項目的將狀態實現爲單例的，實則並未做到 “單例”。

    通常，導致單例不適用的原因是：State 有自己的臨時數據要維護。針對這個問題，我們可以將這些臨時數據也存儲在上下文中（即數據與行爲分離）來解決 —— 這是很常用的方案。

public class Context {
    EStateType stateType;
    // 標籤類，平鋪所有狀態的數據 ...
}

    有些人認爲這樣做以後，單例狀態就沒有障礙了；但在實際的項目開發中，FSM 的狀態通常還涉及到事件監聽。我們在進入新狀態時，許多時候都需要監聽一些事件，一種常見的寫法是這樣的：

public class MyState implements IState<GameObject> {
    public void enter(GameObject entity) {
        // 可能是監聽實體自身的事件，也可能是監聽外部的事件
        addEventHandler(EventType.customEvent, (event) -> onEvent(entity, event));
    }
}

    看起來是不是沒啥問題？非也。由於我們在 Lambda 中捕獲了 entity，這創建了一箇中間對象，這使得我們的單例名存實亡。

    這個問題的根本是：狀態（State）的上下文不全，狀態在處理事件時，缺少 Entity 這個上下文。實際上，我們可以通過將 Entity 存儲在當前狀態上，以避免 Lambda 捕獲 entity。

// 調整後的State接口
public interface IState<E> extends IEventHandler<FSMEvent> {
    // 進入狀態前調用
    void setEntity(E entity);
    // 進入狀態時調用
    void enter();
    // 每幀調用
    void execute(); 
    // 退出狀態調用
    void exit();
    // 收到外部事件 -- 繼承自EvntHandler接口
    @Override
    void onEvent(FSMEvent event);
}
// 具體狀態示例：
public class MyState implements IState<GameObject> {
    private GameObject entity;
    @Override
    public void setEntity(GameObject entity) {
        this.entity = entity;    
    }
    @Override
    public void enter() {
        // 自身便是EventHandler
        addEventHandler(EventType.customEvent,  this);
    }
    @Override
    public void onEvent(FSMEvent event) {
        //...    
    }
}

    對應的，我們需要調整一下狀態機的實現，這裏只寫出 changeState 方法的修改：

public class StateMachine<E, S extends IState> {
    // 請求切換到新狀態
    public void changeState(S newState) {
        if (curState != null) {
            curState.exit();
            // 退出狀態後清理上下文
            curState.setEntity(null);
        }
        curState = newState;
        if (newState != null) {
            // 進入狀態前注入上下文
            newState.setEntity(entity); 
            newState.enter();
        }
    }
}

    不過，這麼修改以後，State 便不能是單例。

    Q：那如果不主動監聽事件，總是外部推送事件給當前狀態，可行嗎？

    A：怎麼說呢，我回想了下歷史經歷的需求，多數情況下可行。我說個不可行的例子，假設現在有個 AI 需求是：當週圍有敵人施放技能時，如果和對方距離小於 5m，則後退一定距離。

現在，我們需要做兩件事：

1. 維護一定範圍內的對象列表 —— 不僅僅是敵人。

2. 監聽周圍對象施放技能事件。

    現在，我們必須在目標實體上註冊我們的監聽器，否則目標對象在施放技能時將不能確定事件的廣播範圍。有人可能說：廣播場景上所有實體不就行了？單從邏輯的正確性上講，確實是可以；但從性能上講，廣播所有實體將快速耗盡機器的計算資源 —— 觀察者模式、發佈訂閱模式的一個重要作用便是：消息（事件）分流，將廣播變爲組播。

通過 Context 監聽事件

    要保持單例狀態，這個問題的正確解法是：通過上下文（Context）來監聽事件。

    注意我們在前文提到的 Entity 誤區，State 依賴的其實是上下文，而不單純是 Entity，只是多數情況下確實只依賴 Entity 便足夠；這裏我們將 State 的依賴恢復爲 Context。

修改後的 State 接口如下：

public IState<E> {
    // 進入狀態時調用
    void enter(FSMContext<E> ctx);
    // 每幀調用
    void execute(FSMContext<E> ctx); 
    // 退出狀態調用
    void exit(FSMContext<E> ctx);
    // 收到外部事件
    void onEvent(FSMContext<E> ctx, FSMEvent event);
}

FSMContext 的定義如下：

// Context作爲一切邏輯的入口，StateMachine隱藏在Context中
public class FSMContext<E> implements IEventHandler<FSMEvent> {
    private E entity;
    private StateMachine<E> stateMachine;
    public void update() {
        stateMachine.update(this);
    }
    public void changeState(IState nextState) {
        stateMachine.changeState(this, nextState);
    }
    // 所有的外部事件，先回調到Context，再通過Context轉發到StateMachine       
    public void onEvent(FSMEvent fsmEvent) {
        stateMachine.onEvent(this, fsmEvent);
    }
}

具體狀態監聽事件的調整如下：

public class MyState implements IState<GameObject> {
    @Override
    public void enter(FSMContext<GameObject> ctx) {
        // 使用ctx充當EventHandler
        addEventHandler(EventType.customEvent, ctx);
    }
}

    雖然通過 Context 監聽事件，可以避免 lambda 捕獲上下文，但這種方案也有一些問題：

1. 將事件先回調到 Context，再轉發到 StateMachine 並不總是合理，這可能產生邏輯上的變化。比如：在遊戲 AI 中，FSM 通常還包含全局狀態（globalState），將事件轉發至 StateMachine 可能產生不期望的邏輯。

2. Context 承擔了不必要的職責，既讓 Context 變得複雜，也讓使用者感覺莫名其妙。

    說實話，如非必要，我一般不會選擇單例 —— 單例會讓許多問題都變得麻煩；就遊戲中的 FSM 而言，我通常都不使用單例，因爲節省的內存太有限了，真正消耗的內存的地方根本不在這裏。

    PS：這裏給大家留幾個思考。

1. FSMContext 和 StateMachine 是否可以合併？如果可以合併，那麼應當保留誰？

2. 將實體（entity） 替換爲 黑板（blackboard），這套結構發生了什麼變化？

3. 將 FSMContext 替換爲 AIComponent，這套結構又發生了什麼變化？

數據和行爲分離的狀態模式

    在我第一個項目中，還出現了數據和行爲分離的狀態模式，State 僅僅是數據，State 的行爲全部委託給 StateHandler。以 GameObject 的 AI 設計爲例，其代碼大概是這樣的：

public interface IState {
    StateType getType();
}
// 行爲轉移到StateHandler類
public interface StateHandler {
    // 進入狀態時調用
    void enter(GameObject entity, IState state);
    // 每幀調用
    void execute(GameObject entity, IState state); 
    // 退出狀態調用
    void exit(GameObject entity, IState state);
    // 收到外部消息
    void onMessage(GameObject entity, IState state, Telegram telegram);
}
// 對象的AI組件
public class GameObjectAI {
    private GameObject entity;
    private IState curState;
    private final EnumMap<StateType, StateHandler> handlerMap = new EnumMap<>(StateType.class);
    public void registerHandler(StateType stateType, StateHandler handler) {
        handlerMap.put(stateType, handler);
    }
    public StateHandler getHandler(StateType stateType) {
        return handlerMap.get(stateType);
    }
    public void update() {
        handlerMap.get(curState.getType()).execute(entity, curState);
    }
    public void onMessage(Telegram telegram) {
        handlerMap.get(curState.getType()).onMessage(entity, curState, telegram);
    }
}

    說實話，這套設計在我離職時（入職三年）都沒有理解得很好。這個設計，不止我有疑惑，另一個維護場景內代碼的同事也有這個疑惑，因爲這樣寫有一個很大的問題：總是要多寫一個 Handler 類，還總是需要向下類型轉換。

    後來，我和同事問了 Leader，Leader 並未對我們做過多的解釋，只是簡單地說了兩句：數據和行爲分離，有更好的擴展性；不過多數情況下，我們也確實不需要這麼高的擴展性，你們也可以不按照這種方式寫。

    說實話，我當時並沒聽懂，那時的我還是一個菜鳥，在代碼設計上的思考還很欠缺。後來，我和同事在寫副本玩法時，便不再按照 State + StateHandler 的方式組織代碼，只有 AI 模塊仍然按照這種方式擴展。

    這套設計，我認爲多數讀者是沒有見過的，也看不明白這麼設計有什麼好處，狀態的邏輯明明能寫在 State 類中，爲什麼要捨近求遠寫在 StateHandler 類中呢？

    就這裏的 FSM 例子，我覺得不太能體現出 “更好的擴展性” 這一點。數據和行爲分離具有更好的擴展性，主要體現在對象的行爲可能產生【多維度的變化】時。如果用繼承來實現多維度的行爲變化，一旦出現不同行爲之間的組合，繼承體系將難以駕馭，而使用組合則容易實現。

（裝飾者模式、橋接模式也是用於解決這類問題的）

    這裏我補充一個優點：減少了數據類的類層次 。在遊戲開發中，減少數據類類層次是非常重要的，以後詳細解釋。

State + StateHandler 模式的缺點：

1. 多數情況下，我們並不需要這麼高的靈活度，因此數據和行爲分離反而增加了我們的開發和維護負擔。

2. StateHandler 需要進行大量的向下類型轉換，有額外的開銷。

    PS：雖然數據與行爲分離我也用得很熟練了，但如果不是在這個項目待過，大概也寫不出 State + StateHandler 這種結構

基礎狀態機的小缺陷

    現在我談一談在日常使用 FSM 中遇見的一些問題，這些問題也是使我不再使用基礎的 FSM 的原因。

狀態之間需要相互瞭解

    雖然許多時候可以由外部來切換狀態，比如 Context 主動發起狀態切換，但多數情況下由 State 自身來切換狀態，因此狀態之間需要互相瞭解，這就導致了複雜的依賴。

    要解決這個問題：可以通過 State 在執行完成時，告知 Context 自身執行完畢（成功或失敗），由 Context 來決定下一步 —— 我們需要實現特殊的 Context 類。

    PS：C# 的 async / await 狀態機其實就是這麼運作的。

public class MyState implements IState {
    public void execute(FSMContext ctx) {
        if (cond()) {
            ctx.onComplected(this, Status.SUCCESS);
            return;        
        }
        // ...
    }
}

複雜的狀態遷移圖（不支持層次化結構）

    由於基礎的 FSM 不支持層次化結構，所有的狀態都處於同一層級，且通常狀態之間需要相互瞭解，這在狀態數量較多時，會產生非常複雜的狀態遷移圖，代碼的維護複雜度急劇上升。

    說起來，以前用 FSM 實現遊戲 AI 時，並沒有遇見特別複雜的狀態遷移圖，反而是在做玩家的登錄狀態機（會話生命週期）時，爲保證健壯性，維護過複雜的狀態機（9 個狀態）。在實現登錄狀態機時，我就發現狀態機不能分層是個問題，當服務器和客戶端完成【數據庫數據】同步後，其實玩家的系統功能操作已經可用，只是場景內的功能尚不可用；但由於狀態機是單層的，因此我不能將完成數據庫同步後的狀態定義爲 Playing，而只能選擇將進入場景後定義爲 Playing 狀態。

    針對這個問題，也有一個解決方案：分層狀態機（HFSM）。不過，我並沒有寫過分層狀態機，我直接從基礎的 FSM 過渡到了通用的任務樹（TaskTree），因此我在這裏不講 HFSM。

缺少運行結果（Status）

    有時我們需要知道當前狀態是執行成功而退出，還是失敗而退出，而基礎的 FSM 框架中是不包含這部分邏輯的。不過，這也並不是普遍需求，而且支持它也並不困難，因此是個小問題。

public abstract class State {
    // 增加狀態的執行結果 UNKNOWN, SUCCESS, FAILED，CANCELLED...
    private Status status = Status.UNKNOWN; 
}
public class MyState extends State {
    public void execute(FSMContext ctx) {
        // 先設置執行結果，然後調用changeState
        setStatus(Status.SUCCESS);
        ctx.changeState(nextState);
        return;
    }
}

    PS：狀態機可以在 ChangeState 的時候檢查任務的 status，如果未賦值，可拋出異常或統一設置爲取消。

更適合執行而非決策

    在基礎的 FSM 實現中，State 不包含運行結果，FSM 只是簡單的執行當前狀態，並響應狀態切換。因此 FSM 並不是控制器，而只是執行器 —— 缺少決策邏輯。

    而在遊戲 AI 中，決策是核心，執行是其次。所以，不論是 FSM，還是 HFSM，都難以勝任複雜的遊戲 AI —— 因爲它們做出的決策是簡單的，“缺少思考” 的。

基礎狀態機的優點

    三點：簡單，高效，強大。

    基礎的 FSM 實現是非常簡單的，稍有編程經驗的程序員都能照貓畫虎，很快學會；而又因爲 FSM 的實現簡單，因此其幾乎沒有額外的開銷，因此是高性能的 —— 比行爲樹高 N 倍。

    不過，雖然 FSM 的實現是簡單的，但 FSM 並不弱小，反而非常強大，因爲 FSM 可以模擬我們遇見的大部分事物；所以，有限狀態機（FSM）永遠是你最有用的工具之一，屬於必須掌握的技術。

結語

    本文介紹了 FSM 的基礎實現，以及基礎的 FSM 實現中包含的一些缺陷，希望能幫助大家在使用 FSM 中的一些問題。下一篇，我們開始講行爲樹。

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/3boQq1pWXo9L1FIxcN29qg