Homework 4: Maze Generation

Due: 2020-04-12 at 23:59

Preliminaries

First, find a partner. You’re allowed to work by yourself, but I highly recommend working with a partner. Click on the assignment link. One partner should create a new team. The second partner should click the link and choose the appropriate team. (Please don’t choose the wrong team, there’s a maximum of two people and if you join the wrong one, you’ll prevent the correct person from joining.)

Once you have accepted the assignment and created/joined a team, you can clone the repository on clyde and begin working. But before you do, read the entire assignment and be sure to check out the expected coding style.

Be sure to ask any questions on Piazza.

Coding style

See homework 2’s coding style.

You should run clang-format on each of the C source and header files you write. This will format all of your files consistently.

Code warnings and errors

Your code must compile without error or warning when compiled with -std=c11 -Wall.

Submission

To submit your homework, you must commit and push to GitHub before the deadline.

Your repository should not contain any programs, object files, or dependency files (the dependency files are the ones ending in .Td or .d.

The README.md should contain

An image link showing the Travis CI build status (see part 0)
The names of both partners (or just your name if you worked alone…but please don’t work alone if you can manage it).
An estimate of the amount of time it took to complete each part.
Any known bugs or incomplete functions.
Any interesting design decisions you’d like to share.

Each of your source files with a main function should contain a comment at the top of the file that contains usage information plus a description of what the program does.

Part 0. Makefile, testing, and Travis CI

Makefile

Unlike previous assignments, this one comes with a full-featured Makefile. If you add additional source files, you should add them to the appropriate _srcs variable. Dependencies should be computed automatically.

The all target should depend on all of the programs you write.

The clean target should delete all of the programs you write and all of the object files.

Testing

The assignment code also comes with a set of unit tests in the tests directory. You can run them by running $ make check.

There are several tests in the tests directory. These consist of the ones I found useful for writing my solutions. You may choose to add to them when testing your own code, although you aren’t required to in this assigment.

As you work through the parts below, run $ make check frequently to make sure that you haven’t broken any code you previously had working.

Travis CI

This homework also uses the Travis CI continuous integration service. Each time you push your code to GitHub, Travis will download the latest version, build your program and then run the tests.

You should be able to see the status of your latest commit by logging in to Travis CI using your GitHub account. You can also see the latest status from Travis by clicking on the 1 branch link near the top of the GitHub page for your repository which has URL https://github.com/systems-programming/${repo_name}/branches. You should see either a green check mark if all tests passed or a red X if one or more tests failed.

You should add a build status image to your README.md by following the instructions to get the Markdown code to paste into README.md.

Overview

In CS 151, you probably had to implement a maze solving function using stacks or queues. In this assignment, you’re going to generate rectangular mazes.

A $m\times n$ maze contains $m$ rows of $n$ columns of rooms. Each room has 0–4 walls: up, down, left, and right. The rooms on the edges of the maze must contain walls along the edge. For example, the room at $(0,0)$ (the top-left corner of the maze) must have the top and left walls. Adjacent rooms must have consistent walls. For example, if the room at $(1,3)$ has walls to the right and down, then the room at $(2,3)$ must have an up wall and the room at $(1,4)$ must have a left wall.

Inside maze.h, there is an enum that defines four values that can be ORed together to specify the possible walls. E.g., WALL_UP | WALL_RIGHT.

Since we’re going to be building the maze, one room at a time, there is an additional value WALL_NOT_SET that represents the fact that the walls have not been set for the room yet.

The first structure you’re going to work with is RoomCoords defined in roomcoords.h. To ease the construction of these, there’s a ROOM(row, col) macro. I found this macro incredibly helpful when writing my solution. There’s a special RoomCoords value UNDEFINED_ROOM_COORDS that is used in several places.

The other main structure is the Maze structure. maze.h declares this as an opaque structure. That is, it doesn’t actually define the structure. You will have to define the structure yourself in maze.c. The idea behind an opaque structure is that all of the code will work with a Maze using the functions defined in maze.h rather than interact with the Maze members directly. The only code that should interact with the Maze members is in maze.c.

As you’re implementing the code, you should not change the function signatures (the names, parameter numbers and types, and return types) for any function declared in a header file. Doing so will break the game code.

Part 1. Basic maze manipulation functions (10 points)

The first task is to define the Maze structure. Each maze will need to keep track of

the number of rows,
the number of columns,
the starting room coordinates,
the ending room coordinates, and
the data representing the rooms themselves.

Start by removing the dummy member from Maze, and add the appropriate members. You’ll need to decide how you want to represent the 2D array of rooms.

One possibility is keeping track of the walls for each room. Thus, if room $(r,c)$ has left and right walls, you’ll want to store WALL_LEFT | WALL_RIGHT. In this case, you’ll need to ensure that $(r,c-1)$ has a right wall, $(r,c+1)$ has a left wall, $(r-1,c)$ doesn’t have a down wall, and $(r+1,c)$ doesn’t have an up wall.

A second possibility is to only keep track of the left and up walls for each room. To determine if room $(r,c)$ has a right wall, you need to check if room $(r,c+1)$ has a left wall (or it’s on the right edge of the maze) and to determine if it has a down wall, you need to check if room $(r+1,c)$ has an up wall (or it’s on the bottom edge of the map). In this way, it’s not possible for the walls to become inconsistent but the logic becomes a little more tricky.

In either case, a single unsigned char is sufficient for each room. This includes keeping track of whether a particular room’s walls have been set.

You’re free to use another representation of your maze. (The nice thing about having an opaque Maze type from the perspective of the rest of the code is that your internal representation doesn’t matter.)

Look at the descriptions of the functions in maze.h, and implement these functions.

Maze *maze_new(size_t rows, size_t cols);
void maze_free(Maze *maze);
size_t maze_get_rows(Maze const *maze);
size_t maze_get_cols(Maze const *maze);
bool maze_in_bounds(Maze const *maze, RoomCoords coords);
RoomCoords maze_get_start(Maze const *maze);
void maze_set_start(Maze *maze, RoomCoords coords);
RoomCoords maze_get_end(Maze const *maze);
void maze_set_end(Maze *maze, RoomCoords coords);

Make sure that when you create a new Maze, you set the members of the maze such that the various maze getter functions return the correct values.

I recommend making liberal use of assert(3) to check for programmer errors.

Run $ make check to make sure that the checks related to those functions pass (but you should expect most of the checks to fail).

Part 2. Getting and setting walls (30 points)

This is probably the trickiest portion of this assignment.

Implement the functions to get and set the walls for a given room.

int maze_get_walls(Maze const *maze, RoomCoords coords);
void maze_set_walls(Maze *maze, RoomCoords coords, int walls);

When setting walls, make sure your maze is consistent as described in Part 0. Furthermore, make sure that setting the walls for one room does not make an adjacent room whose walls haven’t been set lose that property. (I.e., if maze_get_walls(maze, ROOM(r, c)) returns WALL_NOT_SET, then after setting an adjacent room’s walls, maze_get_walls(maze, ROOM(r, c)) should still return WALL_NOT_SET.

Walls for a room may be set multiple times but a room’s walls can never become unset.

Check that all of the tests in tests/test_maze.c pass except for test_first_unset().

Finally, implement

RoomCoords maze_get_first_unset(Maze const *maze);

by using the functions you’ve already implemented. (I.e., there is no real need for this function to be in this file, but it doesn’t obviously belong anywhere else.)

Now when you run $ make check, all of the tests in test_maze should pass.

Part 3. Reading and writing mazes (15 points)

In this part, you’ll implement the functions necessary to read a maze from a FILE * and write a maze to a FILE *.

The structure of the maze file is described in mazeio.h. There is an example in that file and there are more in the mazes directory.

Implement the following functions.

Maze *maze_new_from_stream(FILE *stream);
int maze_write_to_stream(Maze *maze, FILE *stream);

When running $ make check, tests/test_mazeio should pass all tests.

At this point, you should be able to run mazegame. You can pass it the path of a maze (e.g., one of the mazes in mazes) to play that maze. (It’s possible this code is buggy, it’s much harder to test than the rest of the assignment. If you happen to get it to crash, let me know!)

You can also have it solve a maze by giving it the -s option.

Part 4. Random walk (30 points)

The procedure you’re going to use to generate a random maze sounds complicated, but it’s actually pretty straight forward using random walks.

A random walk is a sequence of room coordinates such that each room is adjacent to the room before it and the room after it in the sequence. For example, each room in this sequence $(2,2)$ , $(2,3)$ , $(1,3)$ , $(2,3)$ , $(3,3)$ , $(3,4)$ , $(2,4)$ , $(2,3)$ , $(1,3)$ , $(1,2)$ is adjacent to the rooms before and after it in the sequence. Notice that several rooms are repeated in the sequence. That’s okay.

You’re going to create a random walk starting from a room whose walls have not been set. Each step of the random walk will move to the room above, below, left, or right of the current room, each with equal probability. Any step that would take the walk out side of the bounds of the maze’s grid is simply ignored and a new direction is chosen at random. The walk stops once it encounters a room in the maze whose walls have been set. Thus, if the above sequence of rooms were the outcome of a random walk, then room $(1,2)$ would have the walls set but none of the others would. See randomwalk.h for the specifics.

The next step is to erase the loops in the random walk. This gives you a loop-erased random walk. The procedure for doing this is described in randomwalk.h.

Finally, you’re going to add the loop-erased random walk to the maze, constructing a new corridor in the maze where the start is a dead end and the end is where it connects with the rest of the maze. See randomwalk.h for details and tests/test_walk.c’s test_add_path() function for an illustration of adding four paths to a maze.

Implement the three random walk functions.

RoomCoords *random_walk(Maze const *maze, RoomCoords start, size_t *walk_size);
size_t erase_loops(size_t size, RoomCoords walk[size]);
void add_path_to_maze(Maze *maze, size_t size, RoomCoords const walk[size]);

At this point, all of the tests in tests/test_walk should pass.

Part 5. Generating a maze (15 points)

The final step of maze generation is to put everything together and actually generate some mazes. The complete algorithm is described in generate.c, so take a look and implement the function.

Maze *generate_maze(size_t rows, size_t cols, RoomCoords start, RoomCoords end);

After this, tests/test_generate should pass.

At this point, mazegen should be usable to generate some mazes. Run $ mazegen -h to see how to use it.