端午節(jié)放假總結(jié)了一下好久前寫(xiě)過(guò)的一些游戲引擎雌隅，其中NPC等游戲AI的實(shí)現(xiàn)無(wú)疑是最繁瑣的部分恰起，現(xiàn)在检盼，給大家分享一下：
從一個(gè)簡(jiǎn)單的情景開(kāi)始
怪物吨枉，是游戲中的一個(gè)基本概念哄芜。游戲中的單位分類(lèi)认臊，不外乎玩家、NPC剧腻、怪物這幾種书在。其中胯陋，AI 一定是與三類(lèi)實(shí)體都會(huì)產(chǎn)生交集的游戲模塊之一遏乔。
以我們熟悉的任意一款游戲中的人形怪物為例，假設(shè)有一種怪物的 AI 需求是這樣的：
大部分情況下盟萨，漫無(wú)目的巡邏捻激。玩家進(jìn)入視野，鎖定玩家為目標(biāo)開(kāi)始攻擊垃杖。Hp 低到一定程度调俘，怪會(huì)想法設(shè)法逃跑旺垒，并說(shuō)幾句話先蒋。
我們以這個(gè)為模型，進(jìn)行這篇文章之后的所有討論眯搭。為了簡(jiǎn)化問(wèn)題坦仍，以省去一些不必要的討論叨襟，將文章的核心定位到人工智能上糊闽，這里需要注意幾點(diǎn)的是：
不再考慮 entity 之間的消息傳遞機(jī)制，例如判斷玩家進(jìn)入視野提澎，不再通過(guò)事件機(jī)制觸發(fā)盼忌，而是通過(guò)該人形怪的輪詢觸發(fā)。不再考慮 entity 的行為控制機(jī)制看成，簡(jiǎn)化這個(gè) entity 的控制模型跨嘉。不論是底層是基于 SteeringBehaviour 或者是瞬移祠乃，不論是異步驅(qū)的還是主循環(huán)輪詢，都不在本文模型的討論之列琴拧。
首先可以很容易抽象出來(lái) 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();
}
然后蚓胸，我們可以通過(guò)一個(gè)簡(jiǎn)單的有限狀態(tài)機(jī) (FSM) 來(lái)控制這個(gè)單位的行為赢织。不同狀態(tài)下馍盟，單位都具有不同的行為準(zhǔn)則贞岭，以形成智能體。
具體來(lái)說(shuō)话速，我們可以定義這樣幾種狀態(tài)：
巡邏狀態(tài)： 會(huì)執(zhí)行巡邏泊交，同時(shí)檢查是否有敵對(duì)單位接近柱查，接近的話進(jìn)入戰(zhàn)斗狀態(tài)。戰(zhàn)斗狀態(tài)： 會(huì)執(zhí)行戰(zhàn)斗研乒，同時(shí)檢查自己的血量是否達(dá)到逃跑線以下雹熬，達(dá)成檢查了就會(huì)逃跑。逃跑狀態(tài)： 會(huì)逃跑铅乡，同時(shí)說(shuō)一次話仰楚。
最原始的狀態(tài)機(jī)的代碼：
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);
}
}
決策邏輯與上下文分離
上述是一個(gè)最簡(jiǎn)單僧界、最常規(guī)的狀態(tài)機(jī)實(shí)現(xiàn)捂襟。估計(jì)只有學(xué)生會(huì)這樣寫(xiě)葬荷，業(yè)界肯定是沒(méi)人這樣寫(xiě) AI 的纽帖，不然游戲怎么死的都不知道懊直。
首先有一個(gè)非常明顯的性能問(wèn)題：狀態(tài)機(jī)本質(zhì)是描述狀態(tài)遷移的，并不需要記錄 entity 的 context雕崩，如果 entity 的 context 記錄在 State上盼铁，那么狀態(tài)機(jī)這個(gè)遷移邏輯就需要每個(gè) entity 都來(lái)一份 instance尝偎，這么一個(gè)簡(jiǎn)單的狀態(tài)遷移就需要消耗大約 X 個(gè)字節(jié)致扯，那么一個(gè)場(chǎng)景 1w 個(gè)怪，這些都屬于白白消耗的內(nèi)存醒陆。就目前的實(shí)現(xiàn)來(lái)看刨摩，具體的一個(gè) State 實(shí)例內(nèi)部 hold 住了 Unit，所以 State 實(shí)例是沒(méi)辦法復(fù)用的澡刹。
針對(duì)這一點(diǎn)罢浇，我們做一下優(yōu)化。對(duì)這個(gè)狀態(tài)機(jī)攒岛，把 Context 完全剝離出來(lái)灾锯。
修改狀態(tài)機(jī)接口定義：
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);
}
還是拿之前實(shí)現(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ū)分了動(dòng)態(tài)與靜態(tài)兼雄。靜態(tài)的是狀態(tài)之間的遷移邏輯赦肋，只要不做熱更新嘲碱，是不會(huì)變的結(jié)構(gòu)。動(dòng)態(tài)的是狀態(tài)遷移過(guò)程中的上下文恕稠，根據(jù)不同的上下文來(lái)決定鹅巍。
分層有限狀態(tài)機(jī)
最原始的狀態(tài)機(jī)方案除了性能存在問(wèn)題料祠，還有一個(gè)比較嚴(yán)重的問(wèn)題髓绽。那就是這種狀態(tài)機(jī)框架無(wú)法描述層級(jí)結(jié)構(gòu)的狀態(tài)。
假設(shè)需要對(duì)一開(kāi)始的需求進(jìn)行這樣的擴(kuò)展：怪在巡邏狀態(tài)下有可能進(jìn)入怠工狀態(tài)枫攀，同時(shí)要求，怠工狀態(tài)下也會(huì)進(jìn)行進(jìn)入戰(zhàn)斗的檢查图焰。
這樣的話技羔，雖然在之前的框架下卧抗，單獨(dú)做一個(gè)新的怠工狀態(tài)也可以，但是仔細(xì)分析一下超陆，我們會(huì)發(fā)現(xiàn)浦马，其實(shí)本質(zhì)上巡邏狀態(tài)只是一個(gè)抽象的父狀態(tài)晶默，其存在的意義就是進(jìn)行戰(zhàn)斗檢查磺陡；而具體的是在按路線巡邏還是怠工漠畜，其實(shí)都是巡邏狀態(tài)的一個(gè)子狀態(tài)。
狀態(tài)之間就有了層級(jí)的概念蝴悉，各自獨(dú)立的狀態(tài)機(jī)系統(tǒng)就無(wú)法滿足需求拍冠，需要一種分層次的狀態(tài)機(jī)簇抵，原先的狀態(tài)機(jī)接口設(shè)計(jì)就需要徹底改掉了碟摆。
在重構(gòu)狀態(tài)框架之前，需要注意兩點(diǎn)：
因?yàn)楦笭顟B(tài)需要關(guān)注子狀態(tài)的運(yùn)行結(jié)果断盛，所以狀態(tài)的 Drive 接口需要一個(gè)運(yùn)行結(jié)果的返回值。
子狀態(tài)栖博，比如怠工厢洞，一定是有跨幀的需求在的躺翻，所以這個(gè) Result，我們定義為 Continue踊淳、Sucess迂尝、Failure剪芥。
子狀態(tài)一定是由父狀態(tài)驅(qū)動(dòng)的税肪。
考慮這樣一個(gè)組合狀態(tài)情景：巡邏時(shí)，需要依次得先走到一個(gè)點(diǎn)锻梳，然后怠工一會(huì)兒净捅，再走到下一個(gè)點(diǎn)灸叼，然后再怠工一會(huì)兒，循環(huán)往復(fù)屁魏。這樣就需要父狀態(tài)（巡邏狀態(tài)）注記當(dāng)前激活的子狀態(tài)氓拼，并且根據(jù)子狀態(tài)執(zhí)行結(jié)果的不同來(lái)修改激活的子狀態(tài)集合。這樣不僅是 Unit 自身有上下文坏匪，連組合狀態(tài)也有了自己的上下文适滓。
為了簡(jiǎn)化討論恋追，我們還是從 non-ContextFree 層次狀態(tài)機(jī)系統(tǒng)設(shè)計(jì)開(kāi)始苦囱。
修改后的狀態(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)在是一個(gè)組合狀態(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;
}
}
看過(guò)《游戲人工智能編程精粹》的同學(xué)可能看到這里就會(huì)發(fā)現(xiàn)，這種層次狀態(tài)機(jī)其實(shí)就是這本書(shū)里講的目標(biāo)驅(qū)動(dòng)的狀態(tài)機(jī)羹铅。組合狀態(tài)就是組合目標(biāo)，子狀態(tài)就是子目標(biāo)造锅。父目標(biāo) / 狀態(tài)的調(diào)度取決于子目標(biāo) / 狀態(tài)的完成情況。
這種狀態(tài)框架與普通的 trivial 狀態(tài)機(jī)模型的區(qū)別僅僅是增加了對(duì)層次狀態(tài)的支持倒谷，狀態(tài)的遷移還是需要靠顯式的 ChangeState 來(lái)做。
這本書(shū)里面的狀態(tài)框架牵祟，每個(gè)狀態(tài)的執(zhí)行 status 記錄在了實(shí)例內(nèi)部诺苹，不方便后續(xù)的優(yōu)化雹拄，我們這里實(shí)現(xiàn)的時(shí)候首先把這個(gè)做成純驅(qū)動(dòng)式的。但是還不夠∑汉澹現(xiàn)在之前的 ContextFree 優(yōu)化成果已經(jīng)回退掉了翩肌，我們還需要補(bǔ)充回來(lái)。
分層的上下文
我們對(duì)之前重構(gòu)出來(lái)的層次狀態(tài)機(jī)框架再進(jìn)行一次 Context 分離優(yōu)化兑宇。
要優(yōu)化的點(diǎn)有這樣幾個(gè)：
首先是繼續(xù)之前的顾孽，unit 不應(yīng)該作為一個(gè) state 自己的內(nèi)部 status比规。
組合狀態(tài)的實(shí)例內(nèi)部不應(yīng)該包括自身執(zhí)行的 status。目前的組合狀態(tài)测秸，可以動(dòng)態(tài)增刪子狀態(tài)，也就是根據(jù) status 決定了結(jié)構(gòu)的狀態(tài)钞瀑，理應(yīng)分離靜態(tài)與動(dòng)態(tài)雕什。巡邏狀態(tài)組合了兩個(gè)子狀態(tài)——A 和 B壹士，邏輯中是一個(gè)完成了就添加另一個(gè)偿警，這樣一想的話，其實(shí)巡邏狀態(tài)應(yīng)該重新描述——先進(jìn)行 A，再進(jìn)行 B，循環(huán)往復(fù)抄瑟。
由于有了父狀態(tài)的概念枉疼，其實(shí)狀態(tài)接口的設(shè)計(jì)也可以再迭代骂维，理論上只需要一個(gè) drive 即可贺纲。因?yàn)闋顟B(tài)內(nèi)部的上下文要全部分離出來(lái)，所以也沒(méi)必要對(duì)外提供 OnEnter懈叹、OnExit澄成，提供這兩個(gè)接口的意義只是做一層內(nèi)部信息的隱藏，但是現(xiàn)在內(nèi)部的 status 沒(méi)了肾砂，也就沒(méi)必要隱藏了镐确。
具體分析一下需要拆出的 status：
- 一部分是 entity 本身的 status，這里可以簡(jiǎn)單的認(rèn)為是 unit臼氨。
- 另一部分是 state 本身的 status储矩。
- 對(duì)于組合狀態(tài)，這個(gè) status 描述的是我當(dāng)前執(zhí)行到哪個(gè) substate屡拨。
- 對(duì)于原子狀態(tài)，這個(gè) status 描述的種類(lèi)可能有所區(qū)別哥艇。
- 例如 MoveTo/Flee十饥，OnEnter 的時(shí)候，修改了 unit 的 status，然后 Drive 的時(shí)候去 check隙赁。
- 例如 Idle，OnEnter 時(shí)改了自己的 status厚掷，然后 Drive 的時(shí)候去 check田绑。
經(jīng)過(guò)總結(jié)，我們可以發(fā)現(xiàn)冬竟，每個(gè)狀態(tài)的 status 本質(zhì)上都可以通過(guò)一個(gè)變量來(lái)描述。一個(gè) State 作為一個(gè)最小粒度的單元调缨，具有這樣的 Concept： 輸入一個(gè) Context，輸出一個(gè) Result。
Context 暫時(shí)只需要包括這個(gè) Unit，和之前所說(shuō)的 status默责。同時(shí)，考慮這樣一個(gè)問(wèn)題：
- 父狀態(tài) A，子狀態(tài) B芦鳍。
- 子狀態(tài) B 向上返回 Continue 的同時(shí)，status 記錄下來(lái)為 b菲宴。
- 父狀態(tài) ADrive 子狀態(tài)的結(jié)果為 Continue势誊，自身也需要向上拋出 Continue，同時(shí)自己也有 status 為 a勋颖。
這樣侥祭，再還原現(xiàn)場(chǎng)時(shí)，就需要即給 A 一個(gè) a，還需要讓 A 有能力從 Context 中拿到需要給 B 的 b窑滞。因此上下文的結(jié)構(gòu)理應(yīng)是遞歸定義的，是一個(gè)層級(jí)結(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)簡(jiǎn)潔了暂题。
這樣纵苛，我們對(duì)之前的巡邏狀態(tài)也做下修改，達(dá)到一個(gè) ContextFree 的效果贝椿。利用 Context 中的 Continuation 來(lái)確定當(dāng)前結(jié)點(diǎn)應(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)造的一開(kāi)始就確定了值访雪。這樣結(jié)構(gòu)本身就是靜態(tài)的坝橡，而上下文是動(dòng)態(tài)的计寇。不同的 entity instance 共用同一個(gè)樹(shù)的 instance元莫。
優(yōu)化到這個(gè)版本柒竞，至少在性能上已經(jīng)符合要求了，所有實(shí)例共享一個(gè)靜態(tài)的狀態(tài)遷移邏輯稼虎。面對(duì)之前提出的需求霎俩，也能夠解決。至少算是一個(gè)經(jīng)過(guò)對(duì)《游戲人工智能編程精粹》中提出的目標(biāo)驅(qū)動(dòng)狀態(tài)機(jī)模型優(yōu)化后的一個(gè)符合工業(yè)應(yīng)用標(biāo)準(zhǔn)的 AI 框架。拿來(lái)做小游戲或者是一些 AI 很簡(jiǎn)單的游戲已經(jīng)綽綽有余了捌肴。
