C++で簡単なBehaviorTreeを実装してみた(前編)

>5/14追記
>下記のスペルミスを修正しました。
> Behaviour → Behavior

# 目次
- [概要](#概要)
- [BehaviorTreeとは](#behaviortreeとは)
- [実装](#実装)
	- [ノードの種類](#ノードの種類)
	- [ノードの状態](#ノードの状態)
	- [ブラックボード](#ブラックボード)
- [クラス](#クラス)
    - [インターフェース](#インターフェース)
	- [基底クラス](#基底クラス)
	- [派生クラス](#派生クラス)
	- [Compositeノードの基底クラス](#compositeノードの基底クラス)
	- [Branchノードの基底クラス](#branchノードの基底クラス)
	- [Decoratorノードの基底クラス](#decoratorノードの基底クラス)
	- [Leafノードの基底クラス](#leafノードの基底クラス)
	- [ブラックボード](#ブラックボード-1)
	- [ツリー組み立て](#ツリー組み立て)
- [まとめ](#まとめ)
- [あとがき](#あとがき)


# 概要
BehaviorTree（ビヘイビアツリー）は近年ゲームAIの分野で広く使われており、現在では多くのゲームエンジンに標準搭載されています。  
本記事では、各種アルゴリズムの学習も兼ねてゼロから自前実装した際に得た知見を共有します。
>※本記事で掲載しているコードは学習目的で作成したものであるため、実運用の際は随時調整されることを推奨いたします。

# BehaviorTreeとは
主にNPCや敵アクターの行動制御に用いられる設計パターンです。
行動パターンをツリー構造で階層的に表現し、ルートから順にノードを評価しながら実行します。
また、同じくゲームAIの分野で広く使用されているStateMachine(ステートマシン)と異なり、以下の特徴があります。

- シンプルなツリー上で行動を制御できる
- 各種ノードは特定のアクターに依存しないため、再利用性が高い
- 非循環性のため、バグが発生しにくい
- 拡張性が高い

ただし、大まかな状態を保持することは苦手なため、プロジェクトによっては上位層はステートベース、下位層はビヘイビアベースで行動を制御する手法がとられている場合もあります。

# 実装
![スクリーンショット 2025-05-13 091031.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/4081223/a9231dfb-5460-4d98-a0b5-9d876ba726e5.png)
![BehaviourTreeTest.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/4081223/64210814-4a41-4a6a-af20-cc1cc208f0ac.gif)
自機が緑、敵機が赤です。
自機が一定距離離れていると追跡し、近づくと円形攻撃を一定間隔で繰り返す様子が確認できます。

## ノードの種類
今回実装したノードは大きく4種類に分かれています。

| 種類 | 役割 |
| --- | --- |
| Composite | 子ノードを複数持つ（Sequence / Selector など） |
| Branch | 条件に応じて True/False いずれかの子を実行 |
| Decorator | 子ノードを 1 つだけ持ち、結果を加工して返す |
| Leaf | 末端ノード。実際のアクションを実装 |

## ノードの状態
各ノードは下記の4つの状態を取ります。

| 列挙値 | 意味 |
| --- | --- |
| `Idle` | 待機中 |
| `Running` | 実行中 |
| `Success` | 成功 |
| `Fail` | 失敗 |

CompositeノードやDecoratorノードは子ノードの状態を見て処理を切り替えています。

## ブラックボード
ノードは直接アクターへの参照を持たず、BlackBoard経由で必要な情報（座標など）を取得します。
各アクターは必要に応じてツリーに参照してほしい情報をBlackBoardに書き込む仕組みとなっています。

# クラス
![スクリーンショット 2025-05-01 201756.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/4081223/ca9005c3-df01-4fbf-b74f-9235533c8b54.png)

※本記事ではコード省略のため、実装はすべてヘッダーファイルにまとめています。
手元で動作確認される際は、必要に応じて処理をcppファイルに分離することをお勧めします。
## インターフェース
```cpp:INode.h
class INode {
public:
	// 仮想デストラクタ
	virtual ~INode() = default;
	// 初期化
	virtual void init() = 0;
	// 更新
	virtual void tick() = 0;
	// 後処理
	virtual void finalize() = 0;
	// ノードの状態を取得
	virtual NodeResult get_node_result() const = 0;
};
```
## 基底クラス
```cpp:NodeBase.h
class NodeBase : public INode {
protected:
	explicit NodeBase(BlackBoard* black_board) : mpBlackBoard{ black_board } {}
	virtual ~NodeBase() = default;

	virtual void init() override { mNodeResult = NodeResult::Running; }

	virtual void tick() override {}

	virtual void finalize() override {}

	virtual NodeResult get_node_result() const { return mNodeResult; }

	NodeResult mNodeResult = NodeResult::Idle; // ノードの状態
	BlackBoard* mpBlackBoard = nullptr; // ブラックボード
};
```
以降のノードは全て、この基底クラスNodeBaseを継承します。

## 派生クラス
## Compositeノードの基底クラス
```cpp:CompositeNodeBase.h
class CompositeNodeBase : public NodeBase {
public:
	explicit CompositeNodeBase(BlackBoard* black_board) : NodeBase(black_board) {};

	virtual ~CompositeNodeBase()
	{
	  for (auto node : mChildNodes) 
	  {
		  delete node;
	  }
	  mChildNodes.clear();
	}

	virtual void init() override
	{
		NodeBase::init();
	  mRunningNodeIndex = 0;

	  // 最初のノードを初期化
	  if (mChildNodes.size() > 0) 
	  {
		  mChildNodes[mRunningNodeIndex]->init();
	  }
	  else 
	  {
		  mNodeResult = NodeResult::Fail;
	  }
	}
	
	virtual void finalize() override;
	
	void add_node(INode* node){ mChildNodes.push_back(node); }

protected:
	void node_increment()
	{
		// 現在のノードの後始末
	  mChildNodes[mRunningNodeIndex]->finalize();

	  // インデックスを進める
	  mRunningNodeIndex = get_next_index();

	  // もしすべての子ノードを試しても失敗したら
	  if (mRunningNodeIndex > mChildNodes.size() - 1) 
	  {
		  mNodeResult = NodeResult::Fail;
		  finalize();
		  return;
	  }

	  // 次に回すノードの初期化
	  mChildNodes[mRunningNodeIndex]->init();
	}
	
	virtual const int get_next_index() const = 0; // 派生クラスで実装

protected:
	// 子ノード群
	std::vector<INode*> mChildNodes;
	// 現在動かしているノードのインデックス
	int mRunningNodeIndex{ 0 };
};
```

### Sequenceノード
```cpp:Sequence.h
class Sequence : public CompositeNodeBase {
public:

// 中略

	void tick() override
	{
	  mChildNodes[mRunningNodeIndex]->tick();
      auto result = mChildNodes[mRunningNodeIndex]->get_node_result();

	  if (result == NodeResult::Success) 
	  {
		  // 次回Sequenceに向けてノード番号を進める
		  node_increment();
		  return;
	  }

	  // もし失敗が返されたらノード終了
	  if (result == NodeResult::Fail) 
	  {
		  finalize();
	  }

	  mNodeResult = result;
	}

private:
	const int get_next_index() const override
	{
	  return mRunningNodeIndex + 1;
	}
};
```

### Selectorノード
```cpp:Selector.h
class Selector : public CompositeNodeBase {
public:

// 中略

	void tick() override{
	  mChildNodes[mRunningNodeIndex]->tick();
	  auto result = mChildNodes[mRunningNodeIndex]->get_node_result();

	  if (result == NodeResult::Fail) {
		  // 次回Sequenceに向けてノード番号を進める
		  node_increment();
		  return;
	  }

	  // もし成功が返されたらノード終了
	  if (result == NodeResult::Success) {
		  finalize();
	  }

	  mNodeResult = result;
	}

private:
	const int get_next_index() const override{
	  return mRunningNodeIndex + 1;
	}
};
```

## Branchノードの基底クラス
```cpp:BranchNodeBase.h
class BranchNodeBase : public NodeBase {
public:
	explicit BranchNodeBase(BlackBoard* black_board, INode* true_node, INode* false_node)	
	  : NodeBase(black_board)
  {
	  mpBranchNodes[0] = true_node;
	  mpBranchNodes[1] = false_node;
  }

	virtual ~BranchNodeBase()
	{
	  // ブランチノードの配列を解放
	  for (int i = 0; i < 2; ++i) 
	  {
		  if (mpBranchNodes[i] != nullptr) 
		  {
			  delete mpBranchNodes[i];
			  mpBranchNodes[i] = nullptr;
		  }
	  }
	}

	virtual void init() override
	{
	  NodeBase::init();

	  if (is_condition()) mSatisfyIndex = 0;
	  else mSatisfyIndex = 1;

	  mpBranchNodes[mSatisfyIndex]->init();
	}
	
	virtual void tick() override
	{
	  mpBranchNodes[mSatisfyIndex]->tick();
	  mNodeResult = mpBranchNodes[mSatisfyIndex]->get_node_result();
	}
	
	virtual void finalize() override
	{
	  NodeBase::finalize();
	  mpBranchNodes[mSatisfyIndex]->finalize();
	  mSatisfyIndex = -1;
	}

protected:
	virtual const bool is_condition() = 0; // 派生クラスで実装
	
protected:
	INode* mpBranchNodes[2] = { nullptr, nullptr }; // True,Falseそれぞれのノード
  int mSatisfyIndex = -1; // 条件を満たしているノードのインデックス
};
```


### CheckNearPlayerノード
```cpp:CheckNearPlayer.h
class CheckNearPlayer : public BranchNodeBase {
public:
	explicit CheckNearPlayer(BlackBoard* black_board, INode* true_node, INode* false_node, const float max_distance)
    : BranchNodeBase(black_board, true_node, false_node)
    , mMaxDistance(max_distance) {}

	~CheckNearPlayer(){}

private:
	const bool is_condition() override
    {
        // プレイヤーの位置を取得
        auto player_pos = mpBlackBoard->get_value<Vector2>("PlayerPos");
        auto* agent = mpBlackBoard->get_value<IAgent*>("Agent");

        auto vector = player_pos - agent->get_position();

        // 近ければtrueを返す
        return vector.magnitude() < mMaxDistance;
    }

private:
	const float mMaxDistance = 5;
};
```


## Decoratorノードの基底クラス
```cpp:DecoratorNodeBase.h
class DecoratorNodeBase : public NodeBase {
public:
	explicit DecoratorNodeBase(BlackBoard* black_board) : NodeBase(black_board) {}
	virtual ~DecoratorNodeBase();

	virtual void init() override
    {
    	NodeBase::init();
    	mChildNode->init();
    }
    
	virtual void finalize() override
    {
    	NodeBase::finalize();
    	mChildNode->finalize();
    }

	void set_node(INode* node){ mChildNode = node; }

protected:
	INode* mChildNode = nullptr;
};
```


### Inverterクラス
```cpp:Inverter.h
class Inverter : public DecoratorNodeBase {
public:
	explicit Inverter(BlackBoard* black_board, INode* child_node)
        : DecoratorNodeBase(black_board)
    {
    	set_node(child_node);
    }

	~Inverter(){}

	void tick() override
    {
    	// 子ノードを実行
        mChildNode->tick();
    	// 子ノードの結果を取得
    	NodeResult result = mChildNode->get_node_result();
    	// 結果を反転させる
    	if (result == NodeResult::Success) {
    		mNodeResult = NodeResult::Fail;
    		return;
    	}
    	else if (result == NodeResult::Fail) {
    		mNodeResult = NodeResult::Success;
    		return;
    	}

    	// 子ノードが実行中の場合は、Inverterも実行中にする
    	mNodeResult = NodeResult::Running;
	}
};
```


## Leafノードの基底クラス
```cpp:LeafNodeBase.h
class LeafNodeBase : public NodeBase {
protected:
	explicit LeafNodeBase(BlackBoard* black_board) : NodeBase{ black_board } {}
	virtual ~LeafNodeBase() = default;
};
```


### Waitノード
```cpp:WaitLeaf.h
class WaitLeaf : public LeafNodeBase {
public:
	explicit WaitLeaf(BlackBoard* black_board, const float wait_time)
    	: LeafNodeBase(black_board)
    	, mWaitTime(wait_time)
    	, mWaitCount(wait_time)
    {}
    
	~WaitLeaf(){}

	void tick() override
    {
    	if (mWaitCount <= 0.f) {
		mNodeResult = NodeResult::Success;
		return;
	}

	mWaitCount -= 1.f;
    }
    
	void finalize() override
    {
    	LeafNodeBase::finalize();
    	mWaitCount = mWaitTime;
    }

private:
	float mWaitTime = 0.f;
	float mWaitCount = 0.f;
};
```
>※フレーム毎に減算しているため完全に環境依存してます...

### ChasePlayerノード
```cpp:ChasePlayerLeaf.h
class ChasePlayerLeaf : public LeafNodeBase {
public:
	explicit ChasePlayerLeaf(BlackBoard* black_board);

	~ChasePlayerLeaf();

	void tick() override
    {
    	// プレイヤーの位置を取得
    	auto player_pos = mpBlackBoard->get_value<Vector2>("PlayerPos");
    	auto* agent = mpBlackBoard->get_value<IAgent*>("Agent");

    	auto vector = player_pos - agent->get_position();

    	agent->move_towards(vector.normalized(), mMoveSpeed);
    }

	NodeResult get_node_result() const override
    {
        // 必ず成功を返す
        return NodeResult::Success;
    }

private:
    float mMoveSpeed = 3.25f;
};
```

### AlwaysSuccessノード
```cpp:AlwaysSuccessLeaf.h
class AlwaysSuccessLeaf : public LeafNodeBase {
public:
	explicit AlwaysSuccessLeaf(BlackBoard* black_board) : LeafNodeBase(black_board) {}

	~AlwaysSuccessLeaf() override = default;

	NodeResult get_node_result() const override {
		return NodeResult::Success;
	}
};
```

### CircleAttackノード
```cpp:CircleAttackLeaf.h
class CircleAttackLeaf : public LeafNodeBase {
public:
	explicit CircleAttackLeaf(BlackBoard* black_board) : LeafNodeBase(black_board){}
	~CircleAttackLeaf(){}

	void tick() override
    {
    	// 攻撃
    	auto* agent = mpBlackBoard->get_value<IAgent*>("Agent");
    	agent->attack();
    }

	NodeResult get_node_result() const override
    {
        // 必ず成功を返す
        return NodeResult::Success;
    }
};
```

## ブラックボード
```cpp:BlackBoard.h
class BlackBoard {
public:
	// 要素をセット
	template<typename T>
	void set_value(const std::string& key, const T& value) {
		mData[key] = value;
	}

	// 要素を取得
	template<typename T>
	T get_value(const std::string& key) const {
		auto it = mData.find(key);
		if (it != mData.end()) {
			return std::any_cast<T>(it->second);
		}

		throw std::runtime_error("キーが見つかりませんでした： " + key);
	}

	// キーがあるかチェック
	bool has_key(const std::string& key) const {
        return mData.find(key) != mData.end();
    }

private:
	std::unordered_map<std::string, std::any> mData;
};
```

## ツリー組み立て
```cpp:BehaviorTreeBuilder.cpp
// 中略

INode* get_attacker_tree(BlackBoard* blackboard)
{
	auto chase_inverter = new Inverter(blackboard, new ChasePlayerLeaf(blackboard));

	auto root_sequence = new Sequence(blackboard);
	root_sequence->add_node(new CheckNearPlayer(blackboard, new AlwaysSuccessLeaf(blackboard), chase_inverter, 100.f));
	root_sequence->add_node(new CircleAttackLeaf(blackboard));
	root_sequence->add_node(new WaitLeaf(blackboard, 60.f));
	return root_sequence;
}

// 中略
```

# まとめ
本記事では、C++でシンプルなビヘイビアツリーを自前実装し、その構造やノードの役割について解説しました。

現状、ツリーをソースコードに直接ベタ書きしているため、非常に可読性が低いことが課題となっています。
次回の記事では、一般的なゲームエンジンにあるようなビジュアルツリーエディターを自作し、ゲーム中に反映させる方法を紹介する予定です。

# あとがき
今回、初めて技術系の記事を投稿させていただきました。
わかりづらい点・間違った点がございましたら、コメントにてご指摘いただけると大変助かります...m(_ _)m