— AI分享站

Archive
代码分享

第一部分 第二部分

行为树最后一个要讲的地方,是关于前提(Precondition),在第一部分里,我略微提到了一下,这次我们来仔细看看,再来看看关于前提的纯虚基类的定义:

 1: class BevNodePrecondition
 2: {
 3: public:
 4:     virtual bool ExternalCondition(const BevNodeInputParam& input) const = 0;
 5: };

每一个前提类,都需要实现这个判断的虚函数。我在《用类来表示逻辑运算–关于行为树前提的一种实现方式》提到,我们可以用类来表示逻辑运算,这样的好处是可以做到模块化,同样的判断条件可以复用,所以在库中,我也实现了这种逻辑的表达方式,定义了基本的逻辑运算类

 1: class BevNodePreconditionTRUE{};
 2: class BevNodePreconditionFALSE{};
 3: class BevNodePreconditionNOT{};
 4: class BevNodePreconditionAND{};
 5: class BevNodePreconditionOR{};
 6: class BevNodePreconditionXOR{};

从这些类的名字应该就可以明显的看出这些类的含义了,和逻辑操作符一样,有些类的构造函数需要两个参数,以此来表示二元的逻辑运算(AND,OR,XOR),有些只需要一个参数,以此来表示一元的逻辑运算(NOT)。前提类被用来附在行为树的节点上(每一个节点都可以附加),默认情况下,节点上是没有前提类的,也就是不存在“外在前提”,而只有“内在前提”,这和附了一个BevNodePreconditionTRUE(永远返回True)的“外在前提”的节点是等价的。

好了,行为树库的内容基本就是这些了。接下去我们来看看例子程序,介绍如何用库来创建行为树,例子的代码在BevTreeTest这个工程中,编译后可直接运行,这个例子分别演示了三个行为树,从简单到复杂,单击鼠标可以在这三个例子间切换。这个程序实现了这样一个功能,“在场景地图上,定时会产生一个目标点,智能体就会根据行为树的定义,用不同的行为模式移动到目标点”。

在这个程序中,我为智能体一共定义了4个行为:

 1: class NOD_Idle{};      //空闲,表现是颜色不停变化
 2: class NOD_Breathe{};   //呼吸,表现是大小规律性变化
 3: class NOD_MoveTo{};    //移动,平移到某目标点
 4: class NOD_FaceTo{};    //转向,转向到某方向

再定义了2个“外在前提”:

 1: class CON_HasReachedTarget{};    //是否到达目标点
 2: class CON_HasFacedToTarget{};    //是否朝向目标点

我就用第一个例子来说,第一例子的行为树图如下:

BevTreeTest1

这是一个很简单的行为树,根节点是一个带优先级的行为节点,所以MoveTo比Idle的优先级高,MoveTo带有一个“外在前提”,“当没有到达目标点”时,会选在MoveTo的行为,反之,则选Idle的行为。

在代码中,可以这样来定义这棵行为树

 1: BevNode& ret =
 2:     BevNodeFactory: :o CreatePrioritySelectorNode(NULL, "root");
 3:         BevNodeFactory: :o CreateTeminalNode<NOD_MoveTo>(&ret, "move to")
 4:             .SetNodePrecondition(new BevNodePreconditionNOT(new CON_HasReachedTarget()));
 5:         BevNodeFactory: :o CreateTeminalNode<NOD_Idle>(&ret, "idle")
 6:             .SetNodePrecondition(new BevNodePreconditionTRUE());
 7: m_BevTreeRoot = &ret;

我在库中定义了一些工厂方法,帮助创建相关的节点。值得注意的是,我在这里演示了用类表示逻辑的用法。我在定义行为树的时候,会用一些格式上的缩进,来表示相应的父子结构,这仅仅是为了视觉上比较明了。当然,以后可以改进行为树的定义接口,更可以用数据文件来定义行为树。

这样定义完毕后,我们就可以用行为树来决策我们的行为了,代码相当简单

 1: BevNodeInputParam input(&m_BevTreeInputData);
 2: BevNodeOutputParam output(&m_BevTreeOutputdata);
 3: if(m_BevTreeRoot->Evaluate(input))
 4: {
 5:     m_BevTreeRoot->Tick(input, output);
 6: }

在例子中,我尽量把行为树中要输出的变量写到BevNodeOutputParam结构中(而不是直接修改智能体的信息),这样做的好处是可以让行为树的输入和输出的接口相当清晰,做成黑盒,可以参考我在这里的讨论。

第二个例子演示了并行节点的用法,第三个例子演示了序列节点的用法,就不多说了,大家可以自行看代码。

所有的代码可以通过以下方式获得:

下载地址:

GoogleCode下载点(exe文件夹中已包含可执行文件)

也可用svn通过以下地址来得:

http://tsiu.googlecode.com/svn/branches/blogver/

编译方法:

用VS2005以上打开,选择Debug NoDx或者Release NoDx,编译后,运行BevTreeTest.

相关代码:

TAI_BevTree.h

TAI_BevTree.cpp

关于TsiU

TsiU是我一直在维护的一个自己用的小型的框架,我平时做的一些AI的sample,或者一些工具,都会基于这个框架,TsiU有一些基本的UI控件库,网络模块库,GDI绘图模块,D3D绘图模块等等,可以快速的做成一个小型的示例程序,很方便(具体可参考SampleApps里的例子程序),并且整个架构是用Object的方式来组织,非常容易理解和扩展。整个框架很轻量化,基本就是做了一些底层的基本的功能,这样我在平时做东西的时候,就不需要重新写底层了,把精力都放在高层的实现了。以后分享代码都会基于这个框架,大家也可以通过svn来随时update到我最新的改动。下图就是TsiU里的几个工程介绍,代码不多,大家想看的也可以自己看一下 :)

————————————————————————
作者:Finney
Blog:AI分享站(http://www.aisharing.com/)
Email:finneytang@gmail.com
本文欢迎转载和引用,请保留本说明并注明出处
————————————————————————

Read More

第一部分

上一次说到了节点的基类,它描述了在行为树上一个节点的基本结构。我们知道,在行为树上有两大类的节点,一种我称之为“控制节点”,像“选择节点”,“并行节点”,“序列节点”都属于此类,这类节点负责行为树逻辑的控制,是和具体的游戏逻辑无关的,属于行为树库的一部分,并且这类节点一般不会作为叶节点。还有一类称为“行为节点”,也就是行为树上挂载的具体行为,是和游戏逻辑相关的,不属于行为树库的一部分,需要自己去继承和实现,这类节点一般都作为叶节点出现。

先来看看“行为节点”的代码,我先从节点的基类继承了一个所有“行为节点”的基类

 1: class BevNodeTerminal : public BevNode
 2: {}

在它的Tick方法中,我做了一个简单的状态机(可以自行看代码),负责处理进入行为(Enter),更新行为(Execute),退出行为(Exit),所有的行为节点应该继承自BevNodeTerminal类,并且重写这些虚函数,在进入和退出行为里,可以做一个初始化和清理的工作:

 1: class BevNodeTerminal : public BevNode
 2: {
 3: protected:
 4:     virtual void                _DoEnter(const BevNodeInputParam& input)                                {}
 5:     virtual BevRunningStatus    _DoExecute(const BevNodeInputParam& input, BevNodeOutputParam& output)  { return k_BRS_Finish;}
 6:     virtual void                _DoExit(const BevNodeInputParam& input, BevRunningStatus _ui_ExitID)    {}
 7: }

值得注意的是,在Tick方法中,它有一个返回值,表示当前节点是否处理完毕,在库中,我定义了一个enum来表示节点的运行状态:

 1: enum BevRunningStatus
 2: {
 3:     k_BRS_Executing                 = 0,
 4:     k_BRS_Finish                    = 1,
 5:     ...
 6: };

当返回k_BRS_Finish的时候,就表示当前节点已经处理完毕了,如果再次进入该节点,就认为是重新进入了。用上面描述的那个状态机的来说的话就是,如果是重新进入,会先调用_DoEnter方法,然后调用_DoExecute方法,如果_DoExecute返回正在运行(k_BRS_Executing),那么以后再进入这个节点就会直接调用_DoExectue,如果返回已经结束(k_BRS_Finish),则会调用_DoExit,以后再进入这个节点就会重新调用_DoEnter方法了。

对于控制节点来说,它的运行状态和子节点的运行状态是息息相关的,比如,选择节点的运行状态,就是它当前选择的这个节点的运行状态,并且,有时控制节点的控制逻辑也和子节点的运行状态有关,比如序列节点,当它前一个子节点运行结束,序列节点就会自动的切换到下一个子节点运行。所以在实现具体的行为类时,我们应该要正确的返回节点的运行状态。在例子程序中,我做的一个“空闲”(idle)的行为节点,就能很好的说明问题:

 1: class NOD_Idle : public BevNodeTerminal
 2: {
 3: public:
 4:     NOD_Idle(BevNode* _o_ParentNode)
 5:         :BevNodeTerminal(_o_ParentNode)
 6:     {}
 7: protected:
 8:     virtual void _DoEnter(const BevNodeInputParam& input)
 9:     {
 10:         m_WaitingTime = 0.5f;
 11:     }
 12:     virtual BevRunningStatus _DoExecute(const BevNodeInputParam& input, BevNodeOutputParam& output)
 13:     {
 14:         const BevInputData& inputData = input.GetRealDataType<BevInputData>();
 15:         BevOutputData& outputData = output.GetRealDataType<BevOutputData>();
 16:
 17:         f32 timeStep = inputData.m_TimeStep;
 18:         m_WaitingTime -= timeStep;
 19:         if(m_WaitingTime < 0)
 20:         {
 21:             outputData.m_BodyColor = D_Color(rand() % 256, rand() % 256, rand() % 256);
 22:             return k_BRS_Finish;
 23:         }
 24:         return k_BRS_Executing;
 25:     }
 26: private:
 27:     float m_WaitingTime;
 28: };

这段代码中的某些内容不明白也没有关系,我们主要关注的是关于节点运行状态的部分。这个Idle行为做了一件这样的事,就是不停的变换自己的颜色,间隔是0.5秒,当时间一到,就会返回运行结束(k_BRS_Finish),并输出当前的颜色,当时间还没到,则返回运行中(k_BRS_Executing),并且维持当前颜色。可以看到,我们用运行状态控制了计时器的重置,选择在_DoEnter方法中重置了计时器,当然,更合理的做法是在时间一到的时候,就重置计时器,并且永远返回运行中,不过这个例子里,我主要就是想用来演示运行状态,和_DoEnter的相关用法。

接下去再来看看控制节点,我一共写了5种控制节点,带优先级的选择节点(BevNodePrioritySelector),不带优先级的选择节点(BevNodeNonePrioritySelector),序列节点(BevNodeSequence),并行节点(BevNodeParallel),循环节点(BevNodeLoop),这些节点的进入条件和选择逻辑都是按照在行为树中改节点的定义来做的,我想用一张表格来说明:

测试(Evaluate) 更新(Tick)
带优先级的选择节点(BevNodePrioritySelector) 从第一个子节点开始依次遍历所有的子节点,调用其Evaluate方法,当发现存在可以运行的子节点时,记录子节点索引,停止遍历,返回True。 调用可以运行的子节点的Tick方法,用它所返回的运行状态作为自身的运行状态返回
不带优先级的选择节点(BevNodeNonePrioritySelector) 先调用上一个运行的子节点(若存在)的Evaluate方法,如果可以运行,则继续运保存该节点的索引,返回True,如果不能运行,则重新选择(同带优先级的选择节点的选择方式) 调用可以运行的子节点的Tick方法,用它所返回的运行状态作为自身的运行状态返回
序列节点(BevNodeSequence) 若是从头开始的,则调用第一个子节点的Evaluate方法,将其返回值作为自身的返回值返回。否则,调用当前运行节点的Evaluate方法,将其返回值作为自身的返回值返回。 调用可以运行的子节点的Tick方法,若返回运行结束,则将下一个子节点作为当前运行节点,若当前已是最后一个子节点,表示该序列已经运行结束,则自身返回运行结束。若子节点返回运行中,则用它所返回的运行状态作为自身的运行状态返回
并行节点(BevNodeParallel) 依次调用所有的子节点的Evaluate方法,若所有的子节点都返回True,则自身也返回True,否则,返回False 调用所有子节点的Tick方法,若并行节点是“或者”的关系,则只要有一个子节点返回运行结束,那自身就返回运行结束。若并行节点是“并且”的关系,则只有所有的子节点返回结束,自身才返回运行结束
循环节点(BevNodeLoop) 预设的循环次数到了就返回False,否则,只调用第一个子节点的Evaluate方法,用它所返回的值作为自身的值返回 只调用第一个节点的Tick方法,若返回运行结束,则看是否需要重复运行,若循环次数没到,则自身返回运行中,若循环次数已到,则返回运行结束

可能看表格内的描述会感觉有点拗口,可以结合代码一起看,会理解的更好。特别要提一点的是,在某些控制节点的Evaluate方法中,我会修改和记录可以运行的节点索引,当调用Tick的时候,就可以用这个索引来找到可以运行的节点了。这种模式和我以前提到的行为树更新模式有点不太一样,不过本质上是相同的。

(待续…)

————————————————————————
作者:Finney
Blog:AI分享站(http://www.aisharing.com/)
Email:finneytang@gmail.com
本文欢迎转载和引用,请保留本说明并注明出处
————————————————————————

Read More

最近一直在忙新项目的准备,甚少涉及AI的东西,所以博客也疏于更新。春节前,收到一个网友的邮件,说看了行为树的一些东西,但还是不知道如何去入手实现,我就乘着春节假期,动手写了一个简单的行为树的库,和大家一起边分析代码,边说说行为树的具体实现方法。这个库很简单,一共也就800行的代码左右,不过麻雀虽小,五脏俱全,行为树中的主要部分基本都有涵盖,包括前提(Precondition),选择节点(Selector),并行节点(Parallel),序列节点(Sequence)等等。在分析代码前,如果有朋友对行为树的相关概念还不是很了解,建议先阅读本站上对于行为树介绍的相关文章。

这次的代码以及示例程序,还是基于我自己维护的一个框架TsiU,在系列文章的最后会给出下载链接。

行为树,由名字就可以看到,它是一个树结构,通过各个节点相互连接,所以我先定义了节点的基类:

 1: class BevNode{}

要把树链接起来,需要在这个类中保留父节点指针,和子节点指针,我用了一个固定的数组来保存子节点指针,它的大小是16,也就是说,一个节点最多可以有16个子节点

 1: class BevNode
 2: {
 3: protected:
 4:     BevNode*    mao_ChildNodeList[k_BLimited_MaxChildNodeCnt];
 5:     ...
 6:     BevNode*    mo_ParentNode;
 7: }

有了这些变量的定义,我们就可以串联起一颗树了。到目前为止,这个节点类还仅仅是一个树的节点,作为行为树的节点还差了些东西,在以前的介绍中,我们知道行为树的每一个节点都可以绑定一个称为前提(Precondition)的部分,用来作为是否进入这个节点的条件,在我的实现中,我把这个前提拆分成了两个部分,一个称为“内在前提”,一个称为“外在前提”。“内在前提”是和节点类静态绑定的(也就是说,这个节点的固有前提),而“外在前提”是可以和节点做动态绑定的。这样做的原因是,由于在行为树上,节点是可以被复用的,在不同的子树上他的进入条件往往是不同的。比如,“移动”,这是一个常见的行为节点,逃跑的时候,可能需要“移动”,追击的时候也需要“移动”,但进入这个节点需要不同的“外在前提”,所以这里就需要让节点支持动态绑定的前提。“内在前提”,我用继承的方式来实现,而“外在前提”,我用了另一个类来实现

 1: class BevNode
 2: {
 3: public:
 4:     bool Evaluate(const BevNodeInputParam& input)
 5:     {
 6:         return (mo_NodePrecondition == NULL || mo_NodePrecondition->ExternalCondition(input)) && _DoEvaluate(input);
 7:     }
 8: protected:
 9:     virtual bool _DoEvaluate(const BevNodeInputParam& input)
 10:     {
 11:         return true;
 12:     }
 13: protected:
 14:     BevNodePrecondition* mo_NodePrecondition;
 15: }

可以看到这里用到了一个叫做BevNodePrecondition的类,用来表示“外在前提”,他是一个纯虚函数,只有一个方法,先看一下它的定义,后面会有详细的讨论。

 1: class BevNodePrecondition
 2: {
 3: public:
 4:     virtual bool ExternalCondition(const BevNodeInputParam& input) const = 0;
 5: };

_DoEvaluate虚方法就是需要被子类继承并实现的“内在前提”,这两种前提在Evaluate方法中被结合了起来,用来检测进入条件,当返回True时,就表示当前节点可以被运行。返回False时,就表示当前节点进入条件不满足,不能被运行。

在节点基类的中,还有两个重要的方法是:

 1: class BevNode
 2: {
 3: public:
 4:     void Transition(const BevNodeInputParam& input)
 5:     {
 6:         _DoTransition(input);
 7:     }
 8:     BevRunningStatus Tick(const BevNodeInputParam& input, BevNodeOutputParam& output)
 9:     {
 10:         return _DoTick(input, output);
 11:     }
 12: }

转移(Transition)的概念是第一次出现,转移(Transition)指从上一个可运行的节点切换到另一个节点的行为。这个方法会被在节点切换的时候调用,比如,在一个带优先级的选择节点下有节点A,和节点B,节点A的优先级高于节点B,当前运行的节点是B,然后发现节点A可以运行了,但带优先级的选择节点就会选择去运行节点A,这时就会调用节点B的Transition方法,所以在这个方法中,一般可以用来做一些清理的工作。Tick方法就是通常的更新方法,就不多说了。

再来看一下这三个重要方法的参数,一共有两种类型的参数,BevNodeInputParam和BevNodeOutputParam,前者是传入参数,可以认为是行为树的输入,用const作为限定符,表示只读,后者是传出参数,可以认为是行为树的输出,可以修改。其实,从代码中可以看到,这两种类型的本质都是一样的,都是一个名为AnyData的类

 1: typedef AnyData BevNodeInputParam;
 2: typedef AnyData BevNodeOutputParam;

由于输入和输出参数是游戏相关的,所以这里用AnyData这个类来表示,这个类可以存放任意的数据结构,所以,这个类中真正的内容是需要玩家自己定义的。

最后来看看行为树是如何被定义和更新的(可以在示例程序中找到相关代码)

 1: //define input & output data
 2: struct BevInputData{...}
 3: struct BevOutputData{...}
 4: BevInputData    m_BevTreeInputData;
 5: BevOutputData   m_BevTreeOutputdata;
 6: ....
 7: //create tree
 8: m_BevTreeRoot = CreateTree();
 9: ...
 10: //update
 11: BevNodeInputParam input(&m_BevTreeInputData);
 12: BevNodeOutputParam output(&m_BevTreeOutputdata);
 13: if(m_BevTreeRoot->Evaluate(input))
 14: {
 15:     m_BevTreeRoot->Tick(input, output);
 16: }
  1. 定义自己的输入和输出参数(BevInputData,BevOutputData)
  2. 创建行为树,保存根节点指针(m_BevTreeRoot)
  3. 测试是否有可以运行的节点,如有则更新

(待续…)

————————————————————————
作者:Finney
Blog:AI分享站(http://www.aisharing.com/)
Email:finneytang@gmail.com
本文欢迎转载和引用,请保留本说明并注明出处
————————————————————————

Read More

在上次博文《关于调试AI的闲话(1)》中,提到一个利用共享内存实现的参数调试模块,我整理了一下代码,现在放出来,给大家参考,

下载地址:

GoogleCode下载点

也可用svn通过以下地址来得:

http://tsiu.googlecode.com/svn/branches/blogver/

编译方法:

用VS2005以上打开,选择Debug NoDx或者Release NoDx, 在AITest工程,ATInit.cpp中,有一个宏

#define APP_ONE

打开这个宏,编译一次生成一个可执行文件AITest.exe(在exe\aitest\中),重命名后(比如,AITestA.exe),再关闭这个宏,重新编译一次。

测试方式:

打开编译好的两个exe文件,在其中一个窗口中(有文字提示),按住鼠标左键移动鼠标,就可以看到在另一个窗口中有一个红色的圈在同时移动,另外绿色的圈也是通过这个模块来通信的。

参数调试模块:这次提到的模块代码主要是这两个文件,

TAI_RefValue.h
TAI_RefValue.cpp

说明:

  1. 使用方法可以参考AITest中的例子,注意,需要每帧调用Flush来刷新。
  2. 删除后内存回收的功能还没做,这个需要改变内存的组织方式来做,现在是用数组的方式,可能需要改成链表的方式来组织
  3. 不建议将RefValue用在临时变量里,因为观察一个临时变量的某个值没有什么意义

顺便说一下,整个分享出来的代码是基于一个叫“TsiU”的框架来做的,它是我一直在维护的一个自己用的小型的框架,我平时做的一些AI的sample,或者一些工具,都会基于这个框架,TsiU有一些基本的UI控件库,网络模块库,GDI绘图模块,D3D绘图模块等等,可以快速的做成一个小型的示例程序,很方便(具体可参考AITest),并且整个架构是用Object的方式来组织,非常容易理解和扩展。整个框架很轻量化,基本就是做了一些底层的基本的功能,这样我在平时做东西的时候,就不需要重新写底层了,把精力都放在高层的实现了。以后分享代码都会基于这个框架,大家也可以通过svn来随时update到我最新的改动。下图就是TsiU里的几个工程介绍,代码不多,大家想看的也可以自己看一下 :)

tsiu-project

————————————————————————
作者:Finney
Blog:AI分享站(http://www.aisharing.com/)
Email:finneytang@gmail.com
本文欢迎转载和引用,请保留本说明并注明出处
————————————————————————

Read More