File:Prim Maze.svg

Original file (SVG file, nominally 200 × 200 pixels, file size: 30 KB)

Summary

Description
English: A maze, generated by modified version of en:Prim's algorithm.
Date
Source Generated by the attached program, which 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.
Author Nandhp
Other versions

Derivative works of this file:  Prim Maze 3D.svg

SVG version of en:File:Maze.png.

Licensing

I, the copyright holder of this work, hereby publish it under the following licenses:
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.
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.
You may select the license of your choice.

Generating Program

Java

/*
 * 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
 *
 * 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.
 */
 
import java.awt.*;
import java.applet.*;
import java.util.Random;
 
/* Define the bit masks */
class Constants {
    public static final int WALL_ABOVE = 1;
    public static final int WALL_BELOW = 2;
    public static final int WALL_LEFT = 4;
    public static final int WALL_RIGHT = 8;
    public static final int QUEUED = 16;
    public static final int IN_MAZE = 32;
}
 
public class Maze extends java.applet.Applet {
    /* The width and height (in cells) of the maze */
    private int width;
    private int height;
    private int maze[][];
    private static final Random rnd = new Random();
 
    /* The width in pixels of each cell */
    private int cell_width;
 
    /* Construct a Maze with the default width, height, and cell_width */
    public Maze() {
	this(20,20,10);
    }
 
    /* Construct a Maze with specified width, height, and cell_width */
    public Maze(int width, int height, int cell_width) {
	this.width = width;
	this.height = height;
	this.cell_width = cell_width;
    }
 
    /* Initialization method that will be called when the program is
     * run from the command-line. Maze will be written as SVG file. */
    public static void main(String[] args) {
	Maze m = new Maze();
	m.createMaze();
	m.printSVG();
    }
 
    /* Initialization method that will be called when the program is
     * run as an applet. Maze will be displayed on-screen. */
    public void init() {
	createMaze();
    }
 
    /* The maze generation algorithm. */
    private void createMaze(){
	int x, y, n, d;
	int dx[] = { 0, 0, -1, 1 };
	int dy[] = { -1, 1, 0, 0 };
 
	int todo[] = new int[height * width], todonum = 0;
 
	/* We want to create a maze on a grid. */
	maze = new int[width][height];
 
	/* We start with a grid full of walls. */
	for (x = 0; x < width; ++x) {
	    for (y = 0; y < height; ++y) {
		if (x == 0 || x == width - 1 || y == 0 || y == height - 1) {
		    maze[x][y] = Constants.IN_MAZE;
		} else {
		    maze[x][y] = 63;
		}
	    }
	}
 
	/* Select any square of the grid, to start with. */
	x = 1 + rnd.nextInt (width - 2);
	y = 1 + rnd.nextInt (height - 2);
 
	/* Mark this square as connected to the maze. */
	maze[x][y] &= ~48;
 
	/* Remember the surrounding squares, as we will */
	for (d = 0; d < 4; ++d) {
	    if ((maze[x + dx[d]][y + dy[d]] & Constants.QUEUED) != 0) {
		/* want to connect them to the maze. */              
		todo[todonum++] = ((x + dx[d]) << Constants.QUEUED) | (y + dy[d]);
		maze[x + dx[d]][y + dy[d]] &= ~Constants.QUEUED;
	    }
	}
 
	/* We won't be finished until all is connected. */
	while (todonum > 0) {
	    /* We select one of the squares next to the maze. */
	    n = rnd.nextInt (todonum);
	    x = todo[n] >> 16; /* the top 2 bytes of the data */
	    y = todo[n] & 65535; /* the bottom 2 bytes of the data */
 
	    /* We will connect it, so remove it from the queue. */
	    todo[n] = todo[--todonum];
 
	    /* Select a direction, which leads to the maze. */
	    do {
		d = rnd.nextInt (4);
	    }
	    while ((maze[x + dx[d]][y + dy[d]] & Constants.IN_MAZE) != 0);
 
	    /* Connect this square to the maze. */
	    maze[x][y] &= ~((1 << d) | Constants.IN_MAZE);
	    maze[x + dx[d]][y + dy[d]] &= ~(1 << (d ^ 1));
 
	    /* Remember the surrounding squares, which aren't */
	    for (d = 0; d < 4; ++d) {
		if ((maze[x + dx[d]][y + dy[d]] & Constants.QUEUED) != 0) {      
		    /* connected to the maze, and aren't yet queued to be. */
		    todo[todonum++] = ((x + dx[d]) << Constants.QUEUED) | (y + dy[d]);
		    maze[x + dx[d]][y + dy[d]] &= ~Constants.QUEUED;
		}
	    }
            /* Repeat until finished. */
        }
 
        /* Add an entrance and exit. */
        maze[1][1] &= ~Constants.WALL_ABOVE; 
        maze[width - 2][height - 2] &= ~Constants.WALL_BELOW;
    }
 
    /* Called by the applet infrastructure to display the maze on-screen. */
    public void paint(Graphics g) {
	drawMaze(g);
    }
 
    /* Called to write the maze to an SVG file. */
    public void printSVG() {
	System.out.format("<svg width=\"%d\" height=\"%d\" version=\"1.1\""
			  + " xmlns=\"http://www.w3.org/2000/svg\">\n",
			  width*cell_width, height*cell_width);
	System.out.println("  <g stroke=\"black\" stroke-width=\"1\""
			   + " stroke-linecap=\"round\">");
	drawMaze(null);
	System.out.println("  </g>\n</svg>");
    }
 
    /* Main maze-drawing loop. */
    public void drawMaze(Graphics g) {
        int x, y;
 
        for (x = 1; x < width - 1; ++x) {
            for (y = 1; y < height - 1; ++y) {
                if ((maze[x][y] & Constants.WALL_ABOVE) != 0)
		    drawLine(      x * cell_width,       y * cell_width,
			     (x + 1) * cell_width,       y * cell_width, g);
                if ((maze[x][y] & Constants.WALL_BELOW) != 0)
		    drawLine(      x * cell_width, (y + 1) * cell_width,
			     (x + 1) * cell_width, (y + 1) * cell_width, g);
                if ((maze[x][y] & Constants.WALL_LEFT) != 0)
		    drawLine(      x * cell_width,       y * cell_width,
			           x * cell_width, (y + 1) * cell_width, g);
                if ((maze[x][y] & Constants.WALL_RIGHT) != 0)
		    drawLine((x + 1) * cell_width,       y * cell_width,
			     (x + 1) * cell_width, (y + 1) * cell_width, g);
	    }
	}
    }
 
    /* Draw a line, either in the SVG file or on the screen. */
    public void drawLine(int x1, int y1, int x2, int y2, Graphics g) {
	if ( g != null ) g.drawLine(x1, y1, x2, y2);
	else System.out.format("    <line x1=\"%d\" y1=\"%d\""
			       + " x2=\"%d\" y2=\"%d\" />\n", x1, y1, x2, y2);
    }
}

JavaScript

/*
 * 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
 *
 * 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)
	// if inside a Web page <body> tag (might work better than alert)
//	document.body.appendChild(document.createTextNode(string))
}

/* Define the bit masks */
var Constants =
{
	WALL_ABOVE : 1,
	WALL_BELOW : 2,
	WALL_LEFT : 4,
	WALL_RIGHT : 8,
	QUEUED : 16,
	IN_MAZE : 32
}

/* Construct a Maze with specified width, height, and cell_width */
function Maze(width, height, cell_width) {
	if (width)
		this.width = width;
	else
		this.width = 20;
	if (height)
		this.height = height;
	else
		this.height = 20;
	if (cell_width)
		this.cell_width = cell_width;
	else
		this.cell_width = 10;
	this.maze = []

	/* The maze generation algorithm. */
	this.createMaze = function()  {
		var width = this.width
		var height = this.height
		var maze = this.maze
		var x, y, n, d;
		var dx = [ 0, 0, -1, 1 ];
		var dy = [ -1, 1, 0, 0 ];

		var todo = new Array(height * width);
		var todonum = 0;

		/* We want to create a maze on a grid. */
		/* We start with a grid full of walls. */
		for (x = 0; x < width; ++x) {
			maze[x] = []
			for (y = 0; y < height; ++y) {
				if (x == 0 || x == width - 1 || y == 0 || y == height - 1) {
					maze[x][y] = Constants.IN_MAZE;
				}
				else {
					maze[x][y] = 63;
				}
			}
		}

		/* Select any square of the grid, to start with. */
		x = 1 + Math.nextInt(width - 2);
		y = 1 + Math.nextInt(height - 2);

		/* Mark this square as connected to the maze. */
		maze[x][y] &= ~48;

		/* Remember the surrounding squares, as we will */
		for (d = 0; d < 4; ++d) {
			if ((maze[x + dx[d]][y + dy[d]] & Constants.QUEUED) != 0) {
				/* want to connect them to the maze. */              
				todo[todonum++] = ((x + dx[d]) << Constants.QUEUED) | (y + dy[d]);
				maze[x + dx[d]][y + dy[d]] &= ~Constants.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] >> 16; /* the top 2 bytes of the data */
			y = todo[n] & 65535; /* the bottom 2 bytes of the data */

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

			/* Select a direction, which leads to the maze. */
			do {
				d = Math.nextInt(4);
			}
			while ((maze[x + dx[d]][y + dy[d]] & Constants.IN_MAZE) != 0);

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

			/* Remember the surrounding squares, which aren't */
			for (d = 0; d < 4; ++d) {
				if ((maze[x + dx[d]][y + dy[d]] & Constants.QUEUED) != 0) {      
					/* connected to the maze, and aren't yet queued to be. */
					todo[todonum++] = ((x + dx[d]) << Constants.QUEUED) | (y + dy[d]);
					maze[x + dx[d]][y + dy[d]] &= ~Constants.QUEUED;
				}
			}
			/* Repeat until finished. */
		}

		/* Add an entrance and exit. */
		maze[1][1] &= ~Constants.WALL_ABOVE; 
		maze[width - 2][height - 2] &= ~Constants.WALL_BELOW;
	}
	/* Called to write the maze to an SVG file. */
	this.printSVG = function () {
		var outstring = "<svg width=\"" + (this.width * this.cell_width) + "\" height=\"" + (this.height*this.cell_width) + "\" version=\"1.1\" xmlns=\"http://www.w3.org/2000/svg\">\n"
				+ "  <g stroke=\"black\" stroke-width=\"1\" stroke-linecap=\"round\">\n"
				+ this.drawMaze()
				+ "  </g>\n</svg>\n";
		println(outstring)
	}
	/* Main maze-drawing loop. */
	this.drawMaze = function () {
		var x, y;
		var width = this.width;
		var height = this.height;
		var cell_width = this.cell_width
		var outstring = ""
		for (x = 1; x < width - 1; ++x) {
			for (y = 1; y < height - 1; ++y) {
				if ((this.maze[x][y] & Constants.WALL_ABOVE) != 0)
					outstring += this.drawLine(      x * cell_width,       y * cell_width,		(x + 1) * cell_width,       y * cell_width);
				if ((this.maze[x][y] & Constants.WALL_BELOW) != 0)
					outstring += this.drawLine(      x * cell_width, (y + 1) * cell_width,		(x + 1) * cell_width, (y + 1) * cell_width);
				if ((this.maze[x][y] & Constants.WALL_LEFT) != 0)
					outstring += this.drawLine(      x * cell_width,       y * cell_width,		x * cell_width, (y + 1) * cell_width);
				if ((this.maze[x][y] & Constants.WALL_RIGHT) != 0)
					outstring += this.drawLine((x + 1) * cell_width,       y * cell_width,		(x + 1) * cell_width, (y + 1) * cell_width);
			}
		}
		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";
	}
}

/* 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

1 June 2009

File history

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

Date/TimeThumbnailDimensionsUserComment
current13:14, 1 June 2009Thumbnail for version as of 13:14, 1 June 2009200 × 200 (30 KB)Nandhp{{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 description page for an image

The following 2 pages use this file:

Global file usage

The following other wikis use this file: