    C# Workshop - Project 1: Maze Generator
C# Workshop – Project 1: Maze GeneratorNote: Project 1 Due Date - Sunday, August 12th at 00:00Introduction 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 CoveredAs 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 ClassStrings and Primitive Types Expressions, Selection, Iteration, and ArraysClasses, Structs, Methods, Fields, and ObjectsBackground InformationAs 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 CasesFor 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 TermsFirst, 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 DescriptionLets 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 WalkthroughNow 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 StateRooms: { 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 0This combines room 0 and 1 into the same setWalls 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 1This combines room 1 and 2, but since 1 is in the same set as 0, they all get combinedWalls 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 2This combines room 0 and 3Walls 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 3This combines room 1 and 4Walls Up: { 4, 5, 6, 7, 8, 9, 10, 11 }RoomSets: { {0, 1, 2, 3, 4}, {}, {}, {}, {}, {5}, {6}, {7}, {8} }Step 5: Knock down Wall 4This combines room 2 and 5Walls 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 5This would combine rooms 3 and 4.  However, observe that both rooms 3 and 4 are in the same set alreadySkip the wallStep 7: TRY and knock down Wall 6This would combine rooms 4 and 5.  However, observe that both rooms 4 and 5 are in the same set alreadySkip the wallStep 8: Knock down Wall 7This combines room 3 and 6Walls Up: { 5, 6, 8, 9, 10, 11 }RoomSets: { {0, 1, 2, 3, 4, 5, 6}, {}, {}, {}, {}, {}, {}, {7}, {8} }Step 9: Knock down Wall 8This combines room 4 and 7Walls Up: { 5, 6, 9, 10, 11 }RoomSets: { {0, 1, 2, 3, 4, 5, 6, 7}, {}, {}, {}, {}, {}, {}, {}, {8} }Step 10: Knock down Wall 9This combines room 5 and 8Walls Up: { 5, 6, 10, 11 }RoomSets: { {0, 1, 2, 3, 4, 5, 6, 7, 8}, {}, {}, {}, {}, {}, {}, {}, {} }Step 6: TRY and knock down Wall 10This would combine rooms 3 and 4.  However, observe that both rooms 3 and 4 are in the same set alreadySkip the wallStep 7: TRY and knock down Wall 11This would combine rooms 4 and 5.  However, observe that both rooms 4 and 5 are in the same set alreadySkip the wallWith 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 PermutationNow, 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 StateRooms: { 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 OutlineSo 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:ComputeNumberOfRoomsAndWallsAllocateMemoryForRoomsWallsAndSetsAssignTwoRoomsToEachWallSetEachWallAsBeingUpAddEachRoomToADefaultSetRandomlyPermutateAllWallsIterateThroughEachWall    If(RoomsAreInSameSet) continue    Else    KnockDownWall   AddRoomsToSameSetCreateMazeReturnMazeConclusionWell, 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!   
Quote: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.About when the beginners should try to tackle this program. About what chapter do you think we need to read to before we give this a go? ;  Thanks a lot man.  I've already started to think this out on paper also.  Right now this does seem a little complicated and I am glad.  Though it feels like a math problem.  I think all I need to do is think about it for a couple of days and read a little more and next think I know it will click.  That is how I am with math.Chad;  Who says you never use discrete math?  Fun stuff, looks like it should be simple yet complex at the same time.  Plus learning how to randomly generate a maze is always useful.   ;  The programming doesn't seem like muchbut the making a maze felt pretty confusing ^.^think ill have to read over it, 2-3 more times   ;  Sir Shadow-All-Mighty accepts this chivalrous challenge!But I just HATE how this solution uses 3 data sets in a place where one is needed. I believe that this solution requires 8 bytes for room, and thus you would only be able to do 4000x4000 rooms on a 1GB of RAM. Instead, I decided to do bitwise storage of walls (wall can be up (1) or down (0)), and this way I accomplished 3 bits for a room. That solution will be able to fit 85,000x85,000 rooms in 1GB of RAM. It would be slower, but it is 21 times more memory efficient.  Just think about it:one list contains bottom wall of a room (1 if up)one list contains right wall of a room (1 if up)one list contains 1 if the room is attached, and 0 if it is not attachedThen to find out if a wall exists in roomNumber, we can just do:(WallList[(int)(roomNumber/8)] & ( 1 <<(roomNumber%8) != 0));If I pull this off, will I stop being a newbie and become an intermediate? :D   ;Quote:Original post by ShadowPhoenixInstead, I decided to do bitwise storage of walls (wall can be up (1) or down (0)), and this way I accomplished 3 bits for a room.Wouldn't two bits be enough? [grin]And that's using a naive implementation, just storing the status of the left and bottom walls for each tile. I'm sure there are more efficient representations. [grin](Extra cookie points to whoever implements huffman encoding to compress the maze data [lol])   ;  I don't see any way to represent the data in less bits. Unless we use compression/artificial branching/some other rules (like only 1 connection on each line and lets process one line)....Or an application CAN just have one 16x16 maze with 2 exits that it will just paste over and over...But then it will not be able to show as many mazes.Quote:Original post by SpoonbenderQuote:Original post by ShadowPhoenixInstead, I decided to do bitwise storage of walls (wall can be up (1) or down (0)), and this way I accomplished 3 bits for a room.Wouldn't two bits be enough? [grin]And that's using a naive implementation, just storing the status of the left and bottom walls for each tile. I'm sure there are more efficient representations. [grin](Extra cookie points to whoever implements huffman encoding to compress the maze data [lol])I was thinking of getting 2 bits to represent the room, but it would make the program even slower. The program shall run faster if we use a third bit to indicate if a room is connected or not.And I thought that it will take some time to clear 35,000X35,000 ways.I see no way to go below 2 bits per room unless using compressions(defeating the point of keeping all the rooms in RAM) or doing park of a puzzle at a time (which would still use more than 2 bits per room).Hmm.. if I could only draw a path... but each pointer takes up 4 bytes!!!!At first I tried to use a structure to a 2x2 cell, but the pointer was like 4 bytes and I was like "oh, baby, no way!". It would have been way faster tho.Those 4 bytes will be the stopping factor for the binary tree... a pointer will mean that each node will hold 8 bytes of pointing power.And wow, I love bits, but I dislike bugs.Quote:Original post by Spoonbender(Extra cookie points to whoever implements huffman encoding to compress the maze data [lol])kekeke :Dhttp://www.codeproject.com/cpp/HandyHuffmanCoding.asp   ;Quote:Original post by ShadowPhoenixI was thinking of getting 2 bits to represent the room, but it would make the program even slower. The program shall run faster if we use a third bit to indicate if a room is connected or not.Ok, never mind the number of bits necessary (would be a long discussion, and this probably isn't the place for it)But I do have a more general question.Connected to what, do you mean?Isn't the point that all rooms are connected to all other rooms? (via exactly one path)So what is there for a room to be connected to?   ;Quote:Original post by SpoonbenderQuote:Original post by ShadowPhoenixI was thinking of getting 2 bits to represent the room, but it would make the program even slower. The program shall run faster if we use a third bit to indicate if a room is connected or not.Ok, never mind the number of bits necessary (would be a long discussion, and this probably isn't the place for it)But I do have a more general question.Connected to what, do you mean?Isn't the point that all rooms are connected to all other rooms? (via exactly one path)So what is there for a room to be connected to?Can you please explain the number of bits necessary? It sounds COOL!!!As for the connected part, the faster way of doing it while only wasting 1 byte is to see if the room is in the 'main room'. We only need to have 1 set of room at the end of the moving data, so we only need one bit to see if it in that set or not.[Edited by - ShadowPhoenix on August 1, 2007 8:54:19 AM]