# 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);
	}
}