Created
February 1, 2011 04:38
-
-
Save kenliu/805416 to your computer and use it in GitHub Desktop.
Groovy port of Jamis Buck's Recursive Backtracking maze generation program
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** 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