穴掘り法再び（探索もするよ） [Yz-Learning Base Wiki]

迷路作って、表示できる
左上と右下にStartとGoalを設置
幅優先探索と深さ優先探索で、スタートからゴールまでの道のりを調べる
1. （一応ゴールまで行っても全探索しよう）
ゴールまでの歩数も調べる

Listing. 1: 穴掘り法、ループできないバージョン（バグとっただけ）

# include <Siv3D.hpp> // Siv3D v0.6.14
#include <numeric>
#include <stack>
#include <queue>
#include <map>
 
const Size BLOCK_SIZE{ 32, 32 };
const Size MazeSize{ 25, 19 };//サイズは奇数でなければいけない
const Point Start{ 1,1 };
const Point Goal{ MazeSize.x - 2,MazeSize.y - 2 };
 
 
enum OBJS
{
	WALL, BAR, FLOOR, START, GOAL, MAX_OBJS
};
 
//二次元配列　MazeData[MazeSize.y][MazeSize.x]{FLOORで初期化｝
std::vector<std::vector<int>> MazeData(MazeSize.y, std::vector<int>(MazeSize.x, FLOOR));
//std::vector<std::vector<int>> MazeDataForSearch(MazeSize.y, std::vector<int>(MazeSize.x, FLOOR));
//std::vector<std::vector<int>> MazeDataForDraw(MazeSize.y, std::vector<int>(MazeSize.x, FLOOR));
//std::vector<std::vector<int>> MazeDataForDigDraw(MazeSize.y, std::vector<int>(MazeSize.x, FLOOR));
std::stack<Point> prStack;
 
void AllWall(int w, int h);
void MakeMazeDigDug(int w, int h);
void DigDug(int x, int y);
void DrawMaze(int w, int h);
void MakeWall(int w, int h);
 
void DigDug(int x, int y)
{
	MazeData[y][x] = FLOOR;
	Point Dir[]{ {0,-1},{1, 0},{0, 1},{-1,0} };
	std::vector<int> dList;
	for (int i = 0; i < 4; i++) {
		//nextを0~3まで回してでたーを取得
		Point next = Point{ x, y } + Dir[i];
		Point nextNext = next + Dir[i];
 
		if (nextNext.x < 0 || nextNext.y < 0 || nextNext.x > MazeSize.x - 1 || nextNext.y > MazeSize.y - 1)
			continue;
 
		if (MazeData[nextNext.y][nextNext.x] == WALL)
		{
			dList.push_back(i);
		}
	}
	if (dList.empty())
	{
		return;
	}
	int nrand = rand() % dList.size();
	int tmp = dList[nrand];
 
	Point next = Point{ x, y } + Dir[tmp];
	Point nextNext = next + Dir[tmp];
 
	MazeData[next.y][next.x] = FLOOR;
	MazeData[nextNext.y][nextNext.x] = FLOOR;
 
	prStack.push(nextNext);
	DigDug(nextNext.x, nextNext.y);
}
 
 
void AllWall(int w, int h)
{
	for (int j = 0; j < h; j++)
	{
		for (int i = 0; i < w; i++) {
			if (i == 0 || j == 0 || i == w - 1 || j == h - 1)
				MazeData[j][i] = FLOOR;
			else
				MazeData[j][i] = WALL;
		}
	}
}
 
void MakeMazeDigDug(int w, int h)
{
	AllWall(w, h);
	Point sp{ 1, 1 };
	prStack.push(sp);
	while (!prStack.empty())
	{
		sp = prStack.top();
		prStack.pop();
		DigDug(sp.x, sp.y);
	}
}
 
void DrawMaze(int w, int h)
{
	for (int j = 0; j < h; j++)
	{
		for (int i = 0; i < w; i++)
		{
			Color col[MAX_OBJS]{ Palette::Firebrick,  Palette::Darkorange, Palette::Black,Palette::Yellow,Palette::Yellow };
			//if (MazeData[j][i] != FLOOR)
			Rect{ i * BLOCK_SIZE.x, j * BLOCK_SIZE.y, BLOCK_SIZE }.draw(col[MazeData[j][i]]);
			if (MazeData[j][i] == START) {
				Rect{ i * BLOCK_SIZE.x, j * BLOCK_SIZE.y, BLOCK_SIZE }.drawFrame(1, 1, col[MazeData[j][i]]);
			}
 
			if (MazeData[j][i] == GOAL) {
				Rect{ i * BLOCK_SIZE.x, j * BLOCK_SIZE.y, BLOCK_SIZE }.drawFrame(1, 1, col[MazeData[j][i]]);
			}
 
		}
	}
}
 
void MakeWall(int w, int h)
{
	for (int j = 0; j < h; j++)
	{
		for (int i = 0; i < w; i++)
		{
			if (i == 0 || j == 0 || i == w - 1 || j == h - 1)
				MazeData[j][i] = WALL;
			continue;
		}
	}
}
 
void Main()
{
	FontAsset::Register(U"NUM", 14, Typeface::Medium);
 
	srand((unsigned int)time(nullptr));
	// 背景の色を設定する | Set the background color
	Scene::SetBackground(Palette::Cornflowerblue);
 
	MakeMazeDigDug(MazeSize.x, MazeSize.y);
	MakeWall(MazeSize.x, MazeSize.y);
 
 
 
	while (System::Update())
	{
		DrawMaze(MazeSize.x, MazeSize.y);
	}
}

//const Size BLOCK_SIZE{ 32, 32 };
//const Size MazeSize{ 25, 19 };//サイズは奇数でなければいけない
//const Point Start{ 1,1 };
//const Point Goal{ MazeSize.x - 2,MazeSize.y - 2 };
//
//enum OBJS
//{
//	WALL, BAR, FLOOR, START, GOAL, MAX_OBJS
//};
//スタートとゴールのデータをセット
//void SetSG(int w, int h)
//{
//	MazeDataForSearch = MazeData; //元データは取っておく
//	MazeData[Start.y][Start.x] = START;
//	MazeData[Goal.y][Goal.x] = GOAL;
//}
 
//キューに
std::queue<std::pair<Point, int>> myQueue;
void BFS()
{
	//探索用 ←↑→↓⇒np[0],np[1],np[2],np[3]
	Point np[4]{ {0,-1},{1, 0},{0, 1},{-1,0} }; 
	//迷路には0~MAX_OBJS-1のオブジェクトが置かれている
　　　　//ので邪魔にならん番号を使っていく
	//step - MAX_OBJSが現在の探索ステップ数
	int step = MAX_OBJS;
	//キュースタート地点とステップ数を記録
	myQueue.push({ Start, step });
	//スタート地点のステップ数をstepに設定
	MazeDataForSearch[Start.y][Start.x] = step;
	//探索候補のキューが空ではない間探索を続行
	while ( XXXXXXXXXXX )
	{
		//キューから探索候補をとってくる
　　　　　　　　//(デキュー：C++の場合は.front()で参照して、必要なくなった.front()を.pop()で廃棄）
		std::pair<XXXXXXXXX,XXXXXXXX> Crr = XXXXXXXXX.XXXXXX();
		XXXXXXXXXXX.XXXXXX();
		//上のnp[]を使って自分の４近傍を探索
		for (int i = 0; i < 4; i++)
		{
			//上のnp[]を使って自分の４近傍を探索
			Point tmp = Crr.first + XXXXXXXXXXXX;
			//端っこだったら探索しない
			if (XXXXXXXXXXXXXXXXXX)
				continue;
			//隣がFLOOR（床）だったら進める！（探索候補として隣の位置（tmp.x, tmp.y）をセット）
			if (MazeDataForSearch[tmp.y][tmp.x] == XXXXXXX) {
				MazeDataForSearch[tmp.y][tmp.x] =XXXX;//ステップを1進めて
				myQueue.push({ XXXXXX, XXXXXXXXXXX});//キューに探索候補をセット
			}
		}
	}
}

穴掘り法再び（探索もするよ）

迷路探索課題

BFS（幅優先探索の実装）