端午节放假总结了一下好久前写过的一些游戏引擎，其中NPC等游戏AI的实现无疑是最繁琐的部分，现在，给大家分享一下：

从一个简单的情景开始

怪物，是游戏中的一个基本概念。游戏中的单位分类，不外乎玩家、NPC、怪物这几种。其中，AI 一定是与三类实体都会产生交集的游戏模块之一。 以我们熟悉的任意一款游戏中的人形怪物为例，假设有一种怪物的 AI 需求是这样的：

• 大部分情况下，漫无目的巡逻。

• 玩家进入视野，锁定玩家为目标开始攻击。

• Hp 低到一定程度，怪会想法设法逃跑，并说几句话。

我们以这个为模型，进行这篇文章之后的所有讨论。为了简化问题，以省去一些不必要的讨论，将文章的核心定位到人工智能上，这里需要注意几点的是：

• 不再考虑 entity 之间的消息传递机制，例如判断玩家进入视野，不再通过事件机制触发，而是通过该人形怪的轮询触发。

• 不再考虑 entity 的行为控制机制，简化这个 entity 的控制模型。不论是底层是基于 SteeringBehaviour 或者是瞬移，不论是异步驱的还是主循环轮询，都不在本文模型的讨论之列。

首先可以很容易抽象出来 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();    }

然后，我们可以通过一个简单的有限状态机 (FSM) 来控制这个单位的行为。不同状态下，单位都具有不同的行为准则，以形成智能体。 具体来说，我们可以定义这样几种状态：

• 巡逻状态： 会执行巡逻，同时检查是否有敌对单位接近，接近的话进入战斗状态。

• 战斗状态： 会执行战斗，同时检查自己的血量是否达到逃跑线以下，达成检查了就会逃跑。

• 逃跑状态： 会逃跑，同时说一次话。

最原始的状态机的代码：

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

以逃跑状态为例：

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);        }    }

决策逻辑与上下文分离

上述是一个最简单、最常规的状态机实现。估计只有学生会这样写，业界肯定是没人这样写 AI 的，不然游戏怎么死的都不知道。

首先有一个非常明显的性能问题：状态机本质是描述状态迁移的，并不需要记录 entity 的 context，如果 entity 的 context 记录在 State上，那么状态机这个迁移逻辑就需要每个 entity 都来一份 instance，这么一个简单的状态迁移就需要消耗大约 X 个字节，那么一个场景 1w 个怪，这些都属于白白消耗的内存。就目前的实现来看，具体的一个 State 实例内部 hold 住了 Unit，所以 State 实例是没办法复用的。

针对这一点，我们做一下优化。对这个状态机，把 Context 完全剥离出来。

修改状态机接口定义：

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

还是拿之前实现好的逃跑状态作为例子：

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);        }    }

这样，就区分了动态与静态。静态的是状态之间的迁移逻辑，只要不做热更新，是不会变的结构。动态的是状态迁移过程中的上下文，根据不同的上下文来决定。

分层有限状态机

最原始的状态机方案除了性能存在问题，还有一个比较严重的问题。那就是这种状态机框架无法描述层级结构的状态。 假设需要对一开始的需求进行这样的扩展：怪在巡逻状态下有可能进入怠工状态，同时要求，怠工状态下也会进行进入战斗的检查。

这样的话，虽然在之前的框架下，单独做一个新的怠工状态也可以，但是仔细分析一下，我们会发现，其实本质上巡逻状态只是一个抽象的父状态，其存在的意义就是进行战斗检查；而具体的是在按路线巡逻还是怠工，其实都是巡逻状态的一个子状态。

状态之间就有了层级的概念，各自独立的状态机系统就无法满足需求，需要一种分层次的状态机，原先的状态机接口设计就需要彻底改掉了。

在重构状态框架之前，需要注意两点：

因为父状态需要关注子状态的运行结果，所以状态的 Drive 接口需要一个运行结果的返回值。

子状态，比如怠工，一定是有跨帧的需求在的，所以这个 Result，我们定义为 Continue、Sucess、Failure。

子状态一定是由父状态驱动的。

考虑这样一个组合状态情景：巡逻时，需要依次得先走到一个点，然后怠工一会儿，再走到下一个点，然后再怠工一会儿，循环往复。这样就需要父状态（巡逻状态）注记当前激活的子状态，并且根据子状态执行结果的不同来修改激活的子状态集合。这样不仅是 Unit 自身有上下文，连组合状态也有了自己的上下文。

为了简化讨论，我们还是从 non-ContextFree 层次状态机系统设计开始。

修改后的状态定义：

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

组合状态的定义：

public abstract class UnitCompositeStateBase : UnitStateBase    {        protected readonly LinkedList
    
      subStates = new LinkedList
     
      ();        // ...        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
    
      subStates = new LinkedList
     
      ();         // ...        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 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;        }    }

看过《游戏人工智能编程精粹》的同学可能看到这里就会发现，这种层次状态机其实就是这本书里讲的目标驱动的状态机。组合状态就是组合目标，子状态就是子目标。父目标 / 状态的调度取决于子目标 / 状态的完成情况。

这种状态框架与普通的 trivial 状态机模型的区别仅仅是增加了对层次状态的支持，状态的迁移还是需要靠显式的 ChangeState 来做。

这本书里面的状态框架，每个状态的执行 status 记录在了实例内部，不方便后续的优化，我们这里实现的时候首先把这个做成纯驱动式的。但是还不够。现在之前的 ContextFree 优化成果已经回退掉了，我们还需要补充回来。

分层的上下文

我们对之前重构出来的层次状态机框架再进行一次 Context 分离优化。 要优化的点有这样几个：

首先是继续之前的，unit 不应该作为一个 state 自己的内部 status。

组合状态的实例内部不应该包括自身执行的 status。目前的组合状态，可以动态增删子状态，也就是根据 status 决定了结构的状态，理应分离静态与动态。巡逻状态组合了两个子状态——A 和 B，逻辑中是一个完成了就添加另一个，这样一想的话，其实巡逻状态应该重新描述——先进行 A，再进行 B，循环往复。 　　 　　由于有了父状态的概念，其实状态接口的设计也可以再迭代，理论上只需要一个 drive 即可。因为状态内部的上下文要全部分离出来，所以也没必要对外提供 OnEnter、OnExit，提供这两个接口的意义只是做一层内部信息的隐藏，但是现在内部的 status 没了，也就没必要隐藏了。 　　 具体分析一下需要拆出的 status：

• 一部分是 entity 本身的 status，这里可以简单的认为是 unit。
• 另一部分是 state 本身的 status。
• 对于组合状态，这个 status 描述的是我当前执行到哪个 substate。
• 对于原子状态，这个 status 描述的种类可能有所区别。
• 例如 MoveTo/Flee，OnEnter 的时候，修改了 unit 的 status，然后 Drive 的时候去 check。
• 例如 Idle，OnEnter 时改了自己的 status，然后 Drive 的时候去 check。 经过总结，我们可以发现，每个状态的 status 本质上都可以通过一个变量来描述。一个 State 作为一个最小粒度的单元，具有这样的 Concept： 输入一个 Context，输出一个 Result。

Context 暂时只需要包括这个 Unit，和之前所说的 status。同时，考虑这样一个问题：

• 父状态 A，子状态 B。
• 子状态 B 向上返回 Continue 的同时，status 记录下来为 b。
• 父状态 ADrive 子状态的结果为 Continue，自身也需要向上抛出 Continue，同时自己也有 status 为 a。 这样，再还原现场时，就需要即给 A 一个 a，还需要让 A 有能力从 Context 中拿到需要给 B 的 b。因此上下文的结构理应是递归定义的，是一个层级结构。

Context 如下定义：

public class Continuation    {        public Continuation SubContinuation { get; set; }        public int NextStep { get; set; }        public object Param { get; set; }    }    public class Context
    
         {        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
     
          {        public Continuation Continuation { get; set; }        public T Self { get; set; }    }
     
    

修改 State 的接口定义为：

public interface IState
    
          {         TResult Drive(Context
     
       ctx);    }public interface IState
      
            {         TResult Drive(Context
       
         ctx);    }
       
      
     
    

已经相当简洁了。

这样，我们对之前的巡逻状态也做下修改，达到一个 ContextFree 的效果。利用 Context 中的 Continuation 来确定当前结点应该从什么状态继续：

public class PatrolState : IState
    
         {        private readonly List
     
      
       > subStates;        public PatrolState()        {            subStates = new List
       
        
         >()            {                new MoveToState(),                new IdleState(),            };        }        public Result Drive(Context
         
           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
    
         {        private readonly List
     
      
       > subStates;        public PatrolState()        {            subStates = new List
       
        
         >()            {                new MoveToState(),                new IdleState(),            };        }        public Result Drive(Context
         
           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 的，在组合状态构造的一开始就确定了值。这样结构本身就是静态的，而上下文是动态的。不同的 entity instance 共用同一个树的 instance。

优化到这个版本，至少在性能上已经符合要求了，所有实例共享一个静态的状态迁移逻辑。面对之前提出的需求，也能够解决。至少算是一个经过对《游戏人工智能编程精粹》中提出的目标驱动状态机模型优化后的一个符合工业应用标准的 AI 框架。拿来做小游戏或者是一些 AI 很简单的游戏已经绰绰有余了。

心动了吗？还不赶紧动起来，打造属于自己的游戏世界！顿时满满的自豪感，真的很想知道大家的想法，还请持续关注更新，更多干货和资料请直接联系我，也可以加群710520381，邀请码：柳猫，欢迎大家共同讨论