Class: Amaze::Algorithm::RecursiveBacktracker

Inherits:
Amaze::Algorithm show all
Defined in:
lib/amaze/algorithm/recursive_backtracker.rb

Instance Attribute Summary

Attributes inherited from Amaze::Algorithm

#duration

Instance Method Summary collapse

Methods inherited from Amaze::Algorithm

#on, #speed

Constructor Details

#initialize ⇒ RecursiveBacktracker

Returns a new instance of RecursiveBacktracker.



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

def initialize
  @implementation = :stack
end

Instance Method Details

#carve(path, &block) ⇒ Object

implementation with recursion



43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
 
# File 'lib/amaze/algorithm/recursive_backtracker.rb', line 43

def carve path, &block
  current = path.last

  while current
    unvisited_neighbors = current.neighbors.select {|c| c.links.empty? }

    yield Stat.new(                               # visualize
      current: path,                              #
      pause: segment?(unvisited_neighbors),       #
      info: "Path: #{path.size}") if block_given? #

    if unvisited_neighbors.any?
      neighbor = unvisited_neighbors.sample
      current.link neighbor
      carve [*path, neighbor], &block
    else
      current = nil
    end
  end
end

#configure(implementation) ⇒ Object 



8
9
10
 
# File 'lib/amaze/algorithm/recursive_backtracker.rb', line 8

def configure implementation
  @implementation = implementation
end

#segment?(unvisited_neighbors) ⇒ Boolean

Returns:

  • (Boolean) 


64
65
66
67
68
69
70
71
72
 
# File 'lib/amaze/algorithm/recursive_backtracker.rb', line 64

def segment? unvisited_neighbors
  @forward = true if @forward.nil?
  if unvisited_neighbors.empty? && @forward || unvisited_neighbors.any? && !@forward
    @forward = !@forward
    true
  else
    false
  end
end

#status ⇒ Object 



74
75
76
 
# File 'lib/amaze/algorithm/recursive_backtracker.rb', line 74

def status
  "Recursive Backtracker (#{@implementation}) algorithm: #{duration}s"
end

#work(grid, &block) ⇒ Object 



12
13
14
15
16
17
18
19
 
# File 'lib/amaze/algorithm/recursive_backtracker.rb', line 12

def work grid, &block
  case @implementation
  when :recursion
    carve [grid.random_cell], &block
  when :stack
    work_with_stack [grid.random_cell], &block
  end
end

#work_with_stack(stack, &block) ⇒ Object

implementation with explicit stack



22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
 
# File 'lib/amaze/algorithm/recursive_backtracker.rb', line 22

def work_with_stack stack, &block
  while stack.any?
    current = stack.last
    unvisited_neighbors = current.neighbors.select {|c| c.links.empty? }

    yield Stat.new(                                # visualize
      current: stack,                              #
      pause: segment?(unvisited_neighbors),        #
      info: "Path: #{stack.size}") if block_given? #
    
    if unvisited_neighbors.any?
      neighbor = unvisited_neighbors.sample
      current.link neighbor
      stack << neighbor
    else
      stack.pop
    end
  end
end