【C++】ダンジョン作成プログラム

ダンジョン作成プログラムを作りました。ダンジョン作成関数には、MI値（密度）を実装し、棒倒し法を少しだけアレンジしています。ダンジョン内の経路探索関数も実装しました。
もう少しコードを整形してから、ダンジョンDLLにコンパイルすれば使えるかもしれません。

作成したプログラム

C＋＋で作成したプログラムです。

#include <iostream>
#include <vector>
#include <string>
#include <cstdlib>
#include <ctime>
#include <queue>

using namespace std;

// 迷路のサイズ定義
const int ROWS = 19;
const int COLS = 19;

// 迷路の要素定義
const string PASSABLE = "0"; // 通過可能
const string WALL = "#"; // 通過不可能
const int MI = 7; // 迷宮密度(1-10)

// 迷路を表示する関数
void printMaze(const vector<vector<string>>& maze) {
	// 迷路の幅を取得
	int mazeWidth = maze[0].size();

	for (const auto& row : maze) {
		for (const auto& cell : row) {
			// セルが空の場合は空白を出力
			if (cell.empty()) {
				std::cout << "  ";
			}
			else {
				// セルの値を出力
				if (cell == "0") {
					std::cout << " ";
				}
				else {
					std::cout << cell;
				}
				// セルの値が1桁の場合は1つの空白を追加
				//if (cell.size() == 1) {
				//	std::cout << " ";
				//}
			}
			// セル間のスペースを追加
			std::cout << " ";
		}
		std::cout << endl;
	}
}

// 迷路を表示する関数（最短経路を表示）
void printPathMaze(const vector<vector<string>>& maze, const vector<pair<int, int>>& shortestPath) {
	// 迷路の幅を取得
	int mazeWidth = maze[0].size();

	for (int i = 0; i < maze.size(); ++i) {
		for (int j = 0; j < maze[i].size(); ++j) {
			pair<int, int> currentCell = make_pair(i, j);
			// セルが最短経路上にある場合は歩数を表示
			auto it = find(shortestPath.begin(), shortestPath.end(), currentCell);
			if (it != shortestPath.end()) {
				// 最短経路上のセルの場合
				cout << ":" << " ";
			}
			else {
				// 最短経路上のセルでない場合
				if (maze[i][j].empty() || maze[i][j] == "0") {
					cout << "  ";
				}
				else {
					cout << maze[i][j] << " ";
				}
			}
		}
		cout << endl;
	}
}


//数字があるマスの周囲に空白があれば、数字+1の値を書き込む
void aroundCellsCount(vector<vector<string>>& maze, int y, int x) {

	if (maze[y][x] != "" && maze[y][x] != WALL) {

		int n = 0;
		try {
			// 文字列から整数に変換
			n = std::stoi(maze[y][x]);
			n++;
			if (n > 0) {
				//上が通れるなら
				if (maze[y - 1][x] == "") {
					maze[y - 1][x] = to_string(n);
				}
				//右が通れるなら
				if (maze[y][x + 1] == "") {
					maze[y][x + 1] = to_string(n);
				}
				//下が通れるなら
				if (maze[y + 1][x] == "") {
					maze[y + 1][x] = to_string(n);
				}
				//左が通れるなら
				if (maze[y][x - 1] == "") {
					maze[y][x - 1] = to_string(n);
				}
			}
		}
		catch (const std::invalid_argument& e) {
			// 文字列が整数に変換できない場合の処理
			std::cout << "Conversion failed! (Invalid argument): " << maze[y][x] << std::endl;
		}
		catch (const std::out_of_range& e) {
			// 文字列が範囲外の整数に変換される場合の処理
			std::cout << "Conversion failed! (Out of range): " << e.what() << std::endl;
		}
	}
}

//入口出口が全て行き来できればOKとする
bool checkMaze(vector<vector<string>>& maze) {
	int halfCols = COLS / 2, halfRows = ROWS / 2;

	//全ての出入口前に繋がっていればOKとする
	if (maze[1][halfCols] == WALL || maze[ROWS - 2][halfCols] == WALL || maze[halfRows][1] == WALL || maze[halfRows][COLS - 2] == WALL) {
		return false;
	}

	return true;
}

//迷宮配列の作成
void generateRandomMaze(vector<vector<string>>& maze) {

	//ランダム値の初期化
	srand(time(nullptr));

	do {
		//柱を立てる 
		for (int y = 1; y < ROWS - 1; y++) {
			for (int x = 1; x < COLS - 1; x++) {
				int r = rand() % 10; //迷宮の密度
				if (x % 2 == 0 && y % 2 == 0 && r <= MI) {
					maze[y][x] = WALL;
				}
				else {
					maze[y][x] = PASSABLE;
				}
			}
		}

		//簡易迷路の作成
		for (int y = 1; y < ROWS - 1; y += 2) {
			for (int x = 1; x < COLS - 1; x += 2) {
				int r = rand() % ( 4 +  (10 - MI)); //迷宮の密度

				if (r == 0) {
					maze[y - 1][x] = WALL;
				}
				if (r == 1) {
					maze[y][x + 1] = WALL;
				}
				if (r == 2) {
					maze[y + 1][x] = WALL;
				}
				if (r == 3) {
					maze[y][x - 1] = WALL;
				}
			}
		}

		//迷宮の調整
		//歩行不可能なマスを埋める
		//入口出口のマスを歩行可能にする
		//全ての空白マスに歩行可能
		// 
		//mazeのマスクを作成
		vector<vector<string>> mask_maze = maze;
		int halfCols = COLS / 2, halfRows = ROWS / 2;
		
		//テスト開始地点
		mask_maze[1][halfRows] = "1";

		//MASK　通過可能な場所に""を挿入
		for (int y = 1; y < ROWS; y++) {
			for (int x = 1; x < COLS; x++) {
				if (mask_maze[y][x] == PASSABLE) {
					mask_maze[y][x] = "";
				}
			}
		}

		//歩行可能なマスに歩数を入れる
		for (int z = 0; z < (ROWS + COLS); z++) {
			for (int y = 1; y < ROWS; y++) {
				for (int x = 1; x < COLS; x++) {
					aroundCellsCount(mask_maze, y, x);
				}
			}
		}

		//到達不能のマスをWALLで埋める
		for (int y = 1; y < ROWS; y++) {
			for (int x = 1; x < COLS; x++) {
				if (mask_maze[y][x] == "") {
					mask_maze[y][x] = WALL;
				}
			}
		}

		//mask_mazeをmazeに上書きする
		for (int y = 0; y < ROWS; y++) {
			for (int x = 0; x < COLS; x++) {
				if (mask_maze[y][x] == WALL) {
					maze[y][x] = mask_maze[y][x];
				}
				else {
					maze[y][x] = PASSABLE;
				}
			}
		}
		//空白マスは全て到達可能を保障する

		//全ての出入り口前に到達可能か?
	} while (!checkMaze(maze));
}

// スタート座標からゴール座標までの最短経路を探索する関数
vector<pair<int, int>> findShortestPath(const vector<vector<string>>& maze, pair<int, int> start, pair<int, int> goal) {
	// 移動方向
	static const int dx[] = { 0, 0, -1, 1 };
	static const int dy[] = { -1, 1, 0, 0 };

	// スタートからの距離を管理する配列
	vector<vector<int>> distance(ROWS, vector<int>(COLS, INT_MAX));
	distance[start.first][start.second] = 0;

	// BFS（幅優先探索）による最短経路探索
	queue<pair<int, int>> q;
	q.push(start);

	while (!q.empty()) {
		pair<int, int> current = q.front();
		q.pop();

		// ゴールに到達したら終了
		if (current == goal) {
			break;
		}

		for (int i = 0; i < 4; ++i) {
			int nx = current.first + dx[i];
			int ny = current.second + dy[i];

			// 移動先が迷路の範囲内であり、通行可能かつ未探索であれば探索を続行
			if (nx >= 0 && nx < ROWS && ny >= 0 && ny < COLS && maze[nx][ny] == PASSABLE && distance[nx][ny] == INT_MAX) {
				distance[nx][ny] = distance[current.first][current.second] + 1;
				q.push(make_pair(nx, ny));
			}
		}
	}

	// ゴールに到達できなかった場合は空の経路を返す
	if (distance[goal.first][goal.second] == INT_MAX) {
		return vector<pair<int, int>>();
	}

	// 最短経路を復元する
	vector<pair<int, int>> shortestPath;
	pair<int, int> current = goal;
	shortestPath.push_back(current);

	while (current != start) {
		for (int i = 0; i < 4; ++i) {
			int nx = current.first + dx[i];
			int ny = current.second + dy[i];

			if (nx >= 0 && nx < ROWS && ny >= 0 && ny < COLS && distance[nx][ny] == distance[current.first][current.second] - 1) {
				current = make_pair(nx, ny);
				shortestPath.push_back(current);
				break;
			}
		}
	}

	// 最短経路を逆順にする
	reverse(shortestPath.begin(), shortestPath.end());

	return shortestPath;
}

int main(int argc, char* argv[]) {

	// 迷路の二次元配列を作成し、すべてを壁で初期化する
	vector<vector<string>> maze(ROWS, vector<string>(COLS, WALL));

	// 外枠を生成し、出発地点とゴール地点を設定する
	generateRandomMaze(maze);

	// 迷路を表示する
	printMaze(maze);

	// スタート座標とゴール座標を設定する
	pair<int, int> start = make_pair(1, COLS / 2);
	pair<int, int> goal = make_pair(ROWS - 2, COLS / 2);

	// 最短経路を探索する
	vector<pair<int, int>> shortestPath = findShortestPath(maze, start, goal);
	
	// 最短経路を表示する
	cout << "Shortest Path:" << endl;
	for (const auto& cell : shortestPath) {
		cout << "(" << cell.first << ", " << cell.second << ") -> ";
	}
	cout << endl;

	cout << "Maze with Shortest Path:" << endl;
	printPathMaze(maze, shortestPath);

	return 0;
}

実行結果

　MI＝１０　の実行結果

　MI＝１の実行結果
　実行するたびに、新しいダンジョンが作成されます。
　main関数を見れば使用方法はわかると思います。

思ったこと

　迷宮を作るアルゴリズムを調べてみたら色々あるのですね。
　今回は棒倒し法という簡単なアルゴリズムを使って迷宮を作成したのですが、たどり着けないセルができてしまうため、目的のマップになるまで繰り返し作成させる、ガチャ手法を取り入れましたｗ
　ダンジョンの密度は、柱や壁の出現をランダムで出現させないというものです。
　スッカスカのダンジョンがあってもいいかなと思い、MI値を導入しました。
　ダンジョンの実体について、以前は２次元配列を使っていましたが、ChatGPT先生が
　　　　Vector
を強く勧めてくるので、初めて使用しました。
　配列の要素数を後から変更できるのが強みのようですが、メモリ的にはちょっと気持ちが悪いです（古い人間）
　もう少しコードを整形し、DLL化して、ゲームを作るときに使いまわしたいと思っています。