MP 7 Mazes
- Monday, April 23 at 11:59 PM 4/23 @ 11:59 PM
- Monday, April 30 at 11:59 PM 4/30 @ 11:59 PM
MP7 is a partner MP!
- Part 1 and Part 2 of this MP can be completed with a partner!
- The creative “Part 3” must be completed by yourself and must be unique (and different from your partner’s work).
You should denote who you work with in the PARTNERS.txt file in mp7. If you worked alone, include only your NetID in PARTNERS.txt.
Goals and Overview
In this MP you will:
- Implement the disjoint sets data structure.
- Create a program to generate random mazes.
- Understand graphs, graph distances, and graph traversal.
- 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/mp7 -m "Merging initial mp7 files"
If you’re on your own machine, you may need to run:
git fetch release
git merge --allow-unrelated-histories release/mp7 -m "Merging initial mp7 files"
The mp7
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 required to comment the MP as per the commenting standard described by the Coding Style Policy.
- 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. ASAN tests will be performed separately from the functionality tests.
- 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:
As usual, we recommend implementing, compiling, and testing the functions in MP 7.1 before starting MP 7.2. Submission information is provided for each part in the respective sections below.
MP 7.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 int
s. 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<int>
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 MP 7.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 — MP 7.1
The following files are used to grade MP7:
dsets.cpp
dsets.h
All other files including your testing files will not be used for grading.
MP 7.2: The SquareMaze
random maze generator and solver
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.
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.
Videos
The makeMaze
function
See the Doxygen.
The canTravel
function
See the Doxygen.
The setWall
function
See the Doxygen.
The solveMaze
function
See the Doxygen.
The drawMaze
function
See the Doxygen.
The drawMazeWithSolution
function
See the Doxygen.
Testing MP 7.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
.
MP 7.3: A Final Creative Component
This creative part of the MP must be completed individually and must be significantly different from your partner’s creative work.
Similar to Part 2 of this MP, we are leaving the design of the creative component completely up to you!
Use main.cpp
to generate a file, creative.png
, that contains a creative maze. The only requirement is that this maze must not be a square maze similar to Part 2. For example, what if your maze was a circle? Or in the shape of a block I? What if you maze made us of ideas from MP1, MP2, MP4, or MP5? Be creative. Have fun.
As you complete Part 3, ensure that your Part 2 still continues to function as described. This means you may need to add a drawCreativeMaze()
function instead of modifying your drawMazeWithSolution()
or other function. You should find many of your existing helper functions still useful.
You just made an amazing maze, awesome work! Feel free to share it with the world!
If you use #cs225 on a public post on a Facebook, Twitter, LinkedIn on Instagram we'll make sure to or the post!
Catch Test Suite
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 MP7 by running the command time ./testsquaremaze
.
Grading Information — MP 7.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 requireheight*width*2
calls tocanTravel
. Therefore, it is very important thatcanTravel
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 yourcreateMaze
.
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.
The following files are used to grade MP7:
dsets.cpp
dsets.h
maze.cpp
maze.h
main.cpp
, for Part 3 only
All other files will not be used for grading.