랜덤 미로 생성 및 출력하기

  이전에 C언어로 작성한 랜덤 미로 생성 알고리즘은 성공적이었다.

정상적으로 원하는 형태의 미로가 구현되는 것을 확인할 수 있었다.

 

  그런데, 마침 이번에 친구가 웹 그래픽스 수업을 들으면서 미로를 탈출하는 간단한 게임을 구현하고자 하는데

미로를 어떻게 하면 만들 수 있을지 그 조언을 구하였고, 이에 웹에서 사용할 수 있도록 Java Script 버전으로

재설계하여 그 소스코드를 전달하기로 했다.

 

  아래는 이것을 그래픽으로 출력한 예제를 구현한 것이다.

버튼을 누르면 미로가 무작위로 생성이 되며, 빨간색 사각형에서 파란색 사각형으로 이동하는 것이 목표다.

$(document).ready(function () {
    var wall = '-1', start = '0', end='1', empty = '2';
    var maze;

    function subDFS(maze, visited, y, x) {
        var temp = new Array(4), i, num, size = maze.length;
        var dx = [-2,2,0,0], dy =[0,0,-2,2], wx=[-1,1,0,0], wy=[0,0,-1,1];
        for(i=0; i<4; i++){
            num = Math.floor(Math.random()*4);
            if(temp.indexOf(num) == -1){
                temp[i] = num;
            }else{
                i--;
            }
        }
        for(i=0; i<4; i++){
            //기본적으로 가장자리가 있는 버전은 >=1 && < size-1, 가장자리가 없는 버전은  >=0 && < size
            if(y + dy[temp[i]] >= 1 && y + dy[temp[i]] < size-1&&x + dx[temp[i]] >= 1 && x + dx[temp[i]] < size-1&&visited[y + dy[temp[i]]][x + dx[temp[i]]] == false){
                maze[y+dy[temp[i]]][x+dx[temp[i]]] = empty;
                maze[y+wy[temp[i]]][x+wx[temp[i]]] = empty;
                visited[y+dy[temp[i]]][x+dx[temp[i]]] = true;
                visited[y+wy[temp[i]]][x+wx[temp[i]]] = true;
                subDFS(maze,visited,y+dy[temp[i]],x+dx[temp[i]]);
            }
        }
    };
    function DFS(maze, visited, y, x) {
        maze[y][x] = start;
        visited[y][x] = true;
        subDFS(maze, visited, y, x);
        //==========================================================================
        //좌표는 아래 셋중 하나에서 선택해서 적용
        //1 - setMaze 인자가 짝수일때는 (maze.length-1)/2를 좌표로 주면 정 가운데에서 종료
        //2 - setMaze 인자가 홀수일때는 y, x 좌표가 모두 홀수여야함
        //3 - setMaze 인자가 짝수인지 홀수인지에 상관없이 무조건 y, x 좌표가 모두 홀수여야함
        maze[maze.length-2][maze.length-2] = end;//기본적으로 최우하단이 도착점 maze.length-2, maze.length-2
        //기본적으로 가장자리가 있는 버전은 maze.length-2, 없는 버전은 maze.length-1
        //==========================================================================
    };
    function printMaze(maze){
        $("div[class='maze'").empty();
        for(i=0; i<maze.length; i++){
            for(j=0; j<maze.length; j++){
                //==========================================================================
                //기본적으로 한 블록은 20px, 원하는 크기로 수정 가능
                //==========================================================================
                if(maze[i][j] == '-1'){
                    $("div[id='maze'").append("<div class ='block black' style = 'top : "+20*i+"px; left : "+20*j+"px;'></div>");
                }else if(maze[i][j]=='0'){
                    $("div[id='maze'").append("<div class ='block red' style = 'top : "+20*i+"px; left : "+20*j+"px;'></div>");
                }else if(maze[i][j]=='1'){
                    $("div[id='maze'").append("<div class ='block blue' style = 'top : "+20*i+"px; left : "+20*j+"px;'></div>");
                }else{
                    $("div[id='maze'").append("<div class ='block white' style = 'top : "+20*i+"px; left : "+20*j+"px;'></div>");
                }            
            }
        }
    };

    function setMaze(size) {
        //가장자리가 있는 버전은 width와 height가 모두 size*2+3, 가장자리가 없는 버전은 width와 height가 모두 size*2+1
        var maze,visited, i, j, width = size*2+1, height = size*2+1;
        maze = new Array(height);
        visited = new Array(height);
        for(i=0; i<height; i++){
           maze[i] = new Array(width);
           visited[i] = new Array(width);
       }
       for(i=0; i<height;  i++){
          for(j=0; j<width; j++){
                maze[i][j] = wall;
                visited[i][j] = false;
            }
        }
        //==========================================================================
        //좌표는 아래 셋중 하나에서 선택해서 적용
        //1 - setMaze 인자가 짝수일때는 (maze.length-1)/2를 좌표로 주면 정 가운데에서 시작
        //2 - setMaze 인자가 홀수일때는 y, x 좌표가 모두 홀수여야함
        //3 - setMaze 인자가 짝수인지 홀수인지에 상관없이 무조건 y, x 좌표가 모두 홀수여야함
        DFS(maze,visited,1,1);//기본적으로 가장자리가 있는 버전은 1,1 가장자리가 없는 버전은 0,0이 기본 좌표
        //==========================================================================
        return maze;
    };

    $("button#btn").on("click",function () {
        //==========================================================================
        //setMaze 파라미터는 (가장자리제외한 미로판 크기 -1 )/2 여야함.
        //예를들어 가장자리 제외하고 실제 구현하고자하는 미로판 크기가 7이라면
        // (7-1)/2 = 3을 인자로 전달해야 7X7 미로가 만들어짐
        //==========================================================================
        maze = setMaze(5);
        printMaze(maze);
    });
});

 

 

 

랜덤 미로 알고리즘을 3D 웹 그래픽으로 출력한 모습, 친구의 프로그램에 해당 알고리즘이 적용되어있다.

 

버튼을 클릭하면 랜덤으로 미로가 생성되는 모습을 볼 수 있다.

 

 

 

실제 미로 탈출을 시연하는 영상, 제대로 미로가 구현이 되었고, 빈공간이 아닌 곳으로 이동시 오류가 발생한다.

 

  이런 식으로 직접 구현한 랜덤 미로 생성 알고리즘이 다른 사람의 프로그램에 적용되어 쓰일 수 있었다.