class MazeCrosser::RecursiveAlgorithmRunner
Class responsible for applying resursive algorithm to a maze.
recursive_algorithm = RecursiveAlgorithmRunner.new(maze)
Run the algorithm recursive_algorithm.run
Public Class Methods
new(maze)
click to toggle source
# File lib/maze_crosser/algorithms/recursive_algorithm_runner.rb, line 9 def initialize(maze) @maze = maze @path = [] end
Public Instance Methods
run()
click to toggle source
# File lib/maze_crosser/algorithms/recursive_algorithm_runner.rb, line 14 def run find_path(@maze.start) @path end
Private Instance Methods
already_visited?(coords)
click to toggle source
# File lib/maze_crosser/algorithms/recursive_algorithm_runner.rb, line 42 def already_visited?(coords) @path.include?(coords) end
blocked?(coords)
click to toggle source
# File lib/maze_crosser/algorithms/recursive_algorithm_runner.rb, line 50 def blocked?(coords) @maze.blocked_cell?(coords) end
dead_end?(coords)
click to toggle source
# File lib/maze_crosser/algorithms/recursive_algorithm_runner.rb, line 54 def dead_end?(coords) out_of_bounds?(coords) || blocked?(coords) || already_visited?(coords) end
find_path(coords)
click to toggle source
This method is based on the recursive algorithm described in: www.cs.bu.edu/teaching/alg/maze/ PROS: Easy to understand, simple implementation CONS: Does not necessarily find the shortest path
# File lib/maze_crosser/algorithms/recursive_algorithm_runner.rb, line 25 def find_path(coords) return false if dead_end?(coords) if goal_found?(coords) @path << coords return true end # This cell may actually be part of the solution, let's check @path << coords return true if valid_move_available?(coords) # Since we got here, this cell can't be part of the solution @path.pop false end
goal_found?(coords)
click to toggle source
# File lib/maze_crosser/algorithms/recursive_algorithm_runner.rb, line 60 def goal_found?(coords) coords == @maze.goal end
move_east(coords)
click to toggle source
# File lib/maze_crosser/algorithms/recursive_algorithm_runner.rb, line 79 def move_east(coords) find_path([coords[0], coords[1] + 1]) end
move_north(coords)
click to toggle source
# File lib/maze_crosser/algorithms/recursive_algorithm_runner.rb, line 71 def move_north(coords) find_path([coords[0] - 1, coords[1]]) end
move_south(coords)
click to toggle source
# File lib/maze_crosser/algorithms/recursive_algorithm_runner.rb, line 75 def move_south(coords) find_path([coords[0] + 1, coords[1]]) end
move_west(coords)
click to toggle source
# File lib/maze_crosser/algorithms/recursive_algorithm_runner.rb, line 83 def move_west(coords) find_path([coords[0], coords[1] - 1]) end
out_of_bounds?(coords)
click to toggle source
# File lib/maze_crosser/algorithms/recursive_algorithm_runner.rb, line 46 def out_of_bounds?(coords) !@maze.inside_grid?(coords) end
valid_move_available?(coords)
click to toggle source
# File lib/maze_crosser/algorithms/recursive_algorithm_runner.rb, line 64 def valid_move_available?(coords) return true if move_north(coords) || move_south(coords) || move_east(coords) || move_west(coords) end