Table of Contents

ゲーム開発者の教科書：Game Programming in C++ を読んで理解したことについてを要約します（内容の転載を避け、詳しく説明しすぎないように配慮します）

ゲームプログラミング in C++

人工知能（AI）

ゲームでの人工知能アルゴリズムは、コンピュータが制御するエンティティ（entity）の行動を決めるのに使われる

ここでは、ステートマシンによる振る舞い、エンティティが移動する経路を計算する経路探索（pathfinding）、2人が交換でプレイするターン制の対戦ゲームでの思考に使うゲーム木やミニマックス法を使った"タワーディフェンス"型のゲームについて考える

ステートマシンの振る舞い

以下は実装内容である

それぞれの状態の実装を別々の派生クラスに入れることで、状態のカプセル化を単純にでき、別のAIキャラクターで状態を簡単に再利用することができる

ステートマシンを設計する

状態そのものは、ステートマシンを部分的にしか定義しない

状態の変化を決定する状態間の遷移も重要であり、状態に入る時や出る時に発生するアクションがあることがある

ステルスゲームの護衛キャラを考えるとわかりやすい

基本的なステートマシンの実装

AIComponent.h

状態の振る舞いをカプセル化する

AIComponent.cpp

AIComponent::Update()

ステルスゲームの護衛キャラの場合（P96図4.1）、それぞれの状態に1個ずつの更新関数、UpdatePatrol、UpdateDeath、UpdateAttackを用意する

AIStateクラスのメンバ関数で現在の状態を判定し、個々の状態に対する更新関数を呼び出す

クラスとしての状態

AIState.h

状態を個別のクラスで表現する

この基底クラスには、状態を制御する仮想関数が含まれており、状態を更新するUpdate()、遷移に入る際の処理OnEnter()、遷移から出る際の処理OnExit()を実装する

メンバ変数mOwnerを通して、AIComponentがAIStateに関連つけられる

AIComponent.h

コンストラクタAIComponent()と、状態を判定して更新関数を呼び出すUpdate()、ステートマシンの遷移を処理するChangeState()を宣言する

連想配列std::unorderd_map<std::string, class AIState*> mStateMapと、現時点のAIStateへのポインタmCurrentStateを持つ

RegisterState()は新たな状態を連想配列に登録する

AIComponent.cpp

AIComponent::Update()

現在の状態があれば、そのUpdate()を呼び出す

if (mCurrentState){
	mCurrentState->Update(deltatime);
}

AIComponent::ChangeState()

現在の状態のOnExit()を呼び出し、変更先となる状態を連想配列で探す

新たな状態が見つかれば、mCurrentStateをその状態に変更して、新しい状態のOnEnterを呼び出す

if (mCurrentState) {
	mCurrentState->OnExit();
}
auto iter = mStateMap.find(name);
if (iter != mStateMap.end()) {
	mCurrentState = iter->second;
	mCurrentState->OnEnter();
}
else {
	SDL_Log("Could not find AIState %s in state map", name.c_str());
	mCurrentState = nullptr;
}

AIComponent::RegisterState()

AIStateのポインタを受け取って、その状態を連想配列に追加する

mStateMap.emplace(state->GetName(), state);

AIPatrol.h

AIStateの派生クラス

特別な振る舞いがある場合は、Update()、OnEnter()、OnExit()で実装する

AIPatrol::Update()

例えば、キャラクターが死ぬ時は新しい状態の名前を引数として、所有コンポーネントのChangeState()を呼び出す

ChangeState()が呼び出されると、AIComponentは連想配列std::unordered_map<std::string, class AIState*> mStateMapを調べ、もしDeathという名前の状態があったら、その状態に遷移する（AIDeathとAIAttackのクラスも同様）
※連想配列std::unorderd_mapのメンバ関数find()を利用（ドキュメント）

Game::LoadData()

状態クラスをAIComponentの連想配列に登録するには、アクターとそのAIComponentを作成してから、引数に"ステートマシンに加えたい状態"を指定してRegisterState()を呼び出す

AIComponentをPatrolで初期化するにはChangeState()を呼び出す

経路探索

経路探索（pathfinding）は、2点間の経路を見つけるアルゴリズムである

グラフ

ゲームワールドの各部を表現する方法として、グラフ構造がよく使われる

グラフはノードを複数持ち、エッジでノード間をつなぐ

無向・有向エッジの例えとして、高台から地面にジャンプできても、元の場所には戻れない場合を有効エッジで表現できる

エッジの重みは、砂の上での移動とアスファルトの上での移動の表現などで利用される

メモリ空間でグラフを表現する隣接リスト（adjacency list）は、各ノードが隣接するノードの集合（std::vector）の情報を持つ

重み無しグラフの場合、隣接リストは各ノードmNodesを格納し、各ノードは隣接するノードへのポインタmAdjacentで構成される

struct GraphNode{
	std::vector<GraphNode*> mAdjacent;
};

struct Graph{
	std::vector<GraphNode*> mNodes;
};

重み付きグラフの場合、隣接リストはノードから出ていくエッジmEdgesを格納し、エッジはつながるノードmFrom、mToとエッジの重みmWeightで構成される

struct WeightedEdge{
	struct WeightGraphNode* mFrom;
	struct WeightGraphNode* mTo;
	float mWeight;
};

struct WeightedGraphNode{
	std::vector<WeightedEdge*> mEdges;
};

グラフでゲームワールドを表現する方法として、正方形や正六角形の格子（グリッド）で分割するのがシンプルなアプローチである

幅優先探索

迷路のどこかの開始ノードから、目的物がある終了ノードまでの最短経路を見つけるとする

最初に開始点から1手先の全ての行き先をチェックし、目標物がなければ次は開始点から2手先の行き先をチェックする

つまり、近いノードを調べ尽くしてからでなければ、より遠いノードを考慮しないので、漏れがない

この考え方が幅優先探索（breadth-first search:BFS）という
BFSアルゴリズムの参考記事

このBFSアルゴリズムは、エッジに重みが無い、もしくはどのエッジにも同じ正の重みが付いている時に、最短経路を見つけることが保証される

実装では、NodeToPointerMapというハッシュ連想配列（std::unorderd_map）を定義し、キーと値の両方でGraphNodeポインタをもたせる

using NodeToParentMap = 
	std::unordered_map<const GraphNode*, const GraphNode*>;

キュー（待ち行列）を使ってBFSを実装する

最初のノードをキューに入れた状態からループ処理を始める

ノードの1つを取り出し、そのノードに隣接するノード群をキューに追加する（すでに追加済みのノードでないかのチェックを行う）

bool BFS(const Graph& graph, const GraphNode* start, const GraphNode* goal, NodeToParentMap& outMap){
	bool pathFound = false;
	std::queue<const GraphNode*> q;
	// enqueue
	while (!q.empty){
		// dequeue
		const GraphNode* current = q.front();
		q.pop();
		if (current == goal){
			pathFound = true;
			break;
		}
		for (const GraphNode* node : current->mAdjacent){
			const GraphNode* parent = outMap[node];
			if (parent == nullptr && node != start){
				outMap[Node] = current;
				q.emplace(node);
			}
		}
	}
	return pathFound;
}

Graphgがあるとして、それに含まれる2つのGraphNode間でBFSを実行するには、以下のようにする

NodeToParentMap map;
bool found = BFS(g, g.mNodes[0], g.mNodes[9], map);

最終的に、outMapに入っている親ポインタを使って、親ポインタの連鎖をたどれば、いつかは開始ノードに到達して終点から始点に至る経路が得られる

これを始点から終点に至る経路を得るために、始点と終点を反対にする

ヒューリスティック

多くの探索アルゴリズムは、予想される結果の近似値を求めるヒューリスティック（発見的手法）に依存する

BFSの反復処理においてヒューリスティックを使うと、各ノード終点までの距離を見積もり、より少ない回数で線形探索を行うことができる

ヒューリスティックを$h(x)$と表記すると、$h(x)$はノード$x$から終点ノードへのコストの見積もりと考えることができる

後述するA* アルゴリズムでは、見積もりがノード$x$から終点に至る実際のコストを上回らない許容的ヒューリスティック関数が必要となる

正方形のグリッドを考えた時、ヒューリスティックの計算方法はマンハッタン距離のヒューリスティックとユークリッド距離のヒューリスティックの2種類がある

マンハッタン距離 $h(x)=|start.x - end.x|+|start.y - end.y|$

ユークリッド距離 $h(x)=\sqrt{(start.x - end.x)^2 + (start.y - end.y)^2}$

ユークリッド距離の関数のヒューリスティックが通常では推奨されるが、マンハッタン距離の計算のほうが効率が良い

ヒューリスティックは、ノード$x$が、少なくともそれだけ遠くにあることを保証する（つまり、どのノードが終点ノードに近いかを見積もるのに役立つ）

GameDev #4 人工知能 [Devlog #017]

ゲームプログラミング in C++

人工知能（AI）

ステートマシンの振る舞い

ステートマシンを設計する

基本的なステートマシンの実装

AIComponent.h

AIComponent.cpp

AIComponent::Update()

クラスとしての状態

AIState.h

AIComponent.h

AIComponent.cpp

AIComponent::Update()

AIComponent::ChangeState()

AIComponent::RegisterState()

AIPatrol.h

AIPatrol::Update()

Game::LoadData()

経路探索

グラフ

幅優先探索

ヒューリスティック

欲張り最良優先探索（GBFS）

A* 探索

ダイクストラのアルゴリズム

経路をたどる

その他のグラフ表現

ゲーム木

ミニマックス法

不完全なゲーム木の扱い方

アルファ・ベータ法