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