首页 > 代码库 > 行为树的设计与实现
行为树的设计与实现
原地址:http://blog.csdn.net/luyuncsd123/article/details/18351137
查阅了一些行为树资料,目前最主要是参考了这篇文章,看完后感觉行为树实乃强大,绝对是替代状态机的不二之选。但从理论看起来很简单的行为树,真正着手起来却发现很多细节无从下手。
总结起来,就是:
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#不能多继承,抽象类可能会导致某些时候会很棘手,所以还是用接口。虽然目前还未发现接口的好处。
在进行抽象设计的时候,接口的纯粹性虽然看起来更加清晰,不过有时候遇到需要重复使用某些类函数的时候就挺麻烦,让人感觉有点不利于复用。
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 { }
很多节点的接口都是空的,目前唯一的作用就是用于类型判断,很可能在最后也没有什么实际的作用,搞不好就是所谓的过度设计。如果最终确定没有用再删掉吧。
接口里出现了一个渲染节点,目的是为了能够更方便的把这个节点和负责渲染的节点联系到一起,方便节点的可视化。
如果只有接口,每次实现接口都要重复做很多工作,为了利用面向对象的复用特性,就来实现一些父类
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; } }
然后实现具体的节点,先是序列节点
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的特点设计了
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,组合节点只需要这两个就够了,实际上只需要选择节点、条件节点、动作节点就够了。所以说设计是不完全的,虽然能够实现目标需求,但是实际工作量仍挺大,具体接下来会说明。
行为节点
先放一些渲染节点的代码。实际上我基本上是第一次接触自己去渲染一种数据结构,看完网上的大牛们随随便便就能写出个数据结构的示意图,不得不佩服。我一时半会没想出怎么渲染出树状结构,于是就简单的把树按层分组,一层一层渲染,缺点就是不能很好的表现树的样子,父子关系不能很好的表示。这里放出来希望能抛砖引玉。我以后可能会去完事它,但是现在首先是要搞清楚行为树。实现这个完全是为了看看节点是否正确放置,以方便调试。
public class RenderableNode { public RenderableNode parent; public IBehaviourTreeNode targetNode; public Rect posRect = new Rect(); public string name; public int layer; public RunStatus staus; public override string ToString() { return name + "\n" + staus.ToString(); } public virtual void Render() { bool running = staus == RunStatus.Running; var rect = posRect; rect.y -= (posRect.height / 2); var oldColor = GUI.color; if (running) { GUI.color = Color.green; } GUI.Box(rect, ToString()); GUI.color = oldColor; if (parent == null && targetNode != null && targetNode.parent!=null) { parent = targetNode.parent.renderNode; } if (parent != null) { Vector2 parentPos = new Vector2(); parentPos.x = parent.posRect.x + parent.posRect.width; parentPos.y = parent.posRect.y; GUIHelper.DrawLine(new Vector2(rect.x, rect.y + rect.height / 2), parentPos, running?Color.green:Color.yellow); } } } public class RenderableCondictionNode : RenderableNode { public IConditionNode targetCondictionNode; public override string ToString() { parent = null; return name; } public override void Render() { var rect = posRect; rect.y -= (posRect.height / 2); var oldColor = GUI.color; if (targetCondictionNode.ExternalCondition()) GUI.color = Color.green; else GUI.color = Color.blue; GUI.Box(rect, ToString()); GUI.color = oldColor; } } public class EmptyNode : RenderableNode { public override void Render() { } } public class NodeBox { public Rect posRect = new Rect(); public List<RenderableNode> nodeList = new List<RenderableNode>(); public void AddNode(RenderableNode node) { nodeList.Add(node); } public void Render() { posRect.y = Screen.height / 2; Rect rect = new Rect(); foreach (var node in nodeList) { var n = node; rect.height += (n.posRect.height + 1); rect.width = n.posRect.width + 10; } rect.height += 10; rect.x = posRect.x - rect.width / 2; rect.y = posRect.y - rect.height / 2; //GUI.Box(rect, ""); posRect.width = rect.width; posRect.height = rect.height; float height = 0; for (var i = 0; i < nodeList.Count; i++) { var n = nodeList[i]; n.posRect.y = rect.y + height + n.posRect.height / 2 + 5; n.posRect.x = rect.x + 5; n.Render(); height += n.posRect.height + 1; } } }
放一张渲染出来的效果
虽然每一组都只是简单的居中,不过效果看起来还可以接受
然后从图中就可以看到问题了。所有正条件,都会有一个反条件,不这么做就无法在条件改变时,让当前节点返回FALSE,从而让行为树去寻找其他节点。而如果用状态机来做的话,条件肯定只用判断一次,比如
if(run){ Run(); } else{ Walk(); }
那么可能就回到最初的组合节点的设计了,组合节点就不得不每次都扫描条件。其实本质上我是在担心开销问题,因为变成节点后,就不在是if else那么简单,而是变成了函数调用的开销。简单的AI还好,如果大量复杂的AI,每次对整棵树进行扫描估计够呛。但是目前的设计,条件节点就会非常多,条件不完备就会出现BUG,似乎也不是非常好的情况。
最后放出一些细节
class PatrolAction : BaseActionNode { public PatrolAction() { nodeName_ += "巡逻行为"; } public override bool Tick(object input_, object output_) { // var input = input_ as WarriorInputData; var output = output_ as WarriorOutPutData; output.action = WarriorActon.ePatrol; return true; } } class RunAwayAction : BaseActionNode { public RunAwayAction() { nodeName_ += "逃跑行为"; } public override bool Tick(object input_, object output_) { // var input = input_ as WarriorInputData; var output = output_ as WarriorOutPutData; output.action = WarriorActon.eRunAway; return true; } } class AttackAction : BaseActionNode { public AttackAction() { nodeName_ += "攻击行为"; } public override bool Tick(object input_, object output_) { // var input = input_ as WarriorInputData; var output = output_ as WarriorOutPutData; output.action = WarriorActon.eAttack; return true; } } class CrazyAttackAction : BaseActionNode { public CrazyAttackAction() { nodeName_ += "疯狂攻击行为"; } public override bool Tick(object input_, object output_) { // var input = input_ as WarriorInputData; var output = output_ as WarriorOutPutData; output.action = WarriorActon.eCrazyAttack; return true; } } class AlertAction : BaseActionNode { public AlertAction() { nodeName_ += "警戒行为"; } public override bool Tick(object input_, object output_) { // var input = input_ as WarriorInputData; var output = output_ as WarriorOutPutData; output.action = WarriorActon.eAlert; return true; } } [csharp] view plaincopy private ICompositeNode rootNode = new SelectorNode(); private WarriorInputData inputData = http://www.mamicode.com/new WarriorInputData(); private WarriorOutPutData outputData = http://www.mamicode.com/new WarriorOutPutData(); // Use this for initialization public void Start() { inputData.attribute = GetComponent<CharacterAttribute>(); rootNode.nodeName += "根"; //条件 var hasNoTarget = new PreconditionNOT(() => { return inputData.attribute.hasTarget; }); hasNoTarget.nodeName = "无目标"; var hasTarget = new Precondition(hasNoTarget); hasTarget.nodeName = "发现目标"; var isAnger = new Precondition(() => { return inputData.attribute.isAnger; }); isAnger.nodeName = "愤怒状态"; var isNotAnger = new PreconditionNOT(isAnger); isNotAnger.nodeName = "非愤怒状态"; var HPLessThan500 = new Precondition(() => { return inputData.attribute.health < 500; }); HPLessThan500.nodeName = "血少于500"; var HPMoreThan500 = new PreconditionNOT(HPLessThan500); HPMoreThan500.nodeName = "血大于500"; var isAlert = new Precondition(() => { return inputData.attribute.isAlert; }); isAlert.nodeName = "警戒"; var isNotAlert = new PreconditionNOT(isAlert); isNotAlert.nodeName = "非警戒"; var patrolNode = new SequenceNode(); patrolNode.nodeName += "巡逻"; patrolNode.AddCondition(hasNoTarget); patrolNode.AddCondition(isNotAlert); patrolNode.AddNode(new PatrolAction()); var alert = new SequenceNode(); alert.nodeName += "警戒"; alert.AddCondition(hasNoTarget); alert.AddCondition(isAlert); alert.AddNode(new AlertAction()); var runaway = new SequenceNode(); runaway.nodeName += "逃跑"; runaway.AddCondition(hasTarget); runaway.AddCondition(HPLessThan500); runaway.AddNode(new RunAwayAction()); var attack = new SelectorNode(); attack.nodeName += "攻击"; attack.AddCondition(hasTarget); attack.AddCondition(HPMoreThan500); var attackCrazy = new SequenceNode(); attackCrazy.nodeName += "疯狂攻击"; attackCrazy.AddCondition(isAnger); attackCrazy.AddNode(new CrazyAttackAction()); attack.AddNode(attackCrazy); var attackNormal = new SequenceNode(); attackNormal.nodeName += "普通攻击"; attackNormal.AddCondition(isNotAnger); attackNormal.AddNode(new AttackAction()); attack.AddNode(attackNormal); rootNode.AddNode(patrolNode); rootNode.AddNode(alert); rootNode.AddNode(runaway); rootNode.AddNode(attack); var ret = rootNode.Enter(inputData); if (!ret) { Debug.Log("无可执行节点!"); } } // Update is called once per frame void Update () { var ret = rootNode.Tick(inputData, outputData); if (!ret) rootNode.Leave(inputData); if (rootNode.status == RunStatus.Completed) { ret = rootNode.Enter(inputData); if (!ret) rootNode.Leave(inputData); } else if (rootNode.status == RunStatus.Failure) { Debug.Log("BT Failed"); enabled = false; } if (outputData.action != inputData.action) { OnActionChange(outputData.action, inputData.action); inputData.action = outputData.action; } } void OnActionChange(WarriorActon action, WarriorActon lastAction) { // print("OnActionChange "+action+" last:"+lastAction); switch (lastAction) { case WarriorActon.ePatrol: GetComponent<WarriorPatrol>().enabled = false; break; case WarriorActon.eAttack: case WarriorActon.eCrazyAttack: GetComponent<WarriorAttack>().enabled = false; break; case WarriorActon.eRunAway: GetComponent<WarriorRunAway>().enabled = false; break; case WarriorActon.eAlert: GetComponent<WarriorAlert>().enabled = false; break; } switch (action) { case WarriorActon.ePatrol: GetComponent<WarriorPatrol>().enabled = true; break; case WarriorActon.eAttack: var attack = GetComponent<WarriorAttack>(); attack.revenge = false; attack.enabled = true; break; case WarriorActon.eCrazyAttack: var crazyAttack = GetComponent<WarriorAttack>(); crazyAttack.revenge = true; crazyAttack.enabled = true; break; case WarriorActon.eRunAway: GetComponent<WarriorRunAway>().enabled = true; break; case WarriorActon.eAlert: GetComponent<WarriorAlert>().enabled = true; break; case WarriorActon.eIdle: GetComponent<WarriorPatrol>().enabled = false; GetComponent<WarriorAttack>().enabled = false; GetComponent<WarriorRunAway>().enabled = false; break; } }