4/15/2021 CS 225 | mp_mazes
https://courses.engr.illinois.edu/cs225/sp2021/mps/mazes/#videos 1/4
mp_mazes
Maddening Mazes
Extra credit: Apr 19, 23:59 PM
Due: Apr 26, 23:59 PM
Doxygen AMA slides
Goals and Overview
In this MP you will:
Implement the disjoint sets data structure.
Create a program to generate random mazes.
Applying a DFS traversal to a maze structure
Represent a maze and its solution on a PNG.
Checking Out the Code
From your CS 225 git directory, run the following on EWS:
git fetch release
git merge release/mp_mazes -m "Merging initial mp_mazes files"
If you’re on your own machine, you may need to run:
git fetch release
git merge --allow-unrelated-histories release/mp_mazes -m "Merging initial mp_mazes files"
The mp_mazes directory will contain sample output including all 4 possible 2x2 mazes and one 50x50 maze.
We encourage you to test your code by writing your own main.cpp that uses your classes in different ways.
Assignment Requirements
These are strict requirements that apply to both parts of the MP. Failure to follow these requirements may
result in a failing grade on the MP.
You are recommended to add descriptive comments throughout coding the MP. This will assist you
in debugging process.
You must name all files, public functions, public member variables (if any exist), and executables
exactly as we specify in this document.
Your code must produce the exact output that we specify: nothing more, nothing less. Output
includes standard and error output and files such as Images.
Your code must compile on the EWS machines using clang++. Being able to compile on a different
machine is not sufficient.
Your code must be submitted correctly by the due date and time. Late work is not accepted.
Your code must not have any memory errors or leaks for full credit.
Your public function signatures must match ours exactly for full credit. If using different signatures
prevents compilation, you will receive a zero. Tests for const-correctness may be performed
separately from the other tests (if applicable).
Assignment Description
You will be implementing a Disjoint set data structure and then implementing a random maze generator
and solver. The assignment is broken up into the two following parts:
Part 1 — The DisjointSets data structure
Part 2 — The SquareMaze random maze generator and solver.
 Solo MP This MP, as well as all other MPs in CS 225, are to be completed without a partner.
You are welcome to get help on the MP from course staff, via open lab hours, or Piazza!
Goals and Overview
Checking Out the Code
Assignment Requirements
Assignment Description
4/15/2021 CS 225 | mp_mazes
https://courses.engr.illinois.edu/cs225/sp2021/mps/mazes/#videos 2/4
As usual, we recommend implementing, compiling, and testing the functions in Part 1 before starting Part
2. Submission information is provided for each part in the respective sections below.
Part 1: The DisjointSets data structure
The DisjointSets class should be declared and defined in dsets.h and dsets.cpp, respectively. Each
DisjointSets object will represent a family of disjoint sets, where each element has an integer index. It
should be implemented with the optimizations discussed in lecture, as up-trees stored in a single vector of
ints. Specifically, use path compression and union-by-size. Each element of the vector represents a node.
(Note that this means that the elements in our universe are indexed starting at 0.) A nonnegative number
is the index of the parent of the current node; a negative number in a root node is the negative of the set
size.
Note that the default compiler-supplied Big Three will work flawlessly because the only member data is a
vector and this vector should initially be empty.
The addelements function
See the Doxygen for this function.
The find function
See the Doxygen for this function.
The setunion function
See the Doxygen for this function.
The size function
See the Doxygen for this function.
Testing Part 1
The following command can be used to compile the DisjointSets test executable:
make testdsets
The following command can be used to run the test executable:
./testdsets
Provided Catch test cases are available as well by running:
make test
./test
Grading Information — Part 1
The following files are used to grade mp_mazes:
dsets.cpp
dsets.h
All other files including your testing files will not be used for grading.
Extra Credit Submission
For extra credit, you can submit the code you have implemented and tested for part one of mp_mazes. You
must submit your work before the extra credit deadline as listed at the top of this page. See Handing in
Your Code for instructions.
Part 2: The SquareMaze random maze generator and
solver
Part 1: The DisjointSets data
structure
Part 2: The SquareMaze random
maze generator and solver
4/15/2021 CS 225 | mp_mazes
https://courses.engr.illinois.edu/cs225/sp2021/mps/mazes/#videos 3/4
The SquareMaze class should be declared and defined in maze.h and maze.cpp, respectively. Each SquareMaze
object will represent a randomly-generated square maze and its solution. Note that by “square maze” we
mean a maze in which each cell is a square; the maze itself need not be a square. As always, we
recommend reading the whole specification before starting.
Videos
Cycle Prevention / Detection
The makeMaze function
See the Doxygen.
The canTravel function
See the Doxygen.
The setWall function
See the Doxygen.
The solveMaze function
This should be completed using BFS. Do not use DFS since due to the structure of mazes having very long
paths it has been known to fail on some test cases running out of memory. Though these are recursive
algorithms the solution should not implement them recursively.
See the Doxygen.
The drawMaze function
See the Doxygen.
The drawMazeWithSolution function
See the Doxygen.
Testing Part 2
Square Maze Testing
Since your mazes will be randomly generated, we cannot provide you with any sample images to diff
against. However, we have provided you with all four possible 2x2 mazes. If you have your program create
and solve a 2x2 maze, the resulting image (with solution) should match one (and only one) of the provided
images m0.png, m1.png, m2.png, and m3.png. We strongly suggest that you diff against these to make sure
that you have formatted the output image correctly.
We provide some basic code to test the functionality of SquareMaze.
The following command can be used to compile the SquareMaze test executable:
make testsquaremaze
The following command can be used to run the test executable:
./testsquaremaze
You can compare the console output of your program with the expected by comparing it with the file
soln_testsquaremaze.out.
Catch Test Suite
 setWall and canTravel You should triple check that setWall and canTravel function exactly
according to their descriptions. An error in these two functions will not be caught by making your
own mazes but can cost you a majority of the points during grading.
4/15/2021 CS 225 | mp_mazes
https://courses.engr.illinois.edu/cs225/sp2021/mps/mazes/#videos 4/4
Additional unit tests similar to how we will grade your MP are provided for you in tests/test_part2.cpp.
Once you have completed Part 2, you may uncomment the Part 2 tests and re-compile to include Part 2
tests:
// uncomment test_part2.cpp
make test
./test
Runtime Concerns
You should strive for the best possible implementation. This MP can be implemented so that the given
testsquaremaze.cpp runs in less than a quarter of a second on the EWS linux machines. To have a high
probability of finishing within the time constraints of the grading script, make sure you can run the given
testsquaremaze.cpp in under 3 seconds on an unencumbered machine. You can time mp_mazes by running
the command time ./testsquaremaze.
Grading Information — Part 2
We will use canTravel to reconstruct your randomly generated maze in our own maze class, to check
that it’s a tree and to compare your implementation to a correct implementation of this MP. This will
require height*width*2 calls to canTravel. Therefore, it is very important that canTravel works, and
works quickly (constant time). If it doesn’t work, you will lose a lot of points.
We will use setWall to replace your maze with our own, for the purpose of testing all of your other
functions independently of your createMaze.
The following files are used to grade mp_mazes:
dsets.cpp
dsets.h
maze.cpp
maze.h
All other files will not be used for grading.
 setWall and canTravel You should triple check that setWall and canTravel function exactly
according to spec, as an error in these functions will not be caught by making your own mazes but
can cost you a majority of the points during grading.

欢迎咨询51作业君