VioletaBabel

52. A* 알고리즘 본문

BCA/1. C,C++,C#
52. A* 알고리즘
Beabletoet 2018. 7. 9. 17:48
멍청하니까 하드코딩함
2차원
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
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
#include<iostream>
#include<queue>
#include<functional>
#include<tuple>
#include<stack>
#include<Windows.h>
#include<string>
using namespace std;
struct aMap
{//각 블럭을 담을 구간
    int x;
    int y;
    bool block = false;
    bool check = false;
    int fPoint = 0;
    int gPoint = 0;
    int hPoint = 0;
    bool start = false;
    bool finish = false;
    aMap *parent = NULL;
};
aMap map[8][8];
priority_queue< tuple<int, int, int>, vector<tuple<int, int, int> >, greater<tuple<int, int, int> > > openMap;
bool firstOne = true;
int cMap[8][8];
void aStar(int sx, int sy, int fx, int fy, aMap *parent);
void Pr(WORD w, const char s);
void init(int startX, int startY, int finishX, int finishY);
int main()
{
    //값 초기화(블럭 위치와 맵 기본 값, 시작점 끝점)
    int startX = 1;
    int startY = 4;
    int finishX = 4;
    int finishY = 1;
    init(startX, startY, finishX, finishY);
    //A* 탐색 시작
    aStar(startX, startY, finishX, finishY, &(map[startY][startX]));
}
void init(int startX, int startY, int finishX, int finishY)
{
    for (int i = 0; i < 8; ++i)
        for (int j = 0; j < 8; ++j)
        {
            cMap[i][j] = 7;
        }
    cMap[startY][startX] = 6;
    cMap[finishY][finishX] = 6;
    for (int i = 0; i < 8; ++i)
        for (int j = 0; j < 8; ++j)
        {
            map[i][j].block = false;
            map[i][j].check = false;
            map[i][j].start = false;
            map[i][j].finish = false;
            map[i][j].fPoint = 0;
            map[i][j].gPoint = 0;
            map[i][j].hPoint = 0;
            map[i][j].parent = NULL;
            map[i][j].x = j;
            map[i][j].y = i;
        }
    //장애물 넣기 (block = 장애물 위치, cMap은 컬러 출력용)
    map[1][2].block = true;
    cMap[1][2] = 4;
    for (int i = 2; i < 6; ++i)
    {
        map[2][i].block = true;
        cMap[2][i] = 4;
    }
    map[3][3].block = true;
    map[4][3].block = true;
    cMap[3][3] = 4;
    cMap[4][3] = 4;
    map[1][1].block = true;
    cMap[1][1] = 4;
    map[1][0].block = true;
    cMap[1][0] = 4;
    //시작값, 끝값 구조체 배열에 기억시키기
    map[4][1].start = true;
    map[1][4].finish = true;
}
void aStar(int sx, int sy, int fx, int fy, aMap *parent = NULL)
{
    int nextx, nexty;
    map[sy][sx].block = true; // 탐색한 곳은 탐색했다고 넣어둠
    if (firstOne)
    {//최초 시작점 설정
        if (map[sy][sx].fPoint == 0)
        {
            map[sy][sx].parent = &map[sy][sx];
            int ry = (sy > fy) ? sy - fy : fy - sy;
            int rx = (sx > fx) ? sx - fx : fx - sx;
            map[sy][sx].gPoint = 0;
            map[sy][sx].hPoint = ry * 10 + rx * 10;
            map[sy][sx].fPoint = ry * 10 + rx * 10;
            map[sy][sx].check = true;
        }
        firstOne = false;
    }
    for (int i = sy - 1; i < sy + 2; ++i)
    {
        for (int j = sx - 1; j < sx + 2; ++j)
        {
            if (i < 0 || j < 0 || i>7 || j>7)//맵 밖을 탐색 시 continue
                continue;
            else if (!map[i][j].block && !map[i][j].check)
            {//아직 탐색하지 않은 블럭인 경우(벽인 경우는 block으로 거름)
                map[i][j].check = true;
                if (i == map[sy][sx].y || j == map[sy][sx].x)
                    map[i][j].gPoint = map[sy][sx].gPoint + 10;
                else
                    map[i][j].gPoint = map[sy][sx].gPoint + 14;
                int ry = (i > fy) ? i - fy : fy - i;
                int rx = (j > fx) ? j - fx : fx - j;
                map[i][j].hPoint = ry * 10 + rx * 10;
                map[i][j].fPoint = map[i][j].gPoint + map[i][j].hPoint;
                map[i][j].parent = &(map[sy][sx]);
                openMap.push(tuple<int, int, int>(map[i][j].fPoint, i, j));
            }
            else if (map[i][j].check && !(i == sy && j == sx))
            {//탐색 했던 곳이지만 새로운 루트와 f값을 비교할 경우 확인할 경우
                int g;
                if (i == parent->y || j == parent->x)
                    g = map[sy][sx].gPoint + 10;
                else
                    g = map[sy][sx].gPoint + 14;
                int ry = (i > fy) ? i - fy : fy - i;
                int rx = (j > fx) ? j - fx : fx - j;
                int h = ry * 10 + rx * 10;
                int f = g + h;
                if (map[i][j].fPoint > f)
                {
                    map[i][j].parent = &(map[sy][sx]);
                    map[i][j].fPoint = f;
                    map[i][j].gPoint = g;
                    map[i][j].hPoint = h;
                }
            }
        }
    }
    tuple<int, int, int> t = openMap.top();
    aMap a = map[get<1>(t)][get<2>(t)];
    openMap.pop();
    if (!openMap.empty())
    {//아직 탐색하지 않은 곳이 남았을 때
        aStar(a.x, a.y, fx, fy, &(map[sy][sx]));
    }
    else
    {//모두 탐색했을 때
        aMap go = map[fy][fx];
        stack<pair<int, int> > ans;
        while (1)
        {//끝점부터 역순으로 넣어주자
            ans.push(pair<int, int>(go.x, go.y));
            if (go.start)
                break;
            else
                go = *(go.parent);
        }
        while (!ans.empty())
        {//순서대로 값 출력
            if (cMap[ans.top().second][ans.top().first] != 6)
                cMap[ans.top().second][ans.top().first] = 2;
            cout << "(" << ans.top().first << ", " << ans.top().second << ")\n";
            ans.pop();
        }
        cout << endl;
        for (int i = 0; i < 8; ++i)
        {//눈으로 보이게 맵 출력
            for (int j = 0; j < 8; ++j)
            {
                if (cMap[i][j] == 4)
                    Pr(cMap[i][j], 'X');
                else
                    Pr(cMap[i][j], 'O');
            }
            cout << endl;
        }
    }
}
void Pr(WORD w, const char s)
{//맵 출력용 색깔 글씨 함수
    SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), w);
    cout << s;
}
cs


3차원

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
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
#include<iostream>
#include<queue>
#include<functional>
#include<tuple>
#include<stack>
#include<Windows.h>
#include<string>
using namespace std;
struct aMap
{//각 블럭을 담을 구간
    int x;
    int y;
    int z;
    bool block = false;
    bool check = false;
    int fPoint = 0;
    int gPoint = 0;
    int hPoint = 0;
    bool start = false;
    bool finish = false;
    aMap *parent = NULL;
};
aMap map[8][8][8];
priority_queue< tuple<int, int, int, int>, vector<tuple<int, int, int, int> >, greater<tuple<int, int, int, int> > > openMap;
bool firstOne = true;
void aStar(int sx, int sy, int sz, int fx, int fy, int fz, aMap *parent);
void init(int startX, int startY, int startZ, int finishX, int finishY, int finishZ);
int main()
{
    //값 초기화(블럭 위치와 맵 기본 값, 시작점 끝점)
    int startX = 0;
    int startY = 0;
    int startZ = 0;
    int finishX = 5;
    int finishY = 5;
    int finishZ = 5;
    init(startX, startY, startZ, finishX, finishY, finishZ);
    //A* 탐색 시작
    aStar(startX, startY, startZ, finishX, finishY, finishZ, &(map[startZ][startY][startX]));
}
void init(int startX, int startY, int startZ, int finishX, int finishY, int finishZ)
{
    for (int i = 0; i < 8; ++i)
        for (int j = 0; j < 8; ++j)
            for (int k = 0; k < 8; ++k)
            {
                map[i][j][k].block = false;
                map[i][j][k].check = false;
                map[i][j][k].start = false;
                map[i][j][k].finish = false;
                map[i][j][k].fPoint = 0;
                map[i][j][k].gPoint = 0;
                map[i][j][k].hPoint = 0;
                map[i][j][k].parent = NULL;
                map[i][j][k].x = k;
                map[i][j][k].y = j;
                map[i][j][k].z = i;
            }
 
 
    //장애물 넣기 (block = 장애물 위치, cMap은 컬러 출력용)
    for (int i = 2; i < 5; ++i)
        for (int j = 2; j < 5; ++j)
            for (int k = 2; k < 5; ++k)
            {
                map[i][j][k].block = true;
            }
 
    map[startZ][startY][startX].start = true;
    map[finishZ][finishY][finishX].finish = true;
}
 
void aStar(int sx, int sy, int sz, int fx, int fy, int fz, aMap *parent = NULL)
{
    int nextx, nexty;
    map[sz][sy][sx].block = true; // 탐색한 곳은 탐색했다고 넣어둠
    if (firstOne)
    {//최초 시작점 설정
        if (map[sz][sy][sx].fPoint == 0)
        {
            map[sz][sy][sx].parent = &map[sz][sy][sx];
            int ry = (sy > fy) ? sy - fy : fy - sy;
            int rx = (sx > fx) ? sx - fx : fx - sx;
            int rz = (sz > fz) ? sz - fz : fz - sz;
            map[sz][sy][sx].gPoint = 0;
            map[sz][sy][sx].hPoint = rz * 10 + ry * 10 + rx * 10;
            map[sz][sy][sx].fPoint = rz * 10 + ry * 10 + rx * 10;
            map[sz][sy][sx].check = true;
        }
        firstOne = false;
    }
    for (int k = sz - 1; k < sz + 2; ++k)
    {
        for (int i = sy - 1; i < sy + 2; ++i)
        {
            for (int j = sx - 1; j < sx + 2; ++j)
            {
                if (i < 0 || j < 0 || k < 0 || k > 7 || i>7 || j>7)//맵 밖을 탐색 시 continue
                    continue;
                else if (!map[k][i][j].block && !map[k][i][j].check && !(i == sy && j == sx && k == sz))
                {//아직 탐색하지 않은 블럭인 경우(벽인 경우는 block으로 거름)
                    map[k][i][j].check = true;
                    int diag = 0;
                    if (i != map[sz][sy][sx].y)
                        ++diag;
                    if (j != map[sz][sy][sx].x)
                        ++diag;
                    if (k != map[sz][sy][sx].z)
                        ++diag;
                    if (diag == 3)
                        map[k][i][j].gPoint = map[sz][sy][sx].gPoint + 17;
                    else if (diag == 2)
                        map[k][i][j].gPoint = map[sz][sy][sx].gPoint + 14;
                    else if (diag == 1)
                        map[k][i][j].gPoint = map[sz][sy][sx].gPoint + 10;
                    int ry = (i > fy) ? i - fy : fy - i;
                    int rx = (j > fx) ? j - fx : fx - j;
                    int rz = (k > fz) ? k - fz : fz - k;
                    map[k][i][j].hPoint = rz * 10 + ry * 10 + rx * 10;
                    map[k][i][j].fPoint = map[k][i][j].gPoint + map[k][i][j].hPoint;
                    map[k][i][j].parent = &(map[sz][sy][sx]);
                    openMap.push(tuple<int, int, int, int>(map[k][i][j].fPoint, k, i, j));
                }
                else if (!map[k][i][j].block && map[k][i][j].check && !(i == sy && j == sx && k == sz))
                {//탐색 했던 곳이지만 새로운 루트와 f값을 비교할 경우 확인할 경우
                    int g;
                    int diag = 0;
                    if (i != parent->y)
                        ++diag;
                    if (j != parent->x)
                        ++diag;
                    if (k != parent->z)
                        ++diag;
                    if (diag == 3)
                        g = map[sz][sy][sx].gPoint + 17;
                    else if (diag == 2)
                        g = map[sz][sy][sx].gPoint + 14;
                    else if (diag == 1)
                        g = map[sz][sy][sx].gPoint + 10;
                    int ry = (i > fy) ? i - fy : fy - i;
                    int rx = (j > fx) ? j - fx : fx - j;
                    int rz = (k > fz) ? k - fz : fz - k;
                    int h = rz * 10 + ry * 10 + rx * 10;
                    int f = g + h;
                    if (map[k][i][j].fPoint > f)
                    {
                        map[k][i][j].parent = &(map[sz][sy][sx]);
                        map[k][i][j].fPoint = f;
                        map[k][i][j].gPoint = g;
                        map[k][i][j].hPoint = h;
                    }
                }
            }
        }
    }
    tuple<int, int, int, int> t = openMap.top();
    aMap a = map[get<1>(t)][get<2>(t)][get<3>(t)];
    openMap.pop();
    if (!openMap.empty())
    {//아직 탐색하지 않은 곳이 남았을 때
        aStar(a.x, a.y, a.z, fx, fy, fz, &(map[sz][sy][sx]));
    }
    else
    {//모두 탐색했을 때
        aMap go = map[fz][fy][fx];
        stack<tuple<int, int, int> > ans;
        while (1)
        {//끝점부터 역순으로 넣어주자
            ans.push(tuple<int, int, int>(go.x, go.y, go.z));
            if (go.start)
                break;
            else
                go = *(go.parent);
        }
        while (!ans.empty())
        {//순서대로 값 출력
            cout << "(" << get<0>(ans.top()) << ", " << get<1>(ans.top()) << ", " << get<2>(ans.top()) << ")\n";
            ans.pop();
        }
        cout << endl;
    }
}
cs


저작자표시 비영리 변경금지

'BCA > 1. C,C++,C#' 카테고리의 다른 글

64. 우선순위 큐 (C#)  (0) 2018.08.10
17일 : class 선언과 include의 차이  (0) 2018.03.09
10일 : 템플릿, STL(리스트, 맵)  (0) 2018.02.21
9일 : 다형성을 이용해 간단한 텍스트 RPG 만들기  (0) 2018.02.20
8일 : 상속과 다형성  (0) 2018.02.19
'BCA/1. C,C++,C#' Related Articles more
Comments