[游戏AI] 状态机

(Updated: )
读书笔记
游戏AI

状态机的利与弊。

参考：

  1. 漫谈游戏中的人工智能
  2. 《游戏人工智能编程案例精粹》

状态机

状态机是什么：

为什么选择状态机：

状态机的演进：

最简单的状态机：

首先很容易抽象出IUnit：

1
2
3
4
5
6
7
8
9
10
11
12
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();
}

要注意的是，原作者的实现方式是定义一个单位接口，每个智能体要实现这个单位接口中定义的方法。(这样写会使每个单位类中有着一套自己所有行为的方法。我之前的实现方式是状态机来控制单位进行相应的行为，这样可以使每个状态仅有这个状态下自身的方法，但是耦合性较高。原作者这种接口是不是可以改写成虚方法的形式，在基类中实现基本行为，具体单位子类中再override出特定的行为？)

一个最简单的状态机定义：

1
2
3
4
5
6
7
8
public interface IState<TState,TUnit> where TState : IConvertible
{
  TState Enum {get;}
  TUnit Self {get;}
  void OnEnter();
  void Drive();
  void OnExit();
}

这样写有着一个明显的性能问题：状态机本质是描述状态迁移的，并不需要保存实体的上下文，如果实体的上下文都保存在State中(上文中的TUnit类型的Self)，那么这个状态机的每个状态迁移逻辑需要每个状态都保存一个实体的实例，这样浪费内存，应该将决策逻辑与实体的上下文分离。

决策逻辑和上下文分离：

剥离后：

1
2
3
4
5
6
7
public interface IState<TState,TUnit> where TState : IConvertible
{
  TState Enum {get;}
  void OnEnter(TUnit self);
  void Drive(TUnit self);
  void OnExit(TUnit self);
}

可以使用单例模式保持静态的状态内容实例只有一个，此时状态之间的迁移逻辑变成了静态，动态的是状态迁移过程中的上下文。

分层有限状态机：

如果想要让状态机框架描述层级结构的概念，需要对其进行拓展：

例如一个怪物需要在巡逻一段时间后进行休息，在休息一段时间后再次进行巡逻，而巡逻与休息状态均保持着对于战斗的检查。这时如果按照之前的框架(我之前就是最初级的那种)，就需要手动进行装配，在每个状态中都写入一个关于是否进入战斗状态的检查。可以看出战斗状态的优先级较高，并且相对来说算是一种”全局检查”，可以将其抽离出来作为上层状态。

  • 父状态需要关注子状态的运行结果，所以状态的Drive接口需要一个运行结果的返回值。
  • 子状态一定是由父状态驱动的。

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

状态定义：

1
2
3
4
5
6
public interface IState<TState, TCleverUnit, TResult> where TState : IConvertible
{
	// ...
	TResult Drive();
	// ...
}

组合状态的定义：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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;
	}
	// ...
}

巡逻状态：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
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;
	}
}

分层有限状态机的上下文分离：

　　我们对之前重构出来的层次状态机框架再进行一次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如下定义：

1
2
3
4
5
6
7
8
9
10
11
12
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的接口定义为：

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

　　已经相当简洁了。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
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。

​ (最后这个理解起来比较吃力了)