开启辅助访问
 找回密码
 注册帐号

扫一扫,访问微社区

教程分享

关注:620

当前位置:游戏蛮牛 技术专区 教程分享

查看: 2036|回复: 0

[基础知识] 行为树的设计与实现(一)

[复制链接]  [移动端链接]
抢楼 抢楼 本帖为抢楼帖,欢迎抢楼! 
8常驻蛮牛
9843/10000
排名
386
昨日变化
3

3421

主题

3691

帖子

9843

积分

Rank: 8Rank: 8

UID
1235
好友
168
蛮牛币
174741
威望
110
注册时间
2013-7-29
在线时间
432 小时
最后登录
2016-10-9

社区QQ达人游戏蛮牛QQ群会员蛮牛妹

发表于 2015-2-21 14:45:50 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?注册帐号

x
  查阅了一些行为树资料,目前最主要是参考了这篇文章,看完后感觉行为树实乃强大,绝对是替代状态机的不二之选。但从理论看起来很简单的行为树,真正着手起来却发现很多细节无从下手。

  总结起来,就是:

  1、行为树只是单纯的一棵决策树,还是决策+控制树。为了防止不必要的麻烦,我目前设计成单纯的决策树。

  2、什么时候执行行为树的问题,也就是行为树的Tick问题,是在条件变化的时候执行一次,还是只要对象激活,就在Update里面一直Tick。前者明显很节省开销,但那样设计的最终结果可能是最后陷入事件发送的泥潭中。那么一直Tick可能是最简单的办法,于是就引下面出新的问题。目前采用了一直Tick的办法。

  3、基本上可以明显节点有 Composite Node、Decorator Node、Condition Node、Action Node,但具体细节就很头疼。比如组合节点里的Sequence Node。这个节点是不是在每个Tick周期都从头迭代一次子节点,还是记录正在运行的子节点。每次都迭代子节点,就感觉开销有点大。记录运行节点就会出现条件冗余问题,具体后面再讨论。目前采用保存当前运行节点的办法。

  4、条件节点(Condition Node)的位置问题。看到很多设计都是条件节点在最后才进行判断,而实际上,如果把条件放在组合节点处,就可以有效短路判断,不再往下迭代。于是我就采用了这种方法。

  设计开始

  在Google Code上看到的某个行为树框架,用的是抽象类做节点。考虑到C#不能多继承,抽象类可能会导致某些时候会很棘手,所以还是用接口。虽然目前还未发现接口的好处。

  在进行抽象设计的时候,接口的纯粹性虽然看起来更加清晰,不过有时候遇到需要重复使用某些类函数的时候就挺麻烦,让人感觉有点不利于复用。

[AppleScript] 纯文本查看 复制代码
  public enum RunStatus

  {

  Completed,

  Failure,

  Running,

  }

  public interface IBehaviourTreeNode

  {

  RunStatus status { get; set; }

  string nodeName { get; set; }

  bool Enter(object input);

  bool Leave(object input);

  bool Tick(object input, object output);

  RenderableNode renderNode { get; set; }

  IBehaviourTreeNode parent { get; set; }

  IBehaviourTreeNode Clone();

  }

  /************************************************************************/

  /* 组合结点                                                             */

  /************************************************************************/

  public interface ICompositeNode : IBehaviourTreeNode

  {

  void AddNode(IBehaviourTreeNode node);

  void RemoveNode(IBehaviourTreeNode node);

  bool HasNode(IBehaviourTreeNode node);

  void AddCondition(IConditionNode node);

  void RemoveCondition(IConditionNode node);

  bool HasCondition(IConditionNode node);

  ArrayList nodeList { get; }

  ArrayList conditionList { get; }

  }

  /************************************************************************/

  /* 选择节点                                                             */

  /************************************************************************/

  public interface ISelectorNode : ICompositeNode

  {

  }

  /************************************************************************/

  /*顺序节点                                                              */

  /************************************************************************/

  public interface ISequenceNode : ICompositeNode

  {

  }

  /************************************************************************/

  /* 平行(并列)节点                                                             */

  /************************************************************************/

  public interface IParallelNode : ICompositeNode

  {

  }

  //////////////////////////////////////////////////////////////////////////

  /************************************************************************/

  /* 装饰结点                                                             */

  /************************************************************************/

  public interface IDecoratorNode : IBehaviourTreeNode

  {

  }

  /************************************************************************/

  /* 条件节点                                                             */

  /************************************************************************/

  public interface IConditionNode

  {

  string nodeName { get; set; }

  bool ExternalCondition();

  }

  /************************************************************************/

  /* 行为节点                                                             */

  /************************************************************************/

  public interface IActionNode : IBehaviourTreeNode

  {

  }

  public interface IBehaviourTree

  {

  }


  很多节点的接口都是空的,目前唯一的作用就是用于类型判断,很可能在最后也没有什么实际的作用,搞不好就是所谓的过度设计。如果最终确定没有用再删掉吧。

  接口里出现了一个渲染节点,目的是为了能够更方便的把这个节点和负责渲染的节点联系到一起,方便节点的可视化。

  如果只有接口,每次实现接口都要重复做很多工作,为了利用面向对象的复用特性,就来实现一些父类

[AppleScript] 纯文本查看 复制代码
  public class BaseNode

  {

  public BaseNode() { nodeName_ = this.GetType()。Name + “\n”; }

  protected RunStatus status_ = RunStatus.Completed;

  protected string nodeName_;

  protected RenderableNode renderNode_;

  protected IBehaviourTreeNode parent_;

  public virtual RunStatus status { get { return status_; } set { status_ = value; } }

  public virtual string nodeName { get { return nodeName_; } set { nodeName_ = value; } }

  public virtual RenderableNode renderNode { get { return renderNode_; } set { renderNode_ = value; } }

  public virtual IBehaviourTreeNode parent { get { return parent_; } set { parent_ = value; } }

  public virtual IBehaviourTreeNode Clone() {

  var clone = new BaseNode();

  clone.status_ = status_;

  clone.nodeName_ = nodeName_;

  clone.renderNode_ = renderNode_;

  clone.parent_ = parent_;

  return clone as IBehaviourTreeNode;

  }

  }

  public class BaseActionNode : IActionNode

  {

  public BaseActionNode() { nodeName_ = this.GetType()。Name + “\n”; }

  protected RunStatus status_ = RunStatus.Completed;

  protected string nodeName_;

  protected RenderableNode renderNode_;

  protected IBehaviourTreeNode parent_;

  public virtual RunStatus status { get { return status_; } set { status_ = value; } }

  public virtual string nodeName { get { return nodeName_; } set { nodeName_ = value; } }

  public virtual RenderableNode renderNode { get { return renderNode_; } set { renderNode_ = value; } }

  public virtual IBehaviourTreeNode parent { get { return parent_; } set { parent_ = value; } }

  public virtual IBehaviourTreeNode Clone()

  {

  var clone = new BaseActionNode();

  clone.status_ = status_;

  clone.nodeName_ = nodeName_;

  clone.renderNode_ = renderNode_;

  clone.parent_ = parent_;

  return clone as IBehaviourTreeNode;

  }

  public virtual bool Enter(object input)

  {

  status_ = RunStatus.Running;

  return true;

  }

  public virtual bool Leave(object input)

  {

  status_ = RunStatus.Completed;

  return true;

  }

  public virtual bool Tick(object input, object output)

  {

  return true;

  }

  }

  public class BaseCondictionNode {

  protected string nodeName_;

  public virtual string nodeName { get { return nodeName_; } set { nodeName_ = value; } }

  public BaseCondictionNode() { nodeName_ = this.GetType()。Name+“\n”; }

  public delegate bool ExternalFunc();

  protected ExternalFunc externalFunc;

  public static ExternalFunc GetExternalFunc(BaseCondictionNode node) {

  return node.externalFunc;

  }

  }

  public class Precondition : BaseCondictionNode, IConditionNode{

  public Precondition(ExternalFunc func) { externalFunc = func; }

  public Precondition(BaseCondictionNode pre) { externalFunc = BaseCondictionNode.GetExternalFunc(pre); }

  public bool ExternalCondition()

  {

  if (externalFunc != null) return externalFunc();

  else return false;

  }

  }

  public class PreconditionNOT : BaseCondictionNode, IConditionNode

  {

  public PreconditionNOT(ExternalFunc func) { externalFunc = func; }

  public PreconditionNOT(BaseCondictionNode pre) { externalFunc = BaseCondictionNode.GetExternalFunc(pre); }

  public bool ExternalCondition()

  {

  if (externalFunc != null) return !externalFunc();

  else return false;

  }

  }

  public class BaseCompositeNode : BaseNode{

  protected ArrayList nodeList_ = new ArrayList();

  protected ArrayList conditionList_ = new ArrayList();

  protected int runningNodeIndex = 0;

  protected bool CheckNodeAndCondition() {

  if (nodeList_.Count == 0)

  {

  status_ = RunStatus.Failure;

  Debug.Log(“SequenceNode has no node!”);

  return false;

  }

  return CheckCondition();

  }

  protected bool CheckCondition() {

  foreach (var node in conditionList_)

  {

  var condiction = node as IConditionNode;

  if (!condiction.ExternalCondition())

  return false;

  }

  return true;

  }

  public virtual void AddNode(IBehaviourTreeNode node) { node.parent = (IBehaviourTreeNode)this; nodeList_.Add(node); }

  public virtual void RemoveNode(IBehaviourTreeNode node) { nodeList_.Remove(node); }

  public virtual bool HasNode(IBehaviourTreeNode node) { return nodeList_.Contains(node); }

  public virtual void AddCondition(IConditionNode node) { conditionList_.Add(node); }

  public virtual void RemoveCondition(IConditionNode node) { conditionList_.Remove(node); }

  public virtual bool HasCondition(IConditionNode node) { return conditionList_.Contains(node); }

  public virtual ArrayList nodeList { get { return nodeList_; } }

  public virtual ArrayList conditionList { get { return conditionList_; } }

  public override IBehaviourTreeNode Clone()

  {

  var clone = base.Clone() as BaseCompositeNode;

  clone.nodeList_.AddRange(nodeList_);

  clone.conditionList_.AddRange(conditionList_);

  clone.runningNodeIndex = runningNodeIndex;

  return clone as IBehaviourTreeNode;

  }

  }


  然后实现具体的节点,先是序列节点

[AppleScript] 纯文本查看 复制代码
  public class SequenceNode : BaseCompositeNode, ISequenceNode

  {

  public SequenceNode(bool canContinue_ = false) { canContinue = canContinue_; }

  public bool canContinue = false;

  public bool Enter(object input)

  {

  var checkOk = CheckNodeAndCondition();

  if (!checkOk) return false;

  var runningNode = nodeList_[runningNodeIndex] as IBehaviourTreeNode;

  checkOk = runningNode.Enter(input);

  if (!checkOk) return false;

  status_ = RunStatus.Running;

  return true;

  }

  public bool Leave(object input)

  {

  if (nodeList_.Count == 0)

  {

  status_ = RunStatus.Failure;

  Debug.Log(“SequenceNode has no node!”);

  return false;

  }

  var runningNode = nodeList_[runningNodeIndex] as IBehaviourTreeNode;

  runningNode.Leave(input);

  if (canContinue)

  {

  runningNodeIndex++;

  runningNodeIndex %= nodeList_.Count;

  }

  status_ = RunStatus.Completed;

  return true;

  }

  public bool Tick(object input, object output)

  {

  if (status_ == RunStatus.Failure) return false;

  if (status_ == RunStatus.Completed) return true;

  var runningNode = nodeList_[runningNodeIndex] as IBehaviourTreeNode;

  var checkOk = CheckCondition();

  if (!checkOk)

  {

  return false;

  }

  switch (runningNode.status)

  {

  case RunStatus.Running:

  if (!runningNode.Tick(input, output))

  {

  runningNode.Leave(input);

  return false;

  }

  break;

  default:

  runningNode.Leave(input);

  runningNodeIndex++;

  if(runningNodeIndex >= nodeList_.Count)break;

  var nextNode = nodeList_[runningNodeIndex] as IBehaviourTreeNode;

  var check = nextNode.Enter(input);

  if (!check) return false;

  break;

  }

  return true;

  }

  public override IBehaviourTreeNode Clone()

  {

  var clone = base.Clone() as SequenceNode;

  clone.canContinue = canContinue;

  return clone;

  }

  }


  这就是序列节点的设计,但是明显看起来很不爽,里面还出现了一个别扭的变量canContinue 。为什么会出现这个?因为序列节点的特点就是遇到一个子节点FALSE,就会停止并返回FALSE,但是这里我想用序列节点来做根节点,如果是根节点遇到这种情况,那么就不会执行下一个节点,而我看了很多种对于几大节点的描述,似乎都没提到这个。很多都用序列节点做根节点,有些就直接说是根节点。那么要么根节点另外实现,要么改一下序列节点。因为如果序列节点是非根节点的情况下,如果不是每次都从头开始,似乎又会引来新的问题,虽然目前还没想到会出什么问题。不过最后实现执行起来之后发现,用选择节点其实是一样的。所以目前这样的设计,可能是有根本上的问题。希望哪位大神可以指点一下。

  然后是选择节点,根据了所有FALSE才返回FALSE的特点设计了

[AppleScript] 纯文本查看 复制代码
  public class SelectorNode : BaseCompositeNode, ISelectorNode

  {

  public bool Enter(object input)

  {

  var checkOk = CheckNodeAndCondition();

  if (!checkOk) return false;

  do

  {

  var runningNode = nodeList_[runningNodeIndex] as IBehaviourTreeNode;

  checkOk = runningNode.Enter(input);

  if (checkOk) break;

  runningNodeIndex++;

  if (runningNodeIndex >= nodeList_.Count) return false;

  } while (!checkOk);

  status_ = RunStatus.Running;

  return true;

  }

  public bool Leave(object input)

  {

  var runningNode = nodeList_[runningNodeIndex] as IBehaviourTreeNode;

  runningNode.Leave(input);

  runningNodeIndex = 0;

  status_ = RunStatus.Completed;

  return true;

  }

  public bool Tick(object input, object output)

  {

  if (status_ == RunStatus.Failure) return false;

  if (status_ == RunStatus.Completed) return true;

  var checkOk1 = CheckCondition();

  if (!checkOk1) return false;

  var runningNode = nodeList_[runningNodeIndex] as IBehaviourTreeNode;

  switch (runningNode.status)

  {

  case RunStatus.Running:

  if (!runningNode.Tick(input, output))

  {

  runningNode.Leave(input);

  return false;

  }

  break;

  default:

  runningNode.Leave(input);

  runningNodeIndex++;

  if (runningNodeIndex >= nodeList_.Count) return false;

  bool checkOk = false;

  do

  {

  var nextNode = nodeList_[runningNodeIndex] as IBehaviourTreeNode;

  checkOk = nextNode.Enter(input);

  if (checkOk) break;

  runningNodeIndex++;

  if (runningNodeIndex >= nodeList_.Count) return false;

  } while (!checkOk);

  break;

  }

  return true;

  }

  }


  目前对于我的简单DEMO,组合节点只需要这两个就够了,实际上只需要选择节点、条件节点、动作节点就够了。所以说设计是不完全的,虽然能够实现目标需求,但是实际工作量仍挺大,具体接下来会说明。

评分

参与人数 1鲜花 +1 收起 理由
微末之人 + 1

查看全部评分


我是一朵内心长满小碎花的女汉子!
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册帐号

本版积分规则

快速回复 返回顶部 返回列表