maze_generator.md

미로 생성기

설명

미로를 자동으로 생성하는 turtlecraft(codingmath.xyz) JS 코드이다.

원리

우선 미로를 만들어내는데 사용할 수 있는 알고리즘이 많다. (구글에 maze generation algorithm 이라고 치면 많은 알고리즘을 볼 수 있다.) 나는 여기서 간단한 DFS(깊이 우선 탐색) 알고리즘을 사용하였다.

알고리즘의 설명을 하면 다음과 같다.

1. 우선 아무 칸에서 시작한다.
2. 현재 칸을 방문함(visited)으로 표시하고, 그 칸의 주변 칸 목록을 얻어온다. 무작위로 선택한 이웃하는 칸에서 다음과 같은 작업을 수행한다.

선택한 칸이 방문함으로 표시되지 않았다면, 선택한 칸과 현재 칸 사이의 벽을 없애고, 그 선택한 칸에서 다시 반복한다.

코드의 상세 설명

마지막에 나오는 코드에 대한 자세한 설명이다.

우선 maze 함수는 위에서 설명한 알고리즘을 이용해 미로를 만든다. 이 함수는 미로에 대한 데이터를 리턴하게 된다.

conv2text 함수는 이름처럼 maze 함수에서 리턴한 미로의 데이터를 사람이 읽을 수 있는 문자열으로 변환한다.

그 후, display 함수는 conv2text 함수가 리턴한 문자열을 이용해 turtlecraft 화면에 미로를 그린다.

코드

다음 코드를 turtlecraft에 붙여 넣으면 미로를 볼 수 있다.

function maze(x,y) {
  var n=x*y-1;
  if (n<0) {alert("illegal maze dimensions");return;}
  var horiz =[]; for (var j= 0; j<x+1; j++) horiz[j]= [],
    verti =[]; for (var j= 0; j<x+1; j++) verti[j]= [],
    here = [Math.floor(Math.random()*x), Math.floor(Math.random()*y)],
    path = [here],
    unvisited = [];
  for (var j = 0; j<x+2; j++) {
    unvisited[j] = [];
    for (var k= 0; k<y+1; k++)
      unvisited[j].push(j>0 && j<x+1 && k>0 && (j != here[0]+1 || k != here[1]+1));
  }
  while (0<n) {
    var potential = [[here[0]+1, here[1]], [here[0],here[1]+1],
      [here[0]-1, here[1]], [here[0],here[1]-1]];
    var neighbors = [];
    for (var j = 0; j < 4; j++)
      if (unvisited[potential[j][0]+1][potential[j][1]+1])
        neighbors.push(potential[j]);
    if (neighbors.length) {
      n = n-1;
      next= neighbors[Math.floor(Math.random()*neighbors.length)];
      unvisited[next[0]+1][next[1]+1]= false;
      if (next[0] == here[0])
        horiz[next[0]][(next[1]+here[1]-1)/2]= true;
      else 
        verti[(next[0]+here[0]-1)/2][next[1]]= true;
      path.push(here = next);
    } else 
      here = path.pop();
  }
  return {x: x, y: y, horiz: horiz, verti: verti};
}
 
function conv2text(m) {
  var text= [];
  for (var j= 0; j<m.x*2+1; j++) {
    var line= [];
    if (0 == j%2)
      for (var k=0; k<m.y*4+1; k++)
        if (0 == k%4) 
          line[k]= '+';
        else
          if (j>0 && m.verti[j/2-1][Math.floor(k/4)])
            line[k]= ' ';
          else
            line[k]= '-';
    else
      for (var k=0; k<m.y*4+1; k++)
        if (0 == k%4)
          if (k>0 && m.horiz[(j-1)/2][k/4-1])
            line[k]= ' ';
          else
            line[k]= '|';
        else
          line[k]= ' ';
    if (0 == j) line[1]= line[2]= line[3]= ' ';
    if (m.x*2-1 == j) line[4*m.y]= ' ';
    text.push(line.join('')+'\n');
  }
  return text.join('');
}

function display(text) {
  var textLines = text.split('\n').map(function(str) {
    return str.replace(/[-+|]/g, '#');
  });
  console.log(textLines);
  for (var i = 0; i < textLines.length; i++) {
    for (var j = 0; j < textLines[i].length; j++) {
      if (textLines[i][j] == '#') {
        cube(i, j, 1, 9);
        cube(i, j, 2, 9);
      }
    }
  }
}

var mazeText = conv2text(maze(10, 10));
display(mazeText);