Randomized Permutations Without Lists
I'm writing a new interpreted language called Boss. It has Roguelike syntax and in fact the general idea is for it to be a version of Rogue that doesn't require a C++ compiler or development environment.
As I go I'm writing increasingly sophisticated toy programs to test out Boss. It's ironic that I'm writing the same kinds of simple programs as I did 30 years ago but now for entirely different reasons. Back then it was to learn programming and now it's to test my compiler. Heck yeah!
As my current testbed program I've been writing and improving a 2D maze generator. The basic algorithm is simple:
- Fill an odd-sized rectangle with all walls.
- Randomly pick an odd-numbered starting location and visit it.
- At each location, recursively visit all four adjacent locations that are two steps away, in a random order, unless you've already been to the adjacent location or it's out of bounds.
- As you visit a new location, knock down the wall at the new location and the wall in-between the previous location and the new location.
Here is a simple Boss implementation of the maze generator.
MazeGen(109,25).display
class MazeGen
PROPERTIES
width, height : Int32
maze = Character[]
offsets = [ XY(0,-1), XY(-1,0), XY(0,1), XY(1,0) ]
METHODS
method init( width:Int32, height:Int32 )
generate( width, height )
method generate( width, height )
maze.resize( width * height )
maze.fill('#')
local start_i = Random.int32((width-2)/2+1) * 2 + 1
local start_j = Random.int32((height-2)/2+1) * 2 + 1
visit( start_i, start_j, 0, 0 )
method display
local j = 0
while (j < height)
local i = 0
while (i < width)
print maze[j*width+i]
++i
endWhile
println
++j
endWhile
method visit( i:Int32, j:Int32, di:Int32, dj:Int32 )
local mid_i = i + di
local mid_j = j + dj
i = mid_i + di
j = mid_j + dj
if (i < 0 or j < 0 or i >= width or j >= height) return
local index = j * width + i
if (maze[index] == ' ') return
maze[mid_j*width+mid_i] = ' ' # 1 step
maze[index] = ' ' # 2 steps
local dirs = [0,1,2,3]
dirs.shuffle
while (dirs.count)
local dir = dirs.remove_last
local offset = offsets[ dir ]
visit( i, j, offset.x, offset.y )
endWhile
endClassAnd here is the console output it produces.
Below is the output of the same program that stops after 200 recursions. It might be easier to understand the depth-first algorithm with this halfway-finished maze: it's like a worm that tunnels through rock, going in random direction at each location but making sure not to cross its own path. When it reaches a dead end it backtracks to the most recent position that still has at least one direction to explore and strikes out in one of those directions.
I've written this algorithm many times and these days I wince a bit at allocating a list of randomized directions for each recursion. It's no big deal for this scale of program, but it's just the principle of the thing.
This time I ended up brainstorming a way to generate a random permutations of a sequence of an arbitrary length without needing to allocate a list for storage. The caveat is that to avoid needing a list, code must be designed for a specific sequence length (such as length four for the four directions for the maze generator). Here's how it works.
Say we want to print the numbers 0 through 9 out in a random order.
- It's easy to pick the first number: random(0,9). Let's say we ended up with
r1 = n1 = 3 (r1 = random pick, n1 = resulting sequence number). - Our second number then needs to be 0-2 or 4-9. But if we treat the range as wrapping around there's a simpler way to think of it: 0-2 or 4-9 becomes (3 + 1-9) % 10, or (3 + 0-8 + 1) % 10. Whatever our first number r1 is, the second number will be n2 = (r1 + random(0,8) + 1) % 10. Essentially we're just picking another number out of a contiguous range, adding it to the previous number, and wrapping it around if it goes off the end. Let's say random(0,8) returned r2 = 7 and so the second number is n2 = (r1 + r2 + 1) % 10 = (3 + 7 + 1) % 10 = 1.
- If the second number is n2 = (r1 + r2 + 1) % 10, the third number is n3 = (r1 + r3 + 1) % 10, where r3 is any random number 0-8 except for r2. Another way to express "any random number 0-8 except for r2" is (r2 + random(0,7) + 1) % 9, which uses the same wraparound trick. The full equation for the third number becomes n3 = r1 + (r2 + random(0,7) + 1) % 9) % 10.
- You may see the pattern developing. To select a random permutation of numbers 0..9, we'll need 10 random numbers:
r1 = random(0,9)
r2 = random(0,8)
r3 = random(0,7)
...
r10 = random(0,0)
Each successive sequence expands the previous rX ... % N with
(rX + rY + 1) % (N-1):
n1 = r1
n2 = (r1 + r2 + 1) % 10
n3 = (r1 + (r2 + r3 + 1) % 9 + 1) % 10
n4 = (r1 + (r2 + (r3 + r4 +1) % 8 + 1) % 9 + 1) % 10
...
The pattern is recursive in a general sense and yet it is not well-suited to recursive programming because computing each number requires all random picks thus far.
Here is a recursive Rogue implementation which does use a list (the very thing I'm trying to avoid):
permutation( 10, Int32[] )
routine permutation( count:Int32, r_stack:Int32[] )
local r = Random.int32( count )
local n = r
local limit = count + 1
forEach (previous_r in r_stack step -1)
n = (n + previous_r + 1) % limit
++limit
endForEach
println n
r_stack.add( r )
if (count > 1) permutation( count-1, r_stack )
endRoutineThe maze algorithm just needs a small, fixed-size random permutation of 4 directions, so we can just hard-code the equations listed further up. In my case I did this:
method random_directions->Int32
local r1 = Random.int32(4)
local r2 = Random.int32(3)
local r3 = Random.int32(2)
local d1 = r1
local d2 = (r1 + r2 + 1) % 4
local d3 = (r1 + (r2 + r3 + 1) % 3 + 1) % 4
local d4 = (0 + 1 + 2 + 3) - (d1 + d2 + d3)
return (d1:<<:6) | (d2:<<:4) | (d3:<<:2) | d4
# Returns bits AABBCCDD, where each AA etc. is a direction 0-3.
My full Boss maze program, which also connects adjoining walls using box-drawing characters.
class MazeGen
PROPERTIES
width, height : Int32
maze = Character[]
offsets = [ XY(0,-1), XY(-1,0), XY(0,1), XY(1,0) ]
walls =
[ # ULDR
' ' # ----
'\u2501' # ---R
'\u2503' # --D-
'\u250F' # --DR
'\u2501' # -L--
'\u2501' # -L-R
'\u2513' # -LD-
'\u2533' # -LDR
'\u2503' # U---
'\u2517' # U--R
'\u2503' # U-D-
'\u2523' # U-DR
'\u251B' # UL--
'\u253B' # UL-R
'\u252B' # ULD-
'\u254B' # ULDR
]
METHODS
method init( width:Int32, height:Int32 )
generate( width, height )
method generate( width, height )
maze.resize( width * height )
maze.fill('#')
local start_i = Random.int32((width-2)/2+1) * 2 + 1
local start_j = Random.int32((height-2)/2+1) * 2 + 1
visit( start_i, start_j, 0, 0 )
make_adjoining_walls
method display
local j = 0
while (j < height)
local i = 0
while (i < width)
print maze[j*width+i]
++i
endWhile
println
++j
endWhile
method has_wall( i:Int32, j:Int32 )->Logical
if (i < 0 or j < 0 or i >= width or j >= height) return false
return maze[j*width+i] != ' '
method make_adjoining_walls
local index = width * height
while (index > 0)
--index
if (maze[index] != ' ')
local i = index % width
local j = index / width
local uldr = 0
if (has_wall(i,j-1)) uldr |= 0b1000
if (has_wall(i-1,j)) uldr |= 0b0100
if (has_wall(i,j+1)) uldr |= 0b0010
if (has_wall(i+1,j)) uldr |= 0b0001
maze[index] = walls[uldr]
endIf
endWhile
method visit( i:Int32, j:Int32, di:Int32, dj:Int32 )
local mid_i = i + di
local mid_j = j + dj
i = mid_i + di
j = mid_j + dj
if (i < 0 or j < 0 or i >= width or j >= height) return
local index = j * width + i
if (maze[index] == ' ') return
maze[mid_j*width+mid_i] = ' ' # 1 step
maze[index] = ' ' # 2 steps
local dirs = random_directions
loop 4
local dir = dirs & 3
dirs = dirs :>>>: 2
local offset = offsets[ dir ]
visit( i, j, offset.x, offset.y )
endLoop
method random_directions->Int32
local r1 = Random.int32(4)
local r2 = Random.int32(3)
local r3 = Random.int32(2)
local d1 = r1
local d2 = (r1 + r2 + 1) % 4
local d3 = (r1 + (r2 + r3 + 1) % 3 + 1) % 4
local d4 = (0 + 1 + 2 + 3) - (d1 + d2 + d3)
return (d1:<<:6) | (d2:<<:4) | (d3:<<:2) | d4
# Returns bits AABBCCDD, where each AA etc. is a direction 0-3.
endClass
MazeGen(109,25).display