efg's Mathematics Projects -- Maze Maker

Lab Report

Create a Maze

Purpose
The purpose of this program is to draw a maze of a specified size and show the solution path.

Materials and Equipment

Software Requirements
Windows 95/98
Delphi 4 only (Will not compile in Delphi 3 since new Delphi 4 features are used)

Hardware Requirements
VGA display

Procedure

Double click on the MazeMaker.EXE icon to start the program.
Create a new maze by clicking on the New Maze button. This creates a new random number Seed for creation of the maze.
Select he minimize/maximize Windows buttons at the upper right of the screen to change the display area of the maze. The size of the maze can also be changed by dragging the corners of the widow. However, a minimum window size is enforced -- the window can never be smaller than its original size.
The Cell SpinBoxes change the number of cells used in the maze algorithm. Increase the number of cell columns and rows for a larger maze.
The Pixels SpinBoxes change the size of the bitmap. If the bitmap does not fit in the current window, scroll bars from the ScrollBox will automatically appear so the whole bitmap can be viewed on the screen.
Press the Print button to print a maze. Click "OK" on the Print Maze dialog to print the maze. For now, the printed maze always appears in a landscape orientation and uses as much of the printed page as possible (while leaving a reasonable margin). Except for the larger "pixel area" of the printer canvas, the number of cells, random number generator seed and path style and path color are the same in the printed maze as on the screen.
Press the Save button to create a BMP file. (The PixelFormat of the BMP file will be the same as the current display mode.)
Change the appearance of the maze solution path using the PathStyle or PathColor RadioGroup selections, and the Show Path CheckBox. Click on the Color TShape object to change the definition of the "Solid" path color. If the path is not shown (the Show Path checkbox is not checked), then red ellipses mark the start and end points of the maze.
If you select the Block Path Style, you can flood fill the connected regions of the maze area by clicking on a point on the maze.
Reconstruct any maze by entering the random number generator Seed in the edit box.

Discussion
The WMGetMinMaxInfo routine in the ScreenMazeMaker unit enforces a minimum window size as a response to a Windows wm_GetMinMaxInfo message.

The UpdateMaze routine in the ScreenMazeMaker unit is called by the various controls whenever a value changes that affects the maze.

Direct entry of values in the SpinBoxes can cause problem when the SpinBox is blank. Borland should make a TSpinBox more than an undocumented "Sample," especially by version 4 of Delphi.

The Maze Algorithm is in the MazeLibrary unit in the DrawMaze routine. Each cell in the maze is represented by a 2-bit quantity (a 0..3 type) in a dynamically-allocated two-dimensional Cells array using the Delphi 4 SetLength routine. Bit 0 is set if the cell has an East exit, and bit 1 is set if it has a South exit. To test if a North or West exit exists, the appropriate adjacent cells must be considered.

The DrawMaze routine shows an interesting way to create a stack in Delphi. In-line assembly language was used to Push and Pop values off a memory stack without any other code to implement the stack.

The Rainbow Path Color is one way to segment the solution path into regions. The function WavelengthToColor in the SpectraLibrary unit returns a TColor for a given wavelength of light from 380 to 780 nanometers. The maze path was scaled to vary between these extremes.

Conclusion
The MazeMaker is an interesting recreational math program.

Future Study
For a given array of maze cells, a study of the distribution of the maze length may be interesting.

Further Study

Links:
The Borland February 2000 Delphi Games Contest had some interesting maze generators:
http://homepages.borland.com/ccalvert/Contest/FebContest/FebWinners.html

Random Maze Generator
http://turbo.gamedev.net/Maze.zip

Maze Solving
www.undu.com/Articles/000229a.html

Delphi for Fun: Maze Generator
www.delphiforfun.org/Programs/maze.htm

www.ai.mit.edu/people/shivers/mazes.html
www.mazemaker.com
www.mazeworks.com/mazegen/mazegen.htm
www.flint.umich.edu/cgi-bin/maze.other
Maze Construction FAQ

Books (Amazon Links)
Mazes and Labyrinths: Their History and Development
Labyrinths and Number Mazes
Puzzles, Mazes and Numbers

Keywords
Maze algorithm, ScrollBox, FormResize, wm_GetMinMaxInfo, rainbow colors, stack, Ellipse, MoveTo, LineTo, FrameRect, FillRect

Download
Delphi 4 Source and EXE (208 KB): MazeMaker.ZIP

Because Delphi 4 dynamic arrays were used in the MazeLibrary unit to create an "array of array of 0..3", and because of default parameters used in the DrawMaze routine, this program will NOT compile in Delphi 3.

Updated 18 Feb 2002

since 28 Feb 1998