Class: Theseus::Algorithms::RecursiveBacktracker

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

Overview

The recursive backtracking algorithm is a quick, flexible algorithm for generating mazes. It tends to produce mazes with fewer dead-ends than algorithms like Kruskal’s or Prim’s.

Instance Attribute Summary collapse

Attributes inherited from Base

#maze

Instance Method Summary collapse

Methods inherited from Base

#pending?, #step

Constructor Details

#initialize(maze, options = {}) ⇒ RecursiveBacktracker

:nodoc:



15
16
17
18
19
20
21
22
23
24
25
26
 
# File 'lib/theseus/algorithms/recursive_backtracker.rb', line 15

def initialize(maze, options={}) #:nodoc:
  super

  loop do
    @y = rand(@maze.height)
    @x = rand(@maze.row_length(@y))
    break if @maze.valid?(@x, @y)
  end

  @tries = @maze.potential_exits_at(@x, @y).shuffle
  @stack = []
end

Instance Attribute Details

#x ⇒ Object (readonly)

The x-coordinate that the generation algorithm will consider next.



10
11
12
 
# File 'lib/theseus/algorithms/recursive_backtracker.rb', line 10

def x
  @x
end

#y ⇒ Object (readonly)

The y-coordinate that the generation algorithm will consider next.



13
14
15
 
# File 'lib/theseus/algorithms/recursive_backtracker.rb', line 13

def y
  @y
end

Instance Method Details

#do_step ⇒ Object

:nodoc:



28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
 
# File 'lib/theseus/algorithms/recursive_backtracker.rb', line 28

def do_step #:nodoc:
  direction = next_direction or return false
  nx, ny = @maze.move(@x, @y, direction)

  @maze.apply_move_at(@x, @y, direction)

  # if (nx,ny) is already visited, then we're weaving (moving either over
  # or under the existing passage).
  nx, ny, direction = @maze.perform_weave(@x, @y, nx, ny, direction) if @maze[nx, ny] != 0

  @maze.apply_move_at(nx, ny, @maze.opposite(direction))

  @stack.push([@x, @y, @tries])
  @tries = @maze.potential_exits_at(nx, ny).shuffle
  @tries.push direction if @tries.include?(direction) unless rand(100) < @maze.randomness
  @x, @y = nx, ny

  return true
end