1 public interface IUnit 2 { 3 void ChangeState(UnitStateEnum state); 4 void Patrol(); 5 IUnit GetNearestTarget(); 6 void LockTarget(IUnit unit); 7 float GetFleeBloodRate(); 8 bool CanMove(); 9 bool HPRateLessThan(float rate);10 void Flee();11 void Speak();12 }
1 public interface IState<TState, TUnit> where TState : IConvertible2 {3 TState Enum { get; }4 TUnit Self { get; }5 void OnEnter();6 void Drive();7 void OnExit();8 }
以逃跑状态为例:
1 public class FleeState : UnitStateBase 2 { 3 public FleeState(IUnit self) : base(UnitStateEnum.Flee, self) 4 { 5 } 6 public override void OnEnter() 7 { 8 Self.Flee(); 9 }10 public override void Drive()11 {12 var unit = Self.GetNearestTarget();13 if (unit != null)14 {15 return;16 }17 18 Self.ChangeState(UnitStateEnum.Patrol);19 }20 }
1 public interface IState<TState, TUnit> where TState : IConvertible2 {3 TState Enum { get; }4 void OnEnter(TUnit self);5 void Drive(TUnit self);6 void OnExit(TUnit self);7 }
还是拿之前实现好的逃跑状态作为例子:
1 public class FleeState : UnitStateBase 2 { 3 public FleeState() : base(UnitStateEnum.Flee) 4 { 5 } 6 public override void OnEnter(IUnit self) 7 { 8 base.OnEnter(self); 9 self.Flee();10 }11 public override void Drive(IUnit self)12 {13 base.Drive(self);14 15 var unit = self.GetNearestTarget();16 if (unit != null)17 {18 return;19 }20 21 self.ChangeState(UnitStateEnum.Patrol);22 }23 }
考虑这样一个组合状态情景:巡逻时,需要依次得先走到一个点,然后怠工一会儿,再走到下一个点,然后再怠工一会儿,循环往复。这样就需要父状态(巡逻状态)注记当前激活的子状态,并且根据子状态执行结果的不同来修改激活的子状态集合。这样不仅是Unit自身有上下文,连组合状态也有了自己的上下文。
为了简化讨论,我们还是从non-ContextFree层次状态机系统设计开始。
1 public interface IState<TState, TCleverUnit, TResult> 2 where TState : IConvertible3 {4 // ...5 TResult Drive();6 // ...7 }
组合状态的定义:
1 public abstract class UnitCompositeStateBase : UnitStateBase 2 { 3 protected readonly LinkedList<UnitStateBase> subStates = new LinkedList<UnitStateBase>(); 4 5 // ... 6 protected Result ProcessSubStates() 7 { 8 if (subStates.Count == 0) 9 {10 return Result.Success;11 }12 13 var front = subStates.First;14 var res = front.Value.Drive();15 16 if (res != Result.Continue)17 {18 subStates.RemoveFirst();19 }20 21 return Result.Continue;22 }23 // ...24 }25
1 public class PatrolState : UnitCompositeStateBase 2 { 3 // ... 4 public override void OnEnter() 5 { 6 base.OnEnter(); 7 AddSubState(new MoveToState(Self)); 8 } 9 10 public override Result Drive()11 {12 if (subStates.Count == 0)13 {14 return Result.Success;15 }16 17 var unit = Self.GetNearestTarget();18 if (unit != null)19 {20 Self.LockTarget(unit);21 return Result.Success;22 }23 24 var front = subStates.First;25 var ret = front.Value.Drive();26 27 if (ret != Result.Continue)28 {29 if (front.Value.Enum == CleverUnitStateEnum.MoveTo)30 {31 AddSubState(new IdleState(Self));32 }33 else34 {35 AddSubState(new MoveToState(Self));36 }37 }38 39 return Result.Continue;40 }41 }
1 public class Continuation 2 { 3 public Continuation SubContinuation { get; set; } 4 public int NextStep { get; set; } 5 public object Param { get; set; } 6 } 7 8 public class Context<T> 9 {10 public Continuation Continuation { get; set; }11 public T Self { get; set; }12 }
1 public interface IState<TCleverUnit, TResult>2 {3 TResult Drive(Context<TCleverUnit> ctx);4 }
1 public class PatrolState : IState<ICleverUnit, Result> 2 { 3 private readonly List<IState<ICleverUnit, Result>> subStates; 4 public PatrolState() 5 { 6 subStates = new List<IState<ICleverUnit, Result>>() 7 { 8 new MoveToState(), 9 new IdleState(),10 };11 }12 public Result Drive(Context<ICleverUnit> ctx)13 {14 var unit = ctx.Self.GetNearestTarget();15 if (unit != null)16 {17 ctx.Self.LockTarget(unit);18 19 return Result.Success;20 }21 22 var nextStep = 0;23 if (ctx.Continuation != null)24 {25 // Continuation26 var thisContinuation = ctx.Continuation;27 28 ctx.Continuation = thisContinuation.SubContinuation;29 30 var ret = subStates[nextStep].Drive(ctx);31 32 if (ret == Result.Continue)33 {34 thisContinuation.SubContinuation = ctx.Continuation;35 ctx.Continuation = thisContinuation;36 37 return Result.Continue;38 }39 else if (ret == Result.Failure)40 {41 ctx.Continuation = null;42 43 return Result.Failure;44 }45 46 ctx.Continuation = null;47 nextStep = thisContinuation.NextStep + 1;48 }49 50 for (; nextStep < subStates.Count; nextStep++)51 {52 var ret = subStates[nextStep].Drive(ctx);53 if (ret == Result.Continue)54 {55 ctx.Continuation = new Continuation()56 {57 SubContinuation = ctx.Continuation,58 NextStep = nextStep,59 };60 61 return Result.Continue;62 } 63 else if (ret == Result.Failure) 64 {65 ctx.Continuation = null;66 67 return Result.Failure;68 }69 }70 71 ctx.Continuation = null;72 73 return Result.Success;74 }75 }
subStates是readonly的,在组合状态构造的一开始就确定了值。这样结构本身就是静态的,而上下文是动态的。不同的entity instance共用同一个树的instance。
1 public interface IO<T>2 {3 T Drive(Context ctx);4 }
public class Sequence : IO<Result> { private readonly ICollection<IO<Result>> subTrees; public Sequence(ICollection<IO<Result>> subTrees) { this.subTrees = subTrees; } public Result Drive(Context ctx) { throw new NotImplementedException(); } }
With结点的实现,采用我们之前说的第一种方案:
1 public class With<T, TR> : IO<TR> 2 { 3 // ... 4 public TR Drive(Context ctx) 5 { 6 var thisContinuation = ctx.Continuation; 7 var value = default(T); 8 var skipIoGet = false; 9 10 if (thisContinuation != null)11 {12 // Continuation13 ctx.Continuation = thisContinuation.SubContinuation;14 15 // 0表示需要继续ioGet16 // 1表示需要继续subTree17 if (thisContinuation.NextStep == 1)18 {19 skipIoGet = true;20 value = (T) thisContinuation.Param;21 }22 }23 24 if (!skipIoGet)25 {26 value = ioGet.Drive(ctx);27 28 if (ctx.Continuation != null)29 {30 // ioGet抛出了Continue31 if (thisContinuation == null)32 {33 thisContinuation = new Continuation()34 {35 SubContinuation = ctx.Continuation,36 NextStep = 0,37 };38 }39 else40 {41 thisContinuation.SubContinuation = ctx.Continuation;42 thisContinuation.NextStep = 0;43 }44 45 ctx.Continuation = thisContinuation;46 47 return default(TR);48 }49 }50 51 var oldValue = box.SetVal(value);52 var ret = subTree.Drive(ctx);53 54 box.SetVal(oldValue);55 56 if (ctx.Continuation != null)57 {58 // subTree抛出了Continue59 if (thisContinuation == null)60 {61 thisContinuation = new Continuation()62 {63 SubContinuation = ctx.Continuation,64 };65 }66 67 ctx.Continuation = thisContinuation;68 thisContinuation.Param = value;69 }70 71 return ret;72 }73 }
这样,我们的层次状态机就全部组件化了。我们可以用通用的语义结点来组合出任意的子状态,这些子状态是不具名的,对构建过程更友好。
具体的代码例子:
Par( Seq(IsFleeing, ((Box<object> a) => With(a, GetNearestTarget, Check(IsNull(a))))(new Box<object>()), Patrol) ,Seq(IsAttacking, ((Box<float> a) => With(a, GetFleeBloodRate, Check(HpRateLessThan(a))))(new Box<float>())) ,Seq(IsNormal, Loop(Par(((Box<object> a) => With(a, GetNearestTarget, Seq(Check(IsNull(a)), LockTarget(a)))(new Box<object>()), Seq(Seq(Check(ReachCurrentPatrolPoint), MoveToNextPatrolPoiont), Idle))))))
看起来似乎是变得复杂了,原来可能只需要一句new XXXState(),现在却需要自己用代码拼接出来一个行为逻辑。但是仔细想一下,改成这样的描述其实对整个工作流是有好处的。之前的形式完全是硬编码,而现在,似乎让我们看到了转数据驱动的可能性。
#region HpRateLessThan private class MessageHpRateLessThan : IO<bool> { public readonly float p0; public MessageHpRateLessThan(float p0) { this.p0 = p0; } public bool Drive(Context ctx) { return ((T)ctx.Self).HpRateLessThan(p0); } } public static IO<bool> HpRateLessThan(float p0) { return new MessageHpRateLessThan(p0); } #endregion
public abstract class Thunk<T> { public abstract T GetUserValue(); }
((Box<IO<Result>> a) => With(a, GetNearestTarget, Negate(a)))(new Box<IO<Result>>())
public abstract class IO<T> : Thunk<IO<T>> { public abstract T Drive(Context ctx); public override IO<T> GetUserValue() { return this; } }
(declare (HpRateLessThan :: (Float -> IO Result)) (GetFleeBloodRate :: Float) (IsNull :: (Object -> Bool)) (Idle :: IO Result))(declare (check :: (Bool -> IO Result)) (loop :: (IO Result -> IO Result)) (par :: (List IO Result -> IO Result)))
(import Prelude)(import BaseAI)(define Root (par [(seq [(check IsFleeing) ((/a (check (IsNull a))) GetNearestTarget)]) (seq [(check IsAttacking) ((/b (HpRateLessThan b)) GetFleeBloodRate)]) (seq [(check IsNormal) (loop (par [((/c (seq [(check (IsNull c)) (LockTarget c)])) GetNearestTarget) (seq [(seq [(check ReachCurrentPatrolPoint) MoveToNextPatrolPoiont]) Idle])]))])]))
可以看到,跟S-Expression没什么太大的区别,可能lambda的声明方式变了下。
module Common whereimport qualified Data.Map as Maptype Identifier = Stringtype ValEnv = Map.Map Identifier Valtype TypeEnv = Map.Map Identifier Typetype DecEnv = Map.Map Identifier (String,Dec)data Type = NormalType String | GenericType String Type | APPType [Type]data Dec = DefineDec Pat Exp | ImportDec String | DeclareDec Pat Type | DeclaresDec [Dec] data Exp = ConstExp Val | VarExp Identifier | LambdaExp Pat Exp | AppExp Exp Exp | ADTExp String [Exp] data Val = NilVal | BoolVal Bool | IntVal Integer | FloatVal Float | StringVal String data Pat = VarPat Identifier
我在这里省去了一些跟这篇文章讨论的DSL无关的语言特性,比如Pattern的定义我只保留了VarPat;Value的定义我去掉了ClosureVal,虽然语言本身仍然是支持first class function的。
algebraic data type的一个好处就是清晰易懂,定义起来不过区区二十行,但是我们一看就知道之后输出的AST会是什么样。
haskell的ParseC用起来其实跟PEG是没有本质区别的,组合子本身是自底向上描述的,而parser也是通过parse小元素的parser来构建parse大元素的parser。
例如,haskell的ParseC库就有这样几个强大的特性:
我们可以先根据这些基本的,封装出来一些通用combinator。
比如正则规则中的star:
star :: Parser a -> Parser [a]star p = star_p where star_p = try plus_p <|> (return []) plus_p = (:) <$> p <*> star_p
比如plus:
plus :: Parser a -> Parser [a]plus p = plus_p where star_p = try plus_p <|> (return []) <?> "plus_star_p" plus_p = (:) <$> p <*> star_p <?> "plus_plus_p"
基于这些,我们可以做组装出来一个parse lambda-exp的parser(p_seperate是对char、plus这些的组装,表示形如a,b,c这样的由特定字符分隔的序列):
p_lambda_exp :: Parser Expp_lambda_exp = p_between '(' ')' inner <?> "p_lambda_exp" where inner = make_lambda_exp <$ char '//' <*> p_seperate (p_parse p_pat) "," <*> p_parse p_exp make_lambda_exp [] e = (LambdaExp NilPat e) make_lambda_exp (p:[]) e = (LambdaExp p e) make_lambda_exp (p:ps) e = (LambdaExp p (make_lambda_exp ps e))
有了所有exp的parser,我们就可以组装出来一个通用的exp parser:
p_exp :: Parser Exp p_exp = listplus [p_var_exp, p_const_exp, p_lambda_exp, p_app_exp, p_adt_exp, p_list_exp] <?> "p_exp"
其中,listplus是一种具有优先级的lookahead:
listplus :: [Parser a] -> Parser alistplus lst = foldr (<|>) mzero (map try lst)
-- Prelude.bh
Right [DeclaresDec [ DeclareDec (VarPat "seq") (AppType [GenericType "List" (GenericType "IO" (NormalType "Result")),GenericType "IO" (NormalType "Result")]),DeclareDec (VarPat "check") (AppType [NormalType "Bool",GenericType "IO" (NormalType "Result")])]]
-- BaseAI.bhRight [DeclaresDec [ DeclareDec (VarPat "HpRateLessThan") (AppType [NormalType "Float",GenericType "IO" (NormalType "Result")]),DeclareDec (VarPat "Idle") (GenericType "IO" (NormalType "Result"))]]
-- AI00001.bhRight [ ImportDec "Prelude",ImportDec "BaseAI",DefineDec (VarPat "Root") (AppExp (VarExp "par") (ADTExp "Cons" [ AppExp (VarExp "seq") (ADTExp "Cons" [ AppExp (VarExp "check") (VarExp "IsFleeing") ,ADTExp "Cons" [ AppExp (LambdaExp (VarPat "a")(AppExp (VarExp "check") (AppExp (VarExp "IsNull") (VarExp "a")))) (VarExp "GetNearestTarget") ,ConstExp NilVal]]) ,ADTExp "Cons" [ AppExp (VarExp "seq") (ADTExp "Cons" [ AppExp (VarExp "check") (VarExp "IsAttacking") ,ADTExp "Cons" [ AppExp (LambdaExp (VarPat "b") (AppExp (VarExp "HpRateLessThan") (VarExp "b"))) (VarExp "GetFleeBloodRate") ,ConstExp NilVal]]) ,ADTExp "Cons" [ AppExp (VarExp "seq") (ADTExp "Cons" [ AppExp (VarExp "check") (VarExp "IsNormal") ,ADTExp "Cons" [ AppExp (VarExp "loop") (AppExp (VarExp "par") (ADTExp "Cons" [ AppExp (LambdaExp (VarPat "c") (AppExp (VarExp "seq") (ADTExp "Cons" [ AppExp (VarExp "check") (AppExp (VarExp"IsNull") (VarExp "c")) ,ADTExp "Cons" [ AppExp (VarExp "LockTarget") (VarExp "c") ,ConstExp NilVal]]))) (VarExp "GetNearestTarget") ,ADTExp "Cons" [ AppExp (VarExp"seq") (ADTExp "Cons" [ AppExp (VarExp "seq") (ADTExp "Cons" [ AppExp (VarExp "check") (VarExp "ReachCurrentPatrolPoint") ,ADTExp "Cons" [ VarExp "MoveToNextPatrolPoiont" ,ConstExp NilVal]]) ,ADTExp "Cons" [ VarExp "Idle" ,ConstExp NilVal]]) ,ConstExp NilVal]])) ,ConstExp NilVal]]) ,ConstExp NilVal]]]))]
前面两部分是我把在其他模块定义的declares,选择性地拿过来两条。第三部分是这个人形怪AI的整个的AST。其中嵌套的Cons展开之后就是语言内置的List。
exp_type :: Exp -> TypeEnv -> Maybe Typeexp_type (AppExp lexp aexp) env = (exp_type aexp env) >>= (/at -> case lexp of LambdaExp (VarPat var) exp -> (merge_type_env (Just env) (make_type_env var (Just at))) >>= (/env1 -> exp_type lexp env1) _ -> (exp_type lexp env) >>= (/ltype -> check_type ltype at)) where check_type (AppType (t1:(t2:[]))) at = if t1 == at then (Just t2) else Nothing check_type (AppType (t:ts)) at = if t == at then (Just (AppType ts)) else Nothing
public static IO<Result> Root = Prelude.par(Help.MakeList( Prelude.seq(Help.MakeList( Prelude.check(BaseAI.IsFleeing) ,(((Box<Object> a) => Help.With(a, BaseAI.GetNearestTarget, Prelude.check(BaseAI.IsNull())))(new Box<Object>())))) ,Prelude.seq(Help.MakeList( Prelude.check(BaseAI.IsAttacking) ,(((Box<Float> b) => Help.With(b, BaseAI.GetFleeBloodRate, BaseAI.HpRateLessThan()))(new Box<Float>())))) ,Prelude.seq(Help.MakeList( Prelude.check(BaseAI.IsNormal) ,Prelude.loop(Prelude.par(Help.MakeList( (((Box<Object> c) => Help.With(c, BaseAI.GetNearestTarget, Prelude.seq(Help.MakeList( Prelude.check(BaseAI.IsNull()) ,BaseAI.LockTarget()))))(new Box<Object>())) ,Prelude.seq(Help.MakeList( Prelude.seq(Help.MakeList( Prelude.check(BaseAI.ReachCurrentPatrolPoint) ,BaseAI.MoveToNextPatrolPoiont)) ,BaseAI.Idle)))))))))
((Box<float> a) => (Help.With(a, UnitAI.GetFleeBloodRate, Math.Plus(a, 0.1)))(new Box<float>())
public static Thunk<float> Plus(Thunk<float> a, Thunk<float> b) { return Help.MakePureThunk(a.GetUserValue() + b.GetUserValue()); }
如果a和b都是literal value,那就没问题,但是如果有一个是被box包裹的,那就很显然是有问题的。
所以需要对Thunk这个概念做一下扩展,使之能区别出动态的值与静态的值。一般情况下的值,都是pure的;box包裹的值,是impure的。同时,这个pure的性质具有值传递性,如果这个值属于另一个值的一部分,那么这个整体的pure性质与值的局部的pure性质是一致的。这里特指的值,包括List与IO。
整体的概念我们应该拿haskell中的impure monad做类比,比如haskell中的IO。haskell中的IO依赖于OS的输入,所以任何返回IO monad的函数都具有传染性,引用到的函数一定还会被包裹在IO monad之中。
所以,对于With这种情况的传递,应该具有这样的特征:
所以With结点构造的时候,计算pure应该特殊处理一下。但是这个特殊处理的代码污染性比较大,我在本文就不列出了,只是这样提一下。
有了pure与impure的标记,我们在对函数调用的时候,就需要额外走一层。
本来一个普通的函数调用,比如UnitAI.Func(p0, p1, p2)与Math.Plus(p0, p1)。前者返回一种computing是毫无疑问的,后者就需要根据参数的类型来决定是返回一种计算还是直接的值。
为了避免在这个Plus里面改来改去,我们把Closure这个概念给抽象出来。同时,为了简化讨论,我们只列举T0 -> TR这一种情况,对应的标准库函数取Abs。
public class Closure<T0, TR> : Thunk<Closure<T0, TR>> { class UserFuncApply : Thunk<TR> { private Closure<T0, TR> func; private Thunk<T0> p0; public UserFuncApply(Closure<T0, TR> func, Thunk<T0> p0) { this.func = func; this.p0 = p0; this.pure = false; } public override TR GetUserValue() { return func.funcThunk(p0).GetUserValue(); } } private bool isUserFunc = false; private FuncThunk<T0, TR> funcThunk; private Func<T0, TR> userFunc; public Closure(FuncThunk<T0, TR> funcThunk) { this.funcThunk = funcThunk; } public Closure(Func<T0, TR> func) { this.userFunc = func; this.funcThunk = p0 => Help.MakePureThunk(userFunc(p0.GetUserValue())); this.isUserFunc = true; } public override Closure<T0, TR> GetUserValue() { return this; } public Thunk<TR> Apply(Thunk<T0> p0) { if (!isUserFunc || Help.AllPure(p0)) { return funcThunk(p0); } return new UserFuncApply(this, p0); } }
其中,UserFuncApply就是之前所说的一层计算的概念。UserFunc表示的是等效于可以编译期计算的一种标准库函数。
这样定义:
public static class Math { public static readonly Thunk<Closure<float, float>> Abs = Help.MakeUserFuncThunk<float,float>(System.Math.Abs); }
Message类型的Closure构造,都走FuncThunk构造函数;普通函数类型的构造,走Func构造函数,并且包装一层。
Help.Apply是为了方便做代码生成,描述一种declarative的application。其实就是直接调用Closure的Apply。
考虑以下几种case:
public void Test() { var box1 = new Box<float>(); // Math.Abs(box1) -> UserFuncApply // 在GetUserValue的时候才会求值 var ret1 = Help.Apply(Math.Abs, box1); // Math.Abs(0.2f) -> Thunk<float> // 直接构造出来了一个Thunk<float>(0.2f) var ret2 = Help.Apply(Math.Abs, Help.MakePureThunk(0.2f)); // UnitAISets<IUnit>.HpRateLessThan(box1) -> Message var ret3 = Help.Apply(UnitAISets<IUnit>.HpRateLessThan, box1); // UnitAISets<IUnit>.HpRateLessThan(0.2f) -> Message var ret4 = Help.Apply(UnitAISets<IUnit>.HpRateLessThan, Help.MakePureThunk(0.2f)); }
与之前的runtime版本唯一表现上有区别的地方在于,对于纯pure参数的userFunc,在Apply完之后会直接计算出来值,并重新包装成一个Thunk;而对于参数中有impure的情况,返回一个UserFuncApply,在GetUserValue的时候才会求值。
新闻热点
疑难解答