자동 미로 생성 예제

루비로 구현해 본 자동 미로 생성 예제입니다.

구현된 알고리즘은 깊이 우선 탐색법(DFS; Depth First Search)을 이용한 알고리즘입니다.
지정된 랜덤 방향으로 계속해서 뚫어 나가다가 더 이상 뚫을 수 없게 되면 뒤로 돌아가면서 뚫을 수 있는 곳이 발견되면 다시 뚫어 나가는 구조입니다. 깊이 우선 방식이므로 재귀호출을 이용합니다.

이 방법으로 미로를 만들게 되면 항상 다음과 같은 특징을 갖게 됩니다.
- 미로판 전체에 미로가 생성됨.
- 미로판 어느 곳이든 이동이 가능함.
- 특정 위치에서 특정 위치로 이동하는 문제에 대하여 단 하나의 해만 존재함.

다음은 DFS 자동 미로 예제 코드입니다.

# 자동 미로 생성 예제 (DFS)
class Maze
  # 설정할 값
  CHR_WALL    = "■"
  CHR_EMPTY   = "  "
  CHR_SOLVE   = "○"
  MAZE_WIDTH  = 18        # 미로의 가로 칸 수
  MAZE_HEIGHT = 10        # 미로의 세로 칸 수
  VIEW_SOLUTION = true    # false로 설정하면 해를 표시하지 않음
  
  # 미로 초기설정
  def initialize
    @maze_order = [1, 2, 4, 8]    # 미로 순서 (1하, 2좌, 3우, 4상)
    # 미로판 배열 정의
    @maze_way = Array.new(MAZE_HEIGHT) { Array.new(MAZE_WIDTH, 0) }
    @maze_sway = Array.new(MAZE_HEIGHT) { Array.new(MAZE_WIDTH, false) }
    @maze_solved = false          # 도착지까지 가면 true
  end
  
  # 미로 생성하기 (재귀호출)
  def road_make(y, x)
    @maze_sway[y][x] = true if !@maze_solved && VIEW_SOLUTION
    @maze_solved = true if x == MAZE_WIDTH - 1 && y == MAZE_HEIGHT - 1
    @maze_order.shuffle!    # 미로 뚫는 순서 섞기
    oo = 0                  # 미로 순서 배열 참조용 변수
    while oo <= 3           # 뚫을 방향이 없을 때까지 반복
      xx = x                # 뚫을 x좌표 지정 변수
      yy = y                # 뚫을 y좌표 지정 변수
      noway = true          # 뚫을 수 없음을 지정할 진리변수
      
      case @maze_order[oo]    # 방향에 따른 분기
      when 1
        # 아래(1): 맨 아래가 아닐 경우만 유효
        if y < MAZE_HEIGHT - 1
          yy += 1
          noway = false
        end
      when 2
        # 왼쪽(2): 맨 왼쪽이 아닐 경우만 유효
        if x > 0
          xx -= 1
          noway = false
        end
      when 4
        # 오른쪽(4): 맨 오른쪽이 아닐 경우만 유효
        if x < MAZE_WIDTH - 1
          xx += 1
          noway = false
        end
      when 8
        # 위(8): 맨 위가 아닐 경우만 유효
        if y > 0
          yy -= 1
          noway = false
        end
      end
      
      if !noway && @maze_way[yy][xx] == 0
        # 방향이 유효하고 뚫을 목적지가 비어 있어야 처리
        @maze_way[y][x] += @maze_order[oo]            # 지정 방향으로 뚫기
        @maze_way[yy][xx] += (8 / @maze_order[oo])    # 목적지는 반대로
        road_make(yy, xx)    # 목적지 좌표로 재귀호출
      else
        oo += 1    # 뚫지 못하면 방향 차례를 넘김
      end
    end
    @maze_sway[y][x] = false if !@maze_solved
  end
  
  # 생성된 미로 출력
  def maze_print
    pchar = ""    # 출력용 문자열
    
    # 세로 칸 수만큼 반복
    for i in 0..(MAZE_HEIGHT - 1)
      # 가로 칸 수만큼 반복
      for j in 0..(MAZE_WIDTH - 1)
        # 위쪽(8)이 뚫려 있는가의 여부 검사
        pchar = CHR_WALL
        if @maze_way[i][j] >= 8
          if @maze_sway[i-1][j] && @maze_sway[i][j]
            # 뚫려 있음 + 해
            pchar += CHR_SOLVE
          else
            # 뚫려 있음 + 해 아님
            pchar += CHR_EMPTY
          end
        else
          # 뚫려 있지 않음
          pchar += CHR_WALL
        end
        pchar = "출발" if i == 0 && j == 0
        print pchar
      end
      print CHR_WALL + "\n"    # 맨 우측벽 출력
      
      for j in 0..(MAZE_WIDTH - 1)
        if @maze_way[i][j] % 4 >= 2
          # 왼쪽(2)이 뚫려 있는가의 여부 검사
          if @maze_sway[i][j-1] && @maze_sway[i][j]
            # 뚫려 있음 + 해
            pchar = CHR_SOLVE
          else
            # 뚫려 있음 + 해 아님
            pchar = CHR_EMPTY
          end
        else
          # 뚫려 있지 않음
          pchar = CHR_WALL
        end
        # 해 검사
        @maze_sway[i][j] ? pchar += CHR_SOLVE : pchar += CHR_EMPTY
        print pchar
      end
      print CHR_WALL + "\n"    # 맨 우측벽 출력
    end
    
    # 맨 아래쪽 벽을 출력
    print CHR_WALL * (MAZE_WIDTH * 2 - 1) + "도착"
    puts
  end
  
  # 미로 생성 시작
  def maze_start
    road_make(0, 0)
    maze_print
  end
end

# 미로 시작
mz=Maze.new
mz.maze_start

아래는 이 코드를 실행한 스크린샷입니다.

유용하게 활용하시기 바랍니다.