Maze Generator in C#

[randomfox]

This program generates mazes. It works by starting at an empty cell and doing a random walk, drawing a wall as it goes, until it collides with another maze wall. It does that until all the cells are full.

// mazegen - Generates mazes.
//
// Author: Po Shan Cheah
// Last updated: August 19, 2003
// 
// Compile with: csc /doc:mazegen.xml mazegen.cs

namespace MazeGen {

using System;
using System.Drawing;
using System.Windows.Forms;

class Maze {
    const int UP = 1;
    const int LEFT = 2;
    const int RIGHT = 4;
    const int DOWN = 8;

    // The maze array.
    int[,] maze;
    int rows;
    int cols;

    // Number of cells remaining to be filled.
    int unused;

    public Maze(int rows, int cols) {
	this.rows = rows;
	this.cols = cols;

	maze = new int[cols, rows];

	for (int i = 0; i < cols; ++i)
	    for (int j = 0; j < rows; ++j)
		maze[i, j] = 0;

	// corners
	maze[0, 0] = DOWN | RIGHT;
	maze[cols-1, 0] = DOWN | LEFT;
	maze[0, rows-1] = UP | RIGHT;
	maze[cols-1, rows-1] = UP | LEFT;

	// Sides
	for (int i = 1; i < rows - 1; ++i) {
	    maze[0, i] = DOWN | UP;
	    maze[cols-1, i] = DOWN | UP;
	}
	for (int i = 1; i < cols - 1; ++i) {
	    maze[i, 0] = LEFT | RIGHT;
	    maze[i, rows-1] = LEFT | RIGHT;
	}

	// Openings
	maze[cols/2, 0] = UP | LEFT;
	maze[cols/2 + 1, 0] = UP | RIGHT;
	maze[cols/2, rows-1] = DOWN | LEFT;
	maze[cols/2 + 1, rows-1] = DOWN | RIGHT;

	unused = (cols - 2) * (rows - 2);

	Generate();
	Draw();
    }

    // Offscreen buffer.
    Bitmap image;
    Graphics graphics;

    /// <summary>Draw the maze on an offscreen image buffer.</summary>
    void Draw() {
	const int CELLSIZE = 8;

	int xsize = cols * CELLSIZE;
	int ysize = rows * CELLSIZE;

	image = new Bitmap(xsize, ysize);
	graphics = Graphics.FromImage(image);

	graphics.Clear(Color.DarkBlue);

	Pen pen = new Pen(Color.Yellow);

	for (int i = 0; i < cols; ++i)
	    for (int j = 0; j < rows; ++j) {
		int room = maze[i, j];
		if ((room & UP) != 0)
		    graphics.DrawLine(pen,
				      i * CELLSIZE + CELLSIZE/2,
				      j * CELLSIZE,
				      i * CELLSIZE + CELLSIZE/2,
				      j * CELLSIZE + CELLSIZE/2 - 1);
		if ((room & DOWN) != 0)
		    graphics.DrawLine(pen,
				      i * CELLSIZE + CELLSIZE/2,
				      j * CELLSIZE + CELLSIZE/2,
				      i * CELLSIZE + CELLSIZE/2,
				      j * CELLSIZE + CELLSIZE - 1);
		if ((room & RIGHT) != 0)
		    graphics.DrawLine(pen, 
				      i * CELLSIZE + CELLSIZE/2,
				      j * CELLSIZE + CELLSIZE/2,
				      i * CELLSIZE + CELLSIZE - 1,
				      j * CELLSIZE + CELLSIZE/2);
		if ((room & LEFT) != 0)
		    graphics.DrawLine(pen,
				      i * CELLSIZE,
				      j * CELLSIZE + CELLSIZE/2,
				      i * CELLSIZE + CELLSIZE/2 - 1,
				      j * CELLSIZE + CELLSIZE/2);
	    }
    }

    /// <summary>Paint the image onto the specified graphics
    /// context</summary>
    public void Paint(Graphics g, int x, int y) {
	g.DrawImage(image, x, y);
    }

    /// <summary>Generate a random maze.</summary>
    /// <remarks>We start at an empty cell in the maze. We create a wall by
    /// doing a random walk through the maze. When we hit an existing wall,
    /// we stop. 
    /// <para>Theory: Since the walk started on an empty cell, that path
    /// can never bisect the maze and so there should still be a solution
    /// to the maze after we add each wall.</para></remarks>

    void Generate() {
	// Maximum number of steps to save so that the maze crawler
	// does not close back on itself. Low values may affect the
	// quality of the maze.
	const int Nsave = 20;

	// Array keeping track of the directions the random walk took in
	// the past Nsave steps.
	int[] prevNdir = new int[Nsave];

	// Table stating what we should add to the current row
	// and column to move in that direction.
	int[,] moveTable = {{0, -1}, {-1, 0}, {1, 0}, {0, 1}};
	    
	// The location of the random walker.
	int curx, cury;

	Random random = new Random();

	while (unused > 0) {

	    // Find an empty cell.
	    do {
		curx = random.Next(cols);
		cury = random.Next(rows);
	    } while (maze[curx, cury] != 0);

	    for (int i = 0; i < Nsave; ++i)
		prevNdir[i] = 0;
	    --unused;

	    for (;;) {
		// 1 << dir will be UP, DOWN, LEFT, RIGHT.
		// Those direction constants are chosen so that
		// the dir values for UP and DOWN and the xor of
		// each other and so are the dir values for LEFT
		// and RIGHT.
		int dir;

		for (int i = 0; i < Nsave - 1; ++i)
		    prevNdir[i] = prevNdir[i+1];

		bool[] gotdir = new bool[4];

		do {
		    // Choose a direction that doesn't go back on the
		    // previous step.
		    do {
			dir = random.Next(4);
		    } while (dir == (prevNdir[Nsave - 2] ^ 3));
		    prevNdir[Nsave - 1] = dir;

		    for (int i = 0; i < 4; ++i)
			gotdir[i] = false;
		    for (int i = 0; i < Nsave; ++i)
			gotdir[prevNdir[i]] = true;

		    // Avoid loops within the past nsave steps by
		    // making sure not all four directions are used.
		    // This is more restrictive than necessary but 
		    // it works okay.
		} while (gotdir[0] && gotdir[1] && gotdir[2] && gotdir[3]);

		// Add the wall.
		maze[curx, cury] |= (1 << dir);

		// Go to the next cell.
		curx += moveTable[dir, 0];
		cury += moveTable[dir, 1];

		// Reached another wall?
		bool exitcond = (maze[curx, cury] != 0);

		// Add wall segment needed to join with the previous
		// cell.
		maze[curx, cury] |= (1 << (dir ^ 3));

		if (exitcond)
		    break;

		--unused;
	    }
	}
    } // Generate
	
} // class Maze

class MazeGen : Form {

    // How many pixels down is the maze drawing area from the top of the
    // client rectangle.
    const int TopMargin = 30;

    TextBox rowsfield;
    TextBox colsfield;

    Maze maze = null;

    /// <summary>Event handler for the Go button.</summary>
    void go_Click(object o, EventArgs e) {
	int rows;
	int cols;
	try {
	    rows = int.Parse(rowsfield.Text);
	    cols = int.Parse(colsfield.Text);
	}
	catch (FormatException) {
	    MessageBox.Show("Invalid numeric value entered.");
	    return;
	}

	// The maze breaks down for really small dimensions. The upper
	// limit is to put a cap on the run time.

	const int LowerBound = 10;
	const int UpperBound = 300;

	if (rows < LowerBound || cols < LowerBound) {
	    MessageBox.Show("Out of range\nNumber of rows and columns " +
			    "must be at least " + LowerBound.ToString());
	    return;
	}

	if (rows > UpperBound || cols > UpperBound) {
	    MessageBox.Show("Out of range\nNumber of rows and columns " +
			    "must be below " + UpperBound.ToString());
	    return;
	}

	maze = new Maze(rows, cols);

	Invalidate();
	Update();
    } // go_Click

    /// <summary>Paint event handler.</summary>
    protected override void OnPaint(PaintEventArgs e) {
	e.Graphics.FillRectangle(new SolidBrush(Color.DarkBlue), 
				 0, TopMargin, 
				 ClientRectangle.Width, 
				 ClientRectangle.Height - TopMargin);
	if (maze != null)
	    maze.Paint(e.Graphics, 0, TopMargin);
    }

    MazeGen() {
	Text = "MazeGen";
	Name = "MazeGen";

	// Activate double-buffering.
	SetStyle(ControlStyles.UserPaint, true);
	SetStyle(ControlStyles.AllPaintingInWmPaint, true);
	SetStyle(ControlStyles.DoubleBuffer, true);

	ClientSize = new Size(500, 500);

	Label l1 = new Label();
	l1.Text = "Rows:";
	l1.TextAlign = ContentAlignment.MiddleRight;
	l1.Location = new Point(0, 0);
	l1.Size = new Size(50, 25);

	Controls.Add(l1);

	rowsfield = new TextBox();
	rowsfield.Text = "54";
	rowsfield.MaxLength = 4;
	rowsfield.Location = new Point(60, 3);
	rowsfield.Size = new Size(50, 25);
	
	Controls.Add(rowsfield);

	Label l2 = new Label();
	l2.Text = "Columns:";
	l2.TextAlign = ContentAlignment.MiddleRight;
	l2.Location = new Point(110, 0);
	l2.Size = new Size(75, 25);

	Controls.Add(l2);

	colsfield = new TextBox();
	colsfield.Text = "61";
	colsfield.MaxLength = 4;
	colsfield.Location = new Point(195, 3);
	colsfield.Size = new Size(50, 25);

	Controls.Add(colsfield);

	Button goButton = new Button();
	goButton.Text = "Go";
	goButton.Location = new Point(275, 0);
	goButton.Size = new Size(50, 25);
	goButton.Click += new EventHandler(go_Click);

	Controls.Add(goButton);
	AcceptButton = goButton;

	// Call the event handler on startup so that the window appears
	// with a maze.
	go_Click(null, null);
    }

    static int Main() {
	Application.Run(new MazeGen());
	return 0;
    }
} // class MazeGen

}
// The End