/*
* 3 June 2003, [[:en:User:Cyp]]:
* Maze, generated by my algorithm
* 24 October 2006, [[:en:User:quin]]:
* Source edited for clarity
* 25 January 2009, [[:en:User:DebateG]]:
* Source edited again for clarity and reusability
* 1 June 2009, [[:en:User:Nandhp]]:
* Source edited to produce SVG file when run from the command-line
* 7 January, 2011 [[:en:User:SharkD]]:
* Source converted to JavaScript
* 8 January, 2011 [[:en:User:SharkD]]:
* Added third axis to make the maze 3D
* Added SVG title element
* Corrected width and height SVG parameters
* Modified the script so that the padding arounds the side edges is added *after* the maze is generated
*
* This program was originally written by [[:en:User:Cyp]], who
* attached it to the image description page for an image generated by
* it on en.wikipedia. The image was licensed under CC-BY-SA-3.0/GFDL.
*/
/* Recreate a math function that exists in Java but not JavaScript. */
Math.nextInt = function (number) {
return Math.floor(Math.random() * number);
}
/* Recreate a system function that exists in Java but not JavaScript.
* Uncomment either WScript.Echo() or alert() depending on whether you are
* running the script from the Windows command-line or a Web page.
*/
function println(string)
{
// if inside Windows Scripting Host
WScript.Echo(string);
// if inside a Web page
// alert(string);
}
/* Define the bit masks */
var WALL_ABOVE = 1;
var WALL_BELOW = 2;
var WALL_LEFT = 4;
var WALL_RIGHT = 8;
var WALL_FRONT = 16;
var WALL_BACK = 32;
var QUEUED = 64;
var IN_MAZE = 128;
/* Construct a Maze with specified lenx, leny, and cell_width */
function Maze(lenx, leny, lenz, cell_width) {
if (lenx)
this.lenx = lenx;
else
this.lenx = 9;
if (leny)
this.leny = leny;
else
this.leny = 9;
if (lenz)
this.lenz = lenz;
else
this.lenz = 4;
if (cell_width)
this.cell_width = cell_width;
else
this.cell_width = 10;
this.maze = [];
/* The maze generation algorithm. */
this.createMaze = function() {
var lenx = this.lenx;
var leny = this.leny;
var lenz = this.lenz;
var maze = this.maze;
var x, y, z, x_dx, y_dy, z_dz, n, d;
var dx = 0, 0, -1, 1, 0, 0 ];
var dy = -1, 1, 0, 0, 0, 0 ];
var dz = 0, 0, 0, 0, -1, 1 ];
var todo = new Array(leny * lenx * lenz);
var todonum = 0;
/* We want to create a maze on a grid. */
/* We start with a grid full of walls. */
/* Outer edges are blank and simply used to pad the image. */
for (x = 0; x < lenx; ++x) {
mazex = [];
for (y = 0; y < leny; ++y) {
mazex][y = [];
for (z = 0; z < lenz; ++z) {
mazex][y][z = WALL_ABOVE + WALL_BELOW + WALL_LEFT + WALL_RIGHT + WALL_FRONT + WALL_BACK + QUEUED + IN_MAZE;
}
}
}
/* Select random square of the grid, to start with. */
x = Math.nextInt(lenx - 1);
y = Math.nextInt(leny - 1);
z = Math.nextInt(lenz - 1);
/* Mark this square as connected to the maze. */
mazex][y][z &= ~(QUEUED + IN_MAZE);
/* Remember the surrounding squares, as we will... */
for (d = 0; d < 6; ++d) {
x_dx = x + dxd];
y_dy = y + dyd];
z_dz = z + dzd];
if (x_dx >= 0 && x_dx < lenx && y_dy >= 0 && y_dy < leny && z_dz >= 0 && z_dz < lenz) {
if ((mazex_dx][y_dy][z_dz & QUEUED) != 0) {
/* ...want to connect them to the maze. */
todotodonum++ = x_dx, y_dy, z_dz];
mazex_dx][y_dy][z_dz &= ~QUEUED;
}
}
}
/* We won't be finished until all is connected. */
while (todonum > 0) {
/* We select one of the squares next to the maze. */
n = Math.nextInt(todonum);
x = todon][0];
y = todon][1];
z = todon][2];
/* We will connect it, so remove it from the queue. */
todon = todo--todonum];
/* Select a random direction, which leads to the maze. */
var passBool = 0;
while (passBool == 0)
{
d = Math.nextInt(6);
x_dx = x + dxd];
y_dy = y + dyd];
z_dz = z + dzd];
if (x_dx >= 0 && x_dx < lenx && y_dy >= 0 && y_dy < leny && z_dz >= 0 && z_dz < lenz) {
if ((mazex_dx][y_dy][z_dz & IN_MAZE) == 0)
passBool = 1;
}
}
/* Connect this square to the maze. */
mazex][y][z &= ~((1 << d) | IN_MAZE);
mazex + dxd]][y + dyd]][z + dzd]] &= ~(1 << (d ^ 1));
/* Remember the surrounding squares, which aren't... */
for (d = 0; d < 6; ++d) {
x_dx = x + dxd];
y_dy = y + dyd];
z_dz = z + dzd];
if (x_dx >= 0 && x_dx < lenx && y_dy >= 0 && y_dy < leny && z_dz >= 0 && z_dz < lenz) {
if ((mazex_dx][y_dy][z_dz & QUEUED) != 0) {
/* ...connected to the maze, and aren't yet queued. */
todotodonum++ = x_dx, y_dy, z_dz];
mazex_dx][y_dy][z_dz &= ~QUEUED;
}
}
}
/* Repeat until finished. */
}
/* Add an entrance and exit. */
maze0][Math.floor(leny/2)][0 &= ~WALL_LEFT;
mazelenx - 1][Math.floor(leny/2)][lenz - 1 &= ~WALL_RIGHT;
}
/* Called to write the maze to an SVG file. */
this.printSVG = function () {
var lenx = this.lenx;
var leny = this.leny;
var lenz = this.lenz;
var cell_width = this.cell_width;
var pics_xy = Math.ceil(Math.sqrt(lenz));
var size_x = (lenx + 1) * pics_xy * cell_width + cell_width;
var size_y = (leny + 1) * pics_xy * cell_width + cell_width;
println
(
"<svg width=\"" + size_x + "px\" height=\"" + size_y + "px\" viewBox=\"0 0 " + size_x + " " + size_y + "\" version=\"1.1\" xmlns=\"http://www.w3.org/2000/svg\">\n"
+ " <title>SVG Maze</title>\n"
+ " <desc>A 3D maze generated using a modified version of Prim's algorithm. Vertical layers are numbered starting from the bottom layer to the top. Stairs up are indicated with '/'; stairs down with '\\', and stairs up-and-down with 'x'. License is Cc-by-sa-3.0. See Wikimedia Commons for the algorithm used.</desc>\n"
+ "<!--\n"
+ " <rect width=\"" + size_x + "px\" height=\"" + size_y + "px\" style=\"fill:blue;\" />\n"
+ "-->\n"
+ " <g stroke=\"black\" stroke-width=\"1\" stroke-linecap=\"round\">\n"
+ this.drawMaze()
+ " </g>\n"
+ " <g fill=\"black\">\n"
+ this.drawLabels()
+ " </g>\n"
+ "</svg>\n"
);
}
/* Main maze-drawing loop. */
this.drawMaze = function () {
var x, y, z;
var lenx = this.lenx;
var leny = this.leny;
var lenz = this.lenz;
var cell_width = this.cell_width;
var pics_xy = Math.ceil(Math.sqrt(lenz));
var outstring = "";
for (z = 0; z < lenz; ++z) {
var row_x = cell_width + cell_width * (lenx + 1) * (z % pics_xy);
var row_y = cell_width + cell_width * (leny + 1) * Math.floor(z / pics_xy);
for (y = 0; y < leny; ++y) {
for (x = 0; x < lenx; ++x) {
if ((this.mazex][y][z & WALL_ABOVE) != 0) {
var x1_pos = row_x + cell_width * x;
var y1_pos = row_y + cell_width * y;
var x2_pos = row_x + cell_width * (x + 1);
var y2_pos = row_y + cell_width * y;
outstring += this.drawLine(x1_pos, y1_pos, x2_pos, y2_pos);
}
if ((this.mazex][y][z & WALL_BELOW) != 0) {
var x1_pos = row_x + cell_width * x;
var y1_pos = row_y + cell_width * (y + 1);
var x2_pos = row_x + cell_width * (x + 1);
var y2_pos = row_y + cell_width * (y + 1);
outstring += this.drawLine(x1_pos, y1_pos, x2_pos, y2_pos);
}
if ((this.mazex][y][z & WALL_LEFT) != 0) {
var x1_pos = row_x + cell_width * x;
var y1_pos = row_y + cell_width * y;
var x2_pos = row_x + cell_width * x;
var y2_pos = row_y + cell_width * (y + 1);
outstring += this.drawLine(x1_pos, y1_pos, x2_pos, y2_pos);
}
if ((this.mazex][y][z & WALL_RIGHT) != 0) {
var x1_pos = row_x + cell_width * (x + 1);
var y1_pos = row_y + cell_width * y;
var x2_pos = row_x + cell_width * (x + 1);
var y2_pos = row_y + cell_width * (y + 1);
outstring += this.drawLine(x1_pos, y1_pos, x2_pos, y2_pos);
}
if ((this.mazex][y][z & WALL_FRONT) == 0) {
var x1_pos = row_x + cell_width/3 + cell_width * x;
var y1_pos = row_y + cell_width/3 + cell_width * y;
var x2_pos = row_x - cell_width/3 + cell_width * (x + 1);
var y2_pos = row_y - cell_width/3 + cell_width * (y + 1);
outstring += this.drawLine(x1_pos, y1_pos, x2_pos, y2_pos);
}
if ((this.mazex][y][z & WALL_BACK) == 0) {
var x1_pos = row_x + cell_width/3 + cell_width * x;
var y1_pos = row_y - cell_width/3 + cell_width * (y + 1);
var x2_pos = row_x - cell_width/3 + cell_width * (x + 1);
var y2_pos = row_y + cell_width/3 + cell_width * y;
outstring += this.drawLine(x1_pos, y1_pos, x2_pos, y2_pos);
}
}
}
}
return outstring;
}
/* Draw a line, either in the SVG file or on the screen. */
this.drawLine = function (x1, y1, x2, y2) {
return " <line x1=\"" + x1 + "\" y1=\"" + y1 + "\" x2=\"" + x2 + "\" y2=\"" + y2 + "\" />\n";
}
/* Text labels. */
this.drawLabels = function () {
var z;
var lenx = this.lenx;
var leny = this.leny;
var lenz = this.lenz;
var cell_width = this.cell_width;
var pics_xy = Math.ceil(Math.sqrt(lenz));
var outstring = "";
for (z = 0; z < lenz; ++z) {
var row_x = cell_width + cell_width * (lenx + 1) * (z % pics_xy);
var row_y = cell_width + cell_width * (leny + 1) * Math.floor(z / pics_xy);
outstring += this.drawText(row_x, row_y, z + 1);
}
return outstring;
}
/* Text labels. */
this.drawText = function (x, y, label) {
var cell_width = this.cell_width;
y -= cell_width/10;
return " <text x=\"" + x + "\" y=\"" + y + "\" font-size=\"" + cell_width + "px\" font-family=\"LucidaTypewriter Sans\">" + label + ".</text>\n";
}
}
/* Initialization method that will be called when the program is
* run from the command-line. Maze will be written as SVG file. */
function main(args) {
var m = new Maze();
m.createMaze();
m.printSVG();
}
/* execute the program */
main();