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: require 'cell'
ferencd@0: 
ferencd@0: # Corner constants, to know where to put a torch
ferencd@0: TOP_LEFT = 1
ferencd@0: TOP_RIGHT = 2
ferencd@0: BOTTOM_LEFT = 4
ferencd@0: BOTTOM_RIGHT = 8
ferencd@0: 
ferencd@0: class Room
ferencd@0:   attr_reader :x1, :y1, :x2, :y2
ferencd@0: 
ferencd@0:   def initialize(px1,py1,px2,py2)
ferencd@0:     @x1 = px1
ferencd@0:     @x2 = px2
ferencd@0:     @y1 = py1
ferencd@0:     @y2 = py2
ferencd@0:   end
ferencd@0: 
ferencd@0:   def in(x, y)
ferencd@0:     return x > @x1-1 && x < @x2+1 && y > @y1-1 && y < @y2+1
ferencd@0:   end
ferencd@0: end
ferencd@0: 
ferencd@0: 
ferencd@0: class Grid
ferencd@0:   attr_reader :rows, :columns, :dead_ends
ferencd@0: 
ferencd@0:   def initialize(rows, columns)
ferencd@0:     @rows = rows
ferencd@0:     @columns = columns
ferencd@0:     @grid = prepare_grid
ferencd@0:     @rooms = []
ferencd@0: 
ferencd@0:     # Where food will go
ferencd@0:     @dead_ends = {}
ferencd@0:     @dead_ends[1] = []
ferencd@0:     @dead_ends[2] = []
ferencd@0:     @dead_ends[4] = []
ferencd@0:     @dead_ends[8] = []
ferencd@0: 
ferencd@0:     configure_cells
ferencd@0: 
ferencd@0:   end
ferencd@0: 
ferencd@0:   def prepare_grid
ferencd@0:     Array.new(rows) do |row|
ferencd@0:       Array.new(columns) do |column|
ferencd@0:         Cell.new(row, column)
ferencd@0:       end
ferencd@0:     end
ferencd@0:   end
ferencd@0: 
ferencd@0:   def configure_cells
ferencd@0:     each_cell do |cell|
ferencd@0:       row, col = cell.row, cell.column
ferencd@0: 
ferencd@0:       cell.north = self[row - 1, col]
ferencd@0:       cell.south = self[row + 1, col]
ferencd@0:       cell.west  = self[row, col - 1]
ferencd@0:       cell.east  = self[row, col + 1]
ferencd@0:     end
ferencd@0:   end
ferencd@0: 
ferencd@0:   #
ferencd@0:   # Creates a room in the grid
ferencd@0:   #
ferencd@0:   def create_room(x1,y1, x2,y2)
ferencd@0:     # Firstly: empty the room
ferencd@0:     puts "x1:#{x1}, y1, x2, y2"
ferencd@0:     (x1..x2).each do |col|
ferencd@0:       (y1..y2).each do |row|
ferencd@0:         @grid[row][col].link(@grid[row][col+1]) # -> Next to right
ferencd@0:         @grid[row][col].link(@grid[row+1][col]) # -> Next to down
ferencd@0:       end
ferencd@0:     end
ferencd@0:     # then create the surrounding walls
ferencd@0:     (x1 + 1..x2-1).each do |col|
ferencd@0:       @grid[y1+1][col].unlink(@grid[y1][col])
ferencd@0:       @grid[y2-1][col].unlink(@grid[y2][col])
ferencd@0:     end
ferencd@0: 
ferencd@0:     (y1+1..y2-1).each do |row|
ferencd@0:       @grid[row][x1+1].unlink(@grid[row][x1])
ferencd@0:       @grid[row][x2-1].unlink(@grid[row][x2])
ferencd@0:     end
ferencd@0: 
ferencd@0:     r = Room.new(x1,y1,x2,y2)
ferencd@0:     @rooms << r
ferencd@0: 
ferencd@0:   end
ferencd@0: 
ferencd@0:   def [](row, column)
ferencd@0:     return nil unless row.between?(0, @rows - 1)
ferencd@0:     return nil unless column.between?(0, @grid[row].count - 1)
ferencd@0:     @grid[row][column]
ferencd@0:   end
ferencd@0: 
ferencd@0:   def random_cell
ferencd@0:     row = rand(@rows)
ferencd@0:     column = rand(@grid[row].count)
ferencd@0: 
ferencd@0:     self[row, column]
ferencd@0:   end
ferencd@0: 
ferencd@0:   def size
ferencd@0:     @rows * @columns
ferencd@0:   end
ferencd@0: 
ferencd@0:   def each_row
ferencd@0:     @grid.each do |row|
ferencd@0:       yield row
ferencd@0:     end
ferencd@0:   end
ferencd@0: 
ferencd@0:   def each_cell
ferencd@0:     each_row do |row|
ferencd@0:       row.each do |cell|
ferencd@0:         yield cell if cell
ferencd@0:       end
ferencd@0:     end
ferencd@0:   end
ferencd@0: 
ferencd@0:   # By default, we'll simply display a cell as a blank space. We'll use this
ferencd@0:   # to add other ways of displaying cells.
ferencd@0:   def contents_of(cell)
ferencd@0:     ' '
ferencd@0:   end
ferencd@0: #
ferencd@0:   def background_color_for(cell)
ferencd@0:     nil
ferencd@0:   end
ferencd@0: 
ferencd@0:   def to_s
ferencd@0:     maze_js_array
ferencd@0:   end
ferencd@0: 
ferencd@0:   #
ferencd@0:   # Returns the number for the given cell
ferencd@0:   #
ferencd@0:   def number_for_cell(cell)
ferencd@0:     number = 0
ferencd@0:     number |= EAST if cell.linked?(cell.east)
ferencd@0:     number |= NORTH if cell.linked?(cell.north)
ferencd@0:     number |= SOUTH if cell.linked?(cell.south)
ferencd@0:     number |= WEST if cell.linked?(cell.west)
ferencd@0:     number
ferencd@0:   end
ferencd@0: 
ferencd@0:   #
ferencd@0:   # Returns the maze as a javascript array. This also will initialize all the dead ends
ferencd@0:   # where we will put food or jevelry items
ferencd@0:   #
ferencd@0:    def maze_js_array
ferencd@0:     output = "var maze = [\n"
ferencd@0:     dist_strings = []
ferencd@0: 
ferencd@0:     each_row do |row| 
ferencd@0:       # num array, the number for the row
ferencd@0:       numarray = []
ferencd@0:       row_string = ''
ferencd@0: 
ferencd@0:       row.each do |cell| 
ferencd@0:         cell = Cell.new(-1, -1) unless cell
ferencd@0:         cell_nr = number_for_cell(cell)
ferencd@0:         numarray << cell_nr
ferencd@0: 
ferencd@0:         # Add this cell as a dead end destination
ferencd@0:         @dead_ends[cell_nr] << cell if [1,2,4,8].include? cell_nr
ferencd@0: 
ferencd@0:       end
ferencd@0: 
ferencd@0:       row_string << '[' << numarray.join(', ') << ']'
ferencd@0:       dist_strings << row_string
ferencd@0:       
ferencd@0:     end
ferencd@0:     output << dist_strings.join( ",\n" )
ferencd@0:     output << "];\n"
ferencd@0:     output
ferencd@0:   end
ferencd@0: 
ferencd@0:   def direction(d)
ferencd@0:     return 'N' if d == NORTH
ferencd@0:     return 'W' if d == WEST
ferencd@0:     return 'E' if d == EAST
ferencd@0:     return 'S' if d == SOUTH
ferencd@0:     return '?'
ferencd@0:   end
ferencd@0: 
ferencd@0:   #
ferencd@0:   # Returns the distances as a js array
ferencd@0:   #
ferencd@0:   def distances_js_array_path
ferencd@0:     output = ''
ferencd@0:     dist_strings = []
ferencd@0: 
ferencd@0:     each_row do |row|
ferencd@0:       row.each do |cell|
ferencd@0:         cell = Cell.new(-1, -1) unless cell
ferencd@0:         conts = contents_of(cell).to_s
ferencd@0:         if conts.strip.length > 0
ferencd@0:           dist_strings << {:idx => conts.to_i, :row => cell.row, :col => cell.column}
ferencd@0:         end
ferencd@0:       end
ferencd@0:     end
ferencd@0:     sorted = dist_strings.sort_by {|el| el[:idx]}
ferencd@0: 
ferencd@0:     # The directions this will go
ferencd@0:     walk_string = ''
ferencd@0:     # Now create a direction array from the elements
ferencd@0:     current_cell = self[sorted[0][:row], sorted[0][:col] ]
ferencd@0:     sorted.each_with_index do |cell, index|
ferencd@0:       if index > 0
ferencd@0:           # Find the direction from curent_cell to cell
ferencd@0:         the_cell = self[cell[:row], cell[:col] ]
ferencd@0:         dest = direction(current_cell.direction(the_cell))
ferencd@0:         walk_string << dest
ferencd@0:         current_cell = the_cell
ferencd@0:       end
ferencd@0:     end
ferencd@0:     output << "#{walk_string}"
ferencd@0:     output
ferencd@0:   end
ferencd@0: 
ferencd@0:   #
ferencd@0:   # Returns the distances as a js array
ferencd@0:   #
ferencd@0:   def distances_js_array
ferencd@0:     output = "var distances = [\n"
ferencd@0:     dist_strings = []
ferencd@0: 
ferencd@0:     each_row do |row|
ferencd@0: 
ferencd@0:       row_string = ''
ferencd@0:       numarray = []
ferencd@0: 
ferencd@0:       row.each do |cell|
ferencd@0:         cell = Cell.new(-1, -1) unless cell
ferencd@0:         conts = contents_of(cell).to_s
ferencd@0:         if conts.strip.length > 0
ferencd@0:             numarray << conts
ferencd@0:         else
ferencd@0:           numarray << '-1'
ferencd@0:         end
ferencd@0:       end
ferencd@0:       row_string << '[' << numarray.join(', ') << ']'
ferencd@0:       dist_strings << row_string
ferencd@0:     end
ferencd@0:     output << dist_strings.join(",\n")
ferencd@0:     output << "];\n"
ferencd@0:     output
ferencd@0:   end
ferencd@0: 
ferencd@0:   def maze_serialized_text
ferencd@0:     output = []
ferencd@0:     each_row do |row|
ferencd@0:       numarray = []
ferencd@0:       row.each do |cell|
ferencd@0:         cell = Cell.new(-1, -1) unless cell
ferencd@0:         numarray << number_for_cell(cell)
ferencd@0:       end
ferencd@0:       output << numarray.join(',')
ferencd@0:     end
ferencd@0:     output.join(':')
ferencd@0:   end
ferencd@0: 
ferencd@0:   def deadends
ferencd@0:     list = []
ferencd@0: 
ferencd@0:     each_cell do |cell|
ferencd@0:       list << cell if cell.links.count == 1
ferencd@0:     end
ferencd@0: 
ferencd@0:     list
ferencd@0:   end
ferencd@0: 
ferencd@0:   def braid(p=1.0)
ferencd@0:     deadends.shuffle.each do |cell| 
ferencd@0:       next if cell.links.count != 1 || rand > p
ferencd@0: 
ferencd@0:       neighbors = cell.neighbors.reject { |n| cell.linked?(n) } 
ferencd@0:       best = neighbors.select { |n| n.links.count == 1 } 
ferencd@0:       best = neighbors if best.empty? 
ferencd@0: 
ferencd@0:       neighbor = best.sample 
ferencd@0:       cell.link(neighbor)
ferencd@0:     end
ferencd@0:   end
ferencd@0: 
ferencd@0: 
ferencd@0:   #
ferencd@0:   # Tells us if we can make a room at the given coordinates
ferencd@0:   #
ferencd@0:   def can_make_room(x1, y1, x2, y2)
ferencd@0: 
ferencd@0:     @rooms.each do |room|
ferencd@0:       return FALSE if room.in(x1, y1)
ferencd@0:       return FALSE if room.in(x2, y2)
ferencd@0:       return FALSE if room.in(x1, y2)
ferencd@0:       return FALSE if room.in(x2, y1)
ferencd@0:     end
ferencd@0: 
ferencd@0:     TRUE
ferencd@0:   end
ferencd@0: 
ferencd@0:   #
ferencd@0:   # Creates a list of locations where torches can be found, mostly in corners at unfinshed walls
ferencd@0:   #
ferencd@0:   def identify_torch_locations
ferencd@0:     numarray = []
ferencd@0:     j = 0
ferencd@0:     each_row do |row|
ferencd@0:       i = 0
ferencd@0:       row.each do |cell|
ferencd@0:         number = 0
ferencd@0:         number |= TOP_RIGHT if cell.east && cell.north && cell.linked?(cell.east) && cell.linked?(cell.north) && !cell.east.linked?(cell.east.north) && !cell.north.linked?(cell.north.east)
ferencd@0:         number |= TOP_LEFT if cell.west && cell.north && cell.linked?(cell.west) && cell.linked?(cell.north) && !cell.west.linked?(cell.west.north) && !cell.north.linked?(cell.north.west)
ferencd@0:         number |= BOTTOM_RIGHT if cell.east && cell.south && cell.linked?(cell.east) && cell.linked?(cell.south) && !cell.east.linked?(cell.east.south) && !cell.south.linked?(cell.south.east)
ferencd@0:         number |= BOTTOM_LEFT if cell.west && cell.south && cell.linked?(cell.west) && cell.linked?(cell.south) && !cell.west.linked?(cell.west.south) && !cell.south.linked?(cell.south.west)
ferencd@0:         if number != 0
ferencd@0:           torch_data = { :i => i, :j => j, :number => number}
ferencd@0:           numarray << torch_data
ferencd@0:         end
ferencd@0:         i += 1
ferencd@0:       end
ferencd@0:       j += 1
ferencd@0:     end
ferencd@0:     numarray
ferencd@0:   end
ferencd@0: 
ferencd@0: end