1. 미로는 2차원 배열로 구현된다. maze[x][y]
2. 현재 위치는 출발점(1,1)이다.
3. 다음을 반복한다.
ㄱ. 현재 위치에 방문했다는 표시를 한다.(2)
ㄴ. 현재 위치가 출구라면 종료한다. maze[n-2][n-2]
ㄷ. 현재 위치에서 북, 동, 남, 서 4방향에 대해 순서대로
- 그 방향으로 이동할 수 있는지(벽, 미로의 외부, 이미 방문한 위치)가 아닌지 검사한다.
- 만약 갈 수 있으면 현재 위치를 스택에 push하고 그 방향으로 이동
ㄹ. 만약 ㄷ번에서 4방향 중 어느 쪽으로도 가지 못했다면 스택에서 pop한 위치로 돌아간다.
// position.h
#ifndef position_h
#define position_h
typedef struct pos{
int x,y;
}Position;
Position move_to(Position pos, int dir);
#endif /* position_h */
// position.c
#include "position.h"
// 북동남서방향으로 이동하는 것이다. 세로가 X, 가로가 Y
int offset[4][2] = {
{-1,0},
{0,1},
{1,0},
{0,-1}
};
Position move_to(Position pos,int dir){
Position next;
next.x = pos.x + offset[dir][0];
next.y = pos.y + offset[dir][1];
return next;
}
// stack.h
#ifndef stack_h
#define stack_h
#include <stdio.h>
#include <stdlib.h>
#include "position.h"
typedef struct s{
int dir;
struct s * next;
}Stack;
Stack * new_node(int dir);
void init(Stack **s);
int is_empty(Stack *s);
int peak(Stack *s);
void push(Stack ** top, int dir);
void pop(Stack ** top);
#endif /* stack_h */
// color.h
#ifndef color_h
#define color_h
#define RESET "\033[0m"
#define BLACK "\033[30m" /* Black */
#define RED "\033[31m" /* Red */
#define GREEN "\033[32m" /* Green */
#define YELLOW "\033[33m" /* Yellow */
#define BLUE "\033[34m" /* Blue */
#define MAGENTA "\033[35m" /* Magenta */
#define CYAN "\033[36m" /* Cyan */
#define WHITE "\033[37m" /* White */
#define BOLDBLACK "\033[1m\033[30m" /* Bold Black */
#define BOLDRED "\033[1m\033[31m" /* Bold Red */
#define BOLDGREEN "\033[1m\033[32m" /* Bold Green */
#define BOLDYELLOW "\033[1m\033[33m" /* Bold Yellow */
#define BOLDBLUE "\033[1m\033[34m" /* Bold Blue */
#define BOLDMAGENTA "\033[1m\033[35m" /* Bold Magenta */
#define BOLDCYAN "\033[1m\033[36m" /* Bold Cyan */
#define BOLDWHITE "\033[1m\033[37m" /* Bold White */
#endif /* color_h */
// main.c
#include "stack.h"
#include "position.h"
#include "color.h"
#include <unistd.h>
#define MAX 8
#define PATH 0 // 지나갈 수 있는 길
#define WALL 1 // 지나갈 수 없는 길 == 벽 흰색!
#define VISITED 2 // 이미 방문한 위치
#define BACKTRACKED 3 // 방문했다 되돌아 나온 위치
#define EDGE 4 // 테두리
#define clear() printf("\033[H\033[J")
int maze[MAX+2][MAX+2]= {
{4,4,4,4,4,4,4,4,4,4},
{4,0,0,0,0,0,0,0,1,4},
{4,0,1,1,0,1,1,0,1,4},
{4,0,0,0,1,0,0,0,1,4},
{4,0,1,0,0,1,1,0,0,4},
{4,0,1,1,1,0,0,1,1,4},
{4,0,1,0,0,0,1,0,1,4},
{4,0,0,0,1,0,0,0,1,4},
{4,0,1,1,1,0,1,0,0,4},
{4,4,4,4,4,4,4,4,4,4}
};
int n=MAX; // 미로의 크기
//void make_maze();
void print_maze();
int movable(Position pos,int dir);
int main(int argc, const char * argv[]) {
Stack * top;
init(&top);
// make_maze();
Position cur; // 항상 현재 위치를 표현
cur.x=1;
cur.y=1;
int init_dir = 0; //한 위치에 도착했을 때 처음으로 시도해 볼 이동 방향
while(1){
maze[cur.x][cur.y] = VISITED;
if(cur.x == n && cur.y == n){
print_maze(cur.x,cur.y);
printf("미로를 찾았습니다!\n");
break;
}
// 방문했는지 기록하는 변수
int forwarded = 0;
// 북 동 서 남 순서대로 0, 1, 2, 3
for(int dir = init_dir; dir<4;dir++){
if(movable(cur,dir)){ //이동가능한지 검사
push(&top,dir); // 스택에 현재 위치 대신 이동하는 방향을 push
cur = move_to(cur,dir);
forwarded = 1;
init_dir = 0; //처음 방문하는 위치에서는 항상 0부터 시도
break;
}
}
// 4방향중 아무곳도 가지 못했다면
if(!forwarded){
// 왔다가 되돌아간 곳임을 표시
maze[cur.x][cur.y]=BACKTRACKED;
//원래 출구가 없는 미로
if(is_empty(top)){
printf("길이 없습니다.\n");
break;
}
int d = peak(top);
pop(&top);
// 이전 위치에서 지금 위치에 올때 d방향으로 이동했다면 (d+2)%4번 방향으로 이동하면된다.
// 되돌아가는 방향!
cur = move_to(cur, (d+2)%4);
// 위치에서 d+1번방향부터 시도하면된다.
init_dir = d+1;
print_maze(cur.x, cur.y);
printf("길이없습니다. 되돌아갑니다.\n");
}
}
return 0;
}
int movable(Position pos, int dir){
Position tmp = move_to(pos, dir);
//1. dir방향으로 이동한 좌표가 0~n-1이내에 있어야한다.
print_maze(tmp.x,tmp.y);
printf("maze[%d][%d]=%d\n",tmp.x,tmp.y,maze[tmp.x][tmp.y]);
if( tmp.x<1 || tmp.x>n){
printf("x범위초과\n");
return 0;
}
if(tmp.y<1||tmp.y>n+1){
printf("y범위초과\n");
return 0;
}
//2. wall이 아니고, 벽이아니어야한다.
switch (maze[tmp.x][tmp.y]) {
case 0:
printf("갈 수 있는 길입니다.\n");
return 1;
case 1:
printf("벽입니다. 갈 수 없습니다.\n");
return 0;
case 2:
printf("이미 방문한 길입니다. 갈 수 없습니다.\n");
return 0;
case 3:
printf("이미 방문한 길입니다. 갈 수 없습니다.\n");
return 0;
default:
return 0;
}
}
void print_maze(int x,int y){
sleep(1);
clear();
for(int i=0;i<MAX+2;i++){
for(int j=0;j<MAX+2;j++){
switch (maze[i][j]) {
case 0:
printf(BLACK);
if(i==x&&j==y){
printf(BOLDRED);
}
printf("ㅁ");
printf(RESET);
break;
case 1:
if(i==x&&j==y){
printf(BOLDRED);
}
printf("ㅁ");
break;
case 2:
printf(BOLDYELLOW);
if(i==x&&j==y){
printf(BOLDRED);
}
printf("ㅁ");
printf(RESET);
break;
case 3:
printf(BOLDGREEN);
if(i==x&&j==y){
printf(BOLDRED);
}
printf("ㅁ");
printf(RESET);
break;
case 4:
printf(BOLDBLUE);
if(i==x&&j==y){
printf(BOLDRED);
printf("ㅁ");
}else
printf("ㅁ");
printf(RESET);
break;
default:
break;
}
printf(RESET);
if(j==MAX+1)printf("\n");
}
}
printf(RESET);
}
- 하나의 큐를 만든다.
- 위치(0,0) 는 이미 방문한 위치임을 표시하고, 큐에 위치(0,0)을 넣는다.
- 큐가 빌 때까지 다음을 반복한다.
- 큐에서 하나의 위치 p를 꺼낸다.
- p에서 한 칸 떨어진 위치들 중에서 이동 가능하면서 아직 방문하지 않은 모든 위치들을 방문된 위치임을 표시하고 큐에 넣는다.
- 만약 그 위치가 출구라면 종료한다.
int movable(Position pos, int dir){
Position tmp = move_to(pos, dir);
//1. dir방향으로 이동한 좌표가 1~MAX이내에 있어야한다.
print_maze(tmp.x,tmp.y);
printf("maze[%d][%d]=%d\n",tmp.x,tmp.y,maze[tmp.x][tmp.y]);
if( tmp.x<1 || tmp.x>MAX){
printf("x범위초과\n");
return 0;
}
if(tmp.y<1||tmp.y>MAX){
printf("y범위초과\n");
return 0;
}
//2. wall이 아니고, 벽이아니어야한다.
switch (maze[tmp.x][tmp.y]) {
case 0:
printf("갈 수 있는 길입니다.\n");
return 1;
case 1:
printf("벽입니다. 갈 수 없습니다.\n");
return 0;
default:
printf("이미 방문한 길입니다. 갈 수 없습니다.\n");
return 0;
}
}
// heuristic함수로 가중치를 계산하는 함수
// 여기서 pre는 이전정점의 gx값을 받아온다.
int heuristic(Vertex v, int x,int y, int *pre){
int res;
// h(x)함수 즉, 출구에서 얼마나 걸리는지 계산한다.(맨하탄)
res = ((abs(end.x-x)+abs(end.y-y))*10);
*pre = v.g_x;
// 대각선인 경우
if(abs(v.x-x)==abs(v.y-y)){
*pre = *pre +14;
}else{
*pre = *pre +10;
}
// f(x) = g(x) + h(x)
return res+(*pre);
}
// 인접노드를 queue에 추가하기
void add_openlist(Queue * q,Vertex v){
Vertex tmp;
// pw는 이전 weigt
int i,j,w,pre;
// 인접한 정점 확인
for(i=v.x-1;i<=v.x+1;i++){
if(i<1||i>MAX)continue; // 범위를 벗어나면 통과한다.
for(j=v.y-1;j<=v.y+1;j++){
if(j<1||j>MAX)continue; // 범위를 벗어나면 통과한다.
if(i==v.x&&j==v.y)continue; // i와 j가 현재 노드랑 같으면 통과
if(maze[i][j]!=0)continue; // 길이 아니면 통과
// 가중치 f(x)
w = heuristic(v, i, j, &pre);
// 가중치가 현재보다 낮거나 기록이 안되어있으면 갱신
if(w<weight[i][j]||weight[i][j]==0){
weight[i][j]=w;
// 부모 노드의 정보를 저장한다.
parent[i][j] = (v.x*MAX+2)+v.y;
// 출구를 찾으면 종료
if(end.x == i && end.y ==j)return;
}
tmp.x = i;
tmp.y = j;
tmp.g_x = pre;
enQueue(q, tmp);
}
}
}
void astar(Vertex s,Vertex e){
Queue * q = creat_queue();
Vertex v;
// 시작점의 weight는 0이다.
weight[s.x][s.y] = 0;
// 시작점은 부모노드를 갖고 있지 않는다.
parent[s.x][s.y]=-1;
// 시작점에서 움직인 거리(gx)는 0이다.
s.g_x = 0;
v = s;
add_openlist(q,v);
while(!is_empty(q)){
// 현재 점을 Closed list에 추가 >> maze에 바로표시
maze[v.x][v.y]=CLOSED;
v = front(q);
deQueue(q);
if(v.x==end.x && v.y==end.y)return;
// 새로운 인접노드를 추가해준다.
add_openlist(q, v);
}
}
void backtracking(){
int i, j, back;
if(parent[end.x][end.y]==0){
printf("경로가 없습니다.\n");
return;
}
i = parent[end.x][end.y] / MAX+2;
j = parent[end.x][end.y] % MAX+2;
while( parent[i][j] != -1)
{
back = parent[i][j];
maze[i][j] = FINAL;
i = back / MAX+2;
j = back % MAX+2;
}
maze[start.x][start.y] = FINAL;
}