C++で複雑かつ広大な迷路を作ってみた(穴掘り法かつ非再帰実装)

C++で迷路を作成した。探せばサンプルコードなんて沢山あるではないかと思われるかもしれない。

しかし、穴掘り法による迷路作成は再帰によるプログラムが多い。
このため、少し大きな迷路を作ろうとするとStack overflowを起こしてしまう。

そこで大きな迷路を作ることのできるアルゴリズムを探してみると、棒倒し法ばかりである。
棒倒し法だと簡易的な迷路しか作ることができない。

ざっと調べたところ穴掘り法も簡易アルゴリズムが存在しており、ループ対応しているのは簡易アルゴリズムの方ばかりであった。

なので、以下のアルゴリズムに従った複雑な迷路を作成するプログラムを作った。
①迷路を掘り進める方向をランダムで決定し、2セル先まで掘り進める。これを繰り返す。
②動けなくなったところで、掘り進めた奇数個所をスタート地点として①で掘り進める
③掘り進めた全奇数個所で掘り進められなくなった時に終了

完成像:

結構難しそうになってる

以下コード

#define ROAD 0
#define WALL 1

#include <iostream>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <vector>
#include <cstdlib>
#include <cassert>
#include <unordered_set>
#include <string>
#include <stdio.h>
#include <time.h>

using namespace std;



namespace mzg{
	class MazeGenerator
		{
		public:
			// Methods
			MazeGenerator(int _width, int _height);
			~MazeGenerator();
			void Initialize();
			void Generate(int _x, int _y);
			void Disp();
			void MazeGenerator::Generate_loop(int _init_x, int _init_y);
			vector< vector<bool> > boolMap();
			int randOdd(int _mod);
			vector< vector<int> > map;

			typedef pair<int, int> int_pair;
			vector<int_pair> moveHistory;

			int initialPositionX;
			int initialPositionY;
			int goalPositionX;
			int goalPositionY;
			int width;
			int height;

		private:
			struct {
				int x;
				int y;
			} dir[4] = {
				{ 0, -1 },
				{ 0, 1 }, 
				{ -1, 0 },
				{ 1, 0 } 
			};

		};

    	vector< vector<bool> >  MazeGenerator::boolMap()
		{
			vector< vector<bool> > bmap;

			// Create Array
			bmap.resize(this->height);

			for (int i = 0; i< this->height; i++) {
				bmap[i].resize(this->width);
				for (int j = 0; j < this->width; j++) {
					bmap[i][j] = (bool)this->map[i][j];
				}
			}
			return bmap;
		}

		void MazeGenerator::Disp()
		{
			int x, y;
			for (y = 0; y < this->height; y++) {
				for (x = 0; x < this->width; x++) {
					if (y == this->initialPositionY && x == this->initialPositionX) {
						printf("%c", 'S');
						continue;
					}
					if (y == this->goalPositionY && x == this->goalPositionX) {
						printf("%c", 'G');
						continue;
					}

					if (map[y][x] == WALL) {
						printf("%c", '#');
					}
					if (map[y][x] == ROAD) {
						printf("%c", ' ');
					}
				}
				printf("\n");
			}


			cout << "Initial Position x=" << this->initialPositionX << endl;
			cout << "Initial Position y=" << this->initialPositionY << endl;

			cout << "Initial Goal x=" << this->goalPositionX << endl;
			cout << "Initial Goal y=" << this->goalPositionY << endl;
		}


		MazeGenerator::MazeGenerator(int _width, int _height) {
			this->width = _width;
			this->height = _height;
		}


		int MazeGenerator::randOdd(int _mod) {
			int r = 1 + rand() % _mod;
			if (r % 2 == 0)
				r++;
			if (r > _mod)
				r -= 2;
			return r;
		}


		void MazeGenerator::Generate_loop(int _init_x, int _init_y) {
			int _x = _init_x;
			int _y = _init_y;
			int flag = -1;
			int tmp = -1;

			while (1) {
				int d = rand() % 4;
				int dd = d;

				if (flag != -1) {
					if (this->moveHistory.size() == 0) { break; }
					tmp = rand() % this->moveHistory.size();
					_x = this->moveHistory[tmp].first;
					_y = this->moveHistory[tmp].second;
					flag = 0;
				}

				while (1) {
					int px = _x + dir[d].x * 2;
					int py = _y + dir[d].y * 2;
					if (px < 0 || px >= this->width || py < 0 || py >= this->height || map[py][px] != WALL) {
						d++;
						if (d == 4)
							d = 0;
						if (d == dd) {
							flag = 1;
							if (tmp != -1) {
								this->moveHistory.erase(this->moveHistory.begin() + tmp);
							}
							break;
						}
						continue;
					}
					map[_y + dir[d].y][_x + dir[d].x] = ROAD;
					map[py][px] = ROAD;


					this->moveHistory.push_back(make_pair(px, py));
					this->goalPositionX = _x = px;
					this->goalPositionY = _y = py;
					dd = d = rand() % 4;
				}
			}

		}


		void MazeGenerator::Initialize() {

			// Initilize Time
			time_t t;
			time(&t);
			srand(t);

			// Create Array
			this->map.resize(this->height);
			for (int i = 0; i< this->height; i++) {
				this->map[i].resize(this->width);
				for (int j = 0; j < this->width; j++) {
					this->map[i][j] = WALL;
				}
			}

			// Initial Position
			this->initialPositionX = randOdd(this->width - 2);
			this->initialPositionY = randOdd(this->height - 2);
		}

}


int main() {
	mzg::MazeGenerator *mp = new mzg::MazeGenerator(51, 51);
	mp->Initialize();
	mp->Generate_loop(mp->initialPositionX, mp->initialPositionY);
	mp->Disp();
	vector< vector<bool> > bm = mp->boolMap();

	getchar();
	return 0;
}