/*
 * 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);
    }
}