Lab 9: Labyrinth II: The Bees
Due on Sunday, April 10th at 11:59 PM. This is a team lab. You and your assigned lab partner(s) will complete this lab together. Make sure that you are familiar with the Partner Etiquette guidelines. You may discuss the concepts of this lab with other classmates, but you may not share your code with anyone other than course staff and your lab partner(s). Do not look at solutions written by students other than your team. If your team needs help, please post on the Piazza forum or contact the instructor or ninjas. If you have any doubts about what is okay and what is not, it’s much safer to ask than to risk violating the Academic Integrity Policy.
Overview
For this lab, you will write a min-heap data structure for use as a priority queue. You will then write a labyrinth solver program which uses this priority queue to find the best path through a labyrinth which contains features (such as bees) which may cause a space to be less desirable to use. In the process, you will learn about the vector
class, an array-list-like class from the C++ Standard Template Library.
Starting Code
Your starting code consists of the following files. Files that you will need to change are bolded below.
- Files to define a min-heap and use it as a priority queue.
priority_queue.h
: ThePriorityQueue
interface.array_min_heap.h
/array_min_heap__definitions.h
: TheArrayMinHeap
class. You will need to add some private helper methods to the declaration and then define those methods as well as the public interface methods.
- A simple
Pair
data structure.pair.h
- Files for implementing the labyrinth solver.
feature.h
/feature.cpp
: A couple utility functions pertaining to map features.position.h
/position.cpp
: ThePosition
class.labyrinth2.h
/labyrinth2.cpp
: TheLabyrinth2
class which implements the maze-solving algorithm.
- The main labyrinth-solving program.
labyrinth2_main.h
/labyrinth2_main.cpp
program.cpp
: The file in which the “real”main
function is stored (which we keep separate for testing).
- A program for your tests.
test_utils.h
/test_utils.cpp
tests.cpp
The C++ STL and the vector
Class
The C++ Standard Template Library (STL) is a collection of templated definitions which are useful in developing C++ programs. In this course, we discuss how to create data structures and algorithms which operate over them. The STL is an existing implementation of many of these concepts (and more) and, rather than reinventing the metaphorical wheel, one would typically use these data structures (or others from a similar library) when writing C++ programs.
The vector
class is one of the classes defined by the C++ STL. It provides functionality very similar to that of the ArrayList
class (though it should be noted that it is not circular). For this lab, you should use the vector
class when you need a list; this is mandated by several of the method signatures in the assignment. Here is a brief summary of the differences between using one of our List
data types and the vector
class from the STL:
Operation | List code |
vector code |
---|---|---|
Insert at front | my_list.insert_at_front(value) |
no simple equivalent |
Insert at back | my_list.insert_at_back(value) |
my_vector.push_back(value) |
Determine size | my_list.get_size() |
my_vector.size() |
Get element (method) | my_list.get_item(index) |
my_vector.at(index) |
Get element (operator) | no equivalent | my_vector[index] |
Set element (method) | my_list.set_item(index, value) |
my_vector.at(index) = value |
Set element (operator) | no equivalent | my_vector[index] = value |
Remove from back | my_list.remove_from_back() |
my_vector.pop_back() |
There are several good resources for documentation on the vector
class that can be found with a quick web search. For example, here’s one.
Copying
The vector
variables in this lab contain only vector
objects; they do not contain pointers. Conveniently, the vector
class is implemented such that it may be returned, passed as an argument, or otherwise copied in the same way as basic C++ types (like int
). So you can write
vector<int> a;
a.push_back(4);
vector<int> b = a; // copies the contents of vector a into vector b
a.pop_back();
cout << b[0] << endl; // prints 4; does not crash
Copying vectors like this isn’t a good idea all of the time, of course; it could be quite inefficient depending on how big the list is. For this assignment, however, we copy only very small vectors (e.g. the vector of neighbors). Also, because the vectors can be statically allocated, you’ll have far fewer memory management problems to deal with!
Featured Labyrinths
The provided test data for this assignment includes labyrinth map files which have multiple kinds of non-wall spaces. Each non-wall space is associated with a cost that describes how much work it is to travel through that space.
- Open space (
.
): this is a normal open position in the labyrinth. Cost: 1. - Mud (
_
): this space is covered in mud and difficult to walk through. Cost: 2. - Water (
~
): this space is submerged and requires you to swim. Cost: 4. - Bees (
b
): this space contains bees. They’re grumpy on account of being stuck in a labyrinth. Cost: 10.
As with the previous lab, the code to read these map files has been provided for you. You should familiarize yourself with the Labyrinth2
and Position
classes in this new assignment to see how this information is stored. In particular, the feature.h
file contains the declaration of an enum
type called feature_type
; this creates a new type that can be used in your code. There are only five values of type feature_type
and they are stored in the variables space
, wall
, mud
, and so on.
Your objective isn’t just to find any path through the labyrinth; you must find the one which takes the least effort. This is in contrast to the previous lab, where any valid solution was acceptable.
Dijkstra’s Algorithm
To solve a featured labyrinth, we’ll use a weighted version of the breadth-first search algorithm called Dijkstra’s Algorithm (named after its creator, Edsger Dijkstra). This algorithm is very similar to the generalized searching algorithm we used in the previous labyrinth-solving lab. It is presented below with the differing parts printed in bold:
- Add the start position to your
PriorityQueue
data structure - Mark the start position as having zero cost
- While there are positions left in the data structure:
- Take a position from the data structure; call it the current position.
- If the current position is the exit, then you’re finished!
- Otherwise, for each neighbor of the current position that isn’t a wall:
- Calculate the new cost of the neighbor as the sum of its feature cost and the cost of the current position
- If the current cost of the neighbor is greater than the new cost:
- Set the neighbor’s cost to the newly calculated cost
- Record the current position as previous to the neighbor
- Add the neighbor to the data structure
Just like last time, you can determine whether you found a path by whether you ever visit the bottom right corner of the map. In building your solution vector
, though, note that there’s no easy way to insert at the front of a vector
. (It’s possible, but relies upon concepts we haven’t discussed in class.) Instead, you can just do this:
- Starting from the end, add each position in the solution to the end of the vector (producing a backwards solution)
- Loop over the vector and swap e.g. the first element with the last, the second element with the second-to-last, etc.
You’re not required to use the above approach if you’d prefer to get your solution into the correct order in some other way.
Testing
As usual, you have been provided RUN_MAIN
and CHECK_FILES_EQUAL
. You should write tests in tests.cpp
for your ArrayMinHeap
data structure as well as for your Labyrinth2
class. The labyrinth2_main
function might be a convenient way for you to test Labyrinth2
, as it allows you to use the files in test_data
easily.
Memory
Your program is required to run without any memory leaks or errors; you must free up all of the memory that you allocate and you must only use memory that you have allocated and initialized. We will use valgrind
to determine if you have done this correctly, so you should as well. You should also consider using valgrind
to find bugs in your program as you proceed; it’s one of two very powerful C++ debugging tools that we’ve discussed.
Coding Style Requirements
You are required to observe some good coding practices:
![Well-dressed people (style)](/~zpalmer/cs35/s16/labs/style.png)
-
You should pick meaningful variable names.
// Good int* pixels = new int[size]; // Bad int* p = new int[size];
-
You should use correct and consistent indentation. Lines of code within a block (that is, surrounded by
{
and}
) should be indented four spaces further than the lines surrounding them.// Good if (condition) { cout << "Test" << endl; } // Bad if (condition) { cout << "Test" << endl; }
-
You should use a block whenever possible, even if it’s not necessary. This helps you avoid subtle or messy bugs in the future.
// Good if (condition) { cout << "Something" << endl; } // Bad if (condition) cout << "Something" << endl;
-
Any new methods or fields in your header files should have comments explaining their purpose and behavior. You are permitted to omit documentation for methods that are inherited from other classes; that is, if your class has a
foo
method because its superclass has afoo
method, you don’t need to document that method.// Good public: /** * Saves this image object to a file. * @param file The already-open stream into which this image should be written. * @return The number of pixels in the saved image. * @throws runtime_error If the image could not be saved due to an I/O error. */ int save(ofstream& file); // Bad public: int save(ofstream& file);
Your method/field documentation does not have to be in the format above, but you must describe the method’s behavior, its parameters, its return value, and any exceptions that it may throw. (If you’re indifferent, the above syntax is a good one to know; it’s a de facto standard used by Javadoc, Doxygen, and other tools that automatically process source code comments into other formats like searchable webpages.)
Peer Review
As this is a team assignment, you are required to complete a peer review of your lab partner or partners. You must do this even if everything is fine. You should complete this peer review after you have turned in your assignment. The peer review comes in the form of a simple Google Form and can be accessed here; in most cases, it will likely take less than a minute to complete. If you have trouble accessing this peer review, please make sure that you are logged into Google using your Swarthmore credentials.
Your peer review will be kept private; only course staff will have access to this information. You can also update your peer review after you have submitted it. However, if you do not submit a peer review, you will lose points on your lab. Please don’t forget!
Summary of Requirements
When you are finished, you should have
- A completed implementation of
ArrayMinHeap
- A
Labyrinth2
class which uses Dijkstra’s algorithm - Appropriate tests
- No memory errors!
- Code which conforms to the style requirements above
- A completed peer review