端午节放假总结了一下好久前写过的一些游戏引擎，其中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<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();
}以逃跑状态为例：
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<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);
}还是拿之前实现好的逃跑状态作为例子：
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<TState, TCleverUnit, TResult>
where TState : IConvertible
{
// ...
TResult Drive();
// ...
}
public interface IState<TState, TCleverUnit, TResult>
where TState : IConvertible
{
// ...
TResult Drive();
// ...
}组合状态的定义：
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;
}
// ...
}巡逻状态现在是一个组合状态：
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<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);
}已经相当简洁了。
这样，我们对之前的巡逻状态也做下修改，达到一个 ContextFree 的效果。利用 Context 中的 Continuation 来确定当前结点应该从什么状态继续：
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 的，在组合状态构造的一开始就确定了值。这样结构本身就是静态的，而上下文是动态的。不同的 entity instance 共用同一个树的 instance。
优化到这个版本，至少在性能上已经符合要求了，所有实例共享一个静态的状态迁移逻辑。面对之前提出的需求，也能够解决。至少算是一个经过对《游戏人工智能编程精粹》中提出的目标驱动状态机模型优化后的一个符合工业应用标准的 AI 框架。拿来做小游戏或者是一些 AI 很简单的游戏已经绰绰有余了。
