codepad

Language:

=begin
Backtracking 을 이용하여 미로 탈출

=end

class Location
  attr_accessor :row, :col

end

class Maze
  attr_accessor :map_matrix, :height, :width

attr_accessor :start

WALL = '#'
  ROAD = ' '
  WALK = '+'
  START = 'S'
  GOAL = 'G'

DIRECTION = [:NORTH, :WEST, :EAST, :SOUTH]

def initialize()
    @map_matrix = []

end

def init_map(height, width)
    @height = height
    @width = width

(0..@height).each do |i|
      @map_matrix[i] = []

(0..@width).each { |j| @map_matrix[i][j] = ROAD }
    end
  end

def print_maze
    puts "------------- Start Printing Maze ------------------"

(0...@height).each do |i|
      (0...@width).each do |j|
        print @map_matrix[i][j]
      end

puts
    end

puts "------------- End of Printing Maze -----------------"
  end

def Maze.init_example_maze()
=begin
* 예제 미로 모양
#G#######
#       #
### # ###
### #   #
#   ### #
# ###   #
# #S### #
# #     #
#########
=end

maze = Maze.new
    maze.init_map(9, 9)

maze.map_matrix[0] = [WALL, GOAL, WALL, WALL, WALL, WALL, WALL, WALL, WALL]
    maze.map_matrix[1] = [WALL, ROAD, ROAD, ROAD, ROAD, ROAD, ROAD, ROAD, WALL]
    maze.map_matrix[2] = [WALL, WALL, WALL, ROAD, WALL, ROAD, WALL, WALL, WALL]
    maze.map_matrix[3] = [WALL, WALL, WALL, ROAD, WALL, ROAD, ROAD, ROAD, WALL]
    maze.map_matrix[4] = [WALL, ROAD, ROAD, ROAD, WALL, WALL, WALL, ROAD, WALL]
    maze.map_matrix[5] = [WALL, ROAD, WALL, WALL, WALL, ROAD, ROAD, ROAD, WALL]
    maze.map_matrix[6] = [WALL, ROAD, WALL, START, WALL, WALL, WALL, ROAD, WALL]
    maze.map_matrix[7] = [WALL, ROAD, WALL, ROAD, ROAD, ROAD, ROAD, ROAD, WALL]
    maze.map_matrix[8] = [WALL, WALL, WALL, WALL, WALL, WALL, WALL, WALL, WALL]

maze.start = Location.new
    maze.start.row = 6
    maze.start.col = 3

maze
  end

def Maze.load_maze(file_path)
    maze = Maze.new

start_loc = Location.new

maze_width = -1
    maze_height = 0

File.open(file_path, "r") do |file|
      while line = file.gets

line.chomp!

line_len = line.length

if -1 == maze_width
          maze_width = line_len
        else
          if line_len != maze_width
            puts "Maze data is not square!!!"
            return nil
          end
        end

maze_height += 1
      end

file.rewind

maze.init_map(maze_height, maze_width)

(0...maze_height).each do |i|
        line = file.gets

line.chomp!

line_arr = line.split(//)

(0...maze_width).each do |j|
          maze.map_matrix[i][j] = line_arr[j]

start_loc.row, start_loc.col = i, j if Maze::START == maze.map_matrix[i][j]
        end
      end

end

maze.start = start_loc
    maze
  end

end

class MazeExplorer
  
  def initialize(maze)
    @maze = maze
    
  end

def solve_maze
    if move(@maze.start)
      @maze.map_matrix[@maze.start.row][@maze.start.col] = Maze::START
      @maze.print_maze
    else
      puts("No Way to Exit!!")
    end

end

def move(curr)
    return nil if !check_valid(curr)

return true if Maze::GOAL == @maze.map_matrix[curr.row][curr.col]

@maze.map_matrix[curr.row][curr.col] = Maze::WALK

Maze::DIRECTION.each do |dir|
      new_loc = Location.new

new_loc.row, new_loc.col = curr.row, curr.col

case dir
      when :NORTH
        new_loc.row = curr.row - 1
      when :WEST
        new_loc.col = curr.col - 1
      when :EAST
        new_loc.col = curr.col + 1
      when :SOUTH
        new_loc.row = curr.row + 1
      end

return true if move(new_loc)
    end

# move to new Direction : ALL nil // do backtracking
    @maze.map_matrix[curr.row][curr.col] = Maze::ROAD

return nil
  end

def check_valid(curr)
    return nil if curr.row < 0 || curr.row >= @maze.height
    
    return nil if curr.col < 0 || curr.col >= @maze.width

if Maze::WALL == @maze.map_matrix[curr.row][curr.col] ||
        Maze::WALK == @maze.map_matrix[curr.row][curr.col]
        return nil
    end

return true
  end

end

maze = Maze.init_example_maze
#maze = Maze.load_maze("MazeSample.dat")

person = MazeExplorer.new(maze)
person.solve_maze

Private [?]

Run code