Mercurial > maze-src

annotate grid.rb @ 0:1eef88068f9f tip

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
initial commit of maze game source
author ferencd
date Sun, 15 Sep 2019 11:46:47 +0200
parents
children
rev   line source
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 require 'cell'
ferencd@0 10
ferencd@0 11 # Corner constants, to know where to put a torch
ferencd@0 12 TOP_LEFT = 1
ferencd@0 13 TOP_RIGHT = 2
ferencd@0 14 BOTTOM_LEFT = 4
ferencd@0 15 BOTTOM_RIGHT = 8
ferencd@0 16
ferencd@0 17 class Room
ferencd@0 18 attr_reader :x1, :y1, :x2, :y2
ferencd@0 19
ferencd@0 20 def initialize(px1,py1,px2,py2)
ferencd@0 21 @x1 = px1
ferencd@0 22 @x2 = px2
ferencd@0 23 @y1 = py1
ferencd@0 24 @y2 = py2
ferencd@0 25 end
ferencd@0 26
ferencd@0 27 def in(x, y)
ferencd@0 28 return x > @x1-1 && x < @x2+1 && y > @y1-1 && y < @y2+1
ferencd@0 29 end
ferencd@0 30 end
ferencd@0 31
ferencd@0 32
ferencd@0 33 class Grid
ferencd@0 34 attr_reader :rows, :columns, :dead_ends
ferencd@0 35
ferencd@0 36 def initialize(rows, columns)
ferencd@0 37 @rows = rows
ferencd@0 38 @columns = columns
ferencd@0 39 @grid = prepare_grid
ferencd@0 40 @rooms = []
ferencd@0 41
ferencd@0 42 # Where food will go
ferencd@0 43 @dead_ends = {}
ferencd@0 44 @dead_ends[1] = []
ferencd@0 45 @dead_ends[2] = []
ferencd@0 46 @dead_ends[4] = []
ferencd@0 47 @dead_ends[8] = []
ferencd@0 48
ferencd@0 49 configure_cells
ferencd@0 50
ferencd@0 51 end
ferencd@0 52
ferencd@0 53 def prepare_grid
ferencd@0 54 Array.new(rows) do |row|
ferencd@0 55 Array.new(columns) do |column|
ferencd@0 56 Cell.new(row, column)
ferencd@0 57 end
ferencd@0 58 end
ferencd@0 59 end
ferencd@0 60
ferencd@0 61 def configure_cells
ferencd@0 62 each_cell do |cell|
ferencd@0 63 row, col = cell.row, cell.column
ferencd@0 64
ferencd@0 65 cell.north = self[row - 1, col]
ferencd@0 66 cell.south = self[row + 1, col]
ferencd@0 67 cell.west = self[row, col - 1]
ferencd@0 68 cell.east = self[row, col + 1]
ferencd@0 69 end
ferencd@0 70 end
ferencd@0 71
ferencd@0 72 #
ferencd@0 73 # Creates a room in the grid
ferencd@0 74 #
ferencd@0 75 def create_room(x1,y1, x2,y2)
ferencd@0 76 # Firstly: empty the room
ferencd@0 77 puts "x1:#{x1}, y1, x2, y2"
ferencd@0 78 (x1..x2).each do |col|
ferencd@0 79 (y1..y2).each do |row|
ferencd@0 80 @grid[row][col].link(@grid[row][col+1]) # -> Next to right
ferencd@0 81 @grid[row][col].link(@grid[row+1][col]) # -> Next to down
ferencd@0 82 end
ferencd@0 83 end
ferencd@0 84 # then create the surrounding walls
ferencd@0 85 (x1 + 1..x2-1).each do |col|
ferencd@0 86 @grid[y1+1][col].unlink(@grid[y1][col])
ferencd@0 87 @grid[y2-1][col].unlink(@grid[y2][col])
ferencd@0 88 end
ferencd@0 89
ferencd@0 90 (y1+1..y2-1).each do |row|
ferencd@0 91 @grid[row][x1+1].unlink(@grid[row][x1])
ferencd@0 92 @grid[row][x2-1].unlink(@grid[row][x2])
ferencd@0 93 end
ferencd@0 94
ferencd@0 95 r = Room.new(x1,y1,x2,y2)
ferencd@0 96 @rooms << r
ferencd@0 97
ferencd@0 98 end
ferencd@0 99
ferencd@0 100 def [](row, column)
ferencd@0 101 return nil unless row.between?(0, @rows - 1)
ferencd@0 102 return nil unless column.between?(0, @grid[row].count - 1)
ferencd@0 103 @grid[row][column]
ferencd@0 104 end
ferencd@0 105
ferencd@0 106 def random_cell
ferencd@0 107 row = rand(@rows)
ferencd@0 108 column = rand(@grid[row].count)
ferencd@0 109
ferencd@0 110 self[row, column]
ferencd@0 111 end
ferencd@0 112
ferencd@0 113 def size
ferencd@0 114 @rows * @columns
ferencd@0 115 end
ferencd@0 116
ferencd@0 117 def each_row
ferencd@0 118 @grid.each do |row|
ferencd@0 119 yield row
ferencd@0 120 end
ferencd@0 121 end
ferencd@0 122
ferencd@0 123 def each_cell
ferencd@0 124 each_row do |row|
ferencd@0 125 row.each do |cell|
ferencd@0 126 yield cell if cell
ferencd@0 127 end
ferencd@0 128 end
ferencd@0 129 end
ferencd@0 130
ferencd@0 131 # By default, we'll simply display a cell as a blank space. We'll use this
ferencd@0 132 # to add other ways of displaying cells.
ferencd@0 133 def contents_of(cell)
ferencd@0 134 ' '
ferencd@0 135 end
ferencd@0 136 #
ferencd@0 137 def background_color_for(cell)
ferencd@0 138 nil
ferencd@0 139 end
ferencd@0 140
ferencd@0 141 def to_s
ferencd@0 142 maze_js_array
ferencd@0 143 end
ferencd@0 144
ferencd@0 145 #
ferencd@0 146 # Returns the number for the given cell
ferencd@0 147 #
ferencd@0 148 def number_for_cell(cell)
ferencd@0 149 number = 0
ferencd@0 150 number |= EAST if cell.linked?(cell.east)
ferencd@0 151 number |= NORTH if cell.linked?(cell.north)
ferencd@0 152 number |= SOUTH if cell.linked?(cell.south)
ferencd@0 153 number |= WEST if cell.linked?(cell.west)
ferencd@0 154 number
ferencd@0 155 end
ferencd@0 156
ferencd@0 157 #
ferencd@0 158 # Returns the maze as a javascript array. This also will initialize all the dead ends
ferencd@0 159 # where we will put food or jevelry items
ferencd@0 160 #
ferencd@0 161 def maze_js_array
ferencd@0 162 output = "var maze = [\n"
ferencd@0 163 dist_strings = []
ferencd@0 164
ferencd@0 165 each_row do |row|
ferencd@0 166 # num array, the number for the row
ferencd@0 167 numarray = []
ferencd@0 168 row_string = ''
ferencd@0 169
ferencd@0 170 row.each do |cell|
ferencd@0 171 cell = Cell.new(-1, -1) unless cell
ferencd@0 172 cell_nr = number_for_cell(cell)
ferencd@0 173 numarray << cell_nr
ferencd@0 174
ferencd@0 175 # Add this cell as a dead end destination
ferencd@0 176 @dead_ends[cell_nr] << cell if [1,2,4,8].include? cell_nr
ferencd@0 177
ferencd@0 178 end
ferencd@0 179
ferencd@0 180 row_string << '[' << numarray.join(', ') << ']'
ferencd@0 181 dist_strings << row_string
ferencd@0 182
ferencd@0 183 end
ferencd@0 184 output << dist_strings.join( ",\n" )
ferencd@0 185 output << "];\n"
ferencd@0 186 output
ferencd@0 187 end
ferencd@0 188
ferencd@0 189 def direction(d)
ferencd@0 190 return 'N' if d == NORTH
ferencd@0 191 return 'W' if d == WEST
ferencd@0 192 return 'E' if d == EAST
ferencd@0 193 return 'S' if d == SOUTH
ferencd@0 194 return '?'
ferencd@0 195 end
ferencd@0 196
ferencd@0 197 #
ferencd@0 198 # Returns the distances as a js array
ferencd@0 199 #
ferencd@0 200 def distances_js_array_path
ferencd@0 201 output = ''
ferencd@0 202 dist_strings = []
ferencd@0 203
ferencd@0 204 each_row do |row|
ferencd@0 205 row.each do |cell|
ferencd@0 206 cell = Cell.new(-1, -1) unless cell
ferencd@0 207 conts = contents_of(cell).to_s
ferencd@0 208 if conts.strip.length > 0
ferencd@0 209 dist_strings << {:idx => conts.to_i, :row => cell.row, :col => cell.column}
ferencd@0 210 end
ferencd@0 211 end
ferencd@0 212 end
ferencd@0 213 sorted = dist_strings.sort_by {|el| el[:idx]}
ferencd@0 214
ferencd@0 215 # The directions this will go
ferencd@0 216 walk_string = ''
ferencd@0 217 # Now create a direction array from the elements
ferencd@0 218 current_cell = self[sorted[0][:row], sorted[0][:col] ]
ferencd@0 219 sorted.each_with_index do |cell, index|
ferencd@0 220 if index > 0
ferencd@0 221 # Find the direction from curent_cell to cell
ferencd@0 222 the_cell = self[cell[:row], cell[:col] ]
ferencd@0 223 dest = direction(current_cell.direction(the_cell))
ferencd@0 224 walk_string << dest
ferencd@0 225 current_cell = the_cell
ferencd@0 226 end
ferencd@0 227 end
ferencd@0 228 output << "#{walk_string}"
ferencd@0 229 output
ferencd@0 230 end
ferencd@0 231
ferencd@0 232 #
ferencd@0 233 # Returns the distances as a js array
ferencd@0 234 #
ferencd@0 235 def distances_js_array
ferencd@0 236 output = "var distances = [\n"
ferencd@0 237 dist_strings = []
ferencd@0 238
ferencd@0 239 each_row do |row|
ferencd@0 240
ferencd@0 241 row_string = ''
ferencd@0 242 numarray = []
ferencd@0 243
ferencd@0 244 row.each do |cell|
ferencd@0 245 cell = Cell.new(-1, -1) unless cell
ferencd@0 246 conts = contents_of(cell).to_s
ferencd@0 247 if conts.strip.length > 0
ferencd@0 248 numarray << conts
ferencd@0 249 else
ferencd@0 250 numarray << '-1'
ferencd@0 251 end
ferencd@0 252 end
ferencd@0 253 row_string << '[' << numarray.join(', ') << ']'
ferencd@0 254 dist_strings << row_string
ferencd@0 255 end
ferencd@0 256 output << dist_strings.join(",\n")
ferencd@0 257 output << "];\n"
ferencd@0 258 output
ferencd@0 259 end
ferencd@0 260
ferencd@0 261 def maze_serialized_text
ferencd@0 262 output = []
ferencd@0 263 each_row do |row|
ferencd@0 264 numarray = []
ferencd@0 265 row.each do |cell|
ferencd@0 266 cell = Cell.new(-1, -1) unless cell
ferencd@0 267 numarray << number_for_cell(cell)
ferencd@0 268 end
ferencd@0 269 output << numarray.join(',')
ferencd@0 270 end
ferencd@0 271 output.join(':')
ferencd@0 272 end
ferencd@0 273
ferencd@0 274 def deadends
ferencd@0 275 list = []
ferencd@0 276
ferencd@0 277 each_cell do |cell|
ferencd@0 278 list << cell if cell.links.count == 1
ferencd@0 279 end
ferencd@0 280
ferencd@0 281 list
ferencd@0 282 end
ferencd@0 283
ferencd@0 284 def braid(p=1.0)
ferencd@0 285 deadends.shuffle.each do |cell|
ferencd@0 286 next if cell.links.count != 1 || rand > p
ferencd@0 287
ferencd@0 288 neighbors = cell.neighbors.reject { |n| cell.linked?(n) }
ferencd@0 289 best = neighbors.select { |n| n.links.count == 1 }
ferencd@0 290 best = neighbors if best.empty?
ferencd@0 291
ferencd@0 292 neighbor = best.sample
ferencd@0 293 cell.link(neighbor)
ferencd@0 294 end
ferencd@0 295 end
ferencd@0 296
ferencd@0 297
ferencd@0 298 #
ferencd@0 299 # Tells us if we can make a room at the given coordinates
ferencd@0 300 #
ferencd@0 301 def can_make_room(x1, y1, x2, y2)
ferencd@0 302
ferencd@0 303 @rooms.each do |room|
ferencd@0 304 return FALSE if room.in(x1, y1)
ferencd@0 305 return FALSE if room.in(x2, y2)
ferencd@0 306 return FALSE if room.in(x1, y2)
ferencd@0 307 return FALSE if room.in(x2, y1)
ferencd@0 308 end
ferencd@0 309
ferencd@0 310 TRUE
ferencd@0 311 end
ferencd@0 312
ferencd@0 313 #
ferencd@0 314 # Creates a list of locations where torches can be found, mostly in corners at unfinshed walls
ferencd@0 315 #
ferencd@0 316 def identify_torch_locations
ferencd@0 317 numarray = []
ferencd@0 318 j = 0
ferencd@0 319 each_row do |row|
ferencd@0 320 i = 0
ferencd@0 321 row.each do |cell|
ferencd@0 322 number = 0
ferencd@0 323 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 324 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 325 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 326 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 327 if number != 0
ferencd@0 328 torch_data = { :i => i, :j => j, :number => number}
ferencd@0 329 numarray << torch_data
ferencd@0 330 end
ferencd@0 331 i += 1
ferencd@0 332 end
ferencd@0 333 j += 1
ferencd@0 334 end
ferencd@0 335 numarray
ferencd@0 336 end
ferencd@0 337
ferencd@0 338 end