미로생성소스 (오픈소스)

 지난번에 설명드렸던 배열을 이용해 간단한 알고리즘을 사용해서 미로생성소스를 만들어보았습니다. 이 소스를 만들기 위해

 https://itgeniusyongsook.tistory.com/m/14 이 블로그에 있는 Prim's Algorithm 방법을 참고했습니다. 다만, 그대로 사용시 카톡으로 보내기 힘들어지기 때문에 조금 다르게 만들었습니다.  너비와 높이를 입력받고 이차원 배열을 이용해 모두 채운 후 랜덤으로 길을 뚫어가는 방식입니다.

실행결과

정답

 이 소스또한 사진으로만 올리면 잘못 옮기시는분이 있을 수 있으므로 글 가장 아래에 복붙용 소스를 넣어두겠습니다.

(단, 소스 내의 출처부분은 지우지 말아주세요)

복붙용 소스(PC에서 보시는 것을 추천드립니다.)

/*

  참고문헌: https://itgeniusyongsook.tistory.com/m/14

  이 블로그에서 Prim's Algorithm 방법을 약간 변형하였습니다.

  먼저 너비와 높이를 입력받고 이차원 배열을 이용해 모두 채운 후 랜덤으로 길을 뚫어가는 방식입니다.

  이 소스에서 1은 벽을, 2는 길을 의미합니다.

  사용방법: /미로생성 (높이) (너비)

  

*/

function test(ob,x,y,h,w){  //입력한 좌표 상하좌우 칸이 비어있는지 확인

  var testnum=0;

  if(x-1>=0&&ob[x-1][y]==2) testnum++;

  if(y-1>=0&&ob[x][y-1]==2) testnum++;

  if(x+1<w&&ob[x+1][y]==2) testnum++;

  if(y+1<h&&ob[x][y+1]==2) testnum++;

  if(testnum==1){

    return true;  //상하좌우 하나만 비어있으면 true

  }else{

    return false; //아니면 false

  }

}

function test2(ob,x,y,h,w){  //미로 해답을 만드는데 사용하는 함수

  var testnum=0;             //test2함수는 선택한 좌표에 있는 길 주변에있는 벽의 개수를 반환합니다.

  var x2=x-1;

  var y2=y-1;

  if(x2>=0&&ob[x2][y]==1) testnum++;

  if(y2>=0&&ob[x][y2]==1) testnum++;

  if(x+1<w&&ob[x+1][y]==1) testnum++;

  if(y+1<h&&ob[x][y+1]==1) testnum++;

  if(x-1<0) testnum++;

  if(y-1<0) testnum++;

  if(x+1==w) testnum++;

  if(y+1==h) testnum++;

  return testnum;

}

function fill(mi, x, y, w, h){

  for(var i=0 ; i<w/3 ; i++){

    var ch=[];

    mi[x][y]=2;

    if(x-1>0&&mi[x-1][y]==1&&test(mi,x-1,y,h,w)) ch.push(1);  //시작좌표 주변 빈칸 탐색

    if(x+1<w&&mi[x+1][y]==1&&test(mi,x+1,y,h,w)) ch.push(2);

    if(y-1>0&&mi[x][y-1]==1&&test(mi,x,y-1,h,w)) ch.push(3);

    if(y+1<h&&mi[x][y+1]==1&&test(mi,x,y+1,h,w)) ch.push(4);

    var num=Math.floor(Math.random()*(ch.length+1));  //탐색한 빈칸중 랜덤으로 하나 선택

    var c=ch[num];  //선택한 칸 번호 넣기

    if(c==1){  //선택한 칸 뚫고 좌표설정

      mi[x-1][y]=2;

      x--;

    }

    if(c==2){

      mi[x+1][y]=2;

      x++;

    }

    if(c==3){

      mi[x][y-1]=2;

      y--;

    }

    if(c==4){

      mi[x][y+1]=2;

      y++;

    }

  }

  return mi;

}

function response(room, msg, sender, isGroupChat, replier, ImageDB, packageName, threadId){

  var allsee=new Array(1000).join(String.fromCharCode(847));  //전체보기화용(도배방지) 변수

  

  if(msg.indexOf("/미로생성 ")==0&&Number(msg.split(" ")[2]<=24)&&Number(msg.split(" ")[1])<=300){  //범위제한

    var h=Number(msg.split(" ")[2]);  //높이 저장

    var w=Number(msg.split(" ")[1]);  //너비 저장 (카톡상에서 보기에는 가로가 높이, 세로가 너비 입니다.)

    var mi=[];  //미로배열 선언

    for(var i=0;i<w;i++){

      mi[i]=[];

      for(var j=0;j<h;j++){

        mi[i][j]=1;  //미로배열에 모두 1 넣기(모두 벽으로 꽉 채우기)

      }

    }

    var x=0;  //시작좌표

    var y=0;  //시작좌표

    var mi=fill(mi, x, y, w, h);  //fill함수 실행

    var ranx;

    var rany;

    for(var i=0 ; i<w*50 ; i++){

      do{

        ranx=Math.floor(Math.random()*w);

        rany=Math.floor(Math.random()*h);

      }while(mi[ranx][rany]!=2);  //미로중 뚤린칸(값이 2인 자리) 랜덤으로 하나 고르기

      mi=fill(mi, ranx, rany, w, h);  //고른 칸부터 다시 뚫기

    }  //너비의 50배만큼 반복

    if(mi[w-1][h-2]==1&&mi[w-2][h-1]==1) mi[w-1][h-2]=2;  //마지막부분 작업

    mi[w-1][h-1]=3;

    mi[0][0]="●";  //시작지점 그리기

    var log="";

    for(var i=0;i<w;i++){  //미로 그리기

      for(var j=0;j<h;j++){

        log+=mi[i][j];

      }

      log+="\n";

    }

    var so=[];

    for(var i=0;i<w;i++){  //만든 미로를 so배열에 복사

      so[i]=[];

      for(var j=0;j<h;j++){

        so[i][j]=mi[i][j];

      }

    }

    /*

      so배열에는 미로 해답을 만들었습니다.

      미로 해답을 만드는 방법은 세 면이 모두 벽으로 둘러쌓인 길은 제거하는 방식으로 계속 지워주면

      단 하나의 길만이 남는다는 것을 이용하였습니다.

    */

    for(var z=0 ; z<w*2 ; z++){  //test2함수를 이용해 미로해답 만들기

      for(var i=0 ; i<w ; i++){

        for(var j=0 ; j<h ; j++){

          if(mi[i][j]==2&&test2(mi,i,j,h,w)==3){

            mi[i][j]=1;  //만약 길 주위 벽이 3개이면 길 지우기

          }

        }

      }

    }

    var an=[];

    for(var i=0;i<w;i++){

      for(var j=0;j<h;j++){

        if(mi[i][j]==2) an.push([i, j]);

      }

    }

    for(var i=0;i<an.length;i++){

      so[an[i][0]][an[i][1]]=3;

    }

    log+="밑으로 내리시면 정답이 있습니다."+"\n".repeat(100);

    for(var i=0;i<w;i++){

      for(var j=0;j<h;j++){

        log+=so[i][j];

      }

      log+="\n";

    }

    //이부분은 지우지 말아주세요

    var sources="made by 지영\nhttps://rlawldud7130.tistory.com"

    replier.reply("미로찾기!!"+allsee+"\n\n"+log.replace(/1/g,"■").replace(/2/g,"□").replace(/3/g,"○")+sources);  //미로출력

  }

  if(msg.indexOf("/미로생성 ")==0&&(Number(msg.split(" ")[2]>24)||Number(msg.split(" ")[1])>300)) replier.reply("너무 커요");

  if(msg.indexOf("/미로생성")==0&&msg.replace(/[^ ]/g,"").length!=2) replier.reply("/미로생성 (세로길이) (가로길이) ㄱㄱ");

}