C언어로 구현한 미로 알고리즘 동적 이동(delay함수 이용)

/* 미로를 사용자가 동적으로 생성 시킬 수 있도록 하여준다. 이 때 잘 못된 미로의 값이 리턴 될 수도 있음으로 옳은 미로의 길을 찾을 때 까지 루프를 돌려 사용자가 미로 찾기를 할 때는 길이 있는 미로를 설정 한다. 또 한 '▩'표시로 움직임 경로를 직접 사용자가 볼 수 있도록 하였는데 이 때 딜레이 메소드를 선언하여 Old Time을 잡아 주고 무한 루프로 값체크를 하는데 Old Time - 현재시간을 계산하여 딜레이 함수에서 전달 받은 매개변수의 값보다 커질 때 종료한다. ex>delay(5000) 5초 동안 무한 루프가 계속 실행 되기 때문에 사용자는 정지 한 것 처럼 느껴진다. 그리하여 사용자는 ▩표시를 보여 실제 미로 알고리즘의 움직임을 알 수 있다. */ #include<stdio.h> #include<time.h> #include <malloc.h> #define FALSE 0 #define TRUE 1 typedef struct{ short int row; short int col; short int dir; }element; //써치 스택 element *search_stack; short int Max_Row; short int Max_Col; short int Max_element; typedef struct{ short int vert; short int horiz; }offsets; //방향을 알기 위한 구조체 offsets move[8]; int **mark; int **maze; int tmp=FALSE; void delay(clock_t sleep); int path(); element Pop(int *top); void Push(int *top,element item); void Serching(short int stop_Row,short int stop_Col); int main(){ int i,j; srand((unsigned)time(NULL));//랜덤 함수초기화 move[0].vert = -1; move[0].horiz = 0; //북 move[1].vert = -1; move[1].horiz = 1; //북동 move[2].vert = 0; move[2].horiz = 1; //동 move[3].vert = 1; move[3].horiz = 1; //남동 move[4].vert = 1; move[4].horiz = 0; //남 move[5].vert = 1; move[5].horiz = -1; //남서 move[6].vert = 0; move[6].horiz = -1; //서 move[7].vert = -1; move[7].horiz = -1; //북서 printf(" * * * * 미로 찾기 프로그램 * * * * \n"); //계속 이어지는 게임을 위해 무한 반복으로 실행. while(1){ tmp=FALSE; printf("\n 미로의 크기를 지정 하십시오.(가로,세로 입력) : "); scanf("%d %d",&Max_Row,&Max_Col); //미로를 동적으로 생성하기 때문에 랜덤 함수에서 잘 못 된 길을 만들 수 있다. //그래서 옳은 길일때 까지 실행 하기 위해서 path의 리턴이 1일 때 break를 걸고 //0을 리턴 하게 되면 계속 루프가 돌면서 제대로 된 미로를 생성 시켜준다. while (1) { Max_element = Max_Row*Max_Col; //동적으로 생성. search_stack = (element *)calloc(sizeof(element *),Max_element); maze = (int **)calloc(sizeof(int *),Max_Row); for(i=0;i<Max_Row;i++) maze[i] = (int *)calloc(sizeof(int *),Max_Col); for(i=0; i<Max_Row; i++) { for(j=0;j<Max_Col; j++) { maze[i][j]=rand()%2; //0 아니면 1의 값이 임의로 들어가게끔 } } if(path()){ //제대로 된 미로라면 if문 실행 break; } free(search_stack); free(*maze); free(maze); } maze[0][0]=0; //입구와 출구는 무조건 0으로 초기값설정 maze[Max_Row-1][Max_Col-1]=0; for(i=0; i<Max_Row; i++) { for(j=0;j<Max_Col; j++) { printf("%d ",maze[i][j]); }printf("\n"); } tmp=TRUE; printf("로봇이 길 찾기를 시작합니다.\n"); system("pause"); path(); printf("\n게임을 계속 하시겠습니까?(y/n) : "); { char c; fflush(stdin); c=getchar(); if(c=='y'||c=='Y'){system("cls");} else{ printf("게임을 종료 합니다. 감사합니다^^"); system("pause"); exit(1); } } } return 1; } //search_stack[]의 추가 삭제 기능을 하는 메소드들, void Push(int *top,element item) { if(*top>=Max_element-1) { printf("Stack is_Full.\n"); return; } search_stack[++*top]=item; if(tmp){ delay(1000); Serching(item.row,item.col); } } element Pop(int *top) { if(*top==-1) { printf("Stack is Empty.\n"); return search_stack[Max_element]; } if(tmp){ delay(1000); Serching(search_stack[(*top)].row,search_stack[(*top)].col); } return search_stack[(*top)--]; } //미로 통과 알고리즘 int path() { int i,top, row, col, next_row, next_col, dir; int found=FALSE; element position; mark = (int **)calloc(sizeof(int *),Max_Row); for(i=0; i<=Max_Row; i++){ mark[i] = (int *)calloc(sizeof(int *),Max_Col); } mark[0][0]=1; top=0; search_stack[0].row=0; search_stack[0].col=0; search_stack[0].dir=1; while(top>-1&&!found) { position=Pop(&top); row=position.row; col=position.col; dir=position.dir; while(dir<8 && !found) { if(row+move[dir].vert < 0 || row+move[dir].vert >= Max_Row || col+move[dir].horiz<0 || col+move[dir].horiz >= Max_Col){ dir++; continue; } next_row=row+move[dir].vert; next_col=col+move[dir].horiz; if(next_row==Max_Row-1 && next_col==Max_Col-1) found=TRUE; else if(!maze[next_row][next_col]&&!mark[next_row][next_col]) { mark[next_row][next_col]=1; position.row=row; position.col=col; position.dir=++dir; Push(&top,position); row=next_row; col=next_col; dir=0; } else ++dir; } if(tmp){ delay(1000); Serching(row,col); } } if(found) { if(tmp){ delay(1000); Serching(row,col); delay(1000); Serching(Max_Row-1,Max_Col-1); //최종 경로를 나열 printf("The path is:\n"); printf("row col\n"); for(i=0; i<=top; i++) printf("%2d%5d\n",search_stack[i].row,search_stack[i].col); printf("%2d%5d\n",row,col); printf("%2d%5d\n",Max_Row-1,Max_Col-1); } return 1; } else{ //printf("The maze does not have a path\n"); return 0; } } //딜레이 함수. 움직임을 보여주기 위해. void delay(clock_t sleep){ clock_t cur = clock(), el; while(1){ el = clock(); if((el - cur) > sleep) break ; } } //움직 일 때 타이머 함수를 돌려서 로봇( '▩'로 표시)의 움직임 경로를 콘솔 창에서 보여주기 위한 메소드 void Serching(short int stop_Row,short int stop_Col){ short int row,col; system("cls"); for(row=0; row<Max_Row; row++){ for(col=0; col<Max_Col; col++){ if(stop_Row ==row && stop_Col ==col) printf("▩"); else printf("%d ",maze[row][col]); }printf("\n"); } }

 

 

//프로그램을 실행 하면 사용자는 미로의 싸이즈 값을 입력 하게 된다.

그러면 랜덤 함수를 이용하여 미로를 만들어준다.(이 때 길이 있는 미로를 만들기 위해 무한루프를 돌면서 제대로 된 미로가 나오면 다음으로 넘어 간다.)

 

//▩ 문자를 이용하여 로봇이 미로를 찾아 가는 모습을 보여준다. 0.8초의 딜레이를 주어 차례차례 움직이는 모습을 눈으로 확인 할 수 있도록 만들었다.

 

 

 

 

 

//▩가 출구에 도달하면 처음부터 이동했던 경로를 리스트형식으로 보여준다.