Created

Embed URL

HTTPS clone URL

SSH clone URL

You can clone with HTTPS or SSH.

Download Gist
View maze.rb
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Something went wrong with that request. Please try again.