mo1lusca의 블로그
[Unifox] - 방학 프로젝트 - 미로찾기 시뮬레이터 본문
0. 주제 선정 동기
동아리 시간에 배운 BFS와 DFS 같은 탐색 알고리즘을 활용해 뭘 만들 수 있을까 고민했다.
미로찾기 시뮬레이터를 만들어 여러 알고리즘으로 미로를 해결해보면,
탐색 알고리즘이 어떻게 실행되는지도 이해하기 좋을 것 같아서 해당 주제로 프로젝트를 진행하기로 했다.
1. 개념 소개
i . 미로 생성
미로를 탐색하기 위해서는 일단 미로가 필요하다.
사용자가 미로를 입력하는 방식은, 크고 복잡한 미로를 만들기에 부적합하기에 미로생성을 위한 알고리즘을 짜야 했다.
미로생성에는 Prim, Kruskal 등 다양한 알고리즘을 사용할 수 있지만, 구현이 마냥 쉽진 않기도 하고 주객전도같은 느낌이 들어
간단한 알고리즘을 통해 만들었다.
ii. 미로 탐색
위에서 만든 미로를 탐색한다.
동아리 시간에 배운 DFS와 BFS, 다익스트라 알고리즘을 변형시켜 만든 A* (Astar) 를 탐색에 사용할 것이다.
또한 탐색을 하며, 미로와 방문한 길을 콘솔에 띄워 시각화 하였다.
2. 코드 설명
i. 미로 생성
void init_maze(int start_x, int start_y, int goal_x, int goal_y) {
maze.assign(N, vector<int>(N, 1));
int row = (N + 1) / 2;
int col = (N + 1) / 2;
nodes.assign(row, vector<Node>(col));
for (int y = 1; y < N; y += 2) {
for (int x = 1; x < N; x += 2) {
Node n = { x, y, rand() % 100, false };
nodes[y / 2][x / 2] = n;
maze[y][x] = 0;
}
}
Node* start_node = get_node(start_x, start_y);
Node* goal_node = get_node(goal_x, goal_y);
make_main_path(start_node, goal_node);
connect_remain();
make_random_branch(BRANCH);
}미로를 초기화 하는 함수이다.
미로를 모두 1(=벽)으로 초기화하고, i와 j가 모두 홀수인 칸만 0(=길)로 변경한다.
2중 for문 내에서는 위에서 길로 저장된 칸들을 노드로써 nodes에 저장한다. 이때 랜덤으로 가중치를 부여한다.
이후 순서대로 make_main_path, connect_remain, make_random_branch를 호출한다. (밑의 세 함수)
void make_main_path(Node* start, Node* end) {
Node* cur = start;
cur->visited = true;
int prev_dir = -1;
while (cur != end) {
vector<pair<int, Node*>> hubos;
vector<pair<int, pair<int, int>>> walls;
for (int i = 0; i < 4; i++) {
int nx = cur->x + dx[i];
int ny = cur->y + dy[i];
if (is_bound(nx, ny)) {
Node* next = get_node(nx, ny);
if (next && !next->visited) {
int score = next->weight;
if (prev_dir == i) score += 10;
else if (prev_dir != -1) score -= 5;
hubos.push_back({ score, next });
walls.push_back({ i, {cur->x + wall_dx[i], cur->y + wall_dy[i]} });
}
}
}
if (hubos.empty()) break;
vector<int> idx(hubos.size());
for (int i = 0; i < (int)hubos.size(); i++) {
idx[i] = i;
}
sort(idx.begin(), idx.end(), [&](int a, int b) {
return hubos[a].first < hubos[b].first;
});
int choice = idx[rand() % min(3, (int)idx.size())];
Node* n_node = hubos[choice].second;
int wallX = walls[choice].second.first;
int wallY = walls[choice].second.second;
maze[wallY][wallX] = 0;
maze[n_node->y][n_node->x] = 0;
n_node->visited = true;
prev_dir = walls[choice].first;
cur = n_node;
}
}사용자로부터 입력받은 시작지점과 목표지점을 기준으로 main path를 만든다.
이때, 모든 노드들에 랜덤하게 부여한 가중치를 토대로 현재 노드와 인접한 노드들 중 가중치가 가장 낮은 노드를 선택한다.
(좀 더 복잡한 경로를 위해 패널티 점수를 사용해 직선경로를 줄였다.)
이렇게 만들어진 경로는, 시작지점과 목표지점이 무조건 이어져 있다는 보장이 없다. 이에 대해서는 다음 함수를 보자.
void connect_remain() {
bool progress = true;
while (progress) {
progress = false;
int minWeight = INT_MAX;
Node* from = nullptr;
Node* to = nullptr;
int wallX = 0, wallY = 0;
for (int ny = 0; ny < (int)nodes.size(); ny++) {
for (int nx = 0; nx < (int)nodes[0].size(); nx++) {
Node& cur = nodes[ny][nx];
if (!cur.visited) continue;
for (int i = 0; i < 4; i++) {
int nnx = cur.x + dx[i];
int nny = cur.y + dy[i];
if (is_bound(nnx, nny)) {
Node* next = get_node(nnx, nny);
if (next && !next->visited && next->weight < minWeight) {
minWeight = next->weight;
from = &cur;
to = next;
wallX = cur.x + wall_dx[i];
wallY = cur.y + wall_dy[i];
}
}
}
}
}
if (to) {
maze[wallY][wallX] = 0;
maze[to->y][to->x] = 0;
to->visited = true;
progress = true;
}
}
}이 함수는 main path에 포함되지 못한 노드들을 main path의 branch(가지)로 포함시킨다.
이를 통해 모든 노드가 main path에 포함되며 시작지점과 목표지점이 연결됨이 보장된다.
그 말은 즉, 시작지점에서 목표지점으로 가는 경로가 단 한개라는 것이다.
이렇게 되면 알고리즘 별 차이를 찾기 어렵다. 이에 대해서는 다음 함수를 보자.
void make_random_branch(int cnt) {
for (int k = 0; k < cnt; k++) {
int x = rand() % (N - 2) + 1;
int y = rand() % (N - 2) + 1;
if (x % 2 == y % 2) continue;
if (maze[y][x] == 1) {
maze[y][x] = 0;
}
}
}이 함수는 인자로 넘어온 수 만큼 반복하며 임의의 칸을 선택하며, 그 칸이 벽일 경우 허문다.
인자로 큰 값을 넣어주고 함수를 호출하면 랜덤한 벽들이 허물어지면서 branch끼리 이어지고,
결과적으로 시작지점에서 목표지점까지의 경로가 여러개가 된다.
ii . 미로 탐색
미로 탐색은 BFS, DFS, A* 세 알고리즘으로 진행할 것이다.
SearchResult bfs(Node start, Node goal) {
print_algorithm(BFS);
SearchResult res = { 0,0 };
vector<vector<bool>> visited(N, vector<bool>(N, false));
vector<vector<pair<int, int>>> parent(N, vector<pair<int, int>>(N, { -1,-1 }));
queue<Node> q;
int bfs_dx[4] = { 1, 0, -1, 0 };
int bfs_dy[4] = { 0, 1, 0, -1 };
q.push(start);
visited[start.y][start.x] = true;
while (!q.empty()) {
auto cur = q.front();
q.pop();
Sleep(DELAY);
mark(cur.x, cur.y, "@", GREEN);
print_step(BFS);
if (cur.x == goal.x && cur.y == goal.y) {
res.path_len = search_path(parent, start, goal);
res.step_cnt = count_step(BFS) - 1;
return res;
}
for (int i = 0; i < 4; i++) {
int nx = cur.x + bfs_dx[i];
int ny = cur.y + bfs_dy[i];
if (is_bound(nx, ny) && !visited[ny][nx] && maze[ny][nx] == 0) {
visited[ny][nx] = true;
parent[ny][nx] = { cur.x, cur.y };
q.push({ nx, ny });
}
}
}
res.path_len = search_path(parent, start, goal);
res.step_cnt = count_step(BFS) - 1;
return res;
}BFS를 수행하는 함수이다. 경로 역추적을 위해 parent를 사용했다.
mark 함수를 통해 콘솔에 그려진 미로 위에 방문한 칸을 색칠한다.
목표지점에 도달하면 search_path 함수를 호출해 parent를 토대로 경로를 역추적한다.
SearchResult dfs(Node start, Node goal) {
print_algorithm(DFS);
SearchResult res = { 0,0 };
vector<vector<bool>> visited(N, vector<bool>(N, false));
vector<vector<pair<int, int>>> parent(N, vector<pair<int, int>>(N, { -1,-1 }));
stack<Node> stk;
int dfs_dx[4] = { 1, 0, -1, 0 };
int dfs_dy[4] = { 0, 1, 0, -1 };
stk.push(start);
while (!stk.empty()) {
auto cur = stk.top();
stk.pop();
if (visited[cur.y][cur.x]) continue;
visited[cur.y][cur.x] = true;
Sleep(DELAY);
mark(cur.x, cur.y, "@", GREEN);
print_step(DFS);
if (cur.x == goal.x && cur.y == goal.y) {
res.path_len = search_path(parent, start, goal);
res.step_cnt = count_step(DFS) - 1;
return res;
}
for (int i = 0; i < 4; i++) {
int nx = cur.x + dfs_dx[i];
int ny = cur.y + dfs_dy[i];
if (is_bound(nx, ny) && !visited[ny][nx] && maze[ny][nx] == 0) {
parent[ny][nx] = { cur.x, cur.y };
stk.push({ nx, ny });
}
}
}
res.path_len = search_path(parent, start, goal);
res.step_cnt = count_step(DFS) - 1;
return res;
}DFS를 수행하는 함수이다. BFS 함수와 구조는 똑같으나 queue 대신 stack을 사용한다.
int huri(int x1, int y1, int x2, int y2) {
return abs(x1 - x2) + abs(y1 - y2);
}A* 수행을 위한 맨해튼 거리 기반 휴리스틱 함수이다.
왜 휴리스틱 함수를 사용하는지 알려면 A*에 대한 이해가 필요하기에 짧게 설명하겠다.
A*는 다익스트라를 변형시켜, 현재까지 가장 적은 비용으로 도달한 노드부터 탐색하는 원리를 이용한다.
다익스트라는 현재까지의 비용이 최소인 곳 부터 탐색한다면, A*는 휴리스틱 함수 h(x)로 현재부터 목표까지의 거리를 예상하고,
현재까지의 비용 g(x)와 더해 만든 f(x)가 최소인 곳 부터 탐색한다. ( f(x) = g(x) + h(x) )
이때 남은 거리를 예상하기 위해 앞서 말했듯 휴리스틱 함수가 사용된다.
SearchResult astar(Node start, Node goal) {
print_algorithm(ASTAR);
SearchResult res = { 0,0 };
priority_queue<AstarNode> open;
vector<vector<int>> dist(N, vector<int>(N, INF));
vector<vector<bool>> close(N, vector<bool>(N, false));
vector<vector<pair<int, int>>> parent(N, vector<pair<int, int>>(N, { -1, -1 }));
int a_dx[4] = { 1, 0, -1, 0 };
int a_dy[4] = { 0, 1, 0, -1 };
dist[start.y][start.x] = 0;
open.push({ start.x, start.y, 0, huri(start.x, start.y, goal.x, goal.y) });
while (!open.empty()) {
AstarNode cur = open.top();
open.pop();
if (close[cur.y][cur.x]) {
continue;
}
close[cur.y][cur.x] = true;
mark(cur.x, cur.y, "@", GREEN);
print_step(ASTAR);
if (cur.x == goal.x && cur.y == goal.y) {
res.path_len = search_path(parent, start, goal);
res.step_cnt = count_step(ASTAR) - 1;
return res;
}
for (int i = 0; i < 4; i++) {
AstarNode next = { cur.x + a_dx[i], cur.y + a_dy[i] };
if (is_bound(next.x, next.y) && !close[next.y][next.x] && maze[next.y][next.x] == 0) {
next.g = cur.g + 1;
if (next.g < dist[next.y][next.x]) {
dist[next.y][next.x] = next.g;
next.f = next.g + huri(next.x, next.y, goal.x, goal.y);
open.push(next);
parent[next.y][next.x] = { cur.x, cur.y };
Sleep(DELAY);
}
}
}
}
res.path_len = search_path(parent, start, goal);
res.step_cnt = count_step(ASTAR) - 1;
return res;
}A*를 수행하는 함수이다. priority queue를 사용한다는 점에서 다익스트라와 비슷한 구조를 가진다.
특징은 이미 방문한곳을 다시 탐색하지 않기 위해 close(=visited)를 사용한다는 것이다.
또한, admissible한 휴리스틱 함수를 사용한다는 전제 하에 최단거리를 보장한다.
int search_path(const vector<vector<pair<int, int>>>& parent, Node start, Node goal) {
int cx = goal.x, cy = goal.y;
int length = 0;
while (!(cx == start.x && cy == start.y)) {
if (!is_bound(cx, cy) || (parent[cy][cx].first == -1 && parent[cy][cx].second == -1)) {
break;
}
mark(cx, cy, "@", RED);
auto p = parent[cy][cx];
cx = p.first;
cy = p.second;
length++;
Sleep(DELAY);
}
mark(start.x, start.y, "@", RED);
return length;
}역추적을 수행하는 함수이다.
인자로 parent를 받아 목표지점부터 시작지점까지의 경로를 역추적하고,
그 경로를 콘솔 위의 미로에 빨간색으로 표시한다.
전체 코드
더보기
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <string>
#include <cstdlib>
#include <ctime>
#include <climits>
#include <algorithm>
#include <windows.h>
using namespace std;
const int INF = 2e9;
int N = 151;
int DELAY = 0;
int BRANCH = 1000;
void gotoxy(int x, int y);
void setcolor(unsigned short color);
enum {
BLACK,
DARK_BLUE,
DARK_GREEN,
DARK_SKYBLUE,
DARK_RED,
DARK_VOILET,
DARK_YELLOW,
GRAY,
DARK_GRAY,
BLUE,
GREEN,
SKYBLUE,
RED,
VIOLET,
YELLOW,
WHITE,
BFS = 0,
DFS,
ASTAR
};
struct Node {
int x;
int y;
int weight;
bool visited;
};
struct AstarNode {
int x;
int y;
int g;
int f;
bool operator < (const AstarNode& other) const {
return f > other.f;
}
};
struct SearchResult {
int step_cnt;
int path_len;
};
vector<vector<int>> maze;
vector<vector<Node>> nodes;
int dx[4] = { -2, 0, 2, 0 };
int dy[4] = { 0, 2, 0, -2 };
int wall_dx[4] = { -1, 0, 1, 0 };
int wall_dy[4] = { 0, 1, 0, -1 };
bool is_bound(int x, int y);
Node* get_node(int x, int y);
void mark(int x, int y, string pat, int color);
int search_path(const vector<vector<pair<int, int>>>& parent, Node start, Node goal);
void make_main_path(Node* start, Node* end);
void connect_remain();
void make_random_branch(int cnt);
void init_maze(int start_x, int start_y, int goal_x, int goal_y);
void print_maze(Node goal);
void print_algorithm(int algorithm);
int count_step(int algorithm);
void print_step(int algorithm);
void print_result(SearchResult bfs_step, SearchResult dfs_step, SearchResult astar_step);
SearchResult bfs(Node start, Node goal);
SearchResult dfs(Node start, Node goal);
int huri(int x1, int y1, int x2, int y2);
SearchResult astar(Node start, Node goal);
SearchResult run_algorithm(SearchResult(*algorithm)(Node, Node), Node start, Node goal);
int main() {
srand(time(0));
Node start;
Node goal;
cout << "Input Size of Maze : ";
cin >> N;
cout << "Input Start Point (x, y) : ";
cin >> start.x >> start.y;
cout << "Input Goal Point (x, y) : ";
cin >> goal.x >> goal.y;
if (start.x % 2 == 0) start.x++;
if (start.y % 2 == 0) start.y++;
if (goal.x % 2 == 0) goal.x--;
if (goal.y % 2 == 0) goal.y--;
if (!is_bound(start.x, start.y)) {
return -1;
}
if (!is_bound(goal.x, goal.y)) {
return -1;
}
init_maze(start.x, start.y, goal.x, goal.y);
cout << "\n미로 생성이 완료되었습니다.";
cout << "\n전체화면으로 변경해주세요.";
cout << "\n미로의 크기가 큰 경우, 글자 크기를 줄여주세요.\n\n";
system("pause");
system("cls");
SearchResult bfs_res = run_algorithm(bfs, start, goal);
SearchResult dfs_res = run_algorithm(dfs, start, goal);
SearchResult astar_res = run_algorithm(astar, start, goal);
print_result(bfs_res, dfs_res, astar_res);
return 0;
}
bool is_bound(int x, int y) {
return (x > 0 && y > 0 && x < N - 1 && y < N - 1);
}
Node* get_node(int x, int y) {
if (x % 2 == 1 && y % 2 == 1) {
if (y / 2 < nodes.size() && x / 2 < nodes[0].size()) {
return &nodes[y / 2][x / 2];
}
}
return nullptr;
}
void make_main_path(Node* start, Node* end) {
Node* cur = start;
cur->visited = true;
int prev_dir = -1;
while (cur != end) {
vector<pair<int, Node*>> hubos;
vector<pair<int, pair<int, int>>> walls;
for (int i = 0; i < 4; i++) {
int nx = cur->x + dx[i];
int ny = cur->y + dy[i];
if (is_bound(nx, ny)) {
Node* next = get_node(nx, ny);
if (next && !next->visited) {
int score = next->weight;
if (prev_dir == i) score += 10;
else if (prev_dir != -1) score -= 5;
hubos.push_back({ score, next });
walls.push_back({ i, {cur->x + wall_dx[i], cur->y + wall_dy[i]} });
}
}
}
if (hubos.empty()) break;
vector<int> idx(hubos.size());
for (int i = 0; i < (int)hubos.size(); i++) {
idx[i] = i;
}
sort(idx.begin(), idx.end(), [&](int a, int b) {
return hubos[a].first < hubos[b].first;
});
int choice = idx[rand() % min(3, (int)idx.size())];
Node* n_node = hubos[choice].second;
int wallX = walls[choice].second.first;
int wallY = walls[choice].second.second;
maze[wallY][wallX] = 0;
maze[n_node->y][n_node->x] = 0;
n_node->visited = true;
prev_dir = walls[choice].first;
cur = n_node;
}
}
void connect_remain() {
bool progress = true;
while (progress) {
progress = false;
int minWeight = INT_MAX;
Node* from = nullptr;
Node* to = nullptr;
int wallX = 0, wallY = 0;
for (int ny = 0; ny < (int)nodes.size(); ny++) {
for (int nx = 0; nx < (int)nodes[0].size(); nx++) {
Node& cur = nodes[ny][nx];
if (!cur.visited) continue;
for (int i = 0; i < 4; i++) {
int nnx = cur.x + dx[i];
int nny = cur.y + dy[i];
if (is_bound(nnx, nny)) {
Node* next = get_node(nnx, nny);
if (next && !next->visited && next->weight < minWeight) {
minWeight = next->weight;
from = &cur;
to = next;
wallX = cur.x + wall_dx[i];
wallY = cur.y + wall_dy[i];
}
}
}
}
}
if (to) {
maze[wallY][wallX] = 0;
maze[to->y][to->x] = 0;
to->visited = true;
progress = true;
}
}
}
void make_random_branch(int cnt) {
for (int k = 0; k < cnt; k++) {
int x = rand() % (N - 2) + 1;
int y = rand() % (N - 2) + 1;
if (x % 2 == y % 2) continue;
if (maze[y][x] == 1) {
maze[y][x] = 0;
}
}
}
void init_maze(int start_x, int start_y, int goal_x, int goal_y) {
maze.assign(N, vector<int>(N, 1));
int row = (N + 1) / 2;
int col = (N + 1) / 2;
nodes.assign(row, vector<Node>(col));
for (int y = 1; y < N; y += 2) {
for (int x = 1; x < N; x += 2) {
Node n = { x, y, rand() % 100, false };
nodes[y / 2][x / 2] = n;
maze[y][x] = 0;
}
}
Node* start_node = get_node(start_x, start_y);
Node* goal_node = get_node(goal_x, goal_y);
make_main_path(start_node, goal_node);
connect_remain();
make_random_branch(BRANCH);
}
void print_maze(Node goal) {
for (int y = 0; y < N; y++) {
for (int x = 0; x < N; x++) {
if (maze[y][x] == 1) {
cout << "##";
}
else {
if (x == goal.x && y == goal.y) {
mark(x, y, "@", RED);
}
else {
cout << " ";
}
}
}
cout << "\n";
}
}
void gotoxy(int x, int y) {
COORD Cur;
Cur.X = x;
Cur.Y = y;
SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE), Cur);
}
void setcolor(unsigned short color) {
SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), color);
}
void mark(int x, int y, string pat, int color) {
x *= 2;
setcolor(color);
gotoxy(x, y);
if (pat.size() == 2) {
cout << pat;
}
else if (pat.size() == 1) {
cout << pat << pat;
}
setcolor(WHITE);
}
int search_path(const vector<vector<pair<int, int>>>& parent, Node start, Node goal) {
int cx = goal.x, cy = goal.y;
int length = 0;
while (!(cx == start.x && cy == start.y)) {
if (!is_bound(cx, cy) || (parent[cy][cx].first == -1 && parent[cy][cx].second == -1)) {
break;
}
mark(cx, cy, "@", RED);
auto p = parent[cy][cx];
cx = p.first;
cy = p.second;
length++;
Sleep(DELAY);
}
mark(start.x, start.y, "@", RED);
return length;
}
SearchResult bfs(Node start, Node goal) {
print_algorithm(BFS);
SearchResult res = { 0,0 };
vector<vector<bool>> visited(N, vector<bool>(N, false));
vector<vector<pair<int, int>>> parent(N, vector<pair<int, int>>(N, { -1,-1 }));
queue<Node> q;
int bfs_dx[4] = { 1, 0, -1, 0 };
int bfs_dy[4] = { 0, 1, 0, -1 };
q.push(start);
visited[start.y][start.x] = true;
while (!q.empty()) {
auto cur = q.front();
q.pop();
Sleep(DELAY);
mark(cur.x, cur.y, "@", GREEN);
print_step(BFS);
if (cur.x == goal.x && cur.y == goal.y) {
res.path_len = search_path(parent, start, goal);
res.step_cnt = count_step(BFS) - 1;
return res;
}
for (int i = 0; i < 4; i++) {
int nx = cur.x + bfs_dx[i];
int ny = cur.y + bfs_dy[i];
if (is_bound(nx, ny) && !visited[ny][nx] && maze[ny][nx] == 0) {
visited[ny][nx] = true;
parent[ny][nx] = { cur.x, cur.y };
q.push({ nx, ny });
}
}
}
res.path_len = search_path(parent, start, goal);
res.step_cnt = count_step(BFS) - 1;
return res;
}
SearchResult dfs(Node start, Node goal) {
print_algorithm(DFS);
SearchResult res = { 0,0 };
vector<vector<bool>> visited(N, vector<bool>(N, false));
vector<vector<pair<int, int>>> parent(N, vector<pair<int, int>>(N, { -1,-1 }));
stack<Node> stk;
int dfs_dx[4] = { 1, 0, -1, 0 };
int dfs_dy[4] = { 0, 1, 0, -1 };
stk.push(start);
while (!stk.empty()) {
auto cur = stk.top();
stk.pop();
if (visited[cur.y][cur.x]) continue;
visited[cur.y][cur.x] = true;
Sleep(DELAY);
mark(cur.x, cur.y, "@", GREEN);
print_step(DFS);
if (cur.x == goal.x && cur.y == goal.y) {
res.path_len = search_path(parent, start, goal);
res.step_cnt = count_step(DFS) - 1;
return res;
}
for (int i = 0; i < 4; i++) {
int nx = cur.x + dfs_dx[i];
int ny = cur.y + dfs_dy[i];
if (is_bound(nx, ny) && !visited[ny][nx] && maze[ny][nx] == 0) {
parent[ny][nx] = { cur.x, cur.y };
stk.push({ nx, ny });
}
}
}
res.path_len = search_path(parent, start, goal);
res.step_cnt = count_step(DFS) - 1;
return res;
}
SearchResult astar(Node start, Node goal) {
print_algorithm(ASTAR);
SearchResult res = { 0,0 };
priority_queue<AstarNode> open;
vector<vector<int>> dist(N, vector<int>(N, INF));
vector<vector<bool>> close(N, vector<bool>(N, false));
vector<vector<pair<int, int>>> parent(N, vector<pair<int, int>>(N, { -1, -1 }));
int a_dx[4] = { 1, 0, -1, 0 };
int a_dy[4] = { 0, 1, 0, -1 };
dist[start.y][start.x] = 0;
open.push({ start.x, start.y, 0, huri(start.x, start.y, goal.x, goal.y) });
while (!open.empty()) {
AstarNode cur = open.top();
open.pop();
if (close[cur.y][cur.x]) {
continue;
}
close[cur.y][cur.x] = true;
mark(cur.x, cur.y, "@", GREEN);
print_step(ASTAR);
if (cur.x == goal.x && cur.y == goal.y) {
res.path_len = search_path(parent, start, goal);
res.step_cnt = count_step(ASTAR) - 1;
return res;
}
for (int i = 0; i < 4; i++) {
AstarNode next = { cur.x + a_dx[i], cur.y + a_dy[i] };
if (is_bound(next.x, next.y) && !close[next.y][next.x] && maze[next.y][next.x] == 0) {
next.g = cur.g + 1;
if (next.g < dist[next.y][next.x]) {
dist[next.y][next.x] = next.g;
next.f = next.g + huri(next.x, next.y, goal.x, goal.y);
open.push(next);
parent[next.y][next.x] = { cur.x, cur.y };
Sleep(DELAY);
}
}
}
}
res.path_len = search_path(parent, start, goal);
res.step_cnt = count_step(ASTAR) - 1;
return res;
}
int huri(int x1, int y1, int x2, int y2) {
return abs(x1 - x2) + abs(y1 - y2);
}
void print_algorithm(int algorithm) {
gotoxy(N * 2 + 5, 5);
if (algorithm == BFS) {
cout << "BFS";
}
else if (algorithm == DFS) {
cout << "DFS";
}
else if (algorithm == ASTAR) {
cout << "Astar";
}
}
int count_step(int algorithm) {
if (algorithm == BFS) {
static int s_bfs_step = 0;
return ++s_bfs_step;
}
else if (algorithm == DFS) {
static int s_dfs_step = 0;
return ++s_dfs_step;
}
else if (algorithm == ASTAR) {
static int s_astar_step = 0;
return ++s_astar_step;
}
else {
return -1;
}
}
void print_step(int algorithm) {
gotoxy(N * 2 + 5, 7);
cout << "step : " << count_step(algorithm);
}
void print_result(SearchResult bfs_res, SearchResult dfs_res, SearchResult astar_res) {
vector<pair<SearchResult, string>> v = { {bfs_res, "BFS"}, {dfs_res, "DFS"}, {astar_res, "Astar"} };
sort(v.begin(), v.end(), [](auto a, auto b) -> bool {
return a.first.step_cnt < b.first.step_cnt;
});
cout << "\n######### STEP RANKING #########\n\n";
cout << " 1. " << v[0].second << " - " << v[0].first.step_cnt << " steps\n\n";
cout << " 2. " << v[1].second << " - " << v[1].first.step_cnt << " steps\n\n";
cout << " 3. " << v[2].second << " - " << v[2].first.step_cnt << " steps\n\n";
sort(v.begin(), v.end(), [](auto a, auto b) -> bool {
return a.first.path_len < b.first.path_len;
});
cout << "\n\n######### LENGTH RANKING #########\n\n";
cout << " 1. " << v[0].second << " - " << v[0].first.path_len << " moves\n\n";
cout << " 2. " << v[1].second << " - " << v[1].first.path_len << " moves\n\n";
cout << " 3. " << v[2].second << " - " << v[2].first.path_len << " moves\n\n";
}
SearchResult run_algorithm(SearchResult(*algorithm)(Node, Node), Node start, Node goal) {
print_maze(goal);
Sleep(1000);
SearchResult res = algorithm(start, goal);
gotoxy(0, N + 5);
system("pause");
system("cls");
return res;
}3. 시연 영상
시뮬레이션 전, 미로의 사이즈, 시작지점, 도착지점의 좌표를 입력받는다.
BFS -> DFS -> A* 순으로 시뮬레이션을 수행한다.
시뮬레이션 후, 알고리즘 별 탐색한 칸(steps)과 발견한 경로의 길이(moves)로 순위를 매겨 비교하기 쉽게 보여준다.
4. 배운점, 느낀점 및 개선점
이번 프로젝트를 계기로 A* 알고리즘에 대해 공부하게 되었다. 신기한 알고리즘인 것 같다.
BFS, DFS, A*과 같은 알고리즘이 어떻게 동작하는지 알아볼 수 있고,
알고리즘 별로 차이가 뚜렷하게 보인 것 같아 유익했다.
미로의 경로가 간단해보여서, 내가 만든 알고리즘이 아니라
Prim이나 Kruskal같은 알고리즘으로 미로를 생성해 시뮬레이션 해보면 좋을 것 같다.
미로 탐색과 동시에 시간을 측정해서, 탐색한 시간을 기준으로 비교하면 좋을 것 같다.
'Unifox' 카테고리의 다른 글
| [Unifox] - Python (1) | 2025.08.27 |
|---|---|
| [Unifox] - Node.js 3,4차시 (1) | 2025.08.16 |
| [Unifox] - Node.js 1,2차시 (3) | 2025.08.10 |
| [Unifox] - JavaScript 4차시 (2) | 2025.07.29 |
| [Unifox] - JavaScript 3차시 (1) | 2025.07.28 |