ICS 46 Spring 2017
Project #1: Dark at the End of the Tunnel

Due date and time: Monday, April 24, 11:59pm


Introduction

As a very young kid, I found myself fascinated by mazes. Whenever I saw a maze printed on a piece of paper, I was compelled to grab it and try to solve it. I recall having soft-covered books full of them and, when those weren't satisfying enough, I even tried drawing my own, though with the undeveloped skills I had at the time — both in terms of being able to design a challenging maze, and also the more fundamental skill of being able to draw a straight line — it proved to be a difficult proposition.

While time marched on and I became less enamored with mazes as I got older, I became more interested in computer science, which provided a fresh impetus to consider mazes again; in particular, I considered how software could generate a challenging maze and also figure out automatically how to solve one. As I learned more about computer science, the solutions became evident, and I eventually found it an interesting problem for my students to solve. It's funny how things come full-circle sometimes.

This project asks you to implement one or more classes in C++ that are capable of generating two-dimensional mazes of arbitrary size, along with one or more classes in C++ that are capable of solving them. The goal is to provide you with more practice and a fuller understanding of how to use recursion to solve real problems, as at least one of your generators and at least one of your solvers is required to use a recursive depth-first algorithm. It will also provide you with an opportunity to make heavy use of pre-existing classes for which you have no source code, and for which only part of it will have value to you; understanding how existing code works and determining what parts of it can be applied to solve your own problems are important real-world programming skills that you'll need to employ as you move from "sanitized" coursework to real-world work, so I'd like to help you to develop those skills here.


Getting started

Before you begin work on this project, there are a couple of chores you'll need to complete on your ICS 46 VM to get it set up to proceed.

Refreshing your ICS 46 VM environment

Even if you previously downloaded your ICS 46 VM, you will probably need to refresh its environment before proceeding with this project. Log into your VM and issue the command ics46 version to see what version of the ICS 46 environment you currently have stored on your VM. Note, in particular, the timestamp; if you see a version with a timestamp older than the one listed below, you'll want to refresh your environment by running the command ics46 refresh to download the latest one before you proceed with this project.

2017-04-09 21:52:16
Project #1 template added 

Creating your project directory on your ICS 46 VM

A project template has been created specifically for this project, containing a similar structure to the basic template you saw in Project #0, but including a fair amount of code (both source code and compiled libraries) that is being provided as a starting point. So you'll absolutely need to use the project1 template for this project, as opposed to the basic one.

Decide on a name for your project directory, then issue the command ics46 start YOUR_CHOSEN_PROJECT_NAME project1 to create your new project directory using the project1 template. (For example, if you wanted to call your project directory proj1, you would issue the command ics46 start proj1 project1 to create it.) Now you're ready to proceed!


The project directory

Change into your project directory and take a look around, to be sure you're aware of what's already available. What you'll find will look a lot like the basic and project0 project templates you've seen previously, and the ultimate result of building everything in your project will be three separate programs you can run with a script called run.

As before, you'll be able to build just one of these programs by passing a parameter to the build script, e.g., ./build gtest, to save yourself the time waiting for all three to build if you only actually want one of them.

More specifically, here's what you'll find in your project directory:


The application

Your work on this project begins with an already-existing, already-working application with a graphical user interface (GUI) that can display a maze and its solution, and can also animate the process of generating and solving a maze. The GUI window looks like this:

ICS 46 Project #1 - Screenshot

The large area with a white background is where a maze and its solution are drawn. Initially, this will be an empty area with a white background; when you generate or a solve a maze, the result will appear within that area. In the example above, both a maze and its solution are displayed.

Along the right-hand side of the window are a set of controls, allowing you to:

Just below the display of the maze and its solution is a line of text that displays various messages. When you first start the program, it says Welcome!. When a maze generator or maze solver finishes, this message will tell you about the result — in particular, whether a generated maze is perfect, and whether a solution is complete and correct — which is a good way to verify that your algorithms are doing what you expect them to do.

Note, also, that you can stop a maze generator or maze solver while it's running by clicking the X at the top-right corner of the window. Normally, that X closes the window, but if a maze generator or maze solver is running, it simply cancels the operation in progress instead.

A brief word of warning

When you start the application on your ICS 46 VM, you may notice an error message like this one in your Terminal window:

QApplication: invalid style override passed, ignoring it

This is something you can safely ignore, since it has no effect on our work here.


The requirements

This project requires you to complete two tasks:

Note that you are not required to write any code in exp or gtest, but you are welcome to write anything you'd like that helps you to isolate issues and test your work.

A quick note about extra credit

While we encourage you to explore as many maze generators and maze solvers as you'd like, be aware that we are not offering extra credit for generators or solvers beyond the one of each that you are required to implement. You can receive a perfect score on this project while implementing only a single maze generator and a single maze solver, and writing additional ones will not improve your score, but they can be a lot of fun to build!


Generating a maze

Each maze generator needs to be written in its own class. So, to write a maze generator, create a new class in the core directory of your project directory, declaring the class in a header file and defining its member functions (and other source code) in a corresponding source file.

The GUI automatically displays all of the maze generators that are compiled into the program, but only if you follow a couple of rules to help the GUI find and create them:

The required algorithm

The required algorithm must generate a perfect maze. Viewing a maze as a two-dimensional matrix of square cells, a perfect maze is one in which any two cells are connected by a single unique path. An important consequence of a maze being perfect is that all cells in a perfect maze are reachable from the starting point by some unique path, meaning that perfect mazes are guaranteed to have a solution. They're also guaranteed to have a unique solution, which makes them more interesting to solve.

To generate a perfect maze, you'll use a recursive algorithm to "dig tunnels" of various lengths. It starts with a maze in which all of the possible walls exist (i.e., a wall exists on every side of every cell), then continues removing walls until a perfect maze has been constructed. Naturally, it requires some care not to remove walls that would cause the maze to be imperfect; in our tunnel-digging algorithm, we have to be sure we stop digging before we knock out walls that would lead to places we've already been.

The algorithm works, then, by starting at a particular cell (and it doesn't matter, ultimately, which cell you start from), and does the following:

As you generate your maze, you'll need to call member functions on the Maze object that was provided as a parameter. Don't assume anything in particular about that Maze object, other than it has the correct width and height; make any changes you need to make in order to achieve the correct result, and make sure it works regardless of what walls are in place (or not in place) when your algorithm is called.

The animation in the GUI is automatic; if animation is selected in the GUI, any change you make to your maze will result in the GUI window being redrawn, so you won't need to do anything special to accommodate that feature. (Among other things, this will help you to visualize your own algorithm's progress, which might help you to determine whether it's correct, and also to debug it.)

You can write as many other maze generators as you'd like, by following the same steps (i.e., creating a separate class that derives from MazeGenerator, registering it with the DynamicFactory, giving it a display name, etc.). All of the maze generators you write should show up in the GUI if you set them up right.

Naming your required maze generator so we can find it

Each of your maze generators has a display name, given as a string literal as the third parameter in the call to the ICS46_DYNAMIC_FACTORY_REGISTER macro. So we know which one of your maze generators is the required one (and, thus, the one we should grade), you must choose a display name for your required maze generator that has the parenthesized word (Required) on the end of it (similar to how the provided generators have the parenthesized word (Provided) on the end of their names); capitalization and the parentheses are important here.

Otherwise, you can name your required generator anything you'd like, and you can name any other generators in any way you'd like, except they should not have the word (Required) on the end of them. And, of course, none of your generators should have the word (Provided) on the end of their names, since none of yours were provided to you by us.


Solving a maze

Each maze solver needs to be written in its own class. So, to write a maze solver, create a new class in the core directory of your project directory, declaring the class in a header file and defining its member functions (and other source code) in a corresponding source file.

The GUI automatically displays all of the maze solvers that are compiled into the program, but only if you follow similar rules to those you followed for your generators:

The required algorithm

The required algorithm must solve the maze using a recursive algorithm with backtracking. A backtracking algorithm is one that recursively investigates all of the possibilities by moving down a path that hopefully leads to a solution and then, if that path fails, backing up to the nearest place where some untried alternative is available and trying another path. While you could potentially implement an algorithm like this iteratively, it turns out to be a lot less work to do so recursively, as the process of recursion will naturally and automatically manage details that you would otherwise have to manage yourself.

I'll leave the details of this algorithm as an exercise for you to figure out. If you understand the maze-generating algorithm above, it should not be a big step to design the maze-solving algorithm.

As your algorithm seeks a solution, you'll need to call member functions on the Maze and MazeSolution objects that were provided as parameters, though note that the Maze has been passed as a constant (because you shouldn't have to change a maze in order to solve it).

The animation in the GUI is automatic; if animation is selected in the GUI, any change you make to your maze solution will result in the GUI window being redrawn, so you won't need to do anything special to accommodate that feature. (Among other things, this will help you to visualize your own algorithm's progress, which might help you to determine whether it's correct, and also to debug it.)

You can write as many other maze solvers as you'd like, by following the same steps (i.e., creating a separate class that derives from MazeSolver, registering it with the DynamicFactory, giving it a display name, etc.). All of the maze solvers you write should show up in the GUI if you set them up right.

Naming your required maze solver so we can find it

Each of your maze generators has a display name, given as a string literal as the third parameter in the call to the ICS46_DYNAMIC_FACTORY_REGISTER macro. So we know which one of your maze solvers is the required one, you must choose a display name for your required maze solver that has the parenthesized word (Required) on the end of it (similar to how the provided solvers have the parenthesized word (Provided) on the end of their names); capitalization and the parentheses are important here.

Otherwise, you can name your required solver anything you'd like, and you can name any other solvers in any way you'd like, except they should not have the word (Required) on the end of them. And, of course, none of your solvers should have the word (Provided) on the end of their names, since none of yours were provided to you by us.


Deliverables

After using the gather script in your project directory to gather up your C++ source and header files into a single project1.tar.gz file (as you did in Project #0, submit that file (and only that file) to Checkmate. Refer back to Project #0 if you need instructions on how to do that.

Follow this link for a discussion of how to submit your project via Checkmate. Be aware that I'll be holding you to all of the rules specified in that document, including the one that says that you're reponsible for submitting the version of the project that you want graded. We won't regrade a project simply because you submitted the wrong version accidentally. (It's not a bad idea to look at the contents of your tarball before submitting it; see Project #0 for instructions on how to do that.)

Can I submit after the deadline?

Yes, it is possible, subject to the late work policy for this course, which is described in the section titled Late work at this link.