C# Workshop - Project 1: Maze Generator

C# Workshop – Project 1: Maze Generator Note: Project 1 Due Date - Sunday, August 12th at 00:00 Introduction Welcome to Project 1 of the C# Workshop. This project is designed to give you an opportunity to challenge your understanding of both the material we’ve already covered, as well as the material we will be covering over the next two weeks. For those with previous programming experience, this project wont be overly difficult, but it will give you an opportunity to test your understanding of the programming syntax provided in C#. For those with no previous programming experience, this project will be a challenge. Not because it’s technically difficult or overly complex, but because 90% of being an adequate programmer is your ability to solve problems. Being able to logically break a project description down into discrete, manageable components is one of the most valuable skills any programmer can have. Unfortunately, this is not something that can be taught, it’s something that can only be learned with practice and the development of an analytic mind. Topics Covered As the first project is designed to correspond with the first 4 weeks of the workshop, it will test and exercise your understanding of the following topics:

• The System.Console Class
• Strings and Primitive Types
• Expressions, Selection, Iteration, and Arrays
• Classes, Structs, Methods, Fields, and Objects

Background Information As early as 2000 BC Egyptians were recorded creating complex structures referred to as labyrinths, designed to bring awe to those who wandered the corridors, marveling at the architectural genius. Later, these labyrinths were brought outdoors - designed to confuse and trick those unfortunate enough to be caught within their bushy walls. Legends tell of The Minotaur and magnificent treasures hidden in the center of these maze-like prisons. Since the 1970’s and the so-called ‘maze craze’ book writers, television producers, and even game developers have used the mystery and intrigue inherent in mazes to add complex environment and situations to their audience. And as many of those reading this project description are aspiring game programmers, we too will use the concept of a maze to add an exciting element to our final project of the C# Workshop. Before we do though, lets learn a bit more about mazes and their types. First, Mazes come in many different dimensions and tessellations - with many different routing methods. They can either be 2D, 3D (a multi-level 2D Maze), or even weaved together in which case there is a single 2D path which overlaps itself with tunnels and bridges. As for tessellation (the geometry the rooms are made of) there are orthogonal, which is the classic maze with passages intersecting in right angles, Theta Mazes, which consist of connected concentric circles in which the participant is trying to get either to or from the center, and Zeta Mazes, which consists of an Orthogonal maze that also includes 45 degree diagonal paths. More recently we’ve seen the advent of fractal mazes, which are recursive mazes, which themselves may contain multiple other mazes – each of potentially different tessellation. As for routing methods, there are 3 predominant types. The first, and oldest, is the Unicursal. The Unicursal maze has no junction points is simply a single, longish path which winds around depending upon the tessellation type from the beginning to the end of the maze. This is the routing method of the oldest historic labyrinths. The second type of maze is the Braid Maze. This type introduces the presence of choice, but without the existence of dead-ends. All paths lead to every other path within the maze and is created essentially by knocking down strategic walls between passages in a Unicursal maze. The difficulty introduced in a Braid Maze is that while you never encounter a dead-end, you can’t be sure if you’re going forward or backward. The traveler only becomes aware of their mistake when they end up somewhere they’ve already been – and if the maze is so designed, this itself can often be a difficult challenge. The third type of maze is the so-called “Perfect Maze.” In the perfect maze there are no loops or closed circuits, no inaccessible areas, and from a more mathematical perspective, every single room or corridor in the maze has EXACTLY one path to any other point in the maze. As a result, there are nearly infinite starting and ending points. It is as difficult to get from the center of the maze to a single corner as it is to get from one corner to another. Additionally, while the Braid Maze has loops, the Perfect Maze has dead ends. This can be aggravating as the traveler is forced to backtrack and return to a corridor they know they’ve already been to. From a difficulty perspective, however, a well made Braid Maze can easily become more difficult than a Perfect Maze. Feature Requirements / Use Cases For this workshop we will be implementing a console-based 2D, Orthogonal, Perfect Maze – Maze Generator. Phew, that’s a mouth full. This means, as stated above, that we’ll be generating 2D, rectangular grid mazes, which have exactly 1 path from any two points in the maze. Here’s how your program should work… When the user launches the executable they should immediately be shown welcome text. The text can say whatever you like, but in general, “Welcome to The C# Maze Generator Program” is just fine. At the same time, you should set the title of the Console window to say the same. Beneath the welcome message a few lines the program should prompt the user for how large a maze they want. This should be done in two steps. First the program should ask the user how many rows (how tall) they want the maze. Once the user enters a value and presses enter, the program should check to make sure the number entered was between 2 and 50. If the value was NOT between 2 and 50 (inclusive), the program should ignore the value that was input, and repeat the question. Also, if the user enters in a letter, symbol, or something other than a valid number between 2 and 50, repeat the question. If the value WAS between 2 and 50 (inclusive) continue forward by asking the user how many columns (how wide) the user wants the maze to be. As before, validate that the data that was entered was a valid number between 2 and 50 when the user presses enter. With the above done you should now have enough information to generate your random maze. The algorithm for how to do this will be explained in more detail below. Once you’ve generated a random, perfect maze, which matches the user’s specifications, you should display it to the screen. This will require outputting ‘|’ and ‘_’ where vertical and horizontal lines should be. Additionally, before printing the maze to the screen you’re going to want to make sure the Console window’s buffer is large enough to accommodate the desired size maze. You can do this by using methods on the System.Console class. Finally, after displaying the map, you should prompt the user to determine whether or not they would like to display another map. Available answers should be ‘yes’ ‘y’ ‘no’ and ‘n’. Obviously ‘yes’ and ‘y’ should perform the same action, while ‘no’ and ‘n’ also perform the same action. Any other response should let the user know you didn’t understand their response, and then repeat the question. If they answered with either ‘no’ or ‘n’, terminate execution of the application. If they say ‘yes’ or ‘y’, repeat the process outlined above, beginning with asking them to input the numbers of rows and columns they’d like the maze to be. Here’s a simple screenshot which shows the entire process, and a rough idea of what the output should look like. Feel free to use your own text and messages. Knock-Down Algorithm Key Terms First, when talking about an orthogonal maze it’s common to talk about it in terms of Rooms or cells. A room is simply a single grid element in an MxN grid. If I had a 10x10 maze, for example, I’m speaking of a maze which logically has 100 rooms, which are numbered from 0 to 99, with 0 being the top left, and 99 being the bottom right room. As you might have imagined, each room in the maze is separated by Walls. Technically, a room can be surrounded by 2 to 4 walls. The reason some rooms have 2 or 3 walls, is because, in general, we don’t consider the outer edge as being walls. That’s simply the outer edge. So if I take the room in the bottom left hand corner, for example, I’m speaking of a room that has two interior walls. One horizontal one above it, and one vertical one next to it. Now, the thing that makes a Perfect Maze truly unique is that every room in the maze is connected to every other room in the maze by exactly 1 path. But how do I guarantee that? The answer is surprisingly simple. Before I tear down a wall, and make a new path between two rooms, I simply determine whether or not the two rooms already have a path between them. “Hold up, hold up…you mean I have to write a path finding algorithm?!? “ Uhh, no. Well, sorta…but it’s not as tricky as it sounds. Here, I’ll explain. Knock-Down Algorithm Description Lets assume for a moment that we’ve got a 3x3 maze (draw it out on paper if it helps), in which all 12 interior walls are “Up”. This means that no rooms are connected to any other rooms. So how many sets of rooms do we have? Your first response might be 0, but the truth of the matter is that we have 9 (3x3) sets of rooms, which happen to only contain 1 room each. Now, lets assume I were to start in the top left corner (room 0) and knock down the vertical wall leading to the room to the right of it (room 1). Now how many sets of rooms do I have? Well, there are really two possible answers to this. The first possible answer is 8. You see, by breaking down the wall between rooms 0 and 1, I now have a single set of rooms which contains 2 rooms, and I have 7 sets of rooms which still contain 1 room each. Another possible answer, however, is 9. By combining the two rooms into a single set, I’ve not really reduced the numbers of sets, I’ve merely reduced the number of ROOMS in each set. Specifically, Room Set 0 now contains 2 rooms, while Room Set 1, contains 0 rooms. Moving on. Now lets break down some more walls. Lets break down the wall between room 1 and room 2. This is again the vertical wall to the right of room 1 and when I do, I now have 3 rooms which are in the same set of adjacent rooms. That is room 0, 1, and 2 are all connected, and there are no more vertical walls in the top row. How many sets do I have? Yup, you guessed it, I still have 9 Room Sets. How many rooms are in each set? Set 0 has 3 rooms, and Set 1 and 2 both have 0 rooms. Sets 3 through 9 all have 1 room in them. Still with me? Good. Moving on. Now we’re going to knock down two more walls very quickly in order to advance the explanation. Lets knock down the horizontal wall that separates room 2 from room 5. I call this a “floor” wall because it looks like it’s the floor of room 2. After doing that we’re going to tear down the vertical wall between room 4 and 5. At this point, you should have a maze which looks sort of like a snake, moving back upon itself. Here’s where we get to the fun part. Rooms 0, 1, 2, 5, and 4….have all been connected by ‘knocking down walls’. And each time we knocked down a wall we took the new room we just discovered and we added it the set of the previous room. But what happens if we go to knock down a wall and the room on the other side is ALREADY in that set? Continuing with our example lets say we now decide we’re going to attempt to knock down the wall between rooms 1 and 4. That’s the horizontal floor wall beneath room 1. Before we knock it down, lets check real quick what set each room is in. Room 1 is in set 0 and room 4 is ALSO in set 0. Now what do we do? Nothing. Both rooms being in the same set is an indication that somehow, somewhere, there is already a path between these two rooms. And since knocking this wall down would create two paths between these rooms…we cannot knock it down. Tada! By simply accumulating all of the rooms you explore into the same sets, you make it impossible for two rooms to ever have multiple paths between them. Knock-Down Algorithm Walkthrough Now that we know we can prevent rooms from having multiple paths between them, lets go through a complete working example. Again, as a 3x3. This time, rather than jumping from room to room as we did, lets process the walls sequentially. Imagine as we did before that the rooms are numbered from left to right, top to bottom. Beginning with room 0 in the top left, and room 8 in the bottom right. Now also assume that the WALLS are numbered from 0 to 11. Wall 0 is in the top left, and separates rooms 0 and 1. Wall 1 is between room 1 and 2. Wall 2 is between room 0 and 3. Get where I’m going with this. The walls are numbered horizontally from left to right, top to bottom just like the rooms are. So going through a complete knock-down algorithm run we get the following… Initial State Rooms: { 0, 1, 2, 3, 4, 5, 6, 7, 8 } Walls Up: { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 } RoomSets: { {0}, {1}, {2}, {3}, {4}, {5}, {6}, {7}, {8} } Step 1: Knock down Wall 0 This combines room 0 and 1 into the same set Walls Up: { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 } RoomSets: { {0, 1}, {}, {2}, {3}, {4}, {5}, {6}, {7}, {8} } Step 2: Knock down Wall 1 This combines room 1 and 2, but since 1 is in the same set as 0, they all get combined Walls Up: { 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 } RoomSets: { {0, 1, 2}, {}, {}, {3}, {4}, {5}, {6}, {7}, {8} } Step 3: Knock down Wall 2 This combines room 0 and 3 Walls Up: { 3, 4, 5, 6, 7, 8, 9, 10, 11 } RoomSets: { {0, 1, 2, 3}, {}, {}, {}, {4}, {5}, {6}, {7}, {8} } Step 4: Knock down Wall 3 This combines room 1 and 4 Walls Up: { 4, 5, 6, 7, 8, 9, 10, 11 } RoomSets: { {0, 1, 2, 3, 4}, {}, {}, {}, {}, {5}, {6}, {7}, {8} } Step 5: Knock down Wall 4 This combines room 2 and 5 Walls Up: { 5, 6, 7, 8, 9, 10, 11 } RoomSets: { {0, 1, 2, 3, 4, 5}, {}, {}, {}, {}, {}, {6}, {7}, {8} } Step 6: TRY and knock down Wall 5 This would combine rooms 3 and 4. However, observe that both rooms 3 and 4 are in the same set already Skip the wall Step 7: TRY and knock down Wall 6 This would combine rooms 4 and 5. However, observe that both rooms 4 and 5 are in the same set already Skip the wall Step 8: Knock down Wall 7 This combines room 3 and 6 Walls Up: { 5, 6, 8, 9, 10, 11 } RoomSets: { {0, 1, 2, 3, 4, 5, 6}, {}, {}, {}, {}, {}, {}, {7}, {8} } Step 9: Knock down Wall 8 This combines room 4 and 7 Walls Up: { 5, 6, 9, 10, 11 } RoomSets: { {0, 1, 2, 3, 4, 5, 6, 7}, {}, {}, {}, {}, {}, {}, {}, {8} } Step 10: Knock down Wall 9 This combines room 5 and 8 Walls Up: { 5, 6, 10, 11 } RoomSets: { {0, 1, 2, 3, 4, 5, 6, 7, 8}, {}, {}, {}, {}, {}, {}, {}, {} } Step 6: TRY and knock down Wall 10 This would combine rooms 3 and 4. However, observe that both rooms 3 and 4 are in the same set already Skip the wall Step 7: TRY and knock down Wall 11 This would combine rooms 4 and 5. However, observe that both rooms 4 and 5 are in the same set already Skip the wall With the 12 walls evaluated and either knocked down or not, you can see that all rooms are now in the same set, and thus there is a single path between each room, and there are 4 walls still standing – 5, 6, 10, and 11. If you were to draw this out on paper you’d see a map similar to this:

 _____
|     |
| | | |
|_|_|_|

Knock-Down Algorithm Random Permutation Now, if you were paying attention to the algorithm you might have noticed there’s nothing random about it. Every time the algorithm is ran, it would generate the exact same maze as the one given above, for a 3x3 layout. So how do we create random mazes from this? Simple. What happens if we were to knock the walls down in a different order? Remember, whenever we knock down a wall, all we do is stop to determine whether or not the rooms on either side of the wall are in the same set. We don’t care what order the walls are knocked down. So incidentally, if we knock the walls down in a different order, we’d end up with a maze which looked different. To accomplish this, you can permutate the list of walls before beginning the knock-down process. If you do, you’d get a list of walls that might looks something like this: Initial State Rooms: { 0, 1, 2, 3, 4, 5, 6, 7, 8 } Walls Up: { 0, 2, 3, 1, 6, 5, 4, 7, 11, 9, 10, 8 } RoomSets: { {0}, {1}, {2}, {3}, {4}, {5}, {6}, {7}, {8} } Knock-Down Algorithm Outline So as to make it a little bit easier for those people with no previous coding experience, here’s a rough outline of the code you might use to generate a random maze:

ComputeNumberOfRoomsAndWalls
AllocateMemoryForRoomsWallsAndSets
AssignTwoRoomsToEachWall
SetEachWallAsBeingUp
AddEachRoomToADefaultSet
RandomlyPermutateAllWalls
IterateThroughEachWall
    If(RoomsAreInSameSet) continue
    Else 
        KnockDownWall
        AddRoomsToSameSet
CreateMaze
ReturnMaze

Conclusion Well, here were are the conclusion of the project description for Project 1. Hopefully by the end of this you’ve determined exactly what requirements are expected of you, and code you should use to generate a randomly created, perfect Maze. Feel free to use the Project 1 forum to post your questions regarding design and implementation of Project 1. I request you not actually submit you entire source code until after the project 1 due date. Though feel free to ask for help about sections you’re having a problem with. Finally, I will try and provide hints every few days for the next week and a half or so, to help people keep moving. Feel free to use or not use my advice or hints, as they just provide insight into A WAY to implement this project, not necessarily THE WAY. Cheers!