|
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
|
|
ferencd@0
|
10 # Direction constants
|
|
ferencd@0
|
11 NORTH, SOUTH, EAST, WEST, NOWHERE = 1, 2, 4, 8, 0
|
|
ferencd@0
|
12
|
|
ferencd@0
|
13 DIRECTIONS = { :EAST => 'E', :WEST => 'W', :NORTH => 'N', :SOUTH => 'S', :NOWHERE => '?'}
|
|
ferencd@0
|
14
|
|
ferencd@0
|
15 require 'distances'
|
|
ferencd@0
|
16
|
|
ferencd@0
|
17 class Cell
|
|
ferencd@0
|
18 attr_reader :row, :column
|
|
ferencd@0
|
19 attr_accessor :north, :south, :east, :west
|
|
ferencd@0
|
20
|
|
ferencd@0
|
21 def initialize(row, column)
|
|
ferencd@0
|
22 @row, @column = row, column
|
|
ferencd@0
|
23 @links = {}
|
|
ferencd@0
|
24 end
|
|
ferencd@0
|
25
|
|
ferencd@0
|
26 def link(cell, bidi=true)
|
|
ferencd@0
|
27 @links[cell] = true
|
|
ferencd@0
|
28 cell.link(self, false) if bidi
|
|
ferencd@0
|
29 self
|
|
ferencd@0
|
30 end
|
|
ferencd@0
|
31
|
|
ferencd@0
|
32 def unlink(cell, bidi=true)
|
|
ferencd@0
|
33 @links.delete(cell)
|
|
ferencd@0
|
34 cell.unlink(self, false) if bidi
|
|
ferencd@0
|
35 self
|
|
ferencd@0
|
36 end
|
|
ferencd@0
|
37
|
|
ferencd@0
|
38 def links
|
|
ferencd@0
|
39 @links.keys
|
|
ferencd@0
|
40 end
|
|
ferencd@0
|
41
|
|
ferencd@0
|
42 def linked?(cell)
|
|
ferencd@0
|
43 @links.key?(cell)
|
|
ferencd@0
|
44 end
|
|
ferencd@0
|
45
|
|
ferencd@0
|
46 def neighbors
|
|
ferencd@0
|
47 list = []
|
|
ferencd@0
|
48 list << north if north
|
|
ferencd@0
|
49 list << south if south
|
|
ferencd@0
|
50 list << east if east
|
|
ferencd@0
|
51 list << west if west
|
|
ferencd@0
|
52 list
|
|
ferencd@0
|
53 end
|
|
ferencd@0
|
54
|
|
ferencd@0
|
55 def distances
|
|
ferencd@0
|
56 distances = Distances.new(self)
|
|
ferencd@0
|
57 frontier = [ self ]
|
|
ferencd@0
|
58
|
|
ferencd@0
|
59 while frontier.any?
|
|
ferencd@0
|
60 new_frontier = []
|
|
ferencd@0
|
61
|
|
ferencd@0
|
62 frontier.each do |cell|
|
|
ferencd@0
|
63 cell.links.each do |linked|
|
|
ferencd@0
|
64 next if distances[linked]
|
|
ferencd@0
|
65 distances[linked] = distances[cell] + 1
|
|
ferencd@0
|
66 new_frontier << linked
|
|
ferencd@0
|
67 end
|
|
ferencd@0
|
68 end
|
|
ferencd@0
|
69
|
|
ferencd@0
|
70 frontier = new_frontier
|
|
ferencd@0
|
71 end
|
|
ferencd@0
|
72
|
|
ferencd@0
|
73 distances
|
|
ferencd@0
|
74 end
|
|
ferencd@0
|
75
|
|
ferencd@0
|
76
|
|
ferencd@0
|
77 def direction(cell)
|
|
ferencd@0
|
78 return NORTH if cell == north
|
|
ferencd@0
|
79 return SOUTH if cell == south
|
|
ferencd@0
|
80 return EAST if cell == east
|
|
ferencd@0
|
81 return WEST if cell == west
|
|
ferencd@0
|
82 0
|
|
ferencd@0
|
83 end
|
|
ferencd@0
|
84
|
|
ferencd@0
|
85 end
|
