— AI分享站

Archive
2011-09 Monthly archive

第一部分见这里

模式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

LOD(Level Of Detail)是3D渲染中用到的概念,按照wikipedia上的翻译,可以译为“细节层次”,它是一种根据与观察点的距离,来减低物体或者模型的复杂度来提升渲染效率的优化技术,因为显而易见的是,当一个物体离我们很远的时候,我们不需要用很复杂的多边形来绘制,只要用一个粗略模型或者低精度的贴图即可,所以在3D渲染中,这是一个很常见的优化技术。

对于AI来说,当一个AI对象离我们很远的时候,其实,它做出什么样的决策,做出什么样的行为,我们并不能“感觉的”到,虽然它的行为可能会对游戏世界有影响,但玩家一般只会专注于离自己比较近的AI行为,所以我们在AI的优化中,也可以采用这种“LOD”的技术,来提升AI部分的运行效率。

我在玩真三国无双的时候,对此非常有感触,虽然我并不知道他是否在AI层做了LOD,但类似于这种大场景,超多NPC的游戏,AI层的LOD的优化技术就非常适合。同样的NPC,当他离玩家不同的距离的时候,我们就可以赋予它不同的AI行为,如下表所示:

  1. 近:攻击,防御,追踪,掩护,包围,等待,...
  2. 中:追踪,包围,等待,...
  3. 远:等待,...
一般来说,AI候选的行为越多,它决策所花费的时间也越多,根据这样的假设,我们就可以通过限制AI行为的方式,来起到提升效率的作用。上面说的是一种LOD的方式,还有一种实现方式是减少AI的决策频率,这也是我以前讨论过的AI中的懒惰问题,比如如下表:
 
  1. 近:攻击,防御,追踪,掩护,包围,等待,...(0.1秒决策一次)
  2. 中:攻击,防御,追踪,掩护,包围,等待,...(1秒决策一次)
  3. 远:攻击,防御,追踪,掩护,包围,等待,...(5秒决策一次)

我们可以根据需要来混合使用上面两种方式。说到这里,我想大家脑海中会有一个自己的代码实现框架,我也想了一种,可以用到我经常说的行为树的方式来实现,行为树最好的就是可以任意的添加行为分支,所以可以说,对于第一种的LOD实现是天生支持的,我们只要建立三个行为分支表示近,中,远,并且在这三个分支下,挂上不同的候选行为,这样,我们就建立了一棵带LOD优化功能的行为树,如下图:

 
Lod1
 
对于第二种LOD实现,我们可以创建一种新的控制节点(回忆一下控制节点的概念),可以称之为LazyNode,这是一个一元的节点,它的功能就是维护一个时钟,当时间一到就执行它的子节点。同样的,我们用LazyNode,也建立近,中,远三个行为分支,然后在下面挂上相关的行为子节点,如下图:
 
Lod1 (1)
可以看到,如果我们用行为树,就不需要用什么附加的模块来做LOD优化,而是用行为树强大的扩展能力把这些直接整合进了AI结构中,这种不破坏结构,从架构层面的优化方式,是我相当推崇的。
LOD是一种懒人化的优化方式,无论是概念还是实现都非常简单,当然,所有这些都是以不破坏游戏性为前提的,有时,我们有可能需要远处的AI做一些复杂的决策,比如,在即时战略游戏中,虽然我们AI离我们很远,但它确实需要做一些完整决策,在这种情况下,LOD可能并不是很适用,所以,AI中的一些问题没有一成不变的解决方案,实际情况,实际分析是相当之重要的 :) ,大家对AI优化有什么心得呢,欢迎大家留言讨论。
 
 
————————————————————————
作者:Finney
Blog:AI分享站(http://www.aisharing.com/)
Email:finneytang@gmail.com
本文欢迎转载和引用,请保留本说明并注明出处
————————————————————————
Read More

游戏AI在做决策的时候,最重要的参考依据就是当前游戏世界信息,这其实和人做判断的时候是一样的,我们在做出一个决定的时候,脑中会闪过很多我们已经收集的信息,包括所见,所听,直觉(基于以往的经验)等等。所以,我们如何去抽象游戏世界信息,并收集起来以供AI使用,也是非常值得我们去思考和探讨的问题。

当然,不同的AI决策,对于游戏世界的信息需求是完全不同的,不同的游戏,对于游戏世界的抽象方式也不完全相同,因此,关于游戏信息收集的实现是一种“游戏特定”(Game specific)的问题。说句题外话,正是由于AI中充满了很多“游戏特定”的问题,所以AI不像渲染,声音,网络等其他游戏模块,它很难做成一个“引擎”,不过也正是因为每个游戏的AI需求都不同,因此AI编程也充满了魅力和创造力 :)

虽然存在这样或者那样的不同,但就像我一开始分析的,无论是否存在一个单独的模块来收集并存储游戏世界信息,这确实是AI程序中必不可少的单元。这次我想和大家探讨一个我一直在考虑的想法,虽然在我做过的项目中还没有完全用到(零星的用到一点,没有抽象成单独的模块),不过作为一个思维笔记记下来,还是很有必要的。

假设我们写一个篮球游戏中控球队员的AI,如果我们不考虑复杂的战术配合,一般来说,控球队员要么带球突破,要么直接投篮,要么传球给会造成威胁的空位球员,考虑到篮球场上瞬息万变情况来,如果单纯的if-else,会很难罗列出全部的条件,所以我们可能会采用模糊AI的决策逻辑,比如分数系统,不过,由于今天我们讨论的是收集和存储游戏世界信息的问题,所以对于AI决策相关的东西,我们暂且不讨论。我们仅仅来看,在这个问题中,AI决策时候可能需要知道哪些游戏世界信息:

  1. 场上己方球员的分布
  2. 场上对方球员的分布
  3. 球场上哪里比较有威胁(靠近篮筐的地方)
  4. 球场上哪里比较不安全(比如有强力防守队员,或者防守队员人数很多)
  5. 场地的构成(三分线位置,三秒区)
  6. 球员的相关信息(比如球员能力,位置,当前行为等等)
  7. ……

如果把上面的信息分个类别的话,可以分成以下4种

  • 静态实体信息(比如5)
  • 静态抽象信息(比如3)
  • 动态实体信息(比如1,6)
  • 动态抽象信息(比如4)

静态和动态的概念比较好理解,“静态”就是值不随着游戏的进行而变化的信息,“动态”就是随着游戏的进行会一直改变的信息,像场地信息就是静态的,不会改变的,像场上对方球员分布就是属于动态信息,因为他们的位置是一直变动的。而我这边提到的“实体”信息,指的是“真是存在”的信息,“抽象”是指“自定义”的参考信息。像场地信息,就是实体信息,因为类似三分线位置都是实际存在的信息,但像球场上哪里有威胁,那就是我们根据需要,自己定义的信息了,可以不断的调整和修正。

我借鉴了3D渲染中“帧缓冲区”(Frame Buffer)的概念,想用一种类似的方式来存储游戏世界信息,因为我们看到上面我们需要收集的信息中,不管是静态还是动态,实体还是抽象,很多都是和游戏地图相关的(除了6),所以我们就可以用一种“图”的方式来存储信息,称之为“游戏信息图”(Game World Info Map)。

首先我们按需求将游戏地图栅格化,比10×10,当然,粒度的大小取决于对于精度和效率的平衡。每一个格子就相当于“帧缓冲区”中的像素,然后我们可以创建多个这样的“图”,和创建多个“帧缓冲区”一样。每个图都代表上述信息中的一项内容,图中的每个格子都根据信息的内容填入0.0 ~1.0的值。

例如,我们要建立一个“场地威胁图”,我们定义0表示完全没有危险,1表示薄雾浓云愁永昼威胁值最高,那我们就可以这张图的相应的格子中填入相应的值,而且因为这是静态信息,所以只需要在游戏开始时填入就可以了,当我们填完每一个格子的时候,我们就得到了这样一张“场地威胁图”。对于动态信息的情况,我们需要在每一帧(或者每几帧)对“图”中的信息做一次更新,比如“场地危险图”,就是这样的动态“信息图”,需要根据防守队员的情况来实时更新。这样当我们填完所有的“图”信息后,AI决策时就可以知道任意时刻,在地图上的任意点上的相关信息了。

小地图的情况(如上例)可以直接做栅格化,但对于地图比较大的情况,如果直接栅格化的话,更新起来性能太低,这种情况可以考虑采用层次化的图模型,先将地图分成大块的格子,在大的格子里再细分成小格子,当查看距离近的信息的,采用精细的格子信息,查看远处的时候,采用粗略的信息,这样就可以在效率上取得一些平衡。

用“图”来表示世界信息的另一个好处是,可以方便的将信息绘制出来(在地图上,或者在外部的调试工具中),而不用面对一大堆的数据,如果再将不同的值配以不同的颜色来显示的话,那将大大的降低AI调试的难度。

可以看到,其实“图”的概念,就是对于游戏世界信息中和地图有关的信息的抽象,像我前段时间提到的“势力图”(Influence Map),就是“信息图”的一种应用。“信息图”的想法并不是我的独创,其实可能大家或多或少以前在编写游戏AI的时候也用到过,但我觉得整理一下的话,可以作为一种比较通用的结构来提炼出来,在AI中加以运用。希望对大家有所帮助。

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

Read More