游戏中人工智能的优化

建立一个简单的游戏引擎和人工智能NPC后,我们需要对他们进行优化,如何建立,可以参考我在评论里的链接

语义结点的抽象

不过我们在这篇博客的讨论中是不能仅停留在能解决需求的层面上。目前的方案至少还存在一个比较严重的问题,那就是逻辑复用性太差。组合状态需要 coding 的逻辑太多了,具体的状态内部逻辑需要人肉维护,更可怕的是需要程序员来人肉维护,再多几个组合状态简直不敢想象。程序员真的没这么多时间维护这些东西好么。所以我们应该尝试抽象一下组合状态是否有一些通用的设计 pattern。 为了解决这个问题,我们再对这几个状态的分析一下,可以对结点类型进行一下归纳。

结点基本上是分为两个类型:组合结点、原子结点。

如果把这个状态迁移逻辑体看做一个树结构,那其中组合结点就是非叶子结点,原子结点就是叶子结点。 对于组合结点来说,其行为是可以归纳的。

巡逻结点,不考虑触发进入战斗的逻辑,可以归纳为一种具有这样的行为的组合结点:依次执行每个子结点(移动到某个点、休息一会儿),某个子结点返回 Success 则执行下一个,返回 Failure 则直接向上返回,返回 Continue 就把 Continuation 抛出去。命名具有这样语义的结点为 Sequence。

设想攻击状态下,单位需要同时进行两种子结点的尝试,一个是释放技能,一个是说话。两个需要同时执行,并且结果独立。有一个返回 Success 则向上返回 Success,全部 Failure 则返回 Failure,否则返回 Continue。命名具有如此语义的结点为 Parallel。

在 Parallel 的语义基础上,如果要体现一个优先级 / 顺序性质,那么就需要一个具有依次执行子结点语义的组合结点,命名为 Select。 Sequence 与 Select 组合起来,就能完整的描述一” 趟 “巡逻,Select(ReactAttack, Sequence(MoveTo, Idle)),可以直接干掉之前写的 Patrol 组合状态,组合状态直接拿现成的实现好的语义结点复用即可。 组合结点的抽象问题解决了,现在我们来看叶子结点。

叶子结点也可以归纳一下 pattern,能归纳出三种:

Flee、Idle、MoveTo 三个状态,状态进入的时候调一下宿主的某个函数,申请开始一个持续性的动作。 四个原子状态都有的一个 pattern,就是在 Drive 中轮询,直到某个条件达成了才返回。

  • Attack 状态内部,每次都轮询都会向宿主请求一个数据,然后再判断这个 “外部” 数据是否满足一定条件。
  • pattern 确实是有这么三种,但是叶子结点自身其实是两种,一种是控制单位做某种行为,一种是向单位查询一些信息,其实本质上是没区别的,只是描述问题的方式不一样。 既然我们的最终目标是消除掉四个具体状态的定义,转而通过一些通用的语义结点来描述,那我们就首先需要想办法提出一种方案来描述上述的三个 pattern。

前两个 pattern 其实是同一个问题,区别就在于那些逻辑应该放在宿主提供的接口里面做实现,哪些逻辑应该在 AI 模块里做实现。调用宿主的某个函数,调用是一个瞬间的操作,直接改变了宿主的 status,但是截止点的判断就有不同的实现方式了。

  • 一种实现是宿主的 API 本身就是一个返回 Result 的函数,第一次调用的时候,宿主会改变自己的状态,比如设置单位开始移动,之后每帧都会驱动这个单位移动,而 AI 模块再去调用 MoveTo 就会拿到一个 Continue,直到宿主这边内部驱动单位移动到目的地,即向上返回 Success;发生无法让单位移动完成的情况,就返回 Failure。
  • 另一种实现是宿主提供一些基本的查询 API,比如移动到某一点、是否到达某个点、获得下一个巡逻点,这样的话就相当于是把轮询判断写在了 AI 模块里。这样就需要有一个 Check 结点,来包裹这个查询到的值,向上返回一个 IO 类型的值。
  • 而针对第三种 pattern,可以抽象出这样一种需求情景,就是:

AI 模块与游戏世界的数据互操作

假设宿主提供了接受参数的 api,提供了查询接口,ai 模块需要通过调用宿主的查询接口拿到数据,再把数据传给宿主来执行某种行为。 我们称这种语义为 With,With 用来求出一个结点的值,并合并在当前的 env 中传递给子树,子树中可以 resolve 到这个 symbol。

有了 With 语义,我们就可以方便的在 AI 模块中对游戏世界的数据进行操作,请求一个数据 => 处理一下 => 返回一个数据,更具扩展性。

With 语义的具体需求明确一下就是这样的:由两个子树来构造,一个是 IOGet,一个是 SubTree。With 会首先求值 IOGet,然后 binding 到一个 symbol 上,SubTree 可以直接引用这个 symbol,来当做一个普通的值用。 然后考虑下实现方式。

C# 中,子树要想引用这个 symbol,有两个方法:

  • iogetsubtree 共同 hold 住一个变量,ioget 求得的值赋给这个变量,subtree 构造的时候直接把值传进来。
  • ioget 与 subtree 共同 hold 住一个 env,双方约定统一的 key,ioget 求完就把这个 key 设置一下,subtree 构造的时候直接从 env 里根据 key 取值。

考虑第一种方法,hold 住的不应该是值本身,因为树本身是不同实例共享的,而这个值会直接影响到子树的结构。所以应该用一个 class instance object 对值包裹一下。

这样经过改进后的第一种方法理论上速度应该比 env 的方式快很多,也方便做一些优化,比如说如果子树没有 continue 就不需要把这个值存在 env 中,比如说由于树本身的驱动一定是单线程的,不同的实例可以共用一个包裹,执行子树的时候设置下包裹中的值,执行完子树再把包裹中的值还原。

加入了 with 语义,就需要重新审视一下 IState 的定义了。既然一个结点既有可能返回一个 Result,又有可能返回一个值,那么就需要这样一种抽象:

有这样一种泛化的 concept,他只需要提供一个 drive 接口,接口需要提供一个环境 env,drive 一下,就可以输出一个值。这个 concept 的 instance,需要是 pure 的,也就是结果唯一取决于输入的环境。不同次输入,只要环境相同,输出一定相同。

因为描述的是一种与外部世界的通信,所以就命名为 IO 吧:

public interface IO<T>
     {
         T Drive(Context ctx);
    }

public interface IO<T>
     {
         T Drive(Context ctx);
    }

这样,我们之前的所有结点都应该有 IO 的 concept。

之前提出了 Parallel、Sequence、Select、Check 这样几个语义结点。具体的实现细节就不再细说了,简单列一下代码结构:

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();
        }
    }
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 结点的实现,采用我们之前说的第一种方案:

public class With<T, TR> : IO<TR>
    {
        // ...
        public TR Drive(Context ctx)
        {
            var thisContinuation = ctx.Continuation;
            var value = default(T);
            var skipIoGet = false;

            if (thisContinuation != null)
            {
                // Continuation
                ctx.Continuation = thisContinuation.SubContinuation;

                // 0表示需要继续ioGet
                // 1表示需要继续subTree
                if (thisContinuation.NextStep == 1)
                {
                    skipIoGet = true;
                    value = (T) thisContinuation.Param;
                }
            }

            if (!skipIoGet)
            {
                value = ioGet.Drive(ctx);

                if (ctx.Continuation != null)
                {
                    // ioGet抛出了Continue
                    if (thisContinuation == null)
                    {
                        thisContinuation = new Continuation()
                        {
                            SubContinuation = ctx.Continuation,
                            NextStep = 0,
                        };
                    }
                    else
                    {
                        thisContinuation.SubContinuation = ctx.Continuation;
                        thisContinuation.NextStep = 0;
                    }

                    ctx.Continuation = thisContinuation;

                    return default(TR);
                }
            }
            
            var oldValue = box.SetVal(value);
            var ret = subTree.Drive(ctx);

            box.SetVal(oldValue);

            if (ctx.Continuation != null)
            {
                // subTree抛出了Continue
                if (thisContinuation == null)
                {
                    thisContinuation = new Continuation()
                    {
                        SubContinuation = ctx.Continuation,
                    };
                }

                ctx.Continuation = thisContinuation;
                thisContinuation.Param = value;
            }

            return ret;
        }
    }
public class With<T, TR> : IO<TR>
    {
        // ...
        public TR Drive(Context ctx)
        {
            var thisContinuation = ctx.Continuation;
            var value = default(T);
            var skipIoGet = false;
 
            if (thisContinuation != null)
            {
                // Continuation
                ctx.Continuation = thisContinuation.SubContinuation;
 
                // 0表示需要继续ioGet
                // 1表示需要继续subTree
                if (thisContinuation.NextStep == 1)
                {
                    skipIoGet = true;
                    value = (T) thisContinuation.Param;
                }
            }
 
            if (!skipIoGet)
            {
                value = ioGet.Drive(ctx);
 
                if (ctx.Continuation != null)
                {
                    // ioGet抛出了Continue
                    if (thisContinuation == null)
                    {
                        thisContinuation = new Continuation()
                        {
                            SubContinuation = ctx.Continuation,
                            NextStep = 0,
                        };
                    }
                    else
                    {
                        thisContinuation.SubContinuation = ctx.Continuation;
                        thisContinuation.NextStep = 0;
                    }
 
                    ctx.Continuation = thisContinuation;
 
                    return default(TR);
                }
            }
var oldValue = box.SetVal(value);
            var ret = subTree.Drive(ctx);
 
            box.SetVal(oldValue);
 
            if (ctx.Continuation != null)
            {
                // subTree抛出了Continue
                if (thisContinuation == null)
                {
                    thisContinuation = new Continuation()
                    {
                        SubContinuation = ctx.Continuation,
                    };
                }
 
                ctx.Continuation = thisContinuation;
                thisContinuation.Param = value;
            }
 
            return ret;
        }
    }

这样,我们的层次状态机就全部组件化了。我们可以用通用的语义结点来组合出任意的子状态,这些子状态是不具名的,对构建过程更友好。

具体的代码例子:

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))))))
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(),现在却需要自己用代码拼接出来一个行为逻辑。但是仔细想一下,改成这样的描述其实对整个工作流是有好处的。之前的形式完全是硬编码,而现在,似乎让我们看到了转数据驱动的可能性。

对行为结点做包装

当然这个示例还少解释了一部分,就是叶子结点,或者说是行为结点的定义。

我们之前对行为的定义都是在 IUnit 中,但是这里显然不像是之前定义的 IUnit。

如果把每个行为都看做是树上的一个与 Select、Sequence 等结点无异的普通结点的话,就需要实现 IO 的接口。抽象出一个计算的概念,构造的时候可以构造出这个计算,然后通过 Drive,来求得计算中的值。

包装后的一个行为的代码:

#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
#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

经过包装的行为结点的代码都是有规律可循的,所以我们可以比较容易的通过一些代码生成的机制来做。比如通过反射拿到 IUnit 定义的接口信息,然后直接在这基础之上做一下包装,做出来个行为结点的定义。

现在我们再回忆下讨论过的 With,构造一个叶子结点的时候,参数不一定是 literal value,也有可能是经过 Box 包裹过的。所以就需要对 Boax 和 literal value 抽象出来一个公共的概念,叶子结点 / 行为结点可以从这个概念中拿到值,而行为结点计算本身的构造也只需要依赖于这个概念。

我们把这个概念命名为 Thunk。Thunk 包裹一个值或者一个 box,而就目前来看,这个 Thunk,仅需要提供一个我们可以通过其拿到里面的值的接口就够了。

public abstract class Thunk<T>
    {
        public abstract T GetUserValue();
    }

public abstract class Thunk<T>
    {
        public abstract T GetUserValue();
    }

对于常量,我们可以构造一个包裹了常量的 thunk;而对于 box,其天然就属于 Thunk 的 concept。

这样,我们就通过一个 Thunk 的概念,硬生生把树中的结点与值分割成了两个概念。这样做究竟正确不正确呢?

如果一个行为结点的参数可能有的类型本来就是一些 primitive type,或者是外部世界(相对于 AI 世界)的类型,那肯定是没问题的。但如果需要支持这样一种特性:外部世界的函数,返回值是 AI 世界的某个概念,比如一个树结点;而我的 AI 世界,希望的是通过这个外部世界的函数,动态的拿到一个结点,再动态的加到我的树中,或者再动态的传给不通的外部世界的函数,应该怎么做?

对于一颗 With 子树(Negate 表示对子树结果取反,Continue 仍取 Continue):

((Box<IO<Result>> a) => 
     With(a, GetNearestTarget, Negate(a)))(new Box<IO<Result>>())

((Box<IO<Result>> a) => 
     With(a, GetNearestTarget, Negate(a)))(new Box<IO<Result>>())

语义需要保证,这颗子树执行到任意时刻,都需要是 ContextFree 的。

假设 IOGet 返回的是一个普通的值,确实是没问题的。

但是因为 Box 包裹的可能是任意值,例如,假设 IOGet 返回的是一个 IO,

  • instance a,执行完 IOGet 之后,结构变为 Negate(A)
  • instance b,再执行 IOGet,拿到一个 B,设置 box 里的值为 B,并且拿出来 A,这时候再 run subtree,其实就是按 Negate(B) 来跑的。

我们只有把 IO 本身,做到其就是 Thunk 这个 Concept。这样所有的 Message 对象,都是一个 Thunk。不仅如此,所以在这个树中出现的数据结构,理应都是一个 Thunk,比如 List。

再次改造 IO:

public abstract class IO<T> : Thunk<IO<T>>
    {
        public abstract T Drive(Context ctx);
        public override IO<T> GetUserValue()
        {
            return this;
        }
    }

public abstract class IO<T> : Thunk<IO<T>>
    {
        public abstract T Drive(Context ctx);
        public override IO<T> GetUserValue()
        {
            return this;
        }
    }

BehaviourTree

对 AI 有了解的同学可能已经清楚了,目前我们实现的就是一个行为树的引擎,并且已经基本成型。到目前为止,我们接触过的行为树语义有:

Sequence、Select、Parallel、Check、Negate。

其中 Sequence 与 Select 是两个比较基本的语义,一个相当于逻辑 And,一个相当于逻辑 Or。在组合子设计中这两类组合子也比较常见。

不同的行为树方案,对语义结点的选择也不一样。

比如以前在行为树这块比较权威的一篇 halo2 的行为树方案的 paper,里面提到的几个常用的组合结点有这样几种:

  • prioritized-list : 每次执行优先级最高的结点,高优先级的始终抢占低优先级的。
  • sequential : 按顺序执行每个子结点,执行完最后一个子结点后,父结点就 finished。
  • sequential-looping : 同上,但是会 loop
  • probabilistic : 从子结点中随机选择一个执行。
  • one-off : 从子结点中随机选择或按优先级选择,选择一个排除一个,直到执行完为止。

而腾讯的 behaviac 对组合结点的选择除了传统的 Select 和 Seqence,halo 里面提到的随机选择,还自己扩展了 SelectorProbability(虽然看起来像是一个 select,但其实每次只会根据概率选择一个,更倾向于 halo 中的 Probabilistic),SequenceStochastic(随机地决定执行顺序,然后表现起来确实像是一个 Sequence)。

其他还有各种常用的修饰结点,比如前文实现的 Check,还有一些比较常用的:

  • Wait :子树返回 Success 的时候向上 Success,否则向上 Continue。
  • Forever : 永远返回 Continue。
  • If-Else、Switch-Cond : 对于有编程功底的我想就不需要再多做解释了。
  • forcedXX : 对子树结果强制取值。 还有一类属于特色结点,虽然通过其他各种方式也都能实现,但是在行为树这个层面实现的话肯定扩展性更强一些,毕竟可以分离一部分程序的职责。一个比较典型的应用情景是事件驱动,halo 的 paper 中提到了 Behaviour Impulse,但是我在在 behaviac 中并没有找到类似的概念。

halo 的 paper 里面还提到了一些比较细节的 hack 技巧,比如同一颗行为树可以应用不同的 Style,Parameter Creep 等等,有兴趣的同学也可以自行研究。

至此,行为树的 runtime 话题需要告一段落了,毕竟是一项成熟了十几年的技术。虽然这是目前游戏 AI 的标配,但是,只有行为树的话,离一个完整的 AI 工作流还很远。到目前为止,行为树还都是程序写出来的,但是正确来说 AI 应该是由策划或者 AI 脚本配出来的。因此,这篇文章的话题还需要继续,我们接下来就讨论一下这个程序与策划之间的中间层。 之前的优化思路也好,从其他语言借鉴的设计 pattern 也好,行为树这种理念本身也好,本质上都是术。术很重要,但是无助于优化工作流。这时候,我们更需要一种略。

那么,略是什么

这里我们先扩展下游戏 AI 开发中的一种比较经典的工作流。策划输出 AI 配置,直接在游戏内调试效果。如果现有接口不满足需求,就向程序提开发需求,程序加上新接口之后,策划可以在 AI 配置里面应用新的接口。这个 AI 配置是个比较广义的概念,既可以像很多从立项之初并没有规划 AI 模块的游戏那样,逐渐地、自发地形成了一套基于配表做的决策树;也可以是像腾讯的 behaviac 那样的,用 XML 文件来描述。XML 天生就是描述数据的,腾讯系的组件普遍特别钟爱,tdr 这种配表转数据的工具是 xml,tapp tcplus 什么的配置文件全是 XML,倒不是说 XML,而是很多问题解决起来并不直观。

配表也好,XML 也好,json 也好,这种描述数据的形式本身并没有错。配表帮很多团队跨过了从硬编码到数据驱动的开发模式的转变,现在国内小到创业手游团队,大到天谕这种几百人的 MMO,策划的工作量除了配关卡就是配表。 但是,配表无法自我进化 ,配表无法自己描述流程是什么样,而是流程在描述配表是什么样。

针对策划配置 AI 这个需求,我们希望抽象出来一个中间层,这样,基于这个中间层,开发相应的编辑器也好,直接利用这个中间层来配 AI 也好,都能够灵活地做到调试 AI 这个最终需求。如何解决?我们不妨设计一种 DSL。

DSL

Domain-specific Language,领域特定语言,顾名思义,专门为特定领域设计的语言。设计一门 DSL 远容易于设计一门通用计算语言,我们不用考虑一些特别复杂的特性,不用加一些增加复杂度的模块,不需要 care 跟领域无关的一些流程。Less is more。

游戏 AI 需要怎样一种 DSL

痛点:

  • 对于游戏 AI 来说,需要一种语言可以描述特定类型 entity 的行为逻辑。
  • 而对于程序员来说,只需要提供 runtime 即可。比如组合结点的类型、表现等等。而具体的行为决策逻辑,由其他层次的协作者来定义。
  • 核心需求是做另一种 / 几种高级语言的目标代码生成,对于当前以及未来几年来说,对 C# 的支持一定是不能少的,对 python/lua 等服务端脚本的支持也可以考虑。
  • 对语言本身的要求是足够简单易懂,declarative,这样既可以方便上层编辑器的开发,也可以在没编辑器的时候快速上手。

分析需求:

因为需要做目标代码生成,而且最主要的目标代码应该是 C# 这种强类型的,所以需要有简单的类型系统,以及编译期简单的类型检查。可以确保语言的源文件可以最终 codegen 成不会导致编译出错的 C# 代码。      决定行为树框架好坏的一个比较致命的因素就是对 With 语义的实现。根据我们之前对 With 语义的讨论,可以看到,这个 With 语义的描述其实是天然的可以转化为一个 lambda 的,所以这门 DSL 同样需要对 lambda 进行支持。      关于类型系统,需要支持一些内建的复杂类型,目前来看仅需要 List,只有在 seq、select 等结点的构造时会用到。还是由于需要支持 lambda 的原因,我们需要支持 Applicative Type,也就是形如 A -> B 应该是 first class type,而一个 lambda 也应该是 first class function。根据之前对 runtime 的实现讨论,我们的 DSL 还需要支持 Generic Type,来支持 IO<Result> 这样的类型,以及 List<IO<Result>> 这样的类型。对内建 primitive 类型的支持只要有 String、Bool、Int、Float 即可。需要支持简单的类型推导,实现 hindley-milner 的真子集即可,这样至少我们就不需要在声明 lambda 的时候写的太复杂。      需要支持模块化定义,也就是最基本的 import 语义。这样的话可以方便地模块化构建 AI 接口,也可以比较方便地定义一些预制件。

模块分为两类:

一类是抽象的声明,只有 declare。比如 Prelude,seq、select 等一些结点的具体实现逻辑一定是在 runtime 中做的,所以没必要在 DSL 这个层面填充这类逻辑。具体的代码转换则由一些特设的模块来做。只需要类型检查通过,目标语言的 CodeGenerator 生成了对应的目标代码,具体的逻辑就在 runtime 中直接实现了。    一类是具体的定义,只有 define。比如定义某个具体的 AIXXX 中的 root 结点,或者定义某个通用行为结点。具体的定义就需要对外部模块的 define 以及 declare 进行组合。import 语义就需要支持从外部模块导入符号。

一种 non-trivial 的 DSL 实现方案

由于原则是简单为主,所以我在语言的设计上主要借鉴的是 Scheme。S 表达式的好处就是代码本身即数据,也可以是我们需要的 AST。同时,由于需要引入简单类型系统,需要混入一些其他语言的描述风格。我在 declare 类型时的语言风格借鉴了 haskell,import 语句也借鉴了 haskell。

具体来说,declare 语句可能类似于这样:

(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)))

(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)))

因为是以 Scheme 为主要借鉴对象,所以内建的复杂类型实现上本质是一个 ADT,当然,有针对 list 构造专用的语法糖,但是其 parse 出来拿到的 AST 中一个 list 终究还是一个 ADT。

直接拿例子来说比较直观:

(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])]))])]))

(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 的声明方式变了下。

然后是词法分析和语法分析,这里我选择的是 Haskell 的 ParseC。一些更传统的选择可能是 lex+yacc/flex+bison。但是这种两个工具一起混用学习成本就不用说了,也违背了 simple is better 的初衷。ParseC 使用起来就跟 PEG 是一样的,PEG 这种形式,是天然的结合了正则与 top-down parser。haskell 支持的 algebraic data types,天然就是用来定义 AST 结构的,简单直观。haskell 实现的 hindly-miner 类型系统,又是让你写代码基本编译通过就能直接 run 出正确结果,从一定程度上弥补了 PEG 天生不适合调试的缺陷。一个 haskell 的库就能解决 lexical&grammar,实在方便。

先是一些 AST 结构的预定义:

module Common where

import qualified Data.Map as Map

type Identifier = String
type ValEnv = Map.Map Identifier Val
type TypeEnv = Map.Map Identifier Type
type 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

module Common where
 
import qualified Data.Map as Map
 
type Identifier = String
type ValEnv = Map.Map Identifier Val
type TypeEnv = Map.Map Identifier Type
type 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 库就有这样几个强大的特性:

  • 提供了 char、string,基元的 parse 单个字符或字符串的 parser。
  • 提供了 sat,传一个 predicate,就可以 parse 到符合 predicate 的结果的 parser。
  • 提供了 try,支持 parse 过程中的 lookahead 语义。
  • 提供了 chainl、chainr,这样就省的我们在构造 parser 的时候就无需考虑左递归了。不过这个我也是写完了 parser 才了解到的,所以基本没用上,更何况对于 S-expression 来说,需要我来处理左递归的情况还是比较少的。 我们可以先根据这些基本的,封装出来一些通用 combinator。

比如正则规则中的 star:

star   :: Parser a -> Parser [a]
star p = star_p
    where 
        star_p = try plus_p <|> (return []) 
        plus_p = (:) <$> p <*> star_p

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"

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 Exp
p_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))

p_lambda_exp :: Parser Exp
p_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"

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 a
listplus lst = foldr (<|>) mzero (map try lst)
1
2
listplus :: [Parser a] -> Parser a
listplus lst = foldr (<|>) mzero (map try lst)

对于 parser 来说,其输入是源文件其输出是 AST。具体来说,其实就是 parse 出一个 Dec 数组,拿到 AST,供后续的 pipeline 消费。

我们之前举的 AI 的例子,parse 出来的 AST 大概是这副模样:

-- 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.bh
Right [DeclaresDec [
 DeclareDec (VarPat "HpRateLessThan") (AppType [NormalType "Float",GenericType "IO" (NormalType "Result")])
,DeclareDec (VarPat "Idle") (GenericType "IO" (NormalType "Result"))]]
-- AI00001.bh
Right [
 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]]]))]
-- 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.bh
Right [DeclaresDec [
 DeclareDec (VarPat "HpRateLessThan") (AppType [NormalType "Float",GenericType "IO" (NormalType "Result")])
,DeclareDec (VarPat "Idle") (GenericType "IO" (NormalType "Result"))]]
-- AI00001.bh
Right [
 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。

正如我们之前所说,做代码生成之前需要进行一步类型检查的工作。类型检查工具其输入是 AST 其输出是一个检查结果,同时还可以提供 AST 中的一些辅助信息,包括各标识符的类型信息等等。

类型检查其实主要的逻辑在于处理 Appliacative Type,这中间还有个类型推导的逻辑。形如 (\a (Func a)) 10,AST 中并不记录 a 的 type,我们的 DSL 也不需要支持 concept、typeclass 等有关 type、subtype 的复杂机制,推导的时候只需要着重处理 AppExp,把右边表达式的类型求出,合并一下 env 传给左边表达式递归检查即可。

这部分的代码:

exp_type :: Exp -> TypeEnv -> Maybe Type
exp_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

exp_type :: Exp -> TypeEnv -> Maybe Type
exp_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

此外,还需要有一个通用的 CodeGenerator 模块,其输入也是 AST,其输出是另一些 AST 中的辅助信息,主要是注记下各标识符的 import 源以及具体的 define 内容,用来方便各目标语言 CodeGenerator 直接复用逻辑。

目标语言的 CodeGenerator 目前只做了 C# 的。

目标代码生成的逻辑就比较简单了,毕竟该有的信息前面的各模块都提供了,这里根据之前一个版本的 runtime,代码生成的大致样子:

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)))))))))

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)))))))))

总的来说,大致分为这几个模块:Parser、TypeChecker、CodeGenerator、目标语言的 CodeGenerator。再加上目标语言的 runtime,基本上就可以组成这个 DSL 的全部了。

再扩展 runtime

对比 DSL,我们可以发现,DSL 支持的特性要比之前实现的 runtime 版本多。比如:

  • runtime 中压根就没有 Closure 的概念,但是 DSL 中我们是完全可以把一个 lambda 作为一个 ClosureVal 传给某个函数的。

  • 缺少对标准库的支持。比如常用的 math 函数。 基于上面这点,还会引入一个 With 结点的性能问题,在只有 runtime 的时候我们也许不会 With a <- 1+1。但是 DSL 中是有可能这样的,而且生成出来的代码会每次 run 这棵树的时候都会重新计算一次 1+1。

  • 针对第一个问题,我们要做的工作就多了。首先我们要记录下这个闭包 hold 住的*变量,要传给 runtime,runtime 也要记录,也要做各种各种,想想都麻烦,而且完全偏离了游戏 AI 的话题,不再讨论。

  • 针对第二个问题,我们可以通过解决第三个问题来顺便解决这个问题。

  • 针对第三个问题,我们重新审视一下 With 语义。

With 语义所要表达的其实是这样一个概念:

把一个可能会 Continue/Lazy Evaluation 的计算结果,绑定到一个 variable 上,对于 With 下面的子表达式来说,这个 variable 的值具有 lexical scope。

但是在 runtime 中,我们按照之前的写法,subtree 中直接就进行了函数调用,很显然是存在问题的。

With 结点本身的返回值不一定只是一个 IO<Result>,有可能是一个 IO<float>。

举例:

((Box<float> a) => (Help.With(a, UnitAI.GetFleeBloodRate, Math.Plus(a, 0.1)))(new Box<float>())

((Box<float> a) => (Help.With(a, UnitAI.GetFleeBloodRate, Math.Plus(a, 0.1)))(new Box<float>())

这里 Math.Plus 属于这门 DSL 标准库的一部分,实现上我们就对底层数学函数做一层简单的 wrapper。但是这样由于 C# 语言是 pass-by-value,我们在构造这颗 With 的时候,Math.Plus(a, 0.1) 已经求值。但是这个时候 Box 的值还没有被填充,求出来肯定是有问题的。

所以我们需要对这样一种计算再进行一次抽象。希望可以得到的效果是,对于 Math.Plus(0.1, 0.2),可以在构造树的时候直接求值;对于 Math.Plus(0.1, a),可以得到某种计算,在我们需要的时候再求值。 先明确下函数调用有哪几种情况:

对 UnitAI,也就是外部世界的定义的接口的调用。这种调用,对于 AI 模块来说,本质上是 pure 的,所以不需要考虑这个延迟计算的问题

对标准库的调用

按我们之前的 runtime 设计思路,Math.Plus 这个标准库 API 也许会被设计成这样:

public static Thunk<float> Plus(Thunk<float> a, Thunk<float> b)
        {
            return Help.MakePureThunk(a.GetUserValue() + b.GetUserValue());
        }

 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 内部引用到了 With 外部的 symbol,那么这个 With 本身应该是 impure 的。
  • With 内部只引用了自己的 IOGet,那么这个 With 本身是 pure 的,但是其 SubTree 是 impure 的。
  • 所以 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);
        }
    }

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);
    }

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));
        }
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 的时候才会求值。

TODO

到目前为止,已经形成了一套基本的、non-trivial 的游戏 AI 方案,当然后续还有很多要做的工作,比如:

更多的语言特性:

  • DSL 中支持注释、函数作为普通的 value 传递等等。
  • parser、typechecker 支持更完善的错误处理,我之前单独写一个用例的时候,就因为一些细节问题,调试了老半天。
  • 标准库支持更多,比如 Y-Combinator

编辑器化:

AI 的配置也需要有编辑器,这个编辑器至少能实现的需求有这样几个:

  • 与自己定义的中间层对接良好(配置文件也好、DSL 也好),具有 codegen 功能
  • 支持工作空间、支持模块化定义,制作一些 prefab 什么的
  • 支持可视化调试

心动了吗?还不赶紧动起来,打造属于自己的游戏世界!顿时满满的自豪感,真的很想知道大家的想法,还请持续关注更新,更多干货和资料请直接联系我,也可以加群710520381,邀请码:柳猫,欢迎大家共同讨论

上一篇:C语言——入门


下一篇:边缘计算赋能数字化新模式,施耐德电气再度领跑行业