Skip to content

@peterc /maze.rb
Created

Embed URL

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
# 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.