Class: Maze::Algorithm::RecursiveBacktracker

Inherits:
Object
  • Object
show all
Defined in:
lib/maze/algorithms/recursive_backtracker.rb

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(maze) ⇒ RecursiveBacktracker

Returns a new instance of RecursiveBacktracker.



7
8
9
 
# File 'lib/maze/algorithms/recursive_backtracker.rb', line 7

def initialize(maze)
  @maze = maze
end

Instance Attribute Details

#maze ⇒ Object (readonly)

Returns the value of attribute maze.



5
6
7
 
# File 'lib/maze/algorithms/recursive_backtracker.rb', line 5

def maze
  @maze
end

Instance Method Details

#find_path_from(current_point) ⇒ Object

  1. From the current point pick a neighbouring point which has not been visited in any direction.

  2. The coordinates of the next point has to be fetched w.r.t the direction of traversal. In certain cases like for edge points its possible to step out of bounds. We ignore these moves and pick another one which will keep us within the grid.

  3. When there is a valid move to a neighbouring point and it has not been visited earlier, both points are connected. Now the neighbouring point becomes the current point.

  4. We continue recursively connecting paths until we reach certain points from which there are no unvisited neighbours, in which case we continuously backtrack until we find a neighbouring unvisited point.

  5. The algorithm ends its run when it returns to initial point from where it started it’s traversal. At this point it’s guaranteed to have

    visited all the other points.



31
32
33
34
35
36
37
38
39
40
41
 
# File 'lib/maze/algorithms/recursive_backtracker.rb', line 31

def find_path_from(current_point)
  maze.random_directions.each do |direction|
    next_point = current_point.next(maze, direction)

    if next_point && next_point.unvisited?(maze)
      maze.connect(current_point, next_point, direction)

      find_path_from(next_point)
    end
  end
end

#run ⇒ Object

Start from any random point in the grid.



12
13
14
 
# File 'lib/maze/algorithms/recursive_backtracker.rb', line 12

def run
  find_path_from(Point.random(maze))
end