目次

・はじめに
・完成形の動き
・AI制御の解説
　経路探索の解説
　　ウェイポイントの説明
　　 A*の説明
　　エリアごとに分けた経路探索
　状態管理の解説
　　 StateMacineの実装
　　 BehaviorTreeの実装
・集団制御の解説
　目的に合わせたグループ管理
　メンバーの情報交換方法
・最後に

はじめに

オンライン対戦ゲームを作りました。
そこで対戦中に仲間の回線が落ちても、AIに切り替えることで最後まで楽しめるようにしたいと考え実装しました。
そのゲームで利用したAIの制御方法をまとめてみました。

完成形の動き

実装が完了すると以下のような動きが実現できます。
※動いている６人のキャラクターはすべてAIです。

AI制御の解説

上記の動きを実現するための手順を順を追って解説していきます。
　1.経路探索の解説
　 2.状態管理の解説
　 3.集団制御の解説

経路探索の解説

経路探索には「ウェイポイント」と「A*」を使用して、経路探索をしています。
まずは、ウェイポイントとA*について軽く説明します。

ウェイポイントの説明

下記の図のように、ステージ上に経路探索用のウェイポイントを設定します。
そしてRayを飛ばして障害物がない場合にウェイポイントをエッジで結合します。
エッジで結合されることで、それぞれのウェイポイントが移動可能であることを示します。
この設置したウェイポイントの位置座標を元にA*経路探索をします。

A*の説明

A*はグラフ探索アルゴリズムの一つです。ダイクストラ法を元により効率的に最短経路を求めることができます。
「実際にかかる距離(実コスト)」と「その地点から目的地までの仮想距離(推定コスト)」の和を使用して、最短経路を求めるアルゴリズムです。
推定コストは、ヒューリスティック関数と呼ばれます。
詳しい実装方法や説明は下記のサイトを参考にするとわかりやすいと思います。
https://yttm-work.jp/algorithm/algorithm_0015.html#head_line_01
http://marupeke296.com/ALG_No6_ASter.html

エリアごとに分けた経路探索

上記のように「ウェイポイント」と「A*」を使った経路探索で、目的地への最短経路を求めることができます。
しかし、処理コストが非常に高い問題が残っています。
小さいステージならいいですが、大きいステージでこのままの経路探索を使用することは難しいです。
今回のゲームでは経路探索が発生するたびにゲームが一瞬固まってしまう問題が発生しました。
それを解決するために、経路探索をエリアごとに区切ることにしました。

初めに、目的地のエリアを特定します。
特定したエリアまでの、「エリアごと」の経路探索をします。
上記の図で、開始エリアが「1」で目的地エリアが「7」とした場合は「1→3→5→7」となります。
エリアが切り替わりごとに経路探索を一旦打ち切ることで処理コストを減らすことができました。

    /// <summary>
	/// エリア間のルートを計算する。
	/// </summary>
    /// <returns>エリア間のルート</returns>
	std::queue<int> CalculateMoveAreaRouteQueue() {
        //フィールド影響マップの取得
		auto fieldImpactMap = maru::FieldImpactMap::GetInstance();

		//開始位置と目標位置の取得
		auto startPosition = m_transform.lock()->GetPosition();
		auto targetPosition = CalculateMoveTargetPosition();

		//エリアのルートを取得
		return fieldImpactMap->SearchAreaRouteIndices(startPosition, targetPosition);
	}

状態管理の解説

状態管理に「StateMachine」と「BehaviorTree」を組み合わせました。
「攻撃」や「探索」など大まかな状態をStateMachine側で管理し、
それぞれの状態ごとに、攻撃BehaviorTreeや探索BehaviorTreeなどを実装しています。
入れ子構造にすることで状態遷移の複雑化を回避することができます。
この有用性は下記のサイトで詳しく記述されています。
https://thinkit.co.jp/article/10012

StateMacineの実装

StateMachineは循環型のツリーグラフです。
AIの行動状態を管理します。
上記の説明通り、大まかな状態を管理しています。
今後は「逃走」や「様子見」など、より人間らしい動きを追求するための状態を追加をしたいと考えています。
この開発で使用しているステートマシンの記事はこちらになります。

    //--------------------------------------------------------------------------------------
	///	AIPlayerStatorのステートタイプ
	//--------------------------------------------------------------------------------------
	enum class AIPlayerStator_StateType {
		None,
        Patrol, //探索
		Buttle,	//バトル
		Dyning,	//死亡中
		Dead,	//死亡
	};

    /// <summary>
	/// 更新処理
	/// </summary>
    void AIPlayerStator::OnUpdate() {
        m_stateMachine->OnUpdate();
    }

    /// <summary>
	/// ノードの生成
	/// </summary>
	void AIPlayerStator::CreateNode() {
		auto enemy = GetGameObject()->GetComponent<EnemyBase>();

		//None状態
		m_stateMachine->AddNode(StateType::None, nullptr);

		//探索
		m_stateMachine->AddNode(StateType::HidePlacePatrol, std::make_shared<StateNode::Patrol>(enemy));

		//バトル
		m_stateMachine->AddNode(StateType::Buttle, std::make_shared<StateNode::Buttle>(enemy));

		//死亡中
		m_stateMachine->AddNode(StateType::Dyning, std::make_shared<StateNode::Dyning>(enemy));

		//死亡
		m_stateMachine->AddNode(StateType::Dead, std::make_shared<StateNode::Dead>(enemy));
	}

    /// <summary>
	/// エッジの生成
	/// </summary>
	void AIPlayerStator::CreateEdge() {
		auto enemy = GetGameObject()->GetComponent<EnemyBase>();

		//None
		m_stateMachine->AddEdge(StateType::None, StateType::Patrol, &IsGameState);

		//探索
		m_stateMachine->AddEdge(
			StateType::Patrol, 
			StateType::Buttle, 
			[&](const TransitionMember& member) { return IsFindButtleTarget(member); }
		);

		//バトル
		m_stateMachine->AddEdge(
			StateType::Buttle,
			StateType::Patrol,
			[&](const TransitionMember& member) { return IsLostButtleTarget(member); }
		);
	}

	/// <summary>
	/// ステートの変更
	/// </summary>
	/// <param name="state">変更したいステート</param>
	/// <param name="priority">優先度</param>
	void AIPlayerStator::ChangeState(const EnumType state, const int priority) {
		m_stateMachine->ChangeState(state, priority);
	}

BehaviorTreeの実装

BehaviorTreeは非循環型の一方通行のツリーグラフです。
上記の説明通り、攻撃や探索といったそれぞれの状態ごとのBehaviorTreeを実装しました。

探索用BehaviorTree

	//--------------------------------------------------------------------------------------
	/// 探索用のビヘイビアツリーのタイプ
	//--------------------------------------------------------------------------------------
	enum class PatrolTree_BehaviorType {
		FirstSelecter,			//初回セレクター

		ToGoalRunTask,			//ゴールまで行くタスク。
		ToMoveHasBallEnemyTask,	//ボールを持っている敵まで行くタスク。
		RelifHasBallMemberTask,	//ボールを持っているメンバーを守るタスク。
		ToBallRunTask,			//ボールまで駆けつけるタスク。
		PatrolTask,				//パトロールタスク。
	};

    /// <summary>
	/// ノードの生成(一部抜粋)
	/// </summary>
	void PatrolTree::CreateNode() {
		using namespace maru::Behavior;

		auto owner = GetOwner()->GetComponent<Enemy::EnemyBase>();

		//初回セレクター
		m_behaviorTree->AddSelecter(BehaviorType::FirstSelecter);

		//ボール探すタスク
		m_behaviorTree->AddTask<Task::SearchBall>(
			BehaviorType::PatrolTask, owner
		);

		//見方を守るタスク
		m_behaviorTree->AddTask<Task::RelifMember>(
			BehaviorType::RelifHasBallMemberTask, owner
		);
	}

    /// <summary>
	/// エッジの生成(一部抜粋)
	/// </summary>
	void PatrolTree::CreateEdge() {
		using PriorityControllerBase = maru::Behavior::PriorityControllerBase;

		//初回セレクター

		m_behaviorTree->AddEdge(
			BehaviorType::FirstSelecter, 
			BehaviorType::PatrolTask, 
			(int)BehaviorType::PatrolTask
		);

		m_behaviorTree->AddEdge(
			BehaviorType::FirstSelecter,
			BehaviorType::RelifHasBallMemberTask,
			(int)BehaviorType::RelifHasBallMemberTask
		);
	}

    /// <summary>
	/// デコレータの生成(一部抜粋)
	/// </summary>
	void PatrolTree::CreateDecorator() {
		auto enemy = GetOwner()->GetComponent<Enemy::EnemyBase>();

		//仲間チームにボールを持っている人がいるなら
		m_behaviorTree->AddDecorator<Decorator::HasBall_OtherMember>(
			BehaviorType::RelifHasBallMemberTask, enemy
		);

		//相手チームにボールを持っている人がいるなら
		m_behaviorTree->AddDecorator<Decorator::HasBall_OtherTeam>(
			BehaviorType::ToMoveHasBallEnemyTask, enemy
		);
	}

攻撃用BehaviorTree

ノードやエッジなどの設定方法は探索BehaviorTreeと一緒のため、BihaviorTypeのみ記載しています。

	//--------------------------------------------------------------------------------------
	/// バトル用のビヘイビアツリーのタイプ
	//--------------------------------------------------------------------------------------
	enum class ButtleTree_BihaviorType {
		FirstSelecter,		//初期セレクター

		AttackSelecter,		//攻撃セレクター
			AttackMoveSelecter,	//攻撃中の移動セレクター
				NearMoveSelecter,	//近づくタスク
					NearSeekMoveTask,	//直線的に近づく
					NearAstarMoveTask,	//Astarを使って近づく
			ShotTask,	//撃つ
	};

集団制御の解説

このゲームはチームメンバーが協力して、ゴールにトライを決めることを目指します。
そのため、AIメンバー同士のコミュニケーションが必要になります。
それを解決するために次のような方法で実装しました。

目的に合わせたグループ管理

AIDirectorがチームごとのグループ管理者を作ります。

それぞれのチームグループ管理者が、メンバーの目的に合わせたグループ管理者を生成します。
例えば「探索グループ管理者」や「攻撃グループ管理者」などです。

メンバーは「敵の発見」や「ボックスを開いた」などの行動をグループ管理者に報告します。
報告された内容によって、グループ管理者はメンバーへの命令を考えます。
報告方法については下記にまとめています。

メンバーの情報交換方法

メンバー情報交換用にTupleSpaceクラスを使用ました。
TupleSpaceにそれぞれのメンバーが情報を書き込むことで、チーム全体の管理をすることができます。

TupleSpaceは「書き込み」,「読み込み」,「取得」,「通知」ができます。
通知の設定をすると、特定の条件と一致した書き込みがされた時に、通知が届くようにすることができます。

	/// <summary>
	/// メッセージを書き込む
	/// </summary>
	template<class T, class... Ts,
		std::enable_if_t<std::is_base_of_v<I_Tuple, T> && std::is_constructible_v<T, Ts...>, std::nullptr_t> = nullptr> //基底クラスの制約, コンストラクタの確認
	void Write(Ts&&... params) 
	{
		auto typeIndex = type_index(typeid(T));
		auto newTuple = std::make_shared<T>(params...);

		//同じ情報なら書き込まない
		if (IsSomeTuple(newTuple)) {
    		return;
		}

		//登録
		m_tuplesMap[typeIndex].push_back(newTuple);

		//登録された通知を呼び出す。
		CallNotifys<T>(newTuple);
	}

	/// <summary>
	/// メッセージを読み込む(メッセージは削除しない)
	/// </summary>
	/// <param name="isFunc">取得条件</param>
	template<class T,
		std::enable_if_t<std::is_base_of_v<I_Tuple, T>, std::nullptr_t> = nullptr> //基底クラスの制約
	const std::shared_ptr<const T> Read(
		const std::function<bool(const std::shared_ptr<T>&)>& isFunc = [](const std::shared_ptr<T>&) { return true; } ) const
	{
		return SearchTuple<T>(isFunc);
	}

	/// <summary>
	/// メッセージを受信して、削除する。
	/// </summary>
	/// <param name="isFunc">取得条件</param>
	template<class T,
    	std::enable_if_t<std::is_base_of_v<I_Tuple, T>, std::nullptr_t> = nullptr> //基底クラスの制約
	std::shared_ptr<T> Take(
		const std::function<bool(const std::shared_ptr<T>&)>& isFunc = [](const std::shared_ptr<T>&) { return true; }
	) {
		auto tuple = SearchTuple<T>(isFunc);
		if (!tuple) {	//タプルが存在しないならnullptr
			return nullptr;
		}

		//削除する
		RemoveTuple<T>(tuple);

		return tuple;
	}

	/// <summary>
	/// 条件が一致する命令が受信されたら、通知を受け取る。
	/// </summary>
	/// <param name="requester">登録者</param>
	/// <param name="func">呼び出したい処理</param>
	/// <param name="isCall">呼び出し条件</param>
	template<class T,
		std::enable_if_t<std::is_base_of_v<I_Tuple, T>, std::nullptr_t> = nullptr>	//基底クラスの制約
	void Notify(
		const std::shared_ptr<I_Tupler> requester,
		const std::function<void(const std::shared_ptr<T>&)>& func, 
		const std::function<bool(const std::shared_ptr<T>&)>& isCall = [](const std::shared_ptr<T>& tuple) { return true; }
	) {
		auto typeIndex = type_index(typeid(T));	//型インデックスの取得

		auto newNotify = std::make_shared<NotifyController<T>>(requester, func, isCall);

		if(IsSomeNotify<T>(newNotify)){	//同じ通知登録なら登録しない。
			return;
		}

		m_notifysMap[typeIndex].push_back(newNotify);	//Notipyの生成
	}

最後に

ここまでの実装で動画のような動きが実現できます。
最後まで読んでいただき、ありがとうございます。
今後はより人間らしい動きを実現するためのステートの追加や影響マップを考慮した状態遷移を実装予定です。
AI実装の助けに少しでもなれば幸いです。