{{ message }}

Instantly share code, notes, and snippets.

# jamis/recursive-division.rb

Created Jan 1, 2011
An implementation of the "Recursive Division" algorithm for maze generation.
 # -------------------------------------------------------------------- # An implementation of the "Recursive Division" algorithm. This is a # kind of fractal maze algorithm, recursively dividing the maze into # smaller and smaller cells. This algorithm stops at the integer # boundary, but theoretically the algorithm could continue infinitely # to smaller and smaller scales. # # Note that this algorithm is implemented as a "wall adder", rather # than a "passage carver", so the meaning of the bits in each cell # is reversed: instead of the S bit (for instance) meaning "a passage # goes south", it means "there is a wall to the south". # -------------------------------------------------------------------- # -------------------------------------------------------------------- # 1. Allow the maze to be customized via command-line parameters # -------------------------------------------------------------------- width = (ARGV || 10).to_i height = (ARGV || width).to_i seed = (ARGV || rand(0xFFFF_FFFF)).to_i srand(seed) grid = Array.new(height) { Array.new(width, 0) } # -------------------------------------------------------------------- # 2. Set up constants to aid with describing the passage directions # -------------------------------------------------------------------- S, E = 1, 2 HORIZONTAL, VERTICAL = 1, 2 # -------------------------------------------------------------------- # 3. Helper routines # -------------------------------------------------------------------- def display_maze(grid) print "\e[H" # move to upper-left puts " " + "_" * (grid.length * 2 - 1) grid.each_with_index do |row, y| print "|" row.each_with_index do |cell, x| bottom = y+1 >= grid.length south = (cell & S != 0 || bottom) south2 = (x+1 < grid[y].length && grid[y][x+1] & S != 0 || bottom) east = (cell & E != 0 || x+1 >= grid[y].length) print(south ? "_" : " ") print(east ? "|" : ((south && south2) ? "_" : " ")) end puts end end def choose_orientation(width, height) if width < height HORIZONTAL elsif height < width VERTICAL else rand(2) == 0 ? HORIZONTAL : VERTICAL end end # -------------------------------------------------------------------- # 4. The recursive-division algorithm itself # -------------------------------------------------------------------- def divide(grid, x, y, width, height, orientation) return if width < 2 || height < 2 display_maze(grid) sleep 0.02 horizontal = orientation == HORIZONTAL # where will the wall be drawn from? wx = x + (horizontal ? 0 : rand(width-2)) wy = y + (horizontal ? rand(height-2) : 0) # where will the passage through the wall exist? px = wx + (horizontal ? rand(width) : 0) py = wy + (horizontal ? 0 : rand(height)) # what direction will the wall be drawn? dx = horizontal ? 1 : 0 dy = horizontal ? 0 : 1 # how long will the wall be? length = horizontal ? width : height # what direction is perpendicular to the wall? dir = horizontal ? S : E length.times do grid[wy][wx] |= dir if wx != px || wy != py wx += dx wy += dy end nx, ny = x, y w, h = horizontal ? [width, wy-y+1] : [wx-x+1, height] divide(grid, nx, ny, w, h, choose_orientation(w, h)) nx, ny = horizontal ? [x, wy+1] : [wx+1, y] w, h = horizontal ? [width, y+height-wy-1] : [x+width-wx-1, height] divide(grid, nx, ny, w, h, choose_orientation(w, h)) end print "\e[2J" # clear screen divide(grid, 0, 0, width, height, choose_orientation(width, height)) display_maze(grid) # -------------------------------------------------------------------- # 5. Show the parameters used to build this maze, for repeatability # -------------------------------------------------------------------- puts "#{\$0} #{width} #{height} #{seed}"

### Maumagnaguagno commented Mar 8, 2015

 Hi, I used your Gist as a starting point for GitHub, made a few improvements for speed and added a wall to tile converter. My code is here. It is not quite a fork because I broke your interface for my specific needs. I really like your blog, thanks for sharing code.

### George480 commented Sep 19, 2019

 Thanks for all the great implementations! NOTE: In `divide` function, when `width` or `height` is 2 it will call `rand(0)`. In some other languages, this is unexpected behavior but Ruby seems to call `rand()` without parameters and converts a floating-point number generated (between `0.0` and `1.0`) to integer. So basically it access element at index 0. The index 0 is necessary to be accessed otherwise the passages will be too wide and will not look nice. A workaround for it in other languages: ``````wx = x + (horizontal ? 0 : rand(width == 2 ? 1 : width - 2)) wy = y + (horizontal ? rand(height == 2 ? 1 : height - 2) : 0) `````` which `rand(1)` always returns `0`.

### jamis commented Sep 19, 2019

 Good catch! Thanks for the workaround.