【C++】ゲームAIの基本：ビヘイビアツリーをミニマル実装で学ぶ

ゲームAIの実装方法はいくつもありますが、その中でもビヘイビアツリー/Behavior Treeは、複雑な行動をシンプルな構造で組み立てられることから、ゲーム開発分野では人気の方法となっています。

本記事では、ビヘイビアツリーの本質がわかるように、最小構成のサンプルコードを使って紹介します。

前提知識

• C++の基礎文法を理解している

ビヘイビアツリーとは

ビヘイビアツリー/Behavior Tree/BTは、キャラクターの行動を表現するための仕組みです。

ゲームAIでは、キャラクターが状況に応じて

• 攻撃する
• 逃げる
• パトロールする
• 探索する

といった行動を選択する必要がありますが、条件分岐が増えるほどコードは複雑になり、管理が難しくなります。

ビヘイビアツリーは、この問題を解決するために生まれた手法で、複雑な行動を、小さなノードの組み合わせで表現するという考え方に基づいています。

Compositeパターンの応用であり、先にそちらを理解しておくと理解しやすいと思います。

デメリットとしては

• Running（継続状態）の管理が難しい
• 大規模になるとツリーが肥大化する
• 優先度の動的変更が難しい
  といったものがあり、発展させるには非常に工夫の余地があります。

ビヘイビアツリーの構成

ビヘイビアツリーは以下の要素で構成されます。

• Node/ノード
  • すべてのノードの基底クラス
  • tick()を持ち、毎フレーム処理を行う
  • tick()はSuccess/成功,Failure/失敗,Running/実行中のいずれかの状態を返す
  • CompositeパターンのComponentの役割に近い
• CompositeNode/コンポジットノード
  • 複数の子ノードを持ち、子ノードの結果を組み合わせて意思決定するノード

本記事でも取り扱う代表的なCompositeNodeとして二種類のノードを紹介します。

• SequenceNode/シーケンスノード
  • 子ノードを上から順に実行する
  • Success以外（Failure/Running）が出たら即終了
  • 全部SuccessならSuccessを返す
• SelectorNode/セレクタノード
  • 子ノードを上から順に実行する
  • Failure以外（Success/Running）が出たら即終了
  • 全部FailureならFailureを返す

といったものがあります。

• LeafNode/リーフノード
  • 実際の処理を行う末端ノード
  • 親ノードだけを持ち、子ノードを持たない

LeafNodeは大きく二種類に分かれます。

• ConditionNode/条件ノード
  • 副作用を持たせないノード
  • SuccessかFailureのどちらかのみを返す
  • Running は返さない
• ActionNode/アクションノード
  • 実際の行動を行うノード
  • 副作用のあるノード

ビヘイビアツリーの用語

• tick/評価
  -BTは毎フレームRootノードのtick() を呼び出すことで動作する
  • BTには状態遷移がなく、毎フレーム行動を評価する
  • Compositeノードは短絡評価/short-circuitで効率的に動作する
• Short-circuit Evaluation/短絡評価
  • Compositeノードが持つ性質
  • 結果が決まった時点で残りの子ノードを評価しないこと

SequenceはAND条件、SelectorはORの短絡評価といいます

サンプルコード

BTのみで疑似的にenemyの探索を記述したコード

enemyが見えるなら攻撃、見えないならパトロールを行うという内容をBTで記述したコードになります。

main.cpp

//---------------------------------------------------------------
//! @file	main.cpp
//! @brief	ビヘイビアツリーのサンプル実装
//! @author つきの
//---------------------------------------------------------------
#include <iostream>
#include <vector>
#include <memory>
#include <functional>

//---------------------------------------------------------------
//! @enum	Status
//! @brief	ノードの状態
//! @note	ノードのtick()が返す値。
//---------------------------------------------------------------
enum class Status {
	Success,   // 成功
	Failure,   // 失敗
	Running    // 実行中（長時間行動など）
};

//---------------------------------------------------------------
//! @class	Node
//! @brief	ビヘイビアツリーのノード基底クラス
//! @note	すべてのノードはこのクラスを継承する。
//! @note	Behavior Treeの Component / Node　に相当する
//---------------------------------------------------------------
class Node {
public:
	//---------------------------------------------------------------
	//! @brief	仮想デストラクタ
	//---------------------------------------------------------------
	virtual ~Node() = default;

	//---------------------------------------------------------------
	//! @brief	ノードの処理を実行する
	//---------------------------------------------------------------
	virtual Status tick() = 0;
};


//---------------------------------------------------------------
//! @class	Sequence
//! @brief	シーケンスノード
//! @note	子ノードを順番に実行し、すべてが成功なら成功を返す。
//! @note	Behavior Treeの Composite / Sequence に相当する
//---------------------------------------------------------------
class Sequence : public Node {
public:
	//---------------------------------------------------------------
	//! @brief	子ノードを追加する
	//! @param	child [in] 子ノード
	//---------------------------------------------------------------
	void addChild(std::unique_ptr<Node> child) {
		children_.emplace_back(std::move(child));
	}

	//---------------------------------------------------------------
	//! @brief	ノードの処理を実行する
	//! @return	ノードの状態を返す
	//! @note	子ノードを順番に実行し、Success 以外が出たら即終了
	//---------------------------------------------------------------
	Status tick() override {
		//---------------------------------------------------------------
		// 子ノードを順番に実行
		//---------------------------------------------------------------
		for (auto& c : children_) {
			// 子ノードを実行
			Status s = c->tick();

			// Success 以外（Failure / Running）が出たら即終了
			if (s != Status::Success) {
				return s;
			}
		}
		// すべて Success なら Success を返す
		return Status::Success;
	}

private:
	std::vector<std::unique_ptr<Node>> children_;	// 子ノードの可変長配列
};


//---------------------------------------------------------------
//! @class	Selector
//! @brief	セレクタノード
//! @note	子ノードを順番に実行し、最初に成功したノードの状態を返す。
//---------------------------------------------------------------
class Selector : public Node {
public:
	//---------------------------------------------------------------
	//! @brief	子ノードを追加する
	//! @param	child [in] 子ノード
	//---------------------------------------------------------------
	void addChild(std::unique_ptr<Node> child) {
		children_.emplace_back(std::move(child));
	}

	//---------------------------------------------------------------
	//! @brief	ノードの処理を実行する
	//! @return	ノードの状態を返す
	//! @note	子ノードを順番に実行し、Failure 以外が出たら即終了
	//---------------------------------------------------------------
	Status tick() override {
		//---------------------------------------------------------------
		// 子ノードを順番に実行
		//---------------------------------------------------------------
		for (auto& c : children_) {
			// 子ノードを実行
			Status s = c->tick();

			// Failure 以外（Success / Running）が出たら即終了
			if (s != Status::Failure) {
				return s;
			}
		}
		// すべて Failure なら Failure を返す
		return Status::Failure;
	}

private:
	std::vector<std::unique_ptr<Node>> children_;	// 子ノードの可変長配列
};


//---------------------------------------------------------------
//! @class	 Condition
//! @brief	 条件ノード
//! @note	 条件を評価するノード
//! @note	 Behavior Treeの Leaf / Condition に相当する
//! @warning 条件ノードは副作用を持たないことが望ましい。
//---------------------------------------------------------------
class Condition : public Node {
public:
	//---------------------------------------------------------------
	//! @brief	コンストラクタ
	//! @param	fn [in] 条件を評価する関数
	//! @note	fnはboolを返す関数オブジェクト。
	//---------------------------------------------------------------
	explicit Condition(std::function<bool()> fn)
		: fn_(std::move(fn)) {
	}

	//---------------------------------------------------------------
	//! @brief	ノードの処理を実行する
	//! @return	ノードの状態を返す
	//---------------------------------------------------------------
	Status tick() override {
		bool result = fn_();	// 条件を評価
		// 結果を表示
		std::cout << "[判定のノード状態] -> "
			<< (result ? "Success" : "Failure") << "\n";
		// 成功/失敗を返す
		return result ? Status::Success : Status::Failure;
	}

private:
	std::function<bool()> fn_;	// 条件を評価する関数オブジェクト
};


//---------------------------------------------------------------
//! @class	 Action
//! @brief	 アクションノード
//! @note	 アクションを実行するノード
//! @note	 Behavior Treeの Leaf / Action に相当する
//! @warning アクションノードは普通副作用を持つ
//---------------------------------------------------------------
class Action : public Node {
public:
	//---------------------------------------------------------------
	//! @brief	コンストラクタ
	//! @param	fn [in] アクションを実行する関数
	//---------------------------------------------------------------
	explicit Action(std::function<Status()> fn)
		: fn_(std::move(fn)) {
	}

	//---------------------------------------------------------------
	//! @brief	ノードの処理を実行する
	//! @return	ノードの状態を返す
	//---------------------------------------------------------------
	Status tick() override {
		// アクションを実行
		Status s = fn_();
		// 結果を表示
		std::cout << "[行動のノード状態] -> "
			<< (s == Status::Success ? "Success" :
				s == Status::Failure ? "Failure" : "Running")
			<< "\n";
		// 状態を返す
		return s;
	}

private:
	std::function<Status()> fn_;	// アクションを実行する関数オブジェクト
};

// エントリポイント
int main() {
	bool enemy_visible = false; // 敵が見えるかどうか（外部状態）

	//---------------------------------------------------------------
	// 見えるか見えないかを返す条件ノードの作成
	//---------------------------------------------------------------
	auto enemy_visible_cond = std::make_unique<Condition>(
		// 捕捉した外部状態をキャプチャして返すラムダ式
		[&enemy_visible]() {
			// 敵が見えるかどうかを返す
			return enemy_visible;
		}
	);

	//---------------------------------------------------------------
	// 攻撃を行うアクションノードの作成
	//---------------------------------------------------------------
	auto attack_action = std::make_unique<Action>(
		[]() {
			// 攻撃処理（本サンプルでは単に表示するだけ）
			std::cout << "攻撃する！\n";
			// 成功を返す
			return Status::Success;
		}
	);

	//---------------------------------------------------------------
	// パトロールを行うアクションノードの作成
	//---------------------------------------------------------------
	auto patrol_action = std::make_unique<Action>(
		[]() {
			// パトロール処理（本サンプルでは単に表示するだけ）
			std::cout << "パトロール中...\n";
			// 成功を返す
			return Status::Success;
		}
	);

	//---------------------------------------------------------------
	// 攻撃シーケンスの作成
	//---------------------------------------------------------------
	auto attack_sequence = std::make_unique<Sequence>();
	attack_sequence->addChild(std::move(enemy_visible_cond));
	attack_sequence->addChild(std::move(attack_action));

	//---------------------------------------------------------------
	// ルートノード（セレクタ）の作成
	//---------------------------------------------------------------
	auto root = std::make_unique<Selector>();
	root->addChild(std::move(attack_sequence));
	root->addChild(std::move(patrol_action));

	//---------------------------------------------------------------
	// 見えない状態でビヘイビアツリーの実行
	//---------------------------------------------------------------
	std::cout << "敵が見えない!\n";
	root->tick();

	//---------------------------------------------------------------
	// 敵が見える状態に変更して再度実行
	//---------------------------------------------------------------
	std::cout << "\n敵が見えるようになった!\n";
	enemy_visible = true;
	root->tick();
	// プログラムの終了
	return 0;
}

result

敵が見えない!
[判定のノード状態] -> Failure
パトロール中...
[行動のノード状態] -> Success

敵が見えるようになった!
[判定のノード状態] -> Success
攻撃する！
[行動のノード状態] -> Success

本コードにおけるツリー構造の図解

Node

すべてのノードの基底クラス、毎フレーム呼ばれる動作であるtick()を定義する。

main.cpp

//---------------------------------------------------------------
//! @class	Node
//! @brief	ビヘイビアツリーのノード基底クラス
//! @note	すべてのノードはこのクラスを継承する。
//! @note	Behavior Treeの Component / Node　に相当する
//---------------------------------------------------------------
class Node {
public:
	//---------------------------------------------------------------
	//! @brief	仮想デストラクタ
	//---------------------------------------------------------------
	virtual ~Node() = default;

	//---------------------------------------------------------------
	//! @brief	ノードの処理を実行する
	//---------------------------------------------------------------
	virtual Status tick() = 0;
};

SequenceNode/シーケンスノード

tick()で子ノードを順に実行し、Success以外であれば即終了(ANDの短絡評価)としている。

main.cpp

//---------------------------------------------------------------
//! @class	Sequence
//! @brief	シーケンスノード
//! @note	子ノードを順番に実行し、すべてが成功なら成功を返す。
//! @note	Behavior Treeの Composite / Sequence に相当する
//---------------------------------------------------------------
class Sequence : public Node {
public:
	//---------------------------------------------------------------
	//! @brief	子ノードを追加する
	//! @param	child [in] 子ノード
	//---------------------------------------------------------------
	void addChild(std::unique_ptr<Node> child) {
		children_.emplace_back(std::move(child));
	}

	//---------------------------------------------------------------
	//! @brief	ノードの処理を実行する
	//! @return	ノードの状態を返す
	//! @note	子ノードを順番に実行し、Success 以外が出たら即終了
	//---------------------------------------------------------------
	Status tick() override {
		//---------------------------------------------------------------
		// 子ノードを順番に実行
		//---------------------------------------------------------------
		for (auto& c : children_) {
			// 子ノードを実行
			Status s = c->tick();

			// Success 以外（Failure / Running）が出たら即終了
			if (s != Status::Success) {
				return s;
			}
		}
		// すべて Success なら Success を返す
		return Status::Success;
	}

private:
	std::vector<std::unique_ptr<Node>> children_;	// 子ノードの可変長配列
};

SelectorNode/セレクタノード

tick()内で子ノードを順番に実行し、Failure以外が出たら即終了(ORの短絡評価)としている。

main.cpp

//---------------------------------------------------------------
//! @class	Selector
//! @brief	セレクタノード
//! @note	子ノードを順番に実行し、最初に成功したノードの状態を返す。
//---------------------------------------------------------------
class Selector : public Node {
public:
	//---------------------------------------------------------------
	//! @brief	子ノードを追加する
	//! @param	child [in] 子ノード
	//---------------------------------------------------------------
	void addChild(std::unique_ptr<Node> child) {
		children_.emplace_back(std::move(child));
	}

	//---------------------------------------------------------------
	//! @brief	ノードの処理を実行する
	//! @return	ノードの状態を返す
	//! @note	子ノードを順番に実行し、Failure 以外が出たら即終了
	//---------------------------------------------------------------
	Status tick() override {
		//---------------------------------------------------------------
		// 子ノードを順番に実行
		//---------------------------------------------------------------
		for (auto& c : children_) {
			// 子ノードを実行
			Status s = c->tick();

			// Failure 以外（Success / Running）が出たら即終了
			if (s != Status::Failure) {
				return s;
			}
		}
		// すべて Failure なら Failure を返す
		return Status::Failure;
	}

private:
	std::vector<std::unique_ptr<Node>> children_;	// 子ノードの可変長配列
};

ConditionNode/条件ノード

bool値を返すコールバック関数をメンバに持ち、tick()ではその結果によってSuccessかFailureを返します。

main.cpp

//---------------------------------------------------------------
//! @class	 Condition
//! @brief	 条件ノード
//! @note	 条件を評価するノード
//! @note	 Behavior Treeの Leaf / Condition に相当する
//! @warning 条件ノードは副作用を持たないことが望ましい。
//---------------------------------------------------------------
class Condition : public Node {
public:
	//---------------------------------------------------------------
	//! @brief	コンストラクタ
	//! @param	fn [in] 条件を評価する関数
	//! @note	fnはboolを返す関数オブジェクト。
	//---------------------------------------------------------------
	explicit Condition(std::function<bool()> fn)
		: fn_(std::move(fn)) {
	}

	//---------------------------------------------------------------
	//! @brief	ノードの処理を実行する
	//! @return	ノードの状態を返す
	//---------------------------------------------------------------
	Status tick() override {
		bool result = fn_();	// 条件を評価
		// 結果を表示
		std::cout << "[判定のノード状態] -> "
			<< (result ? "Success" : "Failure") << "\n";
		// 成功/失敗を返す
		return result ? Status::Success : Status::Failure;
	}

private:
	std::function<bool()> fn_;	// 条件を評価する関数オブジェクト
};

ActionNode/アクションノード

副作用のある処理はこのノードのコールバック関数が持ちます。
tick()ではその結果を返します。

main.cpp

//---------------------------------------------------------------
//! @class	 Action
//! @brief	 アクションノード
//! @note	 アクションを実行するノード
//! @note	 Behavior Treeの Leaf / Action に相当する
//! @warning アクションノードは普通副作用を持つ
//---------------------------------------------------------------
class Action : public Node {
public:
	//---------------------------------------------------------------
	//! @brief	コンストラクタ
	//! @param	fn [in] アクションを実行する関数
	//---------------------------------------------------------------
	explicit Action(std::function<Status()> fn)
		: fn_(std::move(fn)) {
	}

	//---------------------------------------------------------------
	//! @brief	ノードの処理を実行する
	//! @return	ノードの状態を返す
	//---------------------------------------------------------------
	Status tick() override {
		// アクションを実行
		Status s = fn_();
		// 結果を表示
		std::cout << "[行動のノード状態] -> "
			<< (s == Status::Success ? "Success" :
				s == Status::Failure ? "Failure" : "Running")
			<< "\n";
		// 状態を返す
		return s;
	}

private:
	std::function<Status()> fn_;	// アクションを実行する関数オブジェクト
};

総括

• Behavior treeを使用することで、複雑な処理を小さな処理の組み合わせで記述することが出来る
• Behavior treeには状態がなく、毎フレームtick()で処理と評価を行う
• Behavior treeはCompositeパターンの応用