copyright Steve J. Hodges   http://steveh.net/cs21/cs21-hw06.html

CS21 Spring 2018

Assignment 6

Amazing Union-Find

Maze Generation with Disjoint Sets

Directory Name

21-6

Required Executable Name

p6

I'll run your program either way:
./p6 n
java p6 n
CS21 Spring 2013 student Raphie Palefsky-Smith
has set up a maze rendering service online
Details at: http://cs21maze.herokuapp.com/
CS21 Spring 2013 student Emmanuel Mendoza wrote a 
maze visualizer using java script
Jeff Bergamini's upgraded Maze Visualizer
with live preview and optional labels

Maze Encoding Scheme Handout

HexMaze_info.pdf

Program Description

Using a Union-Find data structure (coded as a seperate class), create a program that generates nxn sized mazes. Each square in the maze is bounded by four positions: right(1), bottom(2), left(4) and top(8). Each position may have a wall, or may be open. Each square in the maze can be represented by one hex digit (0, 1, 2 ... F). (For example, 'D' is a square with walls to the left, right and top and 'F' is a square surrounded by walls.) Note: See the Hex Maze class houndout for further explanation. Your program should accept n as a command line parameter. The minimum allowed value for n is three -- check for bad values and terminate the program with a reminder. Your program should output (the only output of your program) a nxn block of hex characters (no spaces) that represent the maze to STDOUT. Initially, the maze should have a 'start' at the top left, an 'exit' at the bottom right, and walls around every other square. (For example, a 3x3 maze to be generated would be initialized as "BFF", "FFF", "FFE".) The walls in adjacent squares must match. (For example, the sequence "69" could appear in a legal maze, but not "6D".) In the resulting maze, every square should be 'reachable' from every other square. (For example, "A9D", "C03", "76A" is a legal 3x3 maze.)

Maze Generation

Each square in the maze should be represented by an individual element in your Union-Find data structure. Use a numbering scheme for the squares such that you can tell which squares are adjacent. Select two adjacent squares and union them if they are not already in the same set at the same time that you "knock out" the walls between them (by adjusting the value 0-F of each of the two squares.) Repeat until there is only one set. At this point every square in the maze is mutually reachable. Some techniques to do this efficiently will be discussed in class.

implementation

The Maze Generation logic should have its own class, as should the Disjoint Set. You probably want a seperate main function to handle the minimal i/o (p6.java or main.cpp)

Testing Hint

Short of finding a path from start to end (assignment 8,) or from the start to every square in the maze (which is even trickier,) how can you verify that your maze is valid? Smaller mazes can be checked visually using one of the programs provided. Larger mazes can be partially checked. Verify that no squares are 'F' and check each adjanced pair of squares to make sure that they are in agreement about the presence or lack of a wall between them. Make sure that all the exterior walls are in place (except for the opening for the start and the finish.)


Sample Run

[steveh@pengo2 MazeGen]$ ./p6 5
9ea89
4a835
4b7e3
4bc9d
6a362
[steveh@pengo2 MazeGen]$ 

What to turn in

Put all of the source code files (.cpp, .h, makefile if C++, .java, etc.) but no executeables, binaries, compiler, or data files (omit .o, "a.out" , .class files etc.) in a folder named as shown above in the home directory of your account on pengo. Please don't include any sub-folders.