Skip to content

Instantly share code, notes, and snippets.

@kenliu
Created February 1, 2011 04:38
Show Gist options
  • Save kenliu/805416 to your computer and use it in GitHub Desktop.
Save kenliu/805416 to your computer and use it in GitHub Desktop.
Groovy port of Jamis Buck's Recursive Backtracking maze generation program
/** Groovy port of Jamis Buck's Recursive Backtracking maze generation program
see http://weblog.jamisbuck.org/2010/12/27/maze-generation-recursive-backtracking
Prints a 10x10 ASCII maze and accepts optional dimensions.
Will blow up if dimensions are too big (20x20ish)
*/
def (width, height) = [10, 10]
if (args.length >= 2) {
(width, height) = [args[0] as int, args[1] as int]
}
// Global constants for representing and manipulating maze openings
(UNVISITED, N, S, E, W) = [0, 1, 2, 4, 8]
DX = [4: 1, 8: -1, 1: 0, 2: 0]
DY = [4: 0, 8: 0, 1: -1, 2: 1]
OPPOSITE = [4: 8, 8: 4, 1: 2, 2: 1]
/** Emits the maze as ASCII. */
def printMaze(grid) {
def (width, height) = [grid.length, grid[0].length]
println ' ' + '_' * (width * 2 - 1)
for (int y = 0; y < height; y++) {
print '|'
for (int x = 0; x < width; x++) {
print (((grid[x][y] & E) != 0) ? " " : "_")
if ((grid[x][y] & S) != 0) {
print ((((grid[x][y] | grid[x+1][y]) & E) != 0) ? ' ' : '_')
} else {
print '|'
}
}
println ''
}
}
/** Recursive backtracking algorithm. */
def carvePassagesFrom(cx, cy, grid) {
def directions = [N, S, E, W]
Collections.shuffle(directions)
directions.each { direction ->
def (nx, ny) = [cx + DX[direction], cy + DY[direction]]
//if the new node is unvisited, carve a wall into the
//new node and visit the new node
if ((ny >= 0 && ny <= (grid.length - 1)) &&
(nx >= 0 && nx <= (grid[0].length - 1)) &&
grid[ny][nx] == UNVISITED) {
grid[cy][cx] |= direction
grid[ny][nx] |= OPPOSITE[direction]
carvePassagesFrom(nx, ny, grid)
}
}
}
def grid = new byte[width][height]
carvePassagesFrom(0, 0, grid)
printMaze(grid)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment