端午节放假总结了一下好久前写过的一些游戏引擎, 其中 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 很简单的游戏已经绰绰有余了.
心动了吗? 还不赶紧动起来, 打造属于自己的游戏世界! 顿时满满的自豪感, 真的很想知道大家的想法, 还请持续关注更新, 更多干货和资料请直接联系我, 也可以加群 710520381, 邀请码: 柳猫, 欢迎大家共同讨论
来源: http://www.jianshu.com/p/db2a3bc93b52