如何簡潔實現(xiàn)游戲中的AI

端午節(jié)放假總結(jié)了一下好久前寫過的一些游戲引擎，其中NPC等游戲AI的實現(xiàn)無疑是最繁瑣的部分，現(xiàn)在，給大家分享一下：

從一個簡單的情景開始

怪物，是游戲中的一個基本概念。游戲中的單位分類，不外乎玩家、NPC、怪物這幾種。其中，AI 一定是與三類實體都會產(chǎn)生交集的游戲模塊之一。
以我們熟悉的任意一款游戲中的人形怪物為例，假設(shè)有一種怪物的 AI 需求是這樣的：

  •  大部分情況下，漫無目的巡邏。

  •  玩家進入視野，鎖定玩家為目標(biāo)開始攻擊。

  •  Hp 低到一定程度，怪會想法設(shè)法逃跑，并說幾句話。

我們以這個為模型，進行這篇文章之后的所有討論。為了簡化問題，以省去一些不必要的討論，將文章的核心定位到人工智能上，這里需要注意幾點的是：

  •  不再考慮 entity 之間的消息傳遞機制，例如判斷玩家進入視野，不再通過事件機制觸發(fā)，而是通過該人形怪的輪詢觸發(fā)。

  •  不再考慮 entity 的行為控制機制，簡化這個 entity 的控制模型。不論是底層是基于 SteeringBehaviour 或者是瞬移，不論是異步驅(qū)的還是主循環(huán)輪詢，都不在本文模型的討論之列。

首先可以很容易抽象出來 IUnit：

public interface IUnit
    {
        void ChangeState(UnitStateEnum state);
        void Patrol(); 
        IUnit GetNearestTarget(); 
        void LockTarget(IUnit unit);
        float GetFleeBloodRate();
        bool CanMove();
        bool HpRateLessThan(float rate);
        void Flee();
        void Speak();
    }

public interface IUnit
    {
        void ChangeState(UnitStateEnum state);
        void Patrol(); 
        IUnit GetNearestTarget(); 
        void LockTarget(IUnit unit);
        float GetFleeBloodRate();
        bool CanMove();
        bool HpRateLessThan(float rate);
        void Flee();
        void Speak();
    }

然后，我們可以通過一個簡單的有限狀態(tài)機 (FSM) 來控制這個單位的行為。不同狀態(tài)下，單位都具有不同的行為準(zhǔn)則，以形成智能體。
具體來說，我們可以定義這樣幾種狀態(tài)：

  •  巡邏狀態(tài)： 會執(zhí)行巡邏，同時檢查是否有敵對單位接近，接近的話進入戰(zhàn)斗狀態(tài)。

  •  戰(zhàn)斗狀態(tài)： 會執(zhí)行戰(zhàn)斗，同時檢查自己的血量是否達到逃跑線以下，達成檢查了就會逃跑。

  •  逃跑狀態(tài)： 會逃跑，同時說一次話。

最原始的狀態(tài)機的代碼：

public interface IState<TState, TUnit> where TState : IConvertible
    {
        TState Enum { get; }
        TUnit Self { get; }
        void OnEnter();
        void Drive();
        void OnExit();
    }

public interface IState<TState, TUnit> where TState : IConvertible
    {
        TState Enum { get; }
        TUnit Self { get; }
        void OnEnter();
        void Drive();
        void OnExit();
    }

以逃跑狀態(tài)為例：

public class FleeState : UnitStateBase
    {
        public FleeState(IUnit self) : base(UnitStateEnum.Flee, self)
        {
        }
        public override void OnEnter()
        {
            Self.Flee();
        }
        public override void Drive()
        {
            var unit = Self.GetNearestTarget();
            if (unit != null)
            {
                return;
            }

            Self.ChangeState(UnitStateEnum.Patrol);
        }
    }

public class FleeState : UnitStateBase
    {
        public FleeState(IUnit self) : base(UnitStateEnum.Flee, self)
        {
        }
        public override void OnEnter()
        {
            Self.Flee();
        }
        public override void Drive()
        {
            var unit = Self.GetNearestTarget();
            if (unit != null)
            {
                return;
            }
 
            Self.ChangeState(UnitStateEnum.Patrol);
        }
    }

決策邏輯與上下文分離

上述是一個最簡單、最常規(guī)的狀態(tài)機實現(xiàn)。估計只有學(xué)生會這樣寫，業(yè)界肯定是沒人這樣寫 AI 的，不然游戲怎么死的都不知道。

首先有一個非常明顯的性能問題：狀態(tài)機本質(zhì)是描述狀態(tài)遷移的，并不需要記錄 entity 的 context，如果 entity 的 context 記錄在 State上，那么狀態(tài)機這個遷移邏輯就需要每個 entity 都來一份 instance，這么一個簡單的狀態(tài)遷移就需要消耗大約 X 個字節(jié)，那么一個場景 1w 個怪，這些都屬于白白消耗的內(nèi)存。就目前的實現(xiàn)來看，具體的一個 State 實例內(nèi)部 hold 住了 Unit，所以 State 實例是沒辦法復(fù)用的。

針對這一點，我們做一下優(yōu)化。對這個狀態(tài)機，把 Context 完全剝離出來。

修改狀態(tài)機接口定義：

public interface IState<TState, TUnit> where TState : IConvertible
    {
        TState Enum { get; }
        void OnEnter(TUnit self);
        void Drive(TUnit self);
        void OnExit(TUnit self);
    }

public interface IState<TState, TUnit> where TState : IConvertible
    {
        TState Enum { get; }
        void OnEnter(TUnit self);
        void Drive(TUnit self);
        void OnExit(TUnit self);
    }

還是拿之前實現(xiàn)好的逃跑狀態(tài)作為例子：

public class FleeState : UnitStateBase
    {
        public FleeState() : base(UnitStateEnum.Flee)
        {
        }
        public override void OnEnter(IUnit self)
        {
            base.OnEnter(self);
            self.Flee();
        }
        public override void Drive(IUnit self)
        {
            base.Drive(self);

            var unit = self.GetNearestTarget();
            if (unit != null)
            {
                return;
            }

            self.ChangeState(UnitStateEnum.Patrol);
        }
    }

public class FleeState : UnitStateBase
    {
        public FleeState() : base(UnitStateEnum.Flee)
        {
        }
        public override void OnEnter(IUnit self)
        {
            base.OnEnter(self);
            self.Flee();
        }
        public override void Drive(IUnit self)
        {
            base.Drive(self);
 
            var unit = self.GetNearestTarget();
            if (unit != null)
            {
                return;
            }
 
            self.ChangeState(UnitStateEnum.Patrol);
        }
    }

這樣，就區(qū)分了動態(tài)與靜態(tài)。靜態(tài)的是狀態(tài)之間的遷移邏輯，只要不做熱更新，是不會變的結(jié)構(gòu)。動態(tài)的是狀態(tài)遷移過程中的上下文，根據(jù)不同的上下文來決定。

分層有限狀態(tài)機

最原始的狀態(tài)機方案除了性能存在問題，還有一個比較嚴(yán)重的問題。那就是這種狀態(tài)機框架無法描述層級結(jié)構(gòu)的狀態(tài)。
假設(shè)需要對一開始的需求進行這樣的擴展：怪在巡邏狀態(tài)下有可能進入怠工狀態(tài)，同時要求，怠工狀態(tài)下也會進行進入戰(zhàn)斗的檢查。

這樣的話，雖然在之前的框架下，單獨做一個新的怠工狀態(tài)也可以，但是仔細(xì)分析一下，我們會發(fā)現(xiàn)，其實本質(zhì)上巡邏狀態(tài)只是一個抽象的父狀態(tài)，其存在的意義就是進行戰(zhàn)斗檢查；而具體的是在按路線巡邏還是怠工，其實都是巡邏狀態(tài)的一個子狀態(tài)。

狀態(tài)之間就有了層級的概念，各自獨立的狀態(tài)機系統(tǒng)就無法滿足需求，需要一種分層次的狀態(tài)機，原先的狀態(tài)機接口設(shè)計就需要徹底改掉了。

在重構(gòu)狀態(tài)框架之前，需要注意兩點：

因為父狀態(tài)需要關(guān)注子狀態(tài)的運行結(jié)果，所以狀態(tài)的 Drive 接口需要一個運行結(jié)果的返回值。

子狀態(tài)，比如怠工，一定是有跨幀的需求在的，所以這個 Result，我們定義為 Continue、Sucess、Failure。

子狀態(tài)一定是由父狀態(tài)驅(qū)動的。

考慮這樣一個組合狀態(tài)情景：巡邏時，需要依次得先走到一個點，然后怠工一會兒，再走到下一個點，然后再怠工一會兒，循環(huán)往復(fù)。這樣就需要父狀態(tài)（巡邏狀態(tài)）注記當(dāng)前激活的子狀態(tài)，并且根據(jù)子狀態(tài)執(zhí)行結(jié)果的不同來修改激活的子狀態(tài)集合。這樣不僅是 Unit 自身有上下文，連組合狀態(tài)也有了自己的上下文。

為了簡化討論，我們還是從 non-ContextFree 層次狀態(tài)機系統(tǒng)設(shè)計開始。

修改后的狀態(tài)定義：

public interface IState<TState, TCleverUnit, TResult> 
        where TState : IConvertible
    {
        // ...
        TResult Drive();
        // ...
    }

public interface IState<TState, TCleverUnit, TResult> 
        where TState : IConvertible
    {
        // ...
        TResult Drive();
        // ...
    }

組合狀態(tài)的定義：

public abstract class UnitCompositeStateBase : UnitStateBase
    {
        protected readonly LinkedList<UnitStateBase> subStates = new LinkedList<UnitStateBase>();

        // ...
        protected Result ProcessSubStates()
        {
            if (subStates.Count == 0)
            {
                return Result.Success;
            }

            var front = subStates.First;
            var res = front.Value.Drive();

            if (res != Result.Continue)
            {
                subStates.RemoveFirst();
            }

            return Result.Continue;
        }
        // ...
    }

public abstract class UnitCompositeStateBase : UnitStateBase
    {
        protected readonly LinkedList<UnitStateBase> subStates = new LinkedList<UnitStateBase>();
 
        // ...
        protected Result ProcessSubStates()
        {
            if (subStates.Count == 0)
            {
                return Result.Success;
            }
 
            var front = subStates.First;
            var res = front.Value.Drive();
 
            if (res != Result.Continue)
            {
                subStates.RemoveFirst();
            }
 
            return Result.Continue;
        }
        // ...
    }

巡邏狀態(tài)現(xiàn)在是一個組合狀態(tài)：

public class PatrolState : UnitCompositeStateBase
    {
        // ...
        public override void OnEnter()
        {
            base.OnEnter();
            AddSubState(new MoveToState(Self));
        }

        public override Result Drive()
        {
            if (subStates.Count == 0)
            {
                return Result.Success;
            }

            var unit = Self.GetNearestTarget();
            if (unit != null)
            {
                Self.LockTarget(unit);
                return Result.Success;
            }

            var front = subStates.First;
            var ret = front.Value.Drive();

            if (ret != Result.Continue)
            {
                if (front.Value.Enum == CleverUnitStateEnum.MoveTo)
                {
                    AddSubState(new IdleState(Self));
                }
                else
                {
                    AddSubState(new MoveToState(Self));
                }
            }
            
            return Result.Continue;
        }
    }

public class PatrolState : UnitCompositeStateBase
    {
        // ...
        public override void OnEnter()
        {
            base.OnEnter();
            AddSubState(new MoveToState(Self));
        }
 
        public override Result Drive()
        {
            if (subStates.Count == 0)
            {
                return Result.Success;
            }
 
            var unit = Self.GetNearestTarget();
            if (unit != null)
            {
                Self.LockTarget(unit);
                return Result.Success;
            }
 
            var front = subStates.First;
            var ret = front.Value.Drive();
 
            if (ret != Result.Continue)
            {
                if (front.Value.Enum == CleverUnitStateEnum.MoveTo)
                {
                    AddSubState(new IdleState(Self));
                }
                else
                {
                    AddSubState(new MoveToState(Self));
                }
            }
            
            return Result.Continue;
        }
    }

看過《游戲人工智能編程精粹》的同學(xué)可能看到這里就會發(fā)現(xiàn)，這種層次狀態(tài)機其實就是這本書里講的目標(biāo)驅(qū)動的狀態(tài)機。組合狀態(tài)就是組合目標(biāo)，子狀態(tài)就是子目標(biāo)。父目標(biāo) / 狀態(tài)的調(diào)度取決于子目標(biāo) / 狀態(tài)的完成情況。

這種狀態(tài)框架與普通的 trivial 狀態(tài)機模型的區(qū)別僅僅是增加了對層次狀態(tài)的支持，狀態(tài)的遷移還是需要靠顯式的 ChangeState 來做。

這本書里面的狀態(tài)框架，每個狀態(tài)的執(zhí)行 status 記錄在了實例內(nèi)部，不方便后續(xù)的優(yōu)化，我們這里實現(xiàn)的時候首先把這個做成純驅(qū)動式的。但是還不夠?，F(xiàn)在之前的 ContextFree 優(yōu)化成果已經(jīng)回退掉了，我們還需要補充回來。

分層的上下文

我們對之前重構(gòu)出來的層次狀態(tài)機框架再進行一次 Context 分離優(yōu)化。
要優(yōu)化的點有這樣幾個：

首先是繼續(xù)之前的，unit 不應(yīng)該作為一個 state 自己的內(nèi)部 status。

組合狀態(tài)的實例內(nèi)部不應(yīng)該包括自身執(zhí)行的 status。目前的組合狀態(tài)，可以動態(tài)增刪子狀態(tài)，也就是根據(jù) status 決定了結(jié)構(gòu)的狀態(tài)，理應(yīng)分離靜態(tài)與動態(tài)。巡邏狀態(tài)組合了兩個子狀態(tài)——A 和 B，邏輯中是一個完成了就添加另一個，這樣一想的話，其實巡邏狀態(tài)應(yīng)該重新描述——先進行 A，再進行 B，循環(huán)往復(fù)。
　　
　　由于有了父狀態(tài)的概念，其實狀態(tài)接口的設(shè)計也可以再迭代，理論上只需要一個 drive 即可。因為狀態(tài)內(nèi)部的上下文要全部分離出來，所以也沒必要對外提供 OnEnter、OnExit，提供這兩個接口的意義只是做一層內(nèi)部信息的隱藏，但是現(xiàn)在內(nèi)部的 status 沒了，也就沒必要隱藏了。
　　
具體分析一下需要拆出的 status：

  • 一部分是 entity 本身的 status，這里可以簡單的認(rèn)為是 unit。
  • 另一部分是 state 本身的 status。
  • 對于組合狀態(tài)，這個 status 描述的是我當(dāng)前執(zhí)行到哪個 substate。
  • 對于原子狀態(tài)，這個 status 描述的種類可能有所區(qū)別。
  • 例如 MoveTo/Flee，OnEnter 的時候，修改了 unit 的 status，然后 Drive 的時候去 check。
  • 例如 Idle，OnEnter 時改了自己的 status，然后 Drive 的時候去 check。
    經(jīng)過總結(jié)，我們可以發(fā)現(xiàn)，每個狀態(tài)的 status 本質(zhì)上都可以通過一個變量來描述。一個 State 作為一個最小粒度的單元，具有這樣的 Concept： 輸入一個 Context，輸出一個 Result。

Context 暫時只需要包括這個 Unit，和之前所說的 status。同時，考慮這樣一個問題：

  • 父狀態(tài) A，子狀態(tài) B。
  • 子狀態(tài) B 向上返回 Continue 的同時，status 記錄下來為 b。
  • 父狀態(tài) ADrive 子狀態(tài)的結(jié)果為 Continue，自身也需要向上拋出 Continue，同時自己也有 status 為 a。
    這樣，再還原現(xiàn)場時，就需要即給 A 一個 a，還需要讓 A 有能力從 Context 中拿到需要給 B 的 b。因此上下文的結(jié)構(gòu)理應(yīng)是遞歸定義的，是一個層級結(jié)構(gòu)。

Context 如下定義：

public class Continuation
    {
        public Continuation SubContinuation { get; set; }
        public int NextStep { get; set; }
        public object Param { get; set; }
    }

    public class Context<T>
    {
        public Continuation Continuation { get; set; }
        public T Self { get; set; }
    }

public class Continuation
    {
        public Continuation SubContinuation { get; set; }
        public int NextStep { get; set; }
        public object Param { get; set; }
    }
 
    public class Context<T>
    {
        public Continuation Continuation { get; set; }
        public T Self { get; set; }
    }

修改 State 的接口定義為：

public interface IState<TCleverUnit, TResult>
     {
         TResult Drive(Context<TCleverUnit> ctx);
    }

public interface IState<TCleverUnit, TResult>
     {
         TResult Drive(Context<TCleverUnit> ctx);
    }

已經(jīng)相當(dāng)簡潔了。

這樣，我們對之前的巡邏狀態(tài)也做下修改，達到一個 ContextFree 的效果。利用 Context 中的 Continuation 來確定當(dāng)前結(jié)點應(yīng)該從什么狀態(tài)繼續(xù)：

public class PatrolState : IState<ICleverUnit, Result>
    {
        private readonly List<IState<ICleverUnit, Result>> subStates;
        public PatrolState()
        {
            subStates = new List<IState<ICleverUnit, Result>>()
            {
                new MoveToState(),
                new IdleState(),
            };
        }
        public Result Drive(Context<ICleverUnit> ctx)
        {
            var unit = ctx.Self.GetNearestTarget();
            if (unit != null)
            {
                ctx.Self.LockTarget(unit);

                return Result.Success;
            }

            var nextStep = 0;
            if (ctx.Continuation != null)
            {
                // Continuation
                var thisContinuation = ctx.Continuation;

                ctx.Continuation = thisContinuation.SubContinuation;

                var ret = subStates[nextStep].Drive(ctx);

                if (ret == Result.Continue)
                {
                    thisContinuation.SubContinuation = ctx.Continuation;
                    ctx.Continuation = thisContinuation;

                    return Result.Continue;
                }
                else if (ret == Result.Failure)
                {
                    ctx.Continuation = null;

                    return Result.Failure;
                }

                ctx.Continuation = null;
                nextStep = thisContinuation.NextStep + 1;
            }

            for (; nextStep < subStates.Count; nextStep++)
            {
                var ret = subStates[nextStep].Drive(ctx);
                if (ret == Result.Continue)
                {
                    ctx.Continuation = new Continuation()
                    {
                        SubContinuation = ctx.Continuation,
                        NextStep = nextStep,
                    };

                    return Result.Continue;
                } 
                else if (ret == Result.Failure) 
                {
                    ctx.Continuation = null;

                    return Result.Failure;
                }
            }

            ctx.Continuation = null;

            return Result.Success;
        }
    }

public class PatrolState : IState<ICleverUnit, Result>
    {
        private readonly List<IState<ICleverUnit, Result>> subStates;
        public PatrolState()
        {
            subStates = new List<IState<ICleverUnit, Result>>()
            {
                new MoveToState(),
                new IdleState(),
            };
        }
        public Result Drive(Context<ICleverUnit> ctx)
        {
            var unit = ctx.Self.GetNearestTarget();
            if (unit != null)
            {
                ctx.Self.LockTarget(unit);
 
                return Result.Success;
            }
 
            var nextStep = 0;
            if (ctx.Continuation != null)
            {
                // Continuation
                var thisContinuation = ctx.Continuation;
 
                ctx.Continuation = thisContinuation.SubContinuation;
 
                var ret = subStates[nextStep].Drive(ctx);
 
                if (ret == Result.Continue)
                {
                    thisContinuation.SubContinuation = ctx.Continuation;
                    ctx.Continuation = thisContinuation;
 
                    return Result.Continue;
                }
                else if (ret == Result.Failure)
                {
                    ctx.Continuation = null;
 
                    return Result.Failure;
                }
 
                ctx.Continuation = null;
                nextStep = thisContinuation.NextStep + 1;
            }
 
            for (; nextStep < subStates.Count; nextStep++)
            {
                var ret = subStates[nextStep].Drive(ctx);
                if (ret == Result.Continue)
                {
                    ctx.Continuation = new Continuation()
                    {
                        SubContinuation = ctx.Continuation,
                        NextStep = nextStep,
                    };
 
                    return Result.Continue;
                } 
                else if (ret == Result.Failure) 
                {
                    ctx.Continuation = null;
 
                    return Result.Failure;
                }
            }
 
            ctx.Continuation = null;
 
            return Result.Success;
        }
    }

subStates 是 readonly 的，在組合狀態(tài)構(gòu)造的一開始就確定了值。這樣結(jié)構(gòu)本身就是靜態(tài)的，而上下文是動態(tài)的。不同的 entity instance 共用同一個樹的 instance。

優(yōu)化到這個版本，至少在性能上已經(jīng)符合要求了，所有實例共享一個靜態(tài)的狀態(tài)遷移邏輯。面對之前提出的需求，也能夠解決。至少算是一個經(jīng)過對《游戲人工智能編程精粹》中提出的目標(biāo)驅(qū)動狀態(tài)機模型優(yōu)化后的一個符合工業(yè)應(yīng)用標(biāo)準(zhǔn)的 AI 框架。拿來做小游戲或者是一些 AI 很簡單的游戲已經(jīng)綽綽有余了。

心動了嗎？還不趕緊動起來，打造屬于自己的游戲世界！頓時滿滿的自豪感，真的很想知道大家的想法，還請持續(xù)關(guān)注更新，更多干貨和資料請直接聯(lián)系我，也可以加群710520381，邀請碼：柳貓，歡迎大家共同討論

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

  • Spring Cloud為開發(fā)人員提供了快速構(gòu)建分布式系統(tǒng)中一些常見模式的工具（例如配置管理，服務(wù)發(fā)現(xiàn)，斷路器，智...
    卡卡羅2017閱讀 136,506評論 19贊 139
  • Spring Boot 參考指南 介紹 轉(zhuǎn)載自:https://www.gitbook.com/book/qbgb...
    毛宇鵬閱讀 47,253評論 6贊 342
  • 羨慕 月光的手 憑兩只袖管 奏起黑夜 點點音符 是輕彈的淚珠 還是逃離的心結(jié) 沒有清脆的答案 只有節(jié)拍 和跟著節(jié)拍...
    何事亂翻書閱讀 220評論 0贊 3
  • 缺愛：對于愛情，缺愛的孩子比較“慢熱”，心里有恐懼感，害怕如果我投入了結(jié)果會怎樣…… 但是一旦投入了，就會比較偏激...
    嬌之語閱讀 15,666評論 0贊 4
  • 【讀書10分鐘】 工作生活更輕松 秦剛老師在《創(chuàng)業(yè)僅半年，如何融資超1.5億》中分享了: 一位互聯(lián)網(wǎng)業(yè)內(nèi)的傳奇人物...
    璇轉(zhuǎn)閱讀 154評論 0贊 0

友情鏈接更多精彩內(nèi)容