ゲームプログラミングC++ 第4章：A*探索による最短経路の導出

はじめに

引き続き『ゲームプログラミングC++』についてまとめて記事にしました。
第四章は「ステートマシン」と「経路探索」についてやりますが、この記事は「A*探索」のみについてまとめます。
私が書いたコードは書籍で用意されてあるコードに比べて独自色が強い物になっていますが、よろしければ下記のレポジトリとともに参考にしてください。
(制作途中に何度も方針転換したため、かなりあやふやなコードになってますが大目に見てもらいたいです……。やる気があったら書き直そうと思います。)

概要

まずはA*探索についてざっくりとした手法や必要な要素をまとめます。
A*探索は「スタートからゴールまで隣接したノードの評価を繰り返すことで得たノード群から経路を復元する」というアルゴリズムです。ですから、評価と復元という二つの処理を行わなければなりません。

評価には各ノードからゴールまでの直線距離であるユークリッド距離H(x)とスタートから各ノードまでのコストの総量である経路コストG(x)その二つの合計値であるスコアF(x)を用います。ユークリッド距離で最短のノードを、経路コストでその道中に障害物があったとしても最適な経路を求めます。

復元には最後のノード、すなわちゴールからスタートまで辿る必要があります。将棋やチェスなどの移動に駒の種類以外の制限ないならただ単に最短のノードを配列で保持すべきです。ですが、一方通行の道や行動を阻害する要素を実装するためにはノード同士の繋がりに関する情報が必要です。ですから、移動元・移動先のノードと、移動先のノードの重みに関する情報を持つEdgeを用います。

以上から、経路探索に必要な情報はノードの座標と重み(コスト)、そしてノードごとの繋がりを表すEdgeの三つです。

データについて

今回は以下のような形でデータを表します

#pragma once
#include <vector>
#include "Math.h"
#include <memory>

using GridData = std::vector<std::vector<int>>;

struct Data	//一マスごとの情報
{
	Vector2 mCenterPos = Vector2::Zero;
	bool mHadTurret = false;
	int mTileType = -1;
};

using TileDatas = std::vector<std::vector<Data>>;

struct WeightedGraphNode;

struct WeightedEdge
{
	struct WeightedGraphNode* mFrom = nullptr;
	struct WeightedGraphNode* mTo = nullptr;

	float mWeight = 1.0f;
};

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

struct WeightedGraph
{
	std::vector<std::unique_ptr<WeightedGraphNode>> mNodes;
};

struct GameLevel	//ここでのlevelはマップ、面等の意味
{
	WeightedGraph graph;
	WeightedGraphNode* startNode = nullptr;
	WeightedGraphNode* goalNode = nullptr;
};

enum TileTypes
{
	NONE = -1,
	NORMALGROUND = 1,
	SELCTEDNORMALGROUND = 11,
	LOAD = 2,
	START = 100,
	GOAL = 200,
	TURRETBASEGROUND = 22
};

GridData及びTileMapDataはマップ全体のデータを持ち、タイルマップの描画やWeightedGraphの生成に用います。A*探索に用いるならGridDataで十分です。
GameLevelはA*探索で得たデータをAIが扱うために必要なデータを全て持っています。今回はA*探索のデータをGameLevelで受け渡しを行います。前節で書いたような情報は全てこの構造体で受け渡しすることができます。下に記載されている画像が分かりやすくなっていると思います。

前準備

マップには第二章の課題としてやったCSVファイルとタイルを用います。CSVファイルにはマップの構造が各タイルの種類で表されており、そのタイルの種類を二次元配列で保持したデータから、ノードグラフを作成します。

GameLevel MapLoaderComponent::BuildGraphFromGrid()
{
	GameLevel level;
	int height = static_cast<int>(mTileMap.size());
	if (height == 0) return level;
	int width = static_cast<int>(mTileMap[0].size());

	SDL_Log("BuildGraphFromGrid: width=%d, height=%d, tileSize=(%.1f, %.1f)", width, height, mTileSize.x, mTileSize.y);
	NodeGrid nodeGrid(height, std::vector<WeightedGraphNode*>(width, nullptr));
    //ノードを生成
	GenerateNodes(height, width, mTileSize, &level, &nodeGrid);

	//隣接ノードの設定
	ConnectEdges(height, width, nodeGrid);
	return level;
}

GenerateNodeではただの二次元配列であるGridDataから各マスの座標とEdgeを設定する必要がある特定のデータをnodeGridで保持します。また、この時にスタートノードとゴールノードも設定します。

void MapLoaderComponent::GenerateNodes(const int height, const int width, const Vector2& tileSize, GameLevel* outLevel, NodeGrid* outNodeGrid)
{
	for (int y = 0; y < height; ++y)
	{
		for (int x = 0; x < width; ++x)
		{
			float posX = static_cast<float>(x * tileSize.x + tileSize.x * 0.5f);
			float posY = static_cast<float>(y * tileSize.y + tileSize.y * 0.5f);
			mTileMap[y][x].mCenterPos = Vector2(posX, posY);

			int tileType = mTileMap[y][x].mTileType;
			if (tileType != TileTypes::NONE && tileType != TileTypes::NORMALGROUND)
			{
				std::unique_ptr<WeightedGraphNode> newNode = std::make_unique<WeightedGraphNode>();
				newNode->mPos = Vector2(posX, posY);
				
				WeightedGraphNode* rawNodePtr = newNode.get();

				if (tileType == TileTypes::START) outLevel->startNode = rawNodePtr;
				else if (tileType == TileTypes::GOAL) outLevel->goalNode = rawNodePtr;
				(*outNodeGrid)[y][x] = rawNodePtr;
				outLevel->graph.mNodes.emplace_back(std::move(newNode));
			}
		}
	}
}

ConnectEdgesではGenerateNodeで得たnodeGridから各方向(今回だったら4つ)のEdgeを設定します。ここで重みも設定します。

void MapLoaderComponent::ConnectEdges(const int height, const int width, const NodeGrid& nodeGrid)
{
	int dirX[] = { 0,0, -1, 1 };
	int dirY[] = { -1,1, 0, 0 };

	for (int y = 0; y < height; ++y)
	{
		for (int x = 0; x < width; ++x)
		{
			WeightedGraphNode* currentNode = nodeGrid[y][x];
			if (currentNode == nullptr) continue;

			for (int i = 0; i < 4; ++i)
			{
				int nx = x + dirX[i];
				int ny = y + dirY[i];

				if (nx >= 0 && nx < width && ny >= 0 && ny < height)
				{
					WeightedGraphNode* neighborNode = nodeGrid[ny][nx];
					if (neighborNode != nullptr)
					{
						WeightedEdge edge;
						edge.mFrom = currentNode;
						edge.mTo = neighborNode;
						edge.mWeight = STRAIGHT_COST;
						currentNode->mEdges.emplace_back(edge);
					}
				}
			}
		}
	}
}

A*探索

AStarScratchは各ノードのA*探索に必要な要素をまとめた構造体です。

• mParentEdgeは経路を復元する際に必要となります
• mHeuristicCost・mActualFromStartCostは概要に書いた通り、評価に使います
• mInOpenSet・mInClosedSetはA*探索を行う際にノードの状態管理するためのもので、OpenSetでは現在、評価対象となっているノードを表し、ClosedSetは評価し終わったノードを表します

AStarMapで各ノードとAStarScratchを結び付けます。

struct AStarScratch
{
	const WeightedEdge* mParentEdge = nullptr;	//経路復元用
	float mHeuristicCost = 0.0f;
	float mActualFromStartCost = 0.0f;
	bool mInOpenSet = false;
	bool mInClosedSet = false;
};

using AStarMap = std::unordered_map<const WeightedGraphNode*, AStarScratch>;

ComputeHeuristicはヒューリスティック距離を求める関数

float ComputeHeuristic(const WeightedGraphNode* mFrom, const WeightedGraphNode* goalNode)
{
	Vector2 diff = goalNode->mPos - mFrom->mPos;
	return diff.Length();
}

本来評価する際は優先度付きキューかバイナリヒープを利用するのが最速(計算量$O(1)$)ですが、今回はわかりやすさ優先でmin_element(計算量$O(n)$)を使いました。

std::vector<const WeightedGraphNode*> AStarSearch(const GameLevel& level)
{
	AStarMap nodeMap;		//各ノードごとの情報

	std::vector<const WeightedGraphNode*> openSet;

	const WeightedGraphNode* startNode = level.startNode;
	const WeightedGraphNode* goalNode = level.goalNode;

	if (!startNode || !goalNode)
	{
		SDL_Log("start or goal not exist");
		return {};
	}

	nodeMap[startNode].mInOpenSet = true;
	nodeMap[startNode].mInClosedSet = false;
	nodeMap[startNode].mHeuristicCost = ComputeHeuristic(startNode, goalNode);
	nodeMap[startNode].mActualFromStartCost = 0.0f;
	openSet.emplace_back(startNode);

	while (!openSet.empty())
	{
		//評価
		auto iter = std::min_element(
			openSet.begin(),
			openSet.end(),
			[&nodeMap](const WeightedGraphNode* a, const WeightedGraphNode* b)
			{
				float fa = nodeMap[a].mHeuristicCost + nodeMap[a].mActualFromStartCost;
				float fb = nodeMap[b].mHeuristicCost + nodeMap[b].mActualFromStartCost;
				return fa < fb;
			}
		);

		const WeightedGraphNode* currentNode = *iter;

		
		openSet.erase(iter);
		nodeMap[currentNode].mInOpenSet = false;
		nodeMap[currentNode].mInClosedSet = true;

		//経路の復元
		if (currentNode == goalNode)
		{
			std::vector<const WeightedGraphNode*> path;
			const WeightedGraphNode* curr = goalNode;
			while (curr != startNode && curr != nullptr)
			{
				path.emplace_back(curr);
				const WeightedEdge* parentEdge = nodeMap[curr].mParentEdge;		//親のエッジ(線)を取得
				if (parentEdge)
				{
					curr = parentEdge->mFrom;		//親ノードに移動
				}
				else
				{
					break;
				}
															
			}

			std::reverse(path.begin(), path.end());
			return path;
		}

		//隣のノードを調査
		for (const WeightedEdge& edge : currentNode->mEdges)
		{
			const WeightedGraphNode* neighbor = edge.mTo;
			AStarScratch& data = nodeMap[neighbor];
			if (data.mInClosedSet)
			{
				continue;
			}
            //newGは経路コスト
			float newG = nodeMap[currentNode].mActualFromStartCost + edge.mWeight;

			//オープンセットにない、またはより良い経路が見つかった場合、情報を更新
			if (!data.mInOpenSet || newG < data.mActualFromStartCost)
			{
				data.mActualFromStartCost = newG;
				data.mHeuristicCost = ComputeHeuristic(neighbor, goalNode);
				data.mParentEdge = &edge;
				if (!data.mInOpenSet)
				{
					data.mInOpenSet = true;
					openSet.emplace_back(neighbor);
				}
			}
		}

	}

	// ループを抜けた場合、経路が見つからなかったので空のパスを返す
	SDL_Log("goal not reached");
	return {};
}

このようにして求めたデータによって、AIを動かします。

最後に

初めは思い描いていたタワーディフェンスゲームを適当に作っていたのですが、その最中に何度もやり方を変えたり、果たして本当に必要かわからない変数が無数に出てきたりと、その無計画ぶりに苦労しました。次にゲームを作る際は行うべき処理やそれに必要なデータをよりしっかりとリストアップして堅固な土台を作れるように頑張りたいと思います。