Class: Knossos::Algorithm::RecursiveBacktracker

Inherits:
Object
  • Object
show all
Defined in:
lib/knossos/algorithm/recursive_backtracker.rb

Instance Method Summary collapse

Constructor Details

#initialize ⇒ RecursiveBacktracker

Returns a new instance of RecursiveBacktracker.



4
5
6
 
# File 'lib/knossos/algorithm/recursive_backtracker.rb', line 4

def initialize
  # nothing to do
end

Instance Method Details

#carve(grid:, start_at: nil, seed: nil) ⇒ Object 



8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
 
# File 'lib/knossos/algorithm/recursive_backtracker.rb', line 8

def carve(grid:, start_at: nil, seed: nil)
  srand(seed || Kernel.srand)

  start_at ||= grid.random_cell

  stack = []
  stack.push start_at

  while stack.any?
    current = stack.last
    neighbors = grid.neighborhood(current).select { |n| n.links.empty? }

    if neighbors.empty?
      stack.pop
    else
      neighbor = neighbors.sample
      grid.build_passage(current, neighbor)
      stack.push(neighbor)
    end
  end

  grid
end