Class: Amaze::Algorithm::Wilson

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

Instance Attribute Summary

Attributes inherited from Amaze::Algorithm

#duration

Instance Method Summary collapse

Methods inherited from Amaze::Algorithm

#on, #speed

Instance Method Details

#status ⇒ Object 



51
52
53
 
# File 'lib/amaze/algorithm/wilson.rb', line 51

def status
  "Wilson algorithm: #{duration}s"
end

#work(grid) ⇒ Object 



4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
 
# File 'lib/amaze/algorithm/wilson.rb', line 4

def work grid
  
  # initialize
  unvisited = []
  grid.each_cell {|cell| unvisited << cell }
  
  # pick randon cell and remove from unvisited
  start = unvisited.sample
  unvisited.delete start
  
  while unvisited.any?
    cell = unvisited.sample
    path = [cell]
    
    # loop erased walk
    while unvisited.include? cell
      cell = cell.neighbors.sample

      if path.include? cell
        path = path[0..path.index(cell)]
      else
        path << cell
      end

      yield Stat.new(                                   # visualize
        current: [start, *path].compact,                #
        pause: ! unvisited.include?(cell),              #
        info: "Path: #{path.size}") if block_given?     #

    end
    
    # carve path
    carved = 0                                          # visualize
    path.each_cons(2) do |cell1, cell2|
      cell1.link cell2
      unvisited.delete cell1
      
      yield Stat.new(                                   # visualize
        current: path,                                  #
        pause: cell2 == path.last,                      #
        info: "Carved: #{carved += 1}") if block_given? #

    end
    start = nil                                         # visualize
  end
end