/****************************
	Maze - Digging Method
*****************************/

/* 定数等 */
// 通路・壁情報
#define	MAX_SIZE	99		// 変更可−99以上でも問題ない
#define	MIN_SIZE 	5		// 最低でも5以上は必要
#define Path 		0
#define Wall 		1
// 方向
const int Up		= 0;
const int Right		= 1;
const int Down		= 2;
const int Left		= 3;
const int Direction = 4;

/* クラス定義 */
// 2次元（x, y）座標変数型
class CELL {
public:
    int x;  // x 座標
    int y;  // y 座標
	CELL() {x = y = 0;}
	CELL(int X, int Y) {x = X; y = Y;}
	void Set(int X, int Y) {x = X; y = Y;}
	void operator = (CELL i) {this->x = i.x; this->y = i.y;}
	bool operator == (CELL c) {return (this->x == c.x && this->y == c.y);}
	bool operator != (CELL c) {return (this->x != c.x || this->y != c.y);}
};

// CELLを対象としたスタック管理変数型
class CELLSTACK {
private:
	unsigned int stacklevel;
	CELL *cellptr[MAX_SIZE * MAX_SIZE];
public:
	// コンストラクター
	CELLSTACK() {stacklevel = 0;}
	// デコンストラクター
	~CELLSTACK(){
		while(stacklevel > 0) {
			stacklevel--;
			delete cellptr[stacklevel];
		}	// stacklevel = 0;は不要
	}
	// スタックに積む
	void Push(CELL cel) {
		if(stacklevel < MAX_SIZE * MAX_SIZE) {
			cellptr[stacklevel] = new CELL;
			*cellptr[stacklevel] = cel;
			stacklevel++;
		}
		else {
			MessageBox(0, "Stack overflow!", "Error!", MB_OK | MB_ICONERROR);
			exit(0);
		}
	}
	// FILOベースでスタックから取り出し解放する
	CELL Pop() {
		CELL cel;
		stacklevel--;
		cel = *cellptr[stacklevel];
		delete cellptr[stacklevel];
		return cel;
	}
	// 任意のi番目（0〜）のスタックデータを取り出し解放する
	CELL Pop(int i) {
		CELL cel = *cellptr[i];
		for(int j = i; j < stacklevel - 1; j++)
			*cellptr[j] = *cellptr[j + 1];
		stacklevel--;
		delete cellptr[stacklevel];
		return cel;
	}
	// スタックサイズを返す
	unsigned int Size() {return stacklevel;}
	// 特定のCELLデータを検索する（あればその位置（1〜）、なければ0を返す）
	unsigned int Find(CELL cel) {
		for(int i = 0; i < stacklevel; i++) {
			if(*cellptr[i] == cel)
				return i + 1;
		}
		return 0;
	}
	// 初期化する
	void Clear() {
		while(stacklevel > 0) {
			stacklevel--;
			delete cellptr[stacklevel];
		}	// stacklevel = 0;は不要
	}
};

// 迷路クラス
class MAZE {
private:
	/* 変数 */
	// 迷路情報
	int *m_Mazedata;		// 2次元配列の迷路データへのポインター
	int m_Width;			// 迷路幅
	int m_Height;     		// 迷路高
	// 穴掘り開始候補座標記録用変数
	CELLSTACK m_StartPoints;

	/* プライベート関数 */
	// x, yを始点として穴を掘る
	void Dig(int x, int y) {
		// 掘り進められる方向リストを作成
		while (TRUE) {
		// 掘り進められる方向を記録
			int i = 0, dirs[Direction] = {-1};
			if(y > 1 && m_Mazedata[x + m_Width * (y - 1)] == Wall && m_Mazedata[x + m_Width * (y - 2)] == Wall) {
				dirs[i]= Up;
				i++;
			}				
			if(x < m_Width - 1 && m_Mazedata[x + 1 + m_Width * y] == Wall && m_Mazedata[x + 2 + m_Width * y] == Wall) {
				dirs[i]= Right;
				i++;
			}
			if(y < m_Height - 1 && m_Mazedata[x + m_Width * (y + 1)] == Wall && m_Mazedata[x + m_Width * (y + 2)] == Wall) {
				dirs[i]= Down;
				i++;
			}
			if(x > 1 && m_Mazedata[x - 1 + m_Width * y] == Wall && m_Mazedata[x - 2 + m_Width * y] == Wall) {
				dirs[i]= Left;
				i++;
			}
			// 掘り進められない場合、ループを抜ける
			if(!i) {
				break;
			}
			// 指定座標を通路とし、穴掘り候補座標登録
			SetPath(x, y);
			// 進める方向をランダムに選択し、先2ブロックを通路とする
			switch(dirs[rand() % i]) {
				case Up:
					SetPath(x, --y);
					SetPath(x, --y);
					break;
				case Right:
					SetPath(++x, y);
					SetPath(++x, y);
					break;
				case Down:
					SetPath(x, ++y);
					SetPath(x, ++y);
					break;
				case Left:
					SetPath(--x, y);
					SetPath(--x, y);
					break;
			}
		}
		// どこにも掘り進められない場合、他の穴掘り開始候補座標を取得
		CELL pt;
		if(GetStartPoint(&pt)) {	// 開始候補があれば
			Dig(pt.x, pt.y);		// 再帰呼び出し
		}
		// 候補座標が存在しないとき、穴掘り完了
	}

	// 座標を通路とし、x, yが共に奇数の「穴掘り開始座標候補」をリストに記録
	void SetPath(int x, int y) {
		m_Mazedata[x + m_Width * y] = Path;
		if (x % 2 == 1 && y % 2 == 1) {
			// 穴掘り候補座標の記録
			CELL pt(x, y);
			m_StartPoints.Push(pt);
		}
	}

	// 穴掘り開始位置をランダムに取得する（CELL変数ポインター渡し）
	bool GetStartPoint(CELL* pt) {
		int num = m_StartPoints.Size();
		// 開始位置候補がない場合
		if(!num)
			return FALSE;
		// 開始位置候補がある場合、ランダムに候補を取得して削除する
		else {
			*pt = m_StartPoints.Pop(rand() % num);
			return TRUE;
		}
	}

public:
	// 迷路規模無指定コンストラクター
	MAZE() {
		//乱数（rand()）の初期化
		srand((unsigned int)time(NULL));
		// 迷路規模の指定がない場合、MAX_SIZE内で自動的に迷路規模を決定
		m_Width = rand() % MAX_SIZE;
		m_Height = rand() % MAX_SIZE;
		if (m_Width % 2 == 0)					// 幅が偶数であった場合
			m_Width++;
		if (m_Height % 2 == 0)				// 高さが偶数であった場合
			m_Height++;
		m_Mazedata = new int[m_Width * m_Height];	// 二次元配列を一次元で確保
	}

	// MAZE()コンストラクタの場合、迷路規模確認のために使う
	int GetW() {return m_Width;}
	int GetH() {return m_Height;}
	// 迷路データの取得のために使う
	int* GetMaze() {return m_Mazedata;}

	// 迷路規模指定コンストラクター
	MAZE(int w, int h) {	//迷路規模を指定したコンストラクター
		//乱数（rand()）の初期化
		srand((unsigned int)time(NULL));
		// MIN_SIZE未満のサイズや偶数では生成できない
		if (w < MIN_SIZE) {
			//MessageBox(hMainWnd, "Too narrow! Width is now 5.", "Error", MB_OK | MB_ICONERROR);
			MessageBox(0, "Too narrow! Width is now 5.", "Error", MB_OK | MB_ICONERROR);
			w = MIN_SIZE;
		}
		if (h < MIN_SIZE) {
			//MessageBox(hMainWnd, "Too low! Height is now 5.", "Error", MB_OK | MB_ICONERROR);
			MessageBox(0, "Too low! Height is now 5.", "Error", MB_OK | MB_ICONERROR);
			h = MIN_SIZE;
		}
		if (w % 2 == 0) {	//幅が偶数であった場合
			//MessageBox(hMainWnd, "As the given width is even, it is made +1.", "Caveat", MB_OK | MB_ICONERROR);
			MessageBox(0, "As the given width is even, it is made +1.", "Caveat", MB_OK | MB_ICONERROR);
			w++;
		}
		if (h % 2 == 0) {	//高さが偶数であった場合
			//MessageBox(hMainWnd, "As the given height is even, it is made +1.", "Caveat", MB_OK | MB_ICONERROR);
			MessageBox(0, "As the given height is even, it is made +1.", "Caveat", MB_OK | MB_ICONERROR);
			h++;
		}
		// 迷路情報を初期化
		m_Width = w;
		m_Height = h;
		m_Mazedata = new int[m_Width * m_Height];	// 二次元配列を一次元で確保
	}

	// デストラクタ
	~MAZE() {
		// Mazedataの配列メモリを解放（呼び出し側で迷路データを確保する必要がある）
		delete [] m_Mazedata;			// 配列の開放
	}

	// 迷路生作成
	int* CreateMaze() {
		// 迷路を壁で埋める
		for(int y = 0; y < m_Height; y++) {
			for(int x = 0; x < m_Width; x++) {
				if(x == 0 || y == 0 || x == m_Width - 1 || y == m_Height - 1)
					// 外壁は判定の為、一旦通路（Path = 0）にする
					m_Mazedata[x + m_Width * y] = Path;
				else
					m_Mazedata[x + m_Width * y] = Wall;
			}
		}
		// 座標（1, 1）から穴掘り開始−迷路の周囲は通路になっている
		Dig(1, 1);
		// 外壁を壁（Wall = 1）戻す
		for(int y = 0; y < m_Height; y++) {
			for(int x = 0; x < m_Width; x++) {
				if(x == 0 || y == 0 || x == m_Width - 1 || y == m_Height - 1)
					m_Mazedata[x + m_Width * y] = Wall;
			}
		}
		return m_Mazedata;	// 迷路データ（二次元整数配列）ポインターを返す
	}

	// 外部データによる幅、高さ、迷路データの設定
	void Set(int w, int h, int* data) {

		m_Width = w;		// 幅
		m_Height = h;		// 高さ
		if(m_Mazedata)
			delete [] m_Mazedata;
		m_Mazedata = new int[m_Width * m_Height];
		for(int y = 0; y < m_Height; y++) {
			for(int x = 0; x < m_Width; x++) {
				m_Mazedata[x + m_Width * y] = data[x + m_Width * y];	//迷路データ
			}
		}
	}
};
