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