Maze Representation and Code Review

ASCII Art Maze Representation

Although it's nicest to view mazes graphically, like this,

Maze

people have long represented mazes using ASCII art, like this (try clicking either one for the solution):

# #############################################################################
# #   # #   #       #         #     #           # #     #     #     #     #   #
# # # # ### ####### ######### # # # ### ####### # ### ### ### # ### # ### # # #
# # # # # #   #   # #         # # #   # #     # #           # #   # #   #   # #
# # # # # ### ### # # ####### ##### # # # ######### ##### # # # # # # # ##### #
#   #       #   #   # #     #     # # # #   #     # #   # # # # # #   # #   # #
# ######### # # # # # # ### ##### ### # ### # ### ### # # # # ### ##### # # # #
#     # #   # #   # #   #   #   #     #   #   #   #   #   # #   #     # # # # #
# ### # # ##### ### ### # ### # ####### # ### # ### # ##### ### ##### # ### ###
# #   #         # #   # # # # #         # # # #     #   # # # #       #   #   #
# # ####### ##### ### ### # # # ##### ##### # ### ####### # # ####### ####### #
# #     #   #   #   #     #   #   #   #     #   #       #   #     # #         #
# ### # ####### # # ##### ####### ##### ####### ### ### ##### # ### ###########
# #   #         # #   # #       # # #   #     # #   #   #   # # #             #
# ####### # # ### ### # ####### # # # # # ##### ####### # # ### # ##### ##### #
#   # #   # #       #     #     # #   #   #     #     #   #     #     #   #   #
# # # ##### ####### ####### ##### # # ##### # ### ### ################### #####
# # # #   # #   # #     #       #   #       # #     # #   #     #       #     #
# ### ### ### # # ### ####### ### # ######### # # # # # # # ### # ##### # ### #
#     #   #   # #     # #     #   #   #     #   # # #   #     #   #   # #   # #
### ### # # # # ### ### # ##### ##### # ### ####### ######### ##### ### ##### #
#   #   #   # #         #       #       #       #       #     #               #
############################################################################# #

#o#############################################################################
#o#ooo#.#...#.......#.........#.....#...........#.#.....#.....#.....#.....#...#
#o#o#o#.###.#######.#########.#.#.#.###.#######.#.###.###.###.#.###.#.###.#.#.#
#o#o#o#.#.#...#...#.#.........#.#.#...#.#.....#.#...........#.#...#.#...#...#.#
#o#o#o#.#.###.###.#.#.#######.#####.#.#.#.#########.#####.#.#.#.#.#.#.#.#####.#
#ooo#ooooooo#...#ooo#.#.....#.....#.#.#.#...#.....#.#...#.#.#.#.#.#...#.#...#.#
# #########o#.#.#o#o#.#.###.#####.###.#.###.#.###.###.#.#.#.#.###.#####.#.#.#.#
#     #.#ooo#.#ooo#o#...#...#...#.....#...#...#...#...#...#.#...#.....#.#.#.#.#
# ### #.#o#####o###o###.#.###.#.#######.#.###.#.###.#.#####.###.#####.#.###.###
# #   #..ooooooo# #ooo#.#.#.#.#.........#.#.#.#.....#...#.#.#.#.......#...#...#
# # ####### ##### ###o###.#.#.#.#####.#####.#.###.#######.#.#.#######.#######.#
# #     #   #   #   #ooooo#...#...#...#.....#...#.......#...#.....#.#.........#
# ### # ####### # # #####o#######.#####.#######.###.###.#####.#.###.###########
# #   #         # #   # #ooooooo#.#.#...#.....#.#...#...#...#.#.#.............#
# ####### # # ### ### # #######o#.#.#.#.#.#####.#######.#.#.###.#.#####.#####.#
#   # #   # #       #     #ooooo#.#ooo#...#ooo..#ooooo#...#.....#.....#...#...#
# # # ##### ####### #######o#####.#o#o#####o#o###o###o###################.#####
# # # #   # #   # #     #..ooo..#ooo#ooooooo#o#ooo  #o#ooo#ooooo#ooooooo#.....#
# ### ### ### # # ### #######o###o# #########o#o# # #o#o#o#o###o#o#####o#.###.#
#     #   #   # #     # #ooooo#ooo#   #     #ooo# # #ooo#ooo  #ooo#...#o#...#.#
### ### # # # # ### ### #o#####o##### # ### ####### ######### #####.###o#####.#
#   #   #   # #         #ooooooo#       #       #       #     #........ooooooo#
#############################################################################o#

That really is the same maze as the image above. It looks a bit taller because text characters aren't square! It will look even more stretched in your terminal.

This representation uses the following characters:


`#`	hash	Represents a wall.
	space	The path you can walk on; the gaps in the outer walls are the entrance and exit.
`.`	period	Somewhere we've been (a breadcrumb).
`o`	letter “o”	Indicates a place in the maze we consider “interesting” for some reason (e.g., to mark the solution path).

This representation maps naturally to being represented inside the computer, and that's exactly what our Maze class does.

Overview of the `Maze` Class

The Maze class is responsible for representing a maze and tracking its state as we explore it. Note that this class doesn't solve mazes—it just represents them, displays them, and provides the tools other code will need to find solutions.

So it's like a data structure for mazes?
Exactly! It stores the maze layout and provides operations to query and modify it.
Hay! I noticed it has a Display member. Is that the same Display class from the ASCIImation homework?
Good eye! Yes, it's essentially the same class, but now with color support and a status line at the bottom.

What the `Maze` Class Stores

At its core, the Maze class stores

The maze grid — A std::string that represents the 2D maze as a sequence of characters.
Start and end positions — Where you enter and exit the maze.
Dimensions — The width and height of the maze.
Display pointer (optional) — For showing the maze visually as algorithms run.

The maze uses four different character states for cells (the exact same ones we use in the ASCII art above), but defines handy symbolic names for them in the code:


`#`	`Maze::WALL`	Impassable walls.
	`Maze::PATH`	Open paths you can traverse.
`.`	`Maze::VISITED`	Breadcrumbs showing where you've been.
`o`	`Maze::ACTIVE`	Special markers (often for the solution path)

Why store the 2-D maze as a single giant string rather than an array of strings (one for each maze line) to capture the 2-D structure more directly?
Great question! In many ways, we're doing things the same way we did in the ASCIImation homework. For a cell at position (x, y), its index in the string is y * width_ + x. The std::string class is familiar, as we've used it in previous assignments, but it's also flexible because it allows strings of arbitrary length, which is useful for mazes of different sizes.
In this assignment, we're going to create our own data structure that can handle arbitrary sizes, but that data structure will be to hold maze coordinates, not the maze itself. We didn't want to make you write two data structures from scratch in one assignment, so using std::string was a bit of a cheat to keep things manageable.

Your Task, Part 1: Explore the Public Interface

Before we start using the Maze class, let's understand what it can do. Read through maze.hpp and pay attention to:

Core Functionality

Constructors: The class provides two ways to create a maze (we'll use the file-loading one):
- File-loading constructor — Maze(filename)
- Dimensional constructor — Maze(width, height)
- Question: Is there a default constructor?
Loading and Printing:
- load(istream&) — Reads a maze from any input stream
- print(ostream&) — Outputs the maze in ASCII format
Maze Information:
- width() and height() — Get maze dimensions
- getStart() and getEnd() — Retrieve start and end coordinates
- isValid(x, y) — Check if coordinates are within the maze
State Management:
- hasState(x, y, state) — Checks if a cell is in a particular state
- setState(x, y, state) — Changes a cell's state
- reset() — Clears all VISITED and ACTIVE markers back to PATH
- clear() — Resets to an “empty” maze with a pattern of walls and pillars

Looking at the header file, you'll also find that there are overloaded versions of some functions that take a Coord instead of separate x and y parameters. This is just a convenience to make code cleaner when you already have a Coord instance.

I'm thinking about that clear function. What's the deal with the walls-and-pillars pattern?
It can be useful in testing as it gives a maze with numerous routes to the exit. It's also useful in maze generation, but in this assignment (except for the optional part at the end) we're loading pregenerated mazes from files rather than creating them from scratch. So you won't be using clear.

Coordinate System

The maze uses a standard 2-D coordinate system where

x represents the column (0 to width - 1)
y represents the row (0 to height - 1)
(0, 0) is the top-left corner

The Coord type (defined in coord.hpp) packages these x and y pairs together, similar to how BoundingBox packaged position and size in the previous homework. Conveniently, Coord has public x and y members, so you can access them directly. Coord values can also be printed with << to an output stream, compared with == and !=, and turned into strings with to_string().

Display Integration

One exciting feature is the ability to watch maze algorithms in action!

enableDisplay() — Turns on visual display
disableDisplay() — Turns it off
showStatusText(message, pause_ms) — Shows messages on the status line
setPause(pause_ms) — Controls animation speed

When display is enabled, every call to setState() automatically updates the screen, letting you watch breadcrumbs appear and paths light up in real time!

Ooh! So we can see the maze being solved step by step?
Exactly! It's like having a debugger that's also entertaining to watch.
Meh. What if I don't want to wait for the animation?
Just don't call enableDisplay() and the maze will run at full speed, only showing the final result.

A Quick Test Drive

Open up a terminal in the maze directory of the starter code. Run make.

Everything should compile without errors. Now let's try to solve the maze in mazes/maze-51x11.txt that looks like

# #################################################
#               #       #   #       #     #       #
# ### # ##### ######### # # # ##### ### # # ##### #
#   # #   #     #       # # # #   #     #   # #   #
# # ####### ### # ####### # ### ####### # ### # ###
# # # #     # # # #   #   #       #     # #   #   #
# # # ### ### # # # ### ######### # # ####### ### #
# #     #   # # # #         # # #   #     #   #   #
### # # ##### # # ### # ##### # ######### # # # ###
#   # #       #       #         #         # #     #
################################################# #

Run

./amaze mazes/maze-51x11.txt

It did something, but it didn't solve the maze, and there was no animation at all.
Well, solving the maze is yet to come, but there is also an issue with the Maze class. It's not quite finished and your job is to finish it.
Oh, no. Does it involve new and delete? Of course it does. It had to, didn't it? I was so happy until this moment.

Your Task, Part 2: Finish the `Maze` Class

One of the really useful things about dynamic memory allocation is that it allows us to say “sometimes there is a thing and sometimes there isn't”. The Display class is awesome, but the instant you create one, it takes over your terminal window. That's not always what you want, especially when you're debugging. We want to be able to control when we have a Display object and when we don't, which we can do by allocating the Display object on the heap when we need it, and deallocating it when we don't. So when we don't need it, we don't have a Display object at all.

The Display class already has a data member called displayPtr_.

When there isn't a Display object, displayPtr_ is a nullptr (i.e., doesn't point to anything).
When there is a Display object, displayPtr_ points to it.

If you look at enableDisplay() and disableDisplay(), you'll find TODO comments where you need to add code to allocate and deallocate the Display object.

So, in short, you need to…

Implement `enableDisplay()` and `disableDisplay()`

In enableDisplay(), if displayPtr_ is nullptr, allocate a new Display object on the heap and make displayPtr_ point to it. Remember that the Display constructor needs the width and height of the desired display. Because there can be a status line at the bottom, you might want to add 2 to the height you pass to the Display constructor.
In disableDisplay(), if displayPtr_ is not nullptr, deallocate the Display object and set displayPtr_ back to nullptr.
Look over the destructor for the Maze class. Are we cleaning up properly? If we are, all good, but it's always important to check.

That's it? That wasn't so bad after all.
Yeah, I thought it would be way harder.
Meh. I still think it's a pain.

Try the Code Again

Now that you've implemented enableDisplay() and disableDisplay(), try running the test program again:

make
./amaze mazes/maze-51x11.txt

It still won't do much, but it'll do it with much more panache as the Display object is used to show the maze on the screen as the code tries (weakly) to solve it.

Meh. Why do you like writing code that only half works?
Trying to build everything at once is a recipe for frustration. If you write a lot of code and it doesn't work, it's hard to know where the problem is. If you build things up in small steps, you can test each step as you go, and if something goes wrong, you have a much better idea of where the problem is.
I see. So it's like debugging by construction.
Yeah, I like that idea.
I wouldn't have phrased it quite that way, but, yes, that's the idea.

Helpful Hints

The Grid Storage Pattern

The private grid_ member stores the entire maze as a single string. If your maze is 5×5, then grid_ has 25 characters. The character at position (x, y) lives at index y * width_ + x in the string.

This same pattern appears throughout this course—you saw it in both the Sprite and Asciimation classes. It's a common technique for representing 2-D data in a 1-D container.

Working with `Coord`

The Coord type is a simple struct (defined in coord.hpp) that packages x and y coordinates together. Instead of passing two integers everywhere, you can pass a single Coord:

Coord position{3, 4};  // x=3, y=4
if (maze.hasState(position.x, position.y, Maze::PATH)) {
    // This position is an open path
}

Display Colors

When display is enabled, the maze automatically uses colors to make different states visually distinct:

Walls appear in one color
Visited cells (breadcrumbs) in another
Active cells (solution path) stand out brightly

You don't need to manage colors yourself—just use setState() and the display integration handles the rest.

Is it okay to read over the other functions in maze.cpp?
Absolutely! Most of the code is similar to what you wrote in the ASCIImation homework, so it should look familiar, if a bit simpler overall.
Hay! There's a switch statement in putStateWithColor. I haven't seen one of those before.
A switch statement is like a more structured way to do multiple if/else if checks. It's often cleaner when you're checking the same variable against many different constant values. But it's not essential to understand it for this assignment.

(When logged in, completion status appears here.)

Previous Page Next Page

CS 70

Warning: Missing Prerequisites

Maze Representation and Code Review

ASCII Art Maze Representation

Overview of the `Maze` Class

What the `Maze` Class Stores

Your Task, Part 1: Explore the Public Interface

Core Functionality

Coordinate System

Display Integration

A Quick Test Drive

Your Task, Part 2: Finish the `Maze` Class

Implement `enableDisplay()` and `disableDisplay()`

Try the Code Again

Helpful Hints

The Grid Storage Pattern

Working with `Coord`

Display Colors

To Complete This Part of the Assignment...

Instructor Controls

Warning: Missing Prerequisites

Maze Representation and Code Review

ASCII Art Maze Representation

Overview of the Maze Class

What the Maze Class Stores

Your Task, Part 1: Explore the Public Interface

Core Functionality

Coordinate System

Display Integration

A Quick Test Drive

Your Task, Part 2: Finish the Maze Class

Implement enableDisplay() and disableDisplay()

Try the Code Again

Helpful Hints

The Grid Storage Pattern

Working with Coord

Display Colors

To Complete This Part of the Assignment...

Instructor Controls

Overview of the `Maze` Class

What the `Maze` Class Stores

Your Task, Part 2: Finish the `Maze` Class

Implement `enableDisplay()` and `disableDisplay()`

Working with `Coord`