CSC 105: Project 4 – A-maze-ing! 

Due Monday, November 8, 2021 at 9:15am 

Objectives 

• 

To practice with 1D and 2D lists 

• 

To practice with nested for loops 

• 

To understand procedural generation 

Introduction 

Mazes in computer games have been around a long time, whether it's Pac-Man or the latest 

first-person dungeon crawler. Before computers, mazes were all hand-crafted, but one of 

the popular buzzwords in modern gaming is procedural generation: the ability for the 

computer to generate randomized data (like mazes) on its own. You'll practice that in this 

project as you use a two-dimensional list to represent a procedurally-generated maze from 

which the player will try to escape. 

Maze Representation 

We will use a 2D list for our maze, where each cell contains a string showing which cardinal 

directions (i.e. "N", "S", "E", "W" for north, south, east, and west) the player can move. For 

example, if a cell in the list contains "NSW", that means there are exits (passages, doors, 

etc.) leading north, south, and west from this location. So the 3X3 two-dimensional list 

below left corresponds to the maze shown below right. 

col 0 

col 1 

col 2 

row 0 

"E" 

"WS" 

"S" 

row 1 

"S" 

"NE" 

"NWS" 

row 2 

"NE" 

"WE" 

"NW" 

Setup 

Download the starter code from Nexus. You'll be adding to this file for your project. I have 

already written a draw_maze function that will print the maze similar to the picture above 

right if you provide it with a 2D list of open passages like the one above. Try it yourself by 

adding these two lines to main and then running the code: 

maze = [["E","WS","S"], ["S","NE","NWS"], ["NE","WE","NW"]] 

draw_maze(maze) 

Now you're ready to start the project, which is in two parts. First, you'll implement an 

algorithm to do maze generation. Then you will implement a small game where the player 

tries to navigate out of the maze. 

Part 1: Maze Generation 

There are many algorithms for the procedural generation of mazes. The one we're using is 

conceptually easy but still produces aesthetically-pleasing results. Here's the pseudocode: 

col 0 

col 1 

col 2 

row 0 

row 1 

row 21. 

Create a 2D list of appropriate size (see the ROWS/COLS constants in the starter 

code) where every cell contains the empty string. 

2. 

For each cell, create a passage either to the south or east. Rules: 

a. The lower-right cell (i.e. the southeastern most one), is the only cell that will 

remain an empty string. All other cells will contain either "S" or "E". 

b. Cells in the bottom (southern) row and rightmost (eastern) column only have 

one option since you cannot make a passage outside the maze boundaries. 

c. If a cell has either option, choose it randomly. 

3. 

Iterate through the 2D list and "fill in" each string by consulting the neighboring cells to 

the north and west. For example, if after step 2 we have this grid: 

col 0 

col 1 

col 2 

row 0 

"E" 

"S" 

"S" 

row 1 

"S" 

"E" 

"S" 

row 2 

"E" 

"E" 

"" 

then if cell (0,0) has an "E"ast passage, that means that cell (0,1) must have a "W"est 

passage to correspond. Thus, for any given cell (like (0,1)), we can look at its 

western (left) neighbor and, finding "E" there, we can add "W" to the list, giving us: 

col 0 

col 1 

col 2 

row 0 

"E" 

"WS" 

"S" 

row 1 

"S" 

"E" 

"S" 

row 2 

"E" 

"E" 

"" 

Likewise: 

(0,2): west neighbor has no "E"ast passage, so we add nothing 

(1,0): north neighbor has no "S"outh passage, so we add nothing 

(1,1): west neighbor has no "E"ast passage, but north neighbor (0,1) has a 

"S"outh passage, so we add "N" to its string giving: 

col 0 

col 1 

col 2 

row 0 

"E" 

"WS" 

"S" 

row 1 

"S" 

"NE" 

"S" 

row 2 

"E" 

"E" 

"" 

(1,2): north neighbor has "S" and west neighbor has "E" so add "NW" 

(2,0): north neighbor has "S" so add "N" 

(2,1): north neighbor does not have "S" but west neighbor has "E" so add "W" 

(2,2): north neighbor has "S" and west neighbor has "E" so add "NW" 

col 0 

col 1 

col 2 

row 0 "

E" 

"WS" 

"S" 

row 1 

"S" 

"NE" 

"NWS" 

row 2 

"NE" 

"WE" 

"NW" 

This is the final finished list.Part 2: Escape! 

Finally, make a small game where the player starts in the lower-right (southeastern) corner 

of the maze with the goal of getting to the exit in the upper-right, i.e. at (0,0). On each 

iteration of the game loop, the computer should 

• 

print out the coordinates of the player's current location 

• 

print out the available exits (north, south, east, and/or west) 

• 

ask the user for a direction to move 

Use error-checking to make sure you get a valid direction from the user. 

Implement the player using a 1D list containing the player's current location. For example, 

in a 6X6 maze, the player is initialized to [5,5]—the lower-right corner. Then the list can be 

updated with every move, and you'll know the player escapes when it reaches [0,0]. 

Try out the demo on the CS Lab computers to see what I'm expecting. 

Extras! 

There are a lot of ways to enhance this project. Get 1 to 5 points of extra credit (5 points 

max) depending on the difficulty. Ideas: 

• 

additional game mechanics: 

o 

scoring system (based on number of turns to find the exit or number of dead 

ends reached) 

o 

time limit (player has a fixed number of turns to find the exit; scales with 

maze size) 

• 

add items in maze for player to find: 

o treasure chest, weapon, map (the demo already has this one), teleporter 

(sends player to known or random location), lore (descriptive text of the 

room the player is in) 

o inventory system: allow player to pick up and carry items 

• 

encounters: 

o 

monster (lose game if haven't found a weapon) 

o 

riddler (asks player a riddle; sent back to start if not answered correctly) 

o 

mini-game (gambler challenges player to game of hi-lo. Bonus if won within 

a certain number of guesses.) 

o 

fetch quest-giver (tells user to find an object somewhere in maze. Return for 

a reward.) 

Don’t try to implement all of these. You only have a week. 

Turning it in 

Put your name, honor code affirmation, and a list of what extra credit items you 

implemented at the top of your code (as comments). Name your file with your name and 

upload to Nexus. You did make a backup, right?Grading 

This project is worth 50 points. Here’s the breakdown: 

20 points for correct implementation of the maze generator. 

10 points for good separation of tasks into functions. (Did you notice that I didn't tell you 

what functions to write? That's your job. One function for Part 1 and one for Part 2 won't 

get you many points. Break them into smaller tasks.) 

10 points for implementing the maze escape game. 

10 points for good coding style: comments for functions, meaningful function and variable 

names, good readability using whitespace, a blank line to separate function definitions, 

good labels for output and user interaction, constants instead of magic numbers, etc. 

Gentle Reminder 

Programming projects are individual projects. I encourage you to talk to others about the 

general nature of the project and ideas about how to pursue it. However, the technical 

work, the writing, and the inspiration behind these must be substantially your own. You 

must cite anyone else who contributes in any way to the project by adding appropriate 

comments to the code. Similarly, if you include information that you have gleaned from 

other sources, you must cite them as references. Looking at, and/or copying, other people's 

programs or written work is inappropriate, and will be considered an honor code violation.