ferencd@0: #---
ferencd@0: # Excerpted from "Mazes for Programmers",
ferencd@0: # published by The Pragmatic Bookshelf.
ferencd@0: # Copyrights apply to this code. It may not be used to create training material, 
ferencd@0: # courses, books, articles, and the like. Contact us if you are in doubt.
ferencd@0: # We make no guarantees that this code is fit for any purpose. 
ferencd@0: # Visit http://www.pragmaticprogrammer.com/titles/jbmaze for more book information.
ferencd@0: #---
ferencd@0: 
ferencd@0: # Direction constants
ferencd@0: NORTH, SOUTH, EAST, WEST, NOWHERE = 1, 2, 4, 8, 0
ferencd@0: 
ferencd@0: DIRECTIONS = { :EAST => 'E', :WEST => 'W', :NORTH => 'N', :SOUTH => 'S', :NOWHERE => '?'}
ferencd@0: 
ferencd@0: require 'distances'
ferencd@0: 
ferencd@0: class Cell
ferencd@0:   attr_reader :row, :column
ferencd@0:   attr_accessor :north, :south, :east, :west
ferencd@0: 
ferencd@0:   def initialize(row, column)
ferencd@0:     @row, @column = row, column
ferencd@0:     @links = {}
ferencd@0:   end
ferencd@0: 
ferencd@0:   def link(cell, bidi=true)
ferencd@0:     @links[cell] = true
ferencd@0:     cell.link(self, false) if bidi
ferencd@0:     self
ferencd@0:   end
ferencd@0: 
ferencd@0:   def unlink(cell, bidi=true)
ferencd@0:     @links.delete(cell)
ferencd@0:     cell.unlink(self, false) if bidi
ferencd@0:     self
ferencd@0:   end
ferencd@0: 
ferencd@0:   def links
ferencd@0:     @links.keys
ferencd@0:   end
ferencd@0: 
ferencd@0:   def linked?(cell)
ferencd@0:     @links.key?(cell)
ferencd@0:   end
ferencd@0: 
ferencd@0:   def neighbors
ferencd@0:     list = []
ferencd@0:     list << north if north
ferencd@0:     list << south if south
ferencd@0:     list << east  if east
ferencd@0:     list << west  if west
ferencd@0:     list
ferencd@0:   end
ferencd@0: 
ferencd@0:   def distances
ferencd@0:     distances = Distances.new(self) 
ferencd@0:     frontier = [ self ]
ferencd@0: 
ferencd@0:     while frontier.any? 
ferencd@0:       new_frontier = [] 
ferencd@0: 
ferencd@0:       frontier.each do |cell| 
ferencd@0:         cell.links.each do |linked| 
ferencd@0:           next if distances[linked] 
ferencd@0:           distances[linked] = distances[cell] + 1 
ferencd@0:           new_frontier << linked 
ferencd@0:         end
ferencd@0:       end
ferencd@0: 
ferencd@0:       frontier = new_frontier 
ferencd@0:     end
ferencd@0: 
ferencd@0:     distances
ferencd@0:   end
ferencd@0: 
ferencd@0: 
ferencd@0:   def direction(cell)
ferencd@0:     return NORTH if cell == north
ferencd@0:     return SOUTH if cell == south
ferencd@0:     return EAST if cell == east
ferencd@0:     return WEST if cell == west
ferencd@0:     0
ferencd@0:   end
ferencd@0: 
ferencd@0: end