마이크로 마우스 (Micro Mouse)

#include <stdio.h>
#include <windows.h>
#include <stdlib.h>
#include <conio.h>

#define MAZE_SIZE    19
#define ROBOT        2
#define delay(n) Sleep(n)                        // n/1000초만큼 시간 지연

void gotoxy(int, int);
void clrscr(void);
int get_shape(int [][MAZE_SIZE], int, int);
void draw_maze(int [][MAZE_SIZE]);
void record(int, int);
void forward(int *, int *, int);
void right(int *);
void left(int *);
int still_in_maze(int, int);
int wall_ahead(int [][MAZE_SIZE], int, int, int);
void right_hand(int [][MAZE_SIZE], int , int , int);
void del_path(int, int);
void shortest_path(void);

int maze[MAZE_SIZE][MAZE_SIZE] = {
    {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
    {0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1},
    {1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1},
    {1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1},
    {1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1},
    {1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1},
    {1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1},
    {1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1},
    {1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1},
    {1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1},
    {1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1},
    {1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 1},
    {1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1},
    {1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1},
    {1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1},
    {1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1},
    {1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1},
    {1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
    {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}
};

int sx = MAZE_SIZE - 1;
int sy = MAZE_SIZE - 2; // 생쥐 출발 위치

int *rec; // 최단 경로 계산을 위한 생쥐가 움직인 경로를 저장

#define UP        1
#define RIGHT    2
#define DOWN    4
#define LEFT    8

void main(void)
{
    rec = (int *)malloc(MAZE_SIZE * MAZE_SIZE);    // 생쥐 움직임 저장
    if(rec == NULL)
    {
        cputs("\r\nMemory allocation error! ");
        exit(1);
    }
    clrscr();
    draw_maze(maze);
    gotoxy(40, 5);
    cputs("Simulation of Micro Mouse");
    gotoxy(40, 10);
    cputs(" Press any key to start ... ");
    //bioskey(0);
    right_hand(maze, sx, sy, LEFT);

    gotoxy(40, 10);
    cputs(" Press any key to see shortest path.. ");
    //bioskey(0);
    shortest_path();

    gotoxy(40, 10);
    cputs(" Press any key to end program ... ");
    // bioskey(0);
}

//
// Dos상에서의 gotoxy 를 Visual Studio에서 사용하게끔 SetConsoleCursorPosition을 이용한다.
//
void gotoxy(int x, int y)
{
    COORD Cur;
    Cur.X=x;
    Cur.Y=y;
    SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE),Cur);
}

//
// 도스상의 cls를 사용하기 위해서
//
void clrscr(void)
{
    system("cls");
}

//
// 미로를 화면에 그려주기
//
void draw_maze(int m[][MAZE_SIZE])
{
    int i,j;
    for(j=0; j<MAZE_SIZE; j++)
        for(i=0; i<MAZE_SIZE; i++)
        {
            gotoxy(i+1, j+1);
        
        /*    switch(get_shape(m, i, j))
            {
            case 32:
                putch(" ");
                break;
            case 179:
                putch("│");
                break;
            case 196:
                putch("─");
                break;
            case 192:
                putch("└");
                break;
            case 218:
                putch("┌");
                break;
            case 195:
                putch("├");
                break;
            case 217:
                putch("┘");
                break;
            case 193:
                putch("┴");
                break;
            case 191:
                putch("┐");
                break;
            case 180:
                putch("┤");
                break;
            case 194:
                putch("┬");
                break;
            case 197:
                putch("┼");
                break;
            }*/
            
            putch(get_shape(m, i, j));
        }
}

//
// 벽 배치에 따른 중앙벽의 모양을 리턴
//
int get_shape(int m[][MAZE_SIZE], int x, int y)
{
    static shape[] = {
        32, 179, 196, 192, 179, 179, 218, 195, 196, 217, 196, 193, 191, 180, 194, 197
    };
    //
    // ' ', │, ─, └, │, │, ┌, ├, ─, ┘, ─, ┴, ┐, ┤. ┬, ┼
    //

    int s = 0;
    if(m[y][x])
    {
        if(y > 0 && m[y-1][x]) s |= UP;
        if(y < MAZE_SIZE - 2 && m[y+1][x]) s |= DOWN;
        if(x > 0 && m[y][x-1]) s |= LEFT;
        if(x < MAZE_SIZE -2 && m[y][x+1]) s |= RIGHT;
    }

    return shape[s];
}

//
// 생쥐의 이동 경로를 저장
//
void record(int x, int y)
{
    static int index = 0;
    rec[index++] = x;
    rec[index++] = y;
}

//
// 생쥐를 한 칸 앞으로 이동
//
void forward(int *x, int *y, int dir)
{
    gotoxy(*x + 1, *y + 1);
    putch(' ');

    *x = (dir == LEFT) ? --(*x) :
        (dir == RIGHT) ? ++(*x) : *x;
    *y = (dir == UP) ? --(*y) :
        (dir == DOWN) ? ++(*y) : *y;

    record(*x, *y);
    gotoxy(*x + 1, *y + 1);
    putch(ROBOT);
}

//
// 생쥐를 시계방향으로
//
void right(int *dir)
{
    *dir <<= 1;
    *dir = (*dir > LEFT) ? UP : *dir;
}

//
// 생쥐를 반시계 방향으로
//
void left(int *dir)
{
    *dir >>= 1;
    *dir = (*dir == 0) ? LEFT : *dir;
}

//
// 아직 미로에 들어 있는가?
//
int still_in_maze(int x, int y)
{
    if(x > 0 && x < MAZE_SIZE - 1 && y > 0 && y < MAZE_SIZE -1)
        return 1;
    else
        return 0;
}

//
// 벽이 앞에 있는가?
//
int wall_ahead(int m[][MAZE_SIZE], int x, int y, int dir)
{
    x = (dir == LEFT) ? --x :
        (dir == RIGHT) ? ++x : x;
    y = (dir == UP) ? --y :
        (dir == DOWN) ? ++y : y;

    return m[x][y];
}

//
// 우선법 알고리즘
//
void right_hand(int m[][MAZE_SIZE], int x, int y, int dir)
{
    gotoxy(x+1, y+1);
    putch(ROBOT);
    record(x, y);

    forward(&x, &y, dir);
    while(still_in_maze(x, y))
    {
        delay(100);
        right(&dir);
        while(wall_ahead(m, x, y, dir))
            left(&dir);
        forward(&x, &y, dir);
    }
    record(-1, -1);
}

//
// 중복경로 삭제 알고리즘
//
void del_path(int i, int j)
{
    while(rec[j] >= 0)
        rec[i++] = rec[j++];
    rec[i] = -1;
}

//
// 중복경로 제거 알고리즘
//
void shortest_path(void)
{
    int i = 0;
    int x, y;
    int j;
    int x1, y1;

    while(rec[i] >= 0)
    {
        x = rec[i];
        y = rec[i + 1];
        j = i + 2;
        while(rec[j] >= 0)
        {
            x1 = rec[j];
            y1 = rec[j + 1];
            if(x == x1 && y == y1)
            {
                del_path(i, j);
            }
            j+=2;
        }
        i+=2;
    }

    i=0;        // 최단거리 생쥐 에니메이션
    while(rec[i] >= 0)
    {
        x = rec[i++];
        y = rec[i++];
        gotoxy(x + 1, y + 1);
        putch(ROBOT);
        delay(100);
        gotoxy(x + 1, y + 1);
        putch(' ');
    }
}