— AI分享站

Archive
Tag "状态机"

自开博以来,经常会有网友发信给我,询问一些关于AI方面的问题,一般我都会尽力一一回答,也希望我的这些经验,对网友有些帮助,我想,有些问题可能是大家都会有的,所以,这一次,我会把一些网友的提问,和我的回答列在这个地方,供更多的同学参考,也欢迎一起讨论,才疏学浅,不吝赐教。

Q:你好,我在你的博客上看了你的一些关于行为树的文章,写得很好,让我受益匪浅。我想实践一下怎么用,在网上找了一个相关的库libbehavior(https://code.google.com/p/libbehavior/),想用这个库做个小例子,它里面有一些演示程序,但牵涉到很多库,不好学习,我就想将一个简单的状态机示例程序源码改成用行为树实现,发现还是很茫然,不知道你是否有空给些提示,谢谢!

A:我下载了程序简单看了下,libbehavior好像已经实现了一个可用的behavior tree了,虽然可能还不够完善,但基本的行为树的样子已经有了,你可以考虑基于他这个,然后根据自己的需求添加。 不知道你有没有看到它里面的sample,我从Scenario3.h里摘录了一段建行为树的例子来说明下,我还画了一张示意图作为参考

 1: //opponent->brain是一个ParallelNode,并行的节点
 2: //在并行节点上添加第一个子节点,行为是转向目标TurnTowardsTarget
 3: opponent->brain->addChild(new TurnTowardsTarget(1));
 4: //建立一个随机节点作为第二个子节点,下面三个序列节点应该会随机选一个执行
 5: ProbabilityNode* pNode = new ProbabilityNode();
 6: //在这个随机节点上,建立一个序列节点
 7: pNode->addChild((new SequentialNode())
 8:         //在序列节点上建立第一个子节点,感觉这个应该是个判断条件
 9:          ->addChild(new BoolCondition<GameObject>(&GameObject::alignedWithPlayer,true))
 10:         //在序列节点上建立第二个子节点,行为是射击Fire
 11:          ->addChild(new Fire())
 12:         //在序列节点上建立第二个子节点,行为是等待CD,防止太频繁
 13:          ->addChild(new Cooldown(500)),5.0);
 14: //在这个随机节点上,再建立一个序列节点,下面的子节点就不说明了
 15: pNode->addChild((new SequentialNode())
 16:          ->addChild(new FloatCondition<GameObject>(&Ship::getXPosition,LESS_THAN_FP,200,1))
 17:          ->addChild(new GotoPoint(point(300,50),500))
 18:          ->addChild(new Cooldown(200)))
 19: //在这个随机节点上,再建立一个序列节点,下面的子节点就不说明了
 20: pNode->addChild((new SequentialNode())
 21:          ->addChild(new FloatCondition<GameObject>(&Ship::getXPosition,GREATER_OR_CLOSE,200,1))
 22:          ->addChild(new GotoPoint(point(100,50),500))
 23:          ->addChild(new Cooldown(200)));
 24: //在这个随机节点的上面做一个循环节点,把上面的行为无限循环
 25: opponent->brain
 26:     ->addChild((new RepeatNode(-1))
 27:         ->addChild(pNode));

Scenario3BevTree

 

所以如果你要把状态机改成行为树的话,可以考虑用我说过的Selector节点+Precondition的方式(libbehavior里好像是叫PriorityNode,但它好像没有Preconditon的概念),因为状态机里不是要跳转嘛,你原先每一个state都会有进入条件的,比如下面这个

 1: if (pMiner->PocketsFull())
 2: {
 3:     pMiner->ChangeState(VisitBankAndDepositGold::Instance());
 4: }

这样的话,你可以把pMiner->PocketsFull()作为VisitBankAndDepositGold的Precondition挂在一个Selector节点下面,然后让Selector节点帮助你选择应该进入那个状态。我建议,你可以先看看libbehavior每一个Scenario的行为树创建部分的代码,这样应该会有点感觉,另外,可以边参考我网上的文章,边来看libbehavior\BehaviorTree-src里的源码,会好理解很多 :) ,希望对你有所帮助!欢迎继续来信交流!(状态机和行为树之间转换可以参看这里这里

Q:看了你写的一系列文章,写的真不错。我也最进在游戏行业,做AI相关的工作。涉及一些游戏AI设计的问题,能否指教一下。目前我们游戏AI设计的部分考虑NPC的AI部分可配置成AI执行脚本文件方式。我考虑是可以设计AI框架,依据游戏对象的配置,框架决定加载相应的脚本引擎。我看 《浅谈层次化的AI架构》 不错,你能不能分享一下AI设计中如何分离AI框架和AI脚本内容的呢。分离的话,感觉状态转换是应该在AI脚本中完成的吧? 暴露AI引擎的API接口的通用设计一般是怎么样的呢?学习中...., 谢谢。

A:如果想在脚本中写很多AI逻辑的话,如何调试是个比较麻烦的事情,需要比较好的调试接口。我用过一种做法,你可以试试看,就是用脚本做AI的配置,逻辑还是在C++端。C++提供一个个AI逻辑模块,然后在脚本端把它配置起来,因为我用的是行为树(可以参看我博客上关于行为树的相关文章),所以比较容易配置。接口的话,首先最好是引擎能支持反射,然后就能方便的导出函数和变量直接给脚本用,至少我用lua做脚本语言,这样是可行的。

Q:您好。今天再搜索层次状态机相关资料的时候进入了您的博客。本人只在游戏中使用过简单的FSM,属于AI初学者,阅读了几篇文章后产生了几个问题:

  • HFSM和行为树到底是什么关系。我对行为树和状态机的区别还是把握不了……
  • 您有一文章说:大部分的AI,都可以分成“决策”和“行为”,二者通过一个双缓冲的“请求层”通信,但是这篇文章您没有举例子,我非常模糊。
  • 对“并行节点”我还是很模糊……您可以给我举个例子吗……麻烦了…。

A:谢谢,针对每一个问题,我的回答如下:

  • HFSM和行为树其实没什么关系,是两种不同的AI结构,区别的话,可以看我在这里的评论http://www.aisharing.com/archives/90#comment-111
  • 有人和你提出了一样的问题,可以参看我这里的回复,http://www.aisharing.com/archives/86#comment-115
  • 比如一个并行节点下有A和B两个节点,那在一次循环里,如果前提满足的话,既会执行A,又会执行B,举个实际的例子,比如要描述“又吃又喝”,就可以用并行节点:)

Q:最近在学习行为树,有幸拜读了您几篇关于行为树的文章,感觉收获颇多。刚开始接触行为树,所知有限,特来请教几个问题:

  • 关于以下代码,在文章评论中,您回复说 input 是传入行为树的参数,那么 request 是指输入的事件吗?比如移动事件、死亡事件等。 如果是事件,那您实例代码的行为树是事件驱动的,还是Tick驱动?
 1: action = root.FindNextAction(input);
 2: if action is not empty then
 3:     action.Execute(request,  input)  //request是输出的请求
 4: else
 5:     print “no action is available”
  • 在FSM中,状态进入和退出时可以做相对应的事情,比如进入某个状态身上挂个循环特效,退出该状态将这个特效移除,在行为树上,怎么实现同样的功能?
  • 按我现在对行为树的理解,感觉行为树就是将FSM中的状态变成了子树,挂在行为树的相应位置,通过行为树的节点完成状态的迁移。但是,在您文章的总结中提到:"在AI设计过程中,一般来说,我们并不是先有状态机,再去转化成行为树的,当我们选择用行为树的时候,我们就要充分的理解控制节点,前提,节点等概念,并试着用行为树的逻辑方式去思考和设计。",看后对自己将状态视为子树的理解产生了很大的怀疑,您能详细地解释下这句话吗?不知是否可以提供一张您平时设计的较复杂些的行为树供我学习之用?

A:谢谢,针对每一个问题,我的回答如下:

  • request是输出的请求,也就是行为树的输出,就像你说的,像移动,死亡等,可以看看我博客上关于分层次的AI架构的相关文章,整个行为树的决策还是在Tick中更新的。
  • 一般我在做行为树的Execute时会分成三个阶段,onEnter() ,onExecute(),onExit(),在第一次进入这个节点的时候,会调用onEnter,在从这个节点切换出去的时候,会调用onExit()。每个行为树的节点,我都会做成这种1P(前提Precondition) + 3E(Enter, Execute, Exit)的结构
  • 行为树的思考方式是指,对于每一个节点我都需要明确知道它的进入条件是什么,它要做的事情是什么。把跳转逻辑写到控制节点中,用控制节点来控制行为树的选择流程。和状态机不同的是,对于行为树的节点,一般不需要知道它是从哪个节点过来的,它只是需要关心,满足什么条件(前提)可以进入这个节点,这些条件的判断依据都是通过行为树的输入参数传入的,所以行为树和黑板的组合是很好用的,可以看看我博客上关于黑板和行为树结合的文章
  • 项目里的行为树图不太好给,呵呵,而且需要解释才能明白。复杂的话,一般就会用到序列节点,并行节点等等。行为树的好处就是只要定义了进入前提,就可以加入到现有的行为树中,这样就越来越复杂了~,不过,这也就是行为树的好处了 :)

Q:Hi,在我们现在的项目里面涉及到AI的一些东西,之前学习了关于你写得行为树,正好可以发挥一下,现在有一个问题,就是关于怪物行走,怪物行走我们这边的做法就是发目标A*路径给客户端通知其他玩家,然后,怪物每秒刷一步就走一步...这样的做法...我想问问...你们那边关于怪物行走是如何实现的呢?巡逻和追击 两个地方行为怎么做互斥?

A:针对你的问题,我在想哦,对于怪物移动的话,可以分两个部分,一般的移动,就是你说的巡逻,可以不需要用A*,因为毕竟A*的开销是比较大的,因为怪物一般的移动不会太复杂,而且一般是在一定的区域内移动(当然这是看你们怎么设计了),可以在区域内设置几个路点,然后每过一段时间选择临近的路点就可以了,也就是仅仅做一步的“寻路”。如果是要追击玩家的话,可以尝试用到A*。

网页游戏我没做过,其他游戏里,我们用到过同步位置信息的方式,也就是每隔一段时间同步一次位置,然后两次同步之间的移动,都是客户端本地模拟。如果模拟后的位置和服务器上的位置有偏差,简单的做法是瞬移到服务器上的位置,好一点的话就是平滑的从客户端现在的位置移动到服务器上的位置。

巡逻和追击我觉得比较大的不同是,巡逻中是没有目标敌人的,而追击是存在目标敌人的,所以这样就可以做到互斥了。

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

Read More

第一部分见这里

模式3:根据条件跳转到多个状态,包括自跳转

这是在状态机里最常见的模式,由于是基于条件的跳转,所以可以非常方便的用选择节点和前提的组合来描述,特别值得注意的是,对于自跳转而言,其实就是维持了当前的状态,所以,在构建行为树的时候,我们不需要特别考虑自跳转的转换。如下图所描述了,我们先用序列节点来保证跳转的上下文(可以参考模式2中的相关内容),这里用到的另一个技巧是,我们会在状态a结束的时候,在黑板中记录其结束的原因,以供后续的选择节点来选择。另外,我们在第二层选择节点第一次用到了非优先级的选择节点,和带优先级的选择节点不同,它每次都会从上一次所能运行的节点来运行,而不是每次都从头开始选择。

Fsm2BtPattern3

当然,和模式2类似的是,我们也可以不用序列节点,而是单纯的用选择节点,这样的话,作为默认状态的状态a就需要处在选择节点的最后一个,因为仅当所有跳转条件都不满足的时候,我们才会维持在当前的状态。如上图的下面那颗行为树那样。请仔细查看,我在前三个节点对于前提的定义,除了本身的跳转条件外,还加上了一个额外的条件,InAXState,它保证了仅在上一次运行的是A状态或自身的时候,我们才会运行当前的节点,这样就保证了和原本状态机描述是一致的。

模式4:循环跳转

在状态机中存在这样一种模式,在状态a中,根据某条件1,会跳转到状态b中,而在状态b的时候,又会根据某条件2,跳转到状态a,产生了这样一个跳转的“环”。显而易见的是,行为树是一种树形结构,而带环的状态机是一种图的结构,所以对于这种情况,我想了下,觉得需要引入一种新的选择节点,我称之为动态优先级选择节点(Dynamic Priority Selector),这种选择节点的工作原理是,永远把当前运行的节点作为最低优先级的节点来处理。如下图

Fsm2BtPattern4

当我们在节点a的时候,我们会先判断b的前提,当b的前提满足的时候,我们会运行节点b,下一帧再进来的时候,由于现在运行的是节点b,那它就是最低优先级的,所以,我们会先判断节点a的前提,满足的话,就运行节点a,不满足则继续运行节点b,依次类推。下面是我写的相关代码,可以给大家参考。

 1: void DynamicPrioritySelector::Test(const Blackboard& in) const
 2: {
 3:     bool hasRunningChild = IsValid(m_iCurrentRunningChildIndex);
 4:     int nextRunningChild = -1;
 5:     for(int i = 0; i < m_ChildNodes.Count(); ++i)
 6:     {
 7:         if(hasRunningChild &&
 8:            m_iCurrentRunningChildIndex == i)
 9:         {
 10:             continue;
 11:         }
 12:         else
 13:         {
 14:             if(m_ChildNodes[i]->Test(in))
 15:             {
 16:                 nextRunningChild = i;
 17:                 break;
 18:             }
 19:         }
 20:     }
 21:     if(IsValid(nextRunningChild))
 22:     {
 23:         m_iCurrentRunningChildIndex = nextRunningChild;
 24:     }
 25:     else
 26:     {
 27:         //最后测试当前运行的子节点
 28:         if(hasRunningChild)
 29:         {
 30:             if(!m_ChildNodes[m_iCurrentRunningChildIndex]->Test(in))
 31:             {
 32:                 m_iCurrentRunningChildIndex = -1;
 33:             }
 34:         }
 35:     }
 36:     return IsValid(m_iCurrentRunningChildIndex);
 37: }

总结

从上面4种模式的转化方式中,我们好像会有种感觉,用行为树的表达好像并没有状态机的表述清晰,显的比较复杂,罗嗦。这主要是因为我们用行为树对状态机做了直接的转化,并想要尽力的去维持状态机的语义的缘故。其实,在AI设计过程中,一般来说,我们并不是先有状态机,再去转化成行为树的,当我们选择用行为树的时候,我们就要充分的理解控制节点,前提,节点等概念,并试着用行为树的逻辑方式去思考和设计。

不过,有时,我们也许想用行为树改造一个已有的状态机系统,那这时就可以用我上面提到的这些模式来尝试着去转换,当然在实际转换的过程中,我的建议是,先理清并列出每一个状态跳转的条件,查看哪些是带上下文的跳转,哪些是不带上下文的跳转,哪些是单纯的序列跳转(比如,从状态A,到状态B,到状态C,类似这样的单线跳转,常见于流程控制中),哪些跳转是可以合并的等等,然后再用行为树的控制节点,把这些状态都串联起来,当发现有些跳转用已有的控制节点不能很好的描述的时候,可以像我上面那样,添加新的控制节点。

这四种模式,是我现在能想到的,可能不全,如果大家有问题,可以在后面留言,有指教的也欢迎一起讨论。

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

Read More

选这次主题,要感谢一位网友的来信,他询问了一些如何将有限状态机转成行为树的问题,当时,我回信给了一些建议,但后来我仔细想了一下,觉得可能说得还不够全面,所以我就想通过这篇文章,来整理出一些比较典型的转化“模板”,给有这方面疑惑的朋友一些帮助,如果有朋友有一些自己的见解的,可以在后面留言,我们一起讨论。

有限状态机维护了一张图,图的节点是一个个的状态,节点和节点的连线是状态间根据一定的规则做的状态转换,每一个状态内的逻辑都可以简要描述为:

如果满足条件1,则跳转到状态1
如果满足条件2,则跳转到状态2
...
否则,不做跳转,维持当前状态

稍作整理的话,我们可以对状态机的几种跳转的情况一一描述出来,然后看看如果将这些情况用行为树来表示的话,可以怎么做。这就是我前面说的“转化模板”,当然我不能保证我下面列出的是状态机的所有可能情况,如果大家在实践中发现还有其他的情况,欢迎留言,我随时更新。

在这之前,我们可以先回忆一些关于行为树的一些概念(可以参考12

  • 控制节点:选择节点,序列节点,并行节点,等等
  • 行为节点:两种运行状态,“运行中”和“完成”
  • 前提条件

模式1:当处在任何状态中,一旦某条件满足,即跳转到某个特定的状态。

比如,在状态机中的一些错误处理,经常会用到上面的这种模式,当状态在运行过程中,发生了某些异常,那一般,我们会把状态机跳转到某个异常状态。这种情况,我们可以用到带优先级的选择节点(Priority Selector)方式,如下图,可以看到,我们把状态c作为行为树里的行为节点,跳转条件(Condition1)作为这个节点的前提(Precondition)。

Fsm2BtPattern1

再用上面举到的错误处理的例子,在状态机中,我们一般会这样写:

 1: STATE A::Update()
 2: {
 3:     ...
 4:     if(error)
 5:     {
 6:         return TO_ERROR_STATE();
 7:     }
 8:     ...
 9:     return UNCHANGED_STATE();
 10: }

转换到行为树中,我们会通过外部的黑板来做通信(可以参考这里),在行为节点a中,我们会这样写

 1: EXECUTE_STATE A::Execute(BlackBoard& out)
 2: {
 3:     ...
 4:     if(error)
 5:     {
 6:         out.error = error;
 7:         return EXECUTE_STATE_FINISH;
 8:     }
 9:     ...
 10:     return EXECUTE_STATE_RUNNING;
 11: }

然后对于节点c的前提里,我们来读取黑板里的error值

 1: bool Condition1::IsTrue(const BlackBoard& in) const
 2: {
 3:     return in.error == true;
 4: }

模式2:对于同一个跳转条件,处在不同的状态会有不同的跳转

比如,我们有两个状态,a和b,他们都对同一个跳转条件作出响应,但和模式1不同的是,a对跳转到状态c,而b会跳转到状态d,换句话说,这是一种带有上下文的状态跳转方式。对于这种情况,可以用到序列节点的相关特性,如下图

Fsm2BtPattern2

序列节点中,当前一个节点运行完成后,会执行下一个节点,利用此特性,在上图中可以看到,我们在a中,当满足条件Condition1的时候,则返回“完成”,那行为树就会自动跳转到c节点中,参考代码如下:

 1: EXECUTE_STATE A::Execute(BlackBoard& out)
 2: {
 3:     ...
 4:     if(condition1 == true)
 5:     {
 6:         return EXECUTE_STATE_FINISH;
 7:     }
 8:     ...
 9:     return EXECUTE_STATE_RUNNING;
 10: }

对于这种模式的另一种转化,可以不用序列节点,还是用到选择和前提的组合,但我们在前提中加上一个当前状态的附加条件,如下图

Fsm2BtPattern2 (1)

在第二层的前提中,我们可以这样写

 1: bool InACState::IsTrue(const BlackBoard& in)
 2: {
 3:     return in.current_running_node = A::GetID() ||
 4:            in.current_running_node = C::GetID();
 5: }
 6:
 7: bool InBDState::IsTrue(const BlackBoard& in)
 8: {
 9:     return in.current_running_node = B::GetID() ||
 10:            in.current_running_node = D::GetID();
 11: }

这样对于c的前提就是Condition1和InACState的“与”(回想一下前提的相关内容)。由于我们保留了上下文的信息,所以通过对于前提的组合,我们就转化了这种模式的状态机。

(待续…)

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

Read More

最近和一个同事讨论状态机的问题,记录一下。

我们知道状态机是AI(当然,不光是AI了)中常用的一种架构,有很多中实现方式,总体来说对于表达简单逻辑,还是很有帮助的,而且实现简单,甚至用一个switch-case就可以了,但在实践中状态机有一个致命的缺点,当状态一旦多了之后,它的跳转就会变的不可维护,假设有n个状态的话,那我们就需要维护最多n*n的跳转链接(因为状态机允许自己跳转自己),而且对于当前处在的状态而言,我不能知道我的跳转历史,也就是说,我很难知道为什么我会在这个状态里。这也就是为什么行为树现在成为相对主流的AI架构的原因。下图就演示了多状态间的跳转链接,对于AI程序员来说是非常头疼的。

shit-fsm

所以一般而言,除非是只有两三个状态的简单状态机,如果想要用状态机作为AI整体架构的话,现在都会选择层次化状态机结构(HFSM),并在一定程度上规范状态机的跳转行为。据我所知,微软的著名游戏光环2(Halo2)里就用到了层次化状态机的结构。HFSM就是为了减少跳转链接而做出的努力,举个决策小狗行为的例子,我们对小狗定义了有很多行为,比如跑,吃饭,睡觉,咆哮,撒娇,摇尾巴等等,如果每个行为都是一个状态,用常规状态机的话,我们就需要在这些状态间定义跳转,比如在“跑”的状态下,如果累了,那就跳转到“睡觉”状态,再如,在“撒娇”的状态下,如果感到有威胁,那就跳转到“咆哮”的状态等等,我们会考量每一个状态间的关系,定义所有的跳转链接,建立这样一个状态机。如果用层次化的状态机的话,我们就先会把这些行为“分类”,把几个小状态归并到一个状态里,然后再定义高层状态和高层状态中内部小状态的跳转链接,可能这样说有点晕,还是看图吧

hfsm

从上图可以看到,其实层次化状态机从某种程度上,就是限制了状态机的跳转,而且状态内的状态是不需要关心外部状态的跳转的,这样也做到了无关状态间的隔离,比如对于小狗来说,我们可以把小狗的状态先定义为疲劳,开心,愤怒,然后这些状态里再定义小状态,比如在开心的状态中,有撒桥,摇尾巴等小状态,这样我们在外部只需要关心三个状态的跳转(疲劳,开心,愤怒),在每个状态的内部只需要关心自己的小状态的跳转就可以了。这样就大大的降低了状态机的复杂度,另外,如果觉得两层的状态机还是状态太多的话,可以定义更多的状态层次以降低跳转链接数。

说回到和同事讨论的事情,当然同事的需求并不是用在AI中,是为了处理UI和网络异步请求的问题,我们知道,在网络游戏的UI中,经常需要给网络发送异步请求,然后得一些数据,正因为这些请求是异步的,所以需要在发送后等待网络返回结果,当这些请求很多的时候,很容易在UI端产生混乱(所以,一般来说,在项目中UI的bug是最多的 :) ),所以他提出了一种结构来改善这样的问题,总结下来,其实就类似于这种AI中常用的这种层次化状态机的概念,不过针对他的需求,还增加了一个并行的概念,也就是在一个状态内部,可能有多个同时运行的状态机(因为有同时多个的网络异步请求),所以当收到一个跳转请求或者消息的时候,还需要决定是哪个状态机需要跳转。另外为了防止跳转混乱,我们还谈到给状态机加更多跳转限制,增加语义支持等等问题。

最后,对于状态机,列出一些小的tips作为总结,希望对大家有所帮助

  • 要为状态定义入口动作/出口动作
  • 要详细设计每一个状态,列出层次化状态结构
  • 针对具体问题,严格限制状态跳转的请求
  • 同一层次的状态数量不宜超过5个
  • 记录每一次的跳转历史,方便调试
  • 可能的话,最好使用编辑器来编辑状态机

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

Read More