1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
#include <iostream>
#include <array>
#include <stack>
#include <utility>
#include <vector>
#include <cstdlib>
#include "Tile.h"
#include "Maze.h"
#include <Windows.h>
using namespace std;
 
#define OneMaze    Maze::getMaze()
#define SEED    132270u
const int lineNum = 40;
array< array<Tile*, lineNum>, lineNum > maze;
 
void makeMaze(unsigned seed);
bool validCheckAndIsolate(unsigned x, unsigned y);
void printMaze();
 
int main() {
    unsigned i, j;
 
    for (i = 0; i < lineNum; i++) {
        for (j = 0; j < lineNum; j++) {
            maze[i][j] = new Tile();
        }
    }
 
    //가장자리 제외 출입 가능
    for (i = 1; i < lineNum - 1; i++) {
        for (j = 1; j < lineNum - 1; j++) {
            maze[i][j]->setCh(' ');        //디버깅용
            maze[i][j]->setEnterable(true);
        }
    }
    //실제 통로 연결-초기화(그래프 완성) ---이후 완성된 그래프에 대해서 하나의 타일의 enterable을 변경시킬 때의 변화를 (인접타일까지 5개의 타일 변함)함수로 작성하자.
    for (i = 1; i < lineNum - 1; i++) {
        for (j = 1; j < lineNum - 1; j++) {
            if (maze[i][j - 1]->getEnterable()) { maze[i][j]->setUp(maze[i][j - 1]); }
            if (maze[i][j + 1]->getEnterable()) { maze[i][j]->setDown(maze[i][j + 1]); }
            if (maze[i - 1][j]->getEnterable()) { maze[i][j]->setLeft(maze[i - 1][j]); }
            if (maze[i + 1][j]->getEnterable()) { maze[i][j]->setRight(maze[i + 1][j]); }
        }
    }
 
    //미로 만들기!
    makeMaze(SEED);
    //뷰!
    for (j = 0; j < lineNum; j++) {
        for (i = 0; i < lineNum; i++) {
            cout << maze[i][j]->getCh(); //test용 ch 출력.
        }
        cout << endl;
    }
 
    cout << "complete!" << endl;
 
 
    return 0;
}
 
void printMaze() {
    for (int j = 0; j < lineNum; j++) {
        for (int i = 0; i < lineNum; i++) {
            cout << maze[i][j]->getCh(); //test용 ch 출력.
        }
        cout << endl;
    }
    system("cls");
}
 
//Tile에 좌표를 넣지 않는 자료의 형태는 잠재적인 문제가... 많은 거 같다.
//4칸으로 구성될 게임의 1타일을 확대하는 일도 어렵다.
void makeMaze(unsigned seed) //아무리 생각해봐도, Tile에 직접 좌표를 할당하는게 여러모로 나을 거 같아. ... 음.... 아닌가..?
{
    stack<pair<unsigned,unsigned>> dfsStack;
    auto init = make_pair(1u, 1u);
 
    vector<pair<unsigned, unsigned>> valids;    //좌표쌍을 저장하는 배열(vector)
    pair<unsigned, unsigned> p;
    
    srand(seed); 
    dfsStack.push(init); 
    maze[ init.first ][ init.second ]->setDfsVisited(true);
    while ( !dfsStack.empty() ) {                                
                                                            maze[p.first][p.second]->setCh(' ');    
                                                            ///printMaze();
        p = dfsStack.top();
        maze[p.first][p.second]->setDfsVisited(true);
        //4방향 벽 체크 and 전개 가능 방향 저장
        if( validCheckAndIsolate(p.first, p.second-1) ){ valids.push_back( make_pair(p.first, p.second-1) ); }    ///printMaze();
        if( validCheckAndIsolate(p.first, p.second+1) ){ valids.push_back( make_pair(p.first, p.second+1) ); }    ///printMaze();
        if( validCheckAndIsolate(p.first-1, p.second) ){ valids.push_back( make_pair(p.first-1, p.second) ); }    ///printMaze();
        if( validCheckAndIsolate(p.first+1, p.second) ){ valids.push_back( make_pair(p.first+1, p.second) ); }    ///printMaze();
        // 다음 타일 진행.
        
        if (valids.size()) {
            auto next = valids[rand() % valids.size()];
            dfsStack.push(next);
            ///maze[next.first][next.second]->setCh('0');  //?? 이거 없어도 되야 되는데..?
        } else {
            dfsStack.pop();
        }
                                                                    ///printMaze();
        valids.clear();
    }
}
 
 
//미로는 오직 복도로 구성된다. 방은 없다. maze단계에서 관리.
//전개(dfsStack에 넣기) 가능하면 현재 pair반환, 전개 불가능(고립, 이미 방문함)하면 false반환.
bool validCheckAndIsolate(unsigned x, unsigned y)
{
    if (x >= lineNum || y >= lineNum) { //예외처리는 어쩔겨? lineNum... 
        cout << "이차원배열 범위 밖!" << endl;    
        return false;
    }    
    
    Tile& now = *maze[x][y];
    if( now.getDfsVisited()  ||  !now.getEnterable() ){
        return false;
    }
 
    const Tile& up        = *maze[x][y - 1];
    const Tile& down    = *maze[x][y + 1];
    const Tile& left    = *maze[x - 1][y];
    const Tile& right    = *maze[x + 1][y];
 
    /*
    밑에 거 최적화 가능함.
    결국 벽이 되지 않는다는 것은 1개의 방문한 타일과 인접함을 의미한다.
    1개 이상 인접하는 놈은 벽으로 만든다.
    */
 
    //정사각형 방지(시계방향)    
    if (up.getDfsVisited()        &&    right.getDfsVisited())    { now.isolate();    return false; }
    if (right.getDfsVisited()    &&    down.getDfsVisited())    { now.isolate();    return false; }
    if (down.getDfsVisited()    &&    left.getDfsVisited())    { now.isolate();    return false; }
    if (left.getDfsVisited()    &&    up.getDfsVisited())        { now.isolate();    return false; }
    //직사각형 방지
    if (up.getDfsVisited()        &&    down.getDfsVisited())    { now.isolate();    return false; }
    if (left.getDfsVisited()    &&    right.getDfsVisited())    { now.isolate();    return false; }
 
    //그대로!
    return true;
 
}
 
cs