# Homework 4: Maze Generation

Due: 2019-11-17 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

The coding style requirement is identical to the Coding style section of Homework 2.

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.

## 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 wall’s, 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.