Jump to content

File:Prim Maze 3D.svg

Page contents not supported in other languages.
This is a file from the Wikimedia Commons
From Wikipedia, the free encyclopedia

Original file (SVG file, nominally 400 × 400 pixels, file size: 55 KB)

Description
English: 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'.
Date (UTC)
Source
Author


This is a retouched picture, which means that it has been digitally altered from its original version. Modifications: Extended into the 3D dimension.. The original can be viewed here: Prim Maze.svg. Modifications made by SharkD.

I, the copyright holder of this work, hereby publish it under the following licenses:
w:en:Creative Commons
attribution share alike
This file is licensed under the Creative Commons Attribution-Share Alike 3.0 Unported license.
You are free:
  • to share – to copy, distribute and transmit the work
  • to remix – to adapt the work
Under the following conditions:
  • attribution – You must give appropriate credit, provide a link to the license, and indicate if changes were made. You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use.
  • share alike – If you remix, transform, or build upon the material, you must distribute your contributions under the same or compatible license as the original.
GNU head Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation; with no Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts. A copy of the license is included in the section entitled GNU Free Documentation License.
You may select the license of your choice.

Original upload log

This image is a derivative work of the following images:

  • File:Prim_Maze.svg licensed with Cc-by-sa-3.0, GFDL
    • 2009-06-01T13:14:50Z Nandhp 200x200 (30665 Bytes) {{Information |Description={{en|1=A maze, generated by modified version of [[:en:Prim's algorithm]].}} |Source=Generated by the attached program, which was originally written by [[:en:User:Cyp]], who attached it to the image

Uploaded with derivativeFX

Source code

/*
 * 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) {
			maze[x] = [];
			for (y = 0; y < leny; ++y) {
				maze[x][y] = [];
				for (z = 0; z < lenz; ++z) {
					maze[x][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. */
		maze[x][y][z] &= ~(QUEUED + IN_MAZE);

		/* Remember the surrounding squares, as we will... */
		for (d = 0; d < 6; ++d) {
			x_dx = x + dx[d];
			y_dy = y + dy[d];
			z_dz = z + dz[d];
			if (x_dx >= 0 && x_dx < lenx && y_dy >= 0 && y_dy < leny && z_dz >= 0 && z_dz < lenz) {
				if ((maze[x_dx][y_dy][z_dz] & QUEUED) != 0) {
					/* ...want to connect them to the maze. */              
					todo[todonum++] = [x_dx, y_dy, z_dz];
					maze[x_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 = todo[n][0];
			y = todo[n][1];
			z = todo[n][2];

			/* We will connect it, so remove it from the queue. */
			todo[n] = todo[--todonum];

			/* Select a random direction, which leads to the maze. */
			var passBool = 0;
			while (passBool == 0)
			{
				d = Math.nextInt(6);
				x_dx = x + dx[d];
				y_dy = y + dy[d];
				z_dz = z + dz[d];
				if (x_dx >= 0 && x_dx < lenx && y_dy >= 0 && y_dy < leny && z_dz >= 0 && z_dz < lenz) {
					if ((maze[x_dx][y_dy][z_dz] & IN_MAZE) == 0)
						passBool = 1;
				}
			}

			/* Connect this square to the maze. */
			maze[x][y][z] &= ~((1 << d) | IN_MAZE);
			maze[x + dx[d]][y + dy[d]][z + dz[d]] &= ~(1 << (d ^ 1));

			/* Remember the surrounding squares, which aren't... */
			for (d = 0; d < 6; ++d) {
				x_dx = x + dx[d];
				y_dy = y + dy[d];
				z_dz = z + dz[d];
				if (x_dx >= 0 && x_dx < lenx && y_dy >= 0 && y_dy < leny && z_dz >= 0 && z_dz < lenz) {
					if ((maze[x_dx][y_dy][z_dz] & QUEUED) != 0) {
						/* ...connected to the maze, and aren't yet queued. */
						todo[todonum++] = [x_dx, y_dy, z_dz];
						maze[x_dx][y_dy][z_dz] &= ~QUEUED;
					}
				}
			}
			/* Repeat until finished. */
		}

		/* Add an entrance and exit. */
		maze[0][Math.floor(leny/2)][0] &= ~WALL_LEFT;
		maze[lenx - 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.maze[x][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.maze[x][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.maze[x][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.maze[x][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.maze[x][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.maze[x][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();

Captions

Add a one-line explanation of what this file represents

Items portrayed in this file

depicts

8 January 2011

File history

Click on a date/time to view the file as it appeared at that time.

Date/TimeThumbnailDimensionsUserComment
current09:28, 8 January 2011Thumbnail for version as of 09:28, 8 January 2011400 × 400 (55 KB)DatumizerDouble the size.
09:24, 8 January 2011Thumbnail for version as of 09:24, 8 January 2011200 × 200 (55 KB)Datumizertypo
09:21, 8 January 2011Thumbnail for version as of 09:21, 8 January 2011200 × 200 (55 KB)DatumizerOops, got stairs up and down icons backwards.
09:02, 8 January 2011Thumbnail for version as of 09:02, 8 January 2011200 × 200 (64 KB)DatumizerDoh! Stairs up and down were broken.
08:52, 8 January 2011Thumbnail for version as of 08:52, 8 January 2011200 × 200 (90 KB)DatumizerOops, sides got clipped.
08:51, 8 January 2011Thumbnail for version as of 08:51, 8 January 2011200 × 200 (90 KB)DatumizerMatch dimensions of original.
08:49, 8 January 2011Thumbnail for version as of 08:49, 8 January 2011210 × 210 (90 KB)DatumizerReduce number of rows and columns further so things are not so tiny.
08:47, 8 January 2011Thumbnail for version as of 08:47, 8 January 2011390 × 390 (359 KB)DatumizerReduce number of rows and columns by 2 to match original.
08:28, 8 January 2011Thumbnail for version as of 08:28, 8 January 2011430 × 430 (441 KB)DatumizerCells are aligned in a square grid and labeled.
06:27, 8 January 2011Thumbnail for version as of 06:27, 8 January 2011512 × 512 (528 KB)Datumizer{{Information |Description={{en|1=A maze, generated by modified version of en:Prim's algorithm.}} |Source=*File:Prim_Maze.svg |Date=2011-01-08 06:27 (UTC) |Author=*File:Prim_Maze.svg: Nandhp *derivative work: ~~~ |Permissi

The following page uses this file:

Global file usage

The following other wikis use this file:

Metadata