Difference between revisions of "CISC220 F2021 Lab8"

Revision as of 11:35, 3 November 2021

Lab #8

1. Maze generation using union/find

As discussed in class, the union/find data structure can be used to generate rectangular mazes using grid cells as the set elements and connectivity as the equivalence relation. Three approaches were outlined:

• Knock down random walls one at a time until the START and FINISH are connected. Nothing else is considered
• Same as above, but now only knock down a wall if the cells on either side of it are NOT already connected
• Same as above, but only stop on the condition that the maze is solvable AND that every cell in it is connected to every other cell

Two classes are provided in starter code here: Maze and UnionFind. UnionFind is a stub for the union/find data structure which uses an array to represent the equivalence class trees, and Maze is just a data structure to represent and draw N x M grids with walls (see the comments in maze.hh for details). A sample 3 x 4 maze is shown below:

#########
#S|     #
# +-+ + #
#   | |F#
# +-+ +-#
#       #
#########

You have several programming tasks:

• [0.5 points] Fill in the find(), union_sets(), and union_sets_by_size() functions in unionfind.hh. All of these functions were given in class (the last two were called union() and union_by_size(), but union is a reserved keyword in C++).
• [1 point] There's a starter function called knock_down_all_walls() already provided in main.cpp. This simply knocks down random walls one at a time until they're all gone, drawing the current "maze" M after each step. The union/find data structure U which is associated with M is NOT updated, however. Fill in appropriate calls to find() and union_sets() in knock_down_all_walls() so that U IS updated after each wall is removed (this is called "option 1" in the code).
  • Take a look at the helper functions in maze.hh called UF_index_to_rowcol() and row_to_UF_index() for going back and forth between referring to a grid cell by its row and column vs. by its index in the union/find array.
• [1 point] Write knock_down_til_solvable in main.cpp (first bullet above, but "option 2" in the code).
• [1 point] Write knock_down_til_solvable_better in main.cpp (second bullet above, "option 3" in the code)
• [0.5 points] Write knock_down_til_all_connected in main.cpp (last bullet above, "option 4" in the code)

2. Testing

• [0.5 points] Show sample mazes generated by YOUR solutions to options 2, 3, and 4 for the 5 x 5 default option and something larger, like 8 x 16. You do not need to show intermediate versions of the mazes as they are generated--just the final version.
• [0.5 points] Generate (but don't show) a 100 x 100 maze 10 times using option 4, WITH and WITHOUT smart union. What is the min, max, and average height of the one remaining equivalence class tree over those 10 runs (again, with and without smart union)? NOTE: height is not the same as size! You will need to write your own function to compute the height of your final tree

3. Submission

• Make a PDF file <Your Name>_Lab8_README.pdf with your output mazes (clearly labeling which option gave rise to which) and answers to the height questions above
• Rename your code directory <Your Last Name>_Lab8 and create a single tar/zip/rar file out of it named <Your Last Name>_Lab8.tar (or .zip or .rar, etc.).
• Submit it in Canvas by midnight at the end of Tuesday, November 9