Everything You Ever Wanted to Know About Randomly Generated Quake 2 Mazes

(This readme applies only to Windows machines.)

Required Files:

To generate the mazes: (All of these files can be downloaded in a zip archive HERE AT CIF or HERE AT CS )
Wally The texture creation tool
Maze.class - The maze image generator [All other .class files in the mazes.zip archive are used by Maze]
bmp2map.exe The image -> Quake 1 map converter
mapconv.exe The Quake 1 map -> Quake 2 map converter
qbsp3.exe This renders .map files into playable .bsp files
To run the mazes:
Quake 2 The Game
maze.bsp - The Maze
floor.wal, wall.wal, ceiling.wal - The textures for the map

Generating the Mazes:

1. Download and install all required files for generating the mazes.
2. 3 distinct tiling images should be chosen for the floor, wall, and ceiling textures. These images should be placed in one directory and named floor, wall, and ceiling. Most commonly used image types will work.
3. Open Wally, and select File->Batch Conversion. Choose the directory where the texture images are stored as your input directory, and wherever you wish to store the final textures as your output directory. For the file wildcard, *.whatever-file-extension-you-used works. Then hit convert. This will generate 3 .wal Quake 2 texture files, floor, wall, and ceiling.
4. Run David Sloan's Maze Generator. This will generate an 8-bit palletized windows bitmap image of the maze, with the spawnpoint and goal marked, named maze10x10.bmp (where 10x10 will by whatever dimensions you choose for the maze)
Usage: java Maze -b -s xdim ydim
(xdim and ydim are the x and y dimensions of the pixel maze that this will generate. 10 is the default for both if the -s option is not used.)
5. Use bmp2map on the .bmp image that the maze generator created. This will create a .map file with the same name as the .bmp, but it will be in Quake 1 format.
Usage: bmp2map maze10x10.bmp mazemap.cfg
6. Use mapconv on the .map file that bmp2map created. This will generate a .map file named mazemap that is in proper Quake 2 format.
Usage: mapconv -toq2 -addpath e1u1 mazemap.map maze.map
7. Use qbsp3 on maze.map. This compiles the .map text file into a .bsp named maze file which is actually readable by the game.
Usage: qbsp3 maze.map
8. Gather the map (maze.bsp) and the three texture files (floor.wal, wall.wal, ceiling.wal).
You're done!
Here is a screenshot of part of a map, including the goal:


Running the Maze:

1. Obtain all files necessary to run the maze.
2. Install Quake 2.
3. Place the 3 .wal texture files in the Quake 2/baseq2/textures/e1u1 directory.
4. Place maze.bsp into the baseq2/maps directory.
5. Run Quake 2, drop the console by pressing ~, and type map maze
Navigate the maze!
The goal of the maze is marked by an ammo_rockets object, so when you find that, you've solved the maze!



How the Maze is made:

The mazes are generated using Kruskal's Algorithm. This implements the Union-Find algorithm to join all the cells in the grid, using equivalence classes. This results in a maze with a high branching factor and only one path to the goal. Here is an example of the mazes generated: