NEUROMANTIC

自分でC/C++/UE4/Graphics/ゲームなどをやったことをメモするブログ

超簡単なBehaviour Treeを実装してみた

C++ Algorithm

Finite-State Machineとは（Behaviour Treeの以前に。。。）

en.wikipedia.org

https://cdn.tutsplus.com/gamedev/uploads/2013/10/fsm_enemy_brain.png

  • Finite-State Machineは人工知能または条件による行動の分岐を実装する基本的な方法の一つである。
  • 人工知能の各行動をモジュール化させたので、ある程度に柔軟さは持っているが、遷移条件や状態が多くなると設定がやたらに複雑になる可能性がある。
    • 例えば、IDLE MOVE ATTACKという状態ノードがある状態で、さらなるHYPER-ATTACKというノードを追加する時、既存の３つのノードに新しいノードに繊維する条件などを追加しなければならなくなる。（しない場合もあるけど、最悪の場合を考慮）

Behaviour Treeとは

www.gamasutra.com

https://outforafight.files.wordpress.com/2014/07/selector1.png

  • Behaviour TreeはFSMとは違って、ツリーの構造を持っていて、左から右へとトラバーサルをしながら各ノードに合わせて行動を実行をする。
    • FSMの状態遷移の条件は各ノードになる。
  • BTの基本的なノードは、SelectorとSequenceがある。（これらをCompositeノードとする）
    • Selectorノードは子ノードの中に一つでもtrueを返すと、残りの子ノードの実行を中断して親ノードに戻る。
    • Sequenceノードは子ノードを全部順番に実行し、もしfalseを返されるまで子ノードを巡回する。
  • Decoratorという種類のノードもあるが、これは一つの子ノードを持って、子ノードのリターン値を加工して親に返す役割をする。
  • BTの根ノードはSequenceノードになる。

下準備

std::string sSpace = "";
struct DSpaceRAII final 
{
  DSpaceRAII() { sSpace += "  "; }
  ~DSpaceRAII() { sSpace = sSpace.substr(0, sSpace.length() - 2); }
};
#define INDENT_SPACE() auto s##__LINE__ = DSpaceRAII{}

各ノードを巡回する時に、std::printfを使用してメッセージを出力します。 その時に、ツリー構造の各レベルにある各ノードのレベルが何なのかを知るため、接頭にレベルごとにスペース文字列を付けます。 下のコードを見たらINDENT_SPACE()が各ノードに付けられていることがわかるでしょう。 自動的にスペースを付けて、そしてスタックが解除されたらスペースを外します。

/// @brief Return random percentage value from 0.0f to 100.0f
float GetRandomPercentage()
{
  static bool isInitialized = false;
  static std::random_device dev{};
  static std::mt19937 rnd{dev()};
  static std::uniform_real_distribution<float> dis{0.0f, 100.0f};

  if (isInitialized == false)
  {
    rnd.seed(static_cast<unsigned>(
      std::chrono::steady_clock::now().time_since_epoch().count()));
    isInitialized = true;
  }
  return dis(rnd);
}

各ノードの分岐によるtrueまたはfalse値の返しを実装するために、0から100までの確率を返す関数を実装します。 返す値に対しての確率は全部同じです。std::uniform_real_distribution<>

class IBehaviourNode
{
public:
  virtual ~IBehaviourNode() = 0;
  virtual bool Invoke() = 0;
};
inline IBehaviourNode::~IBehaviourNode() = default;

class ACompositeNode : public IBehaviourNode
{
public:
  virtual ~ACompositeNode() = 0;

  template <typename TType, typename... TArgs>
  TType& AddChild(TArgs&&... args)
  {
    static_assert(std::is_base_of_v<IBehaviourNode, TType>);
    auto& ref = this->mChildren.emplace_back(std::make_unique<TType>(std::forward<TArgs>(args)...));
    assert(ref != nullptr);

    return static_cast<TType&>(*ref);
  }

  const auto& GetChildren() { return this->mChildren; }

private:
  std::vector<std::unique_ptr<IBehaviourNode>> mChildren; 
};
inline ACompositeNode::~ACompositeNode() = default;
  • ACompositeNodeはSequenceとSelectorを実装するための抽象クラスです。子ノード（IBehaviourNodeを継承したタイプ）を持つことができます。
  • 一般のBTノードはIBehaviourNodeを継承して実装します。
class FSelector final : public ACompositeNode
{
public:
  virtual ~FSelector() = default;
  bool Invoke() override final
  {
    INDENT_SPACE();
    std::printf("%sFSelector Invoked!\n", sSpace.c_str()); 
    for (auto& node : this->GetChildren()) { if (node->Invoke() == true) { return true; } }
    return false;
  }
};

class FSequence : public ACompositeNode
{
public:
  virtual ~FSequence() = default;
  bool Invoke() override 
  {
    INDENT_SPACE();
    std::printf("%sFSequence Invoked!\n", sSpace.c_str()); 
    for (auto& node : this->GetChildren()) { if (node->Invoke() == false) { return false; } }
    return true;
  }
};

class FRoot : public FSequence
{
public:
  virtual ~FRoot() = default;
  bool Invoke() override final
  {
    std::printf("%sFRoot Invoked!\n", sSpace.c_str()); 
    for (auto& node : this->GetChildren()) { if (node->Invoke() == false) { return false; } }
    return true;
  }
};

SequenceとSelector、そして根ノードRootを実装しました。根ノードはSequenceを継承してます。

class FCondition final : public IBehaviourNode
{
public:
  virtual ~FCondition() = default;
  bool Invoke() override final
  {
    INDENT_SPACE();
    if (GetRandomPercentage() < 50.f)
    {
      std::printf("%sFCondition Invoked! => true\n", sSpace.c_str()); 
      return true;
    }

    std::printf("%sFCondition Invoked! => false\n", sSpace.c_str()); 
    return false;
  }
};

class FAction final : public IBehaviourNode
{
public:
  virtual ~FAction() = default;
  bool Invoke() override final 
  { 
    INDENT_SPACE();
    std::printf("%sFActor Invoked! => true\n", sSpace.c_str()); 
    return true; 
  }
};

class FMove final : public IBehaviourNode
{
public:
  virtual ~FMove() = default;
  bool Invoke() override final 
  { 
    INDENT_SPACE();
    std::printf("%sFMoved Invoked! => true\n", sSpace.c_str()); 
    return true; 
  }
};

class FCondition2 final : public IBehaviourNode
{
public:
  virtual ~FCondition2() = default;
  bool Invoke() override final
  {
    INDENT_SPACE();
    if (GetRandomPercentage() < 50.f) 
    { 
      std::printf("%sFCondition2 Invoked! => true\n", sSpace.c_str()); 
      return true; 
    }

    std::printf("%sFCondition2 Invoked! => false\n", sSpace.c_str()); 
    return false;
  }
};

一般ノードを実装しました。そして下のコードでBehaviour Treeを組みます。

int main()
{
  auto root = std::make_unique<FRoot>();
    auto& selector = root->AddChild<FSelector>();
      auto& seq0 = selector.AddChild<FSequence>();
        seq0.AddChild<FCondition>();
        seq0.AddChild<FAction>();
      auto& seq1 = selector.AddChild<FSequence>();
        seq1.AddChild<FMove>();
    root->AddChild<FCondition2>();

  for (int i = 0; i < 10; ++i)
  {
    const auto result = root->Invoke();
    std::printf("[%2d] Result : %s\n\n", i, result ? "true" : "false");
  }

  return 0;
}

実行すると、以下の様にBehaviour Treeが実行します。 各ノードはそれぞれのロジックを実行して、trueかfalseを親ノードに返すと、親ノードは親ノードの種類によって分岐をしてくれます。

FRoot Invoked!
  FSelector Invoked!
    FSequence Invoked!
      FCondition Invoked! => true
      FActor Invoked! => true
  FCondition2 Invoked! => true
[ 0] Result : true

FRoot Invoked!
  FSelector Invoked!
    FSequence Invoked!
      FCondition Invoked! => true
      FActor Invoked! => true
  FCondition2 Invoked! => false
[ 1] Result : false

FRoot Invoked!
  FSelector Invoked!
    FSequence Invoked!
      FCondition Invoked! => true
      FActor Invoked! => true
  FCondition2 Invoked! => true
[ 2] Result : true

FRoot Invoked!
  FSelector Invoked!
    FSequence Invoked!
      FCondition Invoked! => false
    FSequence Invoked!
      FMoved Invoked! => true
  FCondition2 Invoked! => false
[ 3] Result : false
  • FSMとは違って、BTは条件チェックが自分のノードとそしてノードに付けられている1階層下の子ノードだけとのことになるので、複雑にならなく、拡張が自由である。
  • そして根ノードがSequenceであるため、他のBTに子ノードとして付けても構わない。

ということで、超簡単なBTを実装してみました。実際に実装してみたら思ってたのより簡単でした。

UE4のBTとの違い

  • UE4で実装しているBTは、基本的なBTとはちょっと違う。
    • BlackBoard（ブラックボード）という、BTで変数の値を共有するために実装されたコンテナがある。
    • Service（サービス）という、コンポジットノード下の子ノードが実行している間に指定したフレームごとに別の処理を行うことが出来る機能がある。主にBlackBoardの値を書き換える時に使われるそうだ。
    • Decoratorはコンポジットまたは一般ノードにつけられるし、そしてDecorator自体が条件式を持ち、結果によって子ノードを実行するか判断もできる。
    • Simple Parallelという、サブツリーと共に並列にノードのロジックを実行できるようにしたコンポジットノードもある。この並列ノードの終わり方もさまざま。

自分で実装してみたいんですけど長道になりそうですねー

参照

kindtis.tistory.com

e-words.jp

基礎から学ぶ！UE4でC++を交えたAI開発、興味ないですか？ - Speaker Deck