public
Created

  • Download Gist
maze.rb
Ruby
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118
# 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

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.