You inspired me to take a shot at the maze generator thing.
Uses..
Depth-first search algorithm
The grid output is a fairly simple array.
grid[y][x][wall direction (0 to 3)] == wall alive boolean
My implementation does have it's limitations however I narrowed out the maximum size to be 35 by 35 but depending on your application (random dungeon level generator for example) that should be more than enough.
PHP Code:
function onCreated() {
// Generate Maze
temp.maze = generateMaze(35, 35);
// For added fun!
randomDestruction(temp.maze.link(), 20);
// Example output
drawGrid(temp.maze.link());
}
public function generateMaze(temp.width, temp.height) {
// Generate Blank Grid
temp.cells = new[temp.height][temp.width][5];
// Begin Adding Rows
for (temp.y = 0; temp.y < temp.width; temp.y++) {
// Begin Adding Columns
for (temp.x = 0; temp.x < temp.height; temp.x++) {
// Generate Cells
temp.cell = {1, 1, 1, 1, false};
// Add Cell to Column
temp.cells[temp.y][temp.x] = temp.cell;
temp.i++;
}
}
// Pick Exit
temp.exit_x = int(random(0, temp.width));
temp.exit_y = int(random(0, temp.height));
// Mark Exit
temp.cells[temp.exit_y][temp.exit_x][4] = true;
// Begin Carving
carveMaze(temp.cells.link(), temp.exit_x, temp.exit_y);
// Trim Visited Fat
for (temp.y = 0; temp.y < temp.width; temp.y++) {
for (temp.x = 0; temp.x < temp.height; temp.x++) {
temp.cells[temp.y][temp.x].delete(4);
}
}
// Return Grid
return temp.cells;
}
function carveMaze(cells, cx, cy) {
// Determine Grids Width and Height
temp.height = cells.size();
temp.width = cells[0].size();
// Find Unvisited Neighbour Cells
for (temp.i = 0; temp.i < 4; temp.i++) {
temp.tx = cx + vecx(temp.i);
temp.ty = cy + vecy(temp.i);
if (cells[ty][tx].size() == 5) {
if (cells[ty][tx][4] == false) {
temp.unvisited.add(temp.i);
}
}
}
// Check if has Unvisited Neighbours
temp.neighbours = temp.unvisited.size();
if (temp.neighbours > 0) {
// Pick Unvisited Neighbour
temp.neighbour = temp.unvisited[int(random(0, temp.neighbours))];
temp.tx = cx + vecx(temp.neighbour);
temp.ty = cy + vecy(temp.neighbour);
// Remove Wall between Neighbours
cells[cy][cx][temp.neighbour] = 0;
cells[ty][tx][(temp.neighbour + 2) % 4] = 0;
// Set Neighbour Cell to Visited
cells[ty][tx][4] = true;
// Continue Carving as Neighbour
carveMaze(cells.link(), temp.tx, temp.ty);
// Continue Carving Local Neighbours
if (temp.neighbours > 0) carveMaze(cells.link(), cx, cy);
}
}
public function randomDestruction(cells, walls) {
// Determine Grids Width and Height
temp.height = cells.size();
temp.width = cells[0].size();
// Check for Proper Cell
if (cells[0][0].size() != 4) return false;
// Begin Random Destruction
while (walls > 0) {
// Pick a Random Cell
temp.cx = int(random(0, temp.width));
temp.cy = int(random(0, temp.height));
// Pick a Random Neighbour
temp.neighbour = int(random(0, 4));
temp.tx = cx + vecx(temp.neighbour);
temp.ty = cy + vecy(temp.neighbour);
// Skip Non-Cells
if (cells[temp.tx][temp.ty].size() != 4) continue;
// Check if Wall Exists
if (cells[temp.cy][temp.cx][temp.neighbour] == true) {
// Remove Wall
cells[cy][cx][temp.neighbour] = 0;
cells[ty][tx][(temp.neighbour + 2) % 4] = 0;
walls--;
}
}
}
/*
Example Rendering of a Maze
*/
public function drawGrid(cells) {
// Determine Grids Width and Height
temp.height = cells.size();
temp.width = cells[0].size();
// Check for Proper Cell
if (cells[0][0].size() != 4) return false;
// Drawing Configuration
temp.cell_width = 24;
temp.cell_height = 24;
temp.lw = 1; // Line Width
// Create Drawing Panel
temp.panel = new TDrawingPanel();
// Line Drawing Functionality (drawline is a jerk)
temp.panel.drawhoriz = function (x1, y1, width) {
this.drawimagestretched(params[0], params[1], width, 1, "whitefill.png", 0, 0, 1, 1);
};
temp.panel.drawvert = function (x1, y1, height) {
this.drawimagestretched(params[0], params[1], 1, height, "whitefill.png", 0, 0, 1, 1);
};
// Set Panel Size
temp.panel.setsize(temp.width * temp.cell_width, temp.height * temp.cell_height);
// Fill Image
temp.panel.drawimagestretched(0, 0, temp.width * temp.cell_width, temp.height * temp.cell_height, "blackfill.png", 0, 0, 1, 1);
// Begin Drawing Cells
for (temp.y = 0; temp.y < temp.width; temp.y++) {
for (temp.x = 0; temp.x < temp.height; temp.x++) {
temp.cell = cells[temp.y][temp.x];
for (temp.i = 0; temp.i < 4; temp.i++) {
// Check if Wall on that Direction
if (temp.cell[temp.i]) {
// Determine Top Corner
temp.tx = temp.x * temp.cell_width;
temp.ty = temp.y * temp.cell_height;
// Draw Walls
if (temp.i == 0) temp.panel.drawhoriz(temp.tx, temp.ty, temp.cell_width);
else if (temp.i == 1) temp.panel.drawvert(temp.tx, temp.ty, temp.cell_height);
else if (temp.i == 2) temp.panel.drawhoriz(temp.tx, temp.ty + temp.cell_height - 1, temp.cell_width);
else if (temp.i == 3) temp.panel.drawvert(temp.tx + temp.cell_width - 1, temp.ty, temp.cell_height);
}
}
}
}
// Save Image (change this to somewhere meaningful to yourself)
temp.panel.saveimage("cartridge/testmaze.png");
// Destroy Panel
temp.panel.destroy();
}
Attached, images used in script and an example output.
http://img40.imageshack.us/img40/7562/whitefill.png
http://img259.imageshack.us/img259/9659/blackfill.png
10-06-2010, 05:13 AM
.
Linear Mode
