|
ferencd@0
|
1 #---
|
|
ferencd@0
|
2 # Excerpted from "Mazes for Programmers",
|
|
ferencd@0
|
3 # published by The Pragmatic Bookshelf.
|
|
ferencd@0
|
4 # Copyrights apply to this code. It may not be used to create training material,
|
|
ferencd@0
|
5 # courses, books, articles, and the like. Contact us if you are in doubt.
|
|
ferencd@0
|
6 # We make no guarantees that this code is fit for any purpose.
|
|
ferencd@0
|
7 # Visit http://www.pragmaticprogrammer.com/titles/jbmaze for more book information.
|
|
ferencd@0
|
8 #---
|
|
ferencd@0
|
9 class Ellers
|
|
ferencd@0
|
10
|
|
ferencd@0
|
11 class RowState
|
|
ferencd@0
|
12 def initialize(starting_set=0)
|
|
ferencd@0
|
13 @cells_in_set = {}
|
|
ferencd@0
|
14 @set_for_cell = []
|
|
ferencd@0
|
15 @next_set = starting_set
|
|
ferencd@0
|
16 end
|
|
ferencd@0
|
17
|
|
ferencd@0
|
18 def record(set, cell)
|
|
ferencd@0
|
19 @set_for_cell[cell.column] = set
|
|
ferencd@0
|
20
|
|
ferencd@0
|
21 @cells_in_set[set] = [] if !@cells_in_set[set]
|
|
ferencd@0
|
22 @cells_in_set[set].push cell
|
|
ferencd@0
|
23 end
|
|
ferencd@0
|
24
|
|
ferencd@0
|
25 def set_for(cell)
|
|
ferencd@0
|
26 if !@set_for_cell[cell.column]
|
|
ferencd@0
|
27 record(@next_set, cell)
|
|
ferencd@0
|
28 @next_set += 1
|
|
ferencd@0
|
29 end
|
|
ferencd@0
|
30
|
|
ferencd@0
|
31 @set_for_cell[cell.column]
|
|
ferencd@0
|
32 end
|
|
ferencd@0
|
33
|
|
ferencd@0
|
34 def merge(winner, loser)
|
|
ferencd@0
|
35 @cells_in_set[loser].each do |cell|
|
|
ferencd@0
|
36 @set_for_cell[cell.column] = winner
|
|
ferencd@0
|
37 @cells_in_set[winner].push cell
|
|
ferencd@0
|
38 end
|
|
ferencd@0
|
39
|
|
ferencd@0
|
40 @cells_in_set.delete(loser)
|
|
ferencd@0
|
41 end
|
|
ferencd@0
|
42
|
|
ferencd@0
|
43 def next
|
|
ferencd@0
|
44 RowState.new(@next_set)
|
|
ferencd@0
|
45 end
|
|
ferencd@0
|
46
|
|
ferencd@0
|
47 def each_set
|
|
ferencd@0
|
48 @cells_in_set.each { |set, cells| yield set, cells }
|
|
ferencd@0
|
49 self
|
|
ferencd@0
|
50 end
|
|
ferencd@0
|
51 end
|
|
ferencd@0
|
52
|
|
ferencd@0
|
53 def on(grid)
|
|
ferencd@0
|
54 row_state = RowState.new
|
|
ferencd@0
|
55
|
|
ferencd@0
|
56 grid.each_row do |row|
|
|
ferencd@0
|
57 row.each do |cell|
|
|
ferencd@0
|
58 next unless cell.west
|
|
ferencd@0
|
59
|
|
ferencd@0
|
60 set = row_state.set_for(cell)
|
|
ferencd@0
|
61 prior_set = row_state.set_for(cell.west)
|
|
ferencd@0
|
62
|
|
ferencd@0
|
63 should_link = set != prior_set &&
|
|
ferencd@0
|
64 (cell.south.nil? || rand(2) == 0)
|
|
ferencd@0
|
65
|
|
ferencd@0
|
66 if should_link
|
|
ferencd@0
|
67 cell.link(cell.west)
|
|
ferencd@0
|
68 row_state.merge(prior_set, set)
|
|
ferencd@0
|
69 end
|
|
ferencd@0
|
70 end
|
|
ferencd@0
|
71
|
|
ferencd@0
|
72 if row[0].south
|
|
ferencd@0
|
73 next_row = row_state.next
|
|
ferencd@0
|
74
|
|
ferencd@0
|
75 row_state.each_set do |_, list|
|
|
ferencd@0
|
76 list.shuffle.each_with_index do |cell, index|
|
|
ferencd@0
|
77 if index == 0 || rand(3) == 0
|
|
ferencd@0
|
78 cell.link(cell.south)
|
|
ferencd@0
|
79 next_row.record(row_state.set_for(cell), cell.south)
|
|
ferencd@0
|
80 end
|
|
ferencd@0
|
81 end
|
|
ferencd@0
|
82 end
|
|
ferencd@0
|
83
|
|
ferencd@0
|
84 row_state = next_row
|
|
ferencd@0
|
85 end
|
|
ferencd@0
|
86 end
|
|
ferencd@0
|
87 end
|
|
ferencd@0
|
88
|
|
ferencd@0
|
89 end
|
