Class: Theseus::Algorithms::Prim

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

Constant Summary collapse

IN =

indicate that a cell, though blank, is part of the IN set

0x10000
FRONTIER =

indicate that a cell is part of the frontier set

0x20000

Instance Attribute Summary

Attributes inherited from Base

#maze

Instance Method Summary collapse

Methods inherited from Base

#pending?, #step

Constructor Details

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

:nodoc:



9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
 
# File 'lib/theseus/algorithms/prim.rb', line 9

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

  if @maze.weave > 0
    raise ArgumentError, "weave mazes cannot be generated with prim's algorithm"
  end

  @frontier = []

  loop do
    y = rand(@maze.height)
    x = rand(@maze.row_length(y))
    next unless @maze.valid?(x, y)

    mark_cell(x, y)
    break
  end
end

Instance Method Details

#do_step ⇒ Object

:nodoc:



36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
 
# File 'lib/theseus/algorithms/prim.rb', line 36

def do_step #:nodoc:
  if rand(100) < @maze.randomness
    x, y = @frontier.delete_at(rand(@frontier.length))
  else
    x, y = @frontier.pop
  end

  neighbors = find_neighbors_of(x, y)
  direction, nx, ny = neighbors[rand(neighbors.length)]

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

  mark_cell(x, y)

  @pending = @frontier.any?
end

#each_frontier ⇒ Object

Iterates over each cell in the frontier space, yielding the coordinates of each one.



30
31
32
33
34
 
# File 'lib/theseus/algorithms/prim.rb', line 30

def each_frontier
  @frontier.each do |x, y|
    yield x, y
  end
end