Instantly share code, notes, and snippets.

# peterc/maze.rb Created Dec 17, 2009

What would you like to do?
 # Peter Cooper's initial Maze solution class Maze START_CHARACTER = 'A' END_CHARACTER = 'B' WALL_CHARACTER = '#' def initialize(maze) # Get the height and width of the maze @maze_width = maze[/^.*?\n/].length - 1 @maze_height = maze.split(/\n/).length # Store the maze as a string without any newlines @maze = maze.gsub(/\n/, '') # Get co-ordinates of the start and end points @start_x, @start_y = position_to_coords(@maze.index(START_CHARACTER)) @end_x, @end_y = position_to_coords(@maze.index(END_CHARACTER)) @routes = [] end # Returns true if the maze is solvable, false if not. def solvable? old_maze = @maze.dup flood_fill(@start_x, @start_y) possible = !@maze.index(END_CHARACTER) @maze = old_maze possible end # Returns how many steps are necessary to get from the start to the end of the maze def steps @steps = [] old_maze = @maze.dup walk_maze(@start_x, @start_y) possible = !@maze.index(END_CHARACTER) @maze = old_maze @steps.min end private # Convert a literal position within the maze string to X/Y co-ordinates def position_to_coords(pos) [pos % @maze_width, pos / @maze_width] end # Convert X/Y co-ordinates into a literal position within the maze string def coords_to_position(x, y) y * @maze_width + x end # Flood fill non wall areas of the maze def flood_fill(x, y) unless [WALL_CHARACTER, '.'].include?(@maze[coords_to_position(x, y)].chr) @maze[coords_to_position(x, y)] = '.' flood_fill(x - 1, y) flood_fill(x + 1, y) flood_fill(x, y - 1) flood_fill(x, y + 1) end end # Flood fill but track steps involved to an end point # A horribly lazy way to solve the "steps" issue def walk_maze(x, y, steps = 0) unless [WALL_CHARACTER, '.'].include?(@maze[coords_to_position(x, y)].chr) if x == @end_x && y == @end_y @steps << steps return end @i ||= 0 @i += 1 if defined?(DEBUG) sleep 0.05 print "\e[2J\e[f" puts @maze.scan(/.{37}/) end @maze[coords_to_position(x, y)] = '.' walk_maze(x - 1, y, steps + 1) if neighbors(x - 1, y) == 1 walk_maze(x + 1, y, steps + 1) if neighbors(x + 1, y) == 1 walk_maze(x, y - 1, steps + 1) if neighbors(x, y - 1) == 1 walk_maze(x, y + 1, steps + 1) if neighbors(x, y + 1) == 1 @maze[coords_to_position(x, y)] = ' ' end end # Return how many neighboring dots there are at a certain location def neighbors(x, y) neighbors = 0 neighbors += 1 if x - 1 >= 0 && @maze[coords_to_position(x - 1, y)].chr == '.' neighbors += 1 if x + 1 < @maze_width && @maze[coords_to_position(x + 1, y)].chr == '.' neighbors += 1 if y - 1 >= 0 && @maze[coords_to_position(x, y - 1)].chr == '.' neighbors += 1 if y + 1 < @maze_height && @maze[coords_to_position(x, y + 1)].chr == '.' neighbors end end if \$0 == __FILE__ MAZE1 = %{##################################### # # # # # # # # # # # # # ####### # ### # ####### # # # # # # # # # # # ##### # ################# # ####### # A# # # # # # # # ##### ##### ### ### # ### # # # # # # # # # # # # B# # # # # # # # ##### ##### # # ### # # ####### # # # # # # # # # # # # # # ### ### # # # # ##### # # # ##### # # # # # # # # #####################################} a = Maze.new(MAZE1) puts a.solvable? puts a.steps end