🎉 Celebrating 25 Years of GameDev.net! 🎉

Not many can claim 25 years on the Internet! Join us in celebrating this milestone. Learn more about our history, and thank you for being a part of our community!

Back to Old Archive

C# Workshop - Project 1: Maze Generator

Jeromy Walsh · 2007-09-11T08:52:49

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!

Old Archive Archive

Started by JWalsh July 26, 2007 04:57 PM

35 comments, last by Telastyn 16 years, 9 months ago

Emmanuel Deloget

1,382

August 02, 2007 08:26 AM

Quote: Original post by ShadowPhoenix
Quote: Original post by Spoonbender
Quote: Original post by ShadowPhoenix
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.

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.

Are you discussion some optimization technique in a beginner workshop? [grin]

-- Emmanuel D. [blog, in French] [blog, very bad googlized translation]

Spoonbender

1,258

August 02, 2007 09:31 AM

Yeah, better start by getting the maze working. Once you have that, feel free to start another thread if you want to discuss clever extensions, optimizations and extra-features you can implement. [grin]

foolios

133

August 02, 2007 11:51 PM

Is there a way to specify the range of characters allowed from the keyboard?

Like, is characters on the keyboard numbered from 1 - 110 whereby you could write a conditional to make sure that only numbers from the keyboard were entered.
I was just wondering if numbers from the keyboard were within a certain range like 1-10.
Then check to see if the char read was between that then parse it to int.

if (Console.Read() < 11)
{
int mazeHght = int.Parse(Console.ReadLine());
}
else
{
Console.Write("You aren't inputting numbers");
}

I rate users. Its just not having much impact as my rating is low...

GameDev Doctor

166

August 03, 2007 01:01 AM

Digits have a byte value between 0x30 to 0x39, or 48 to 57 in decimal (0-9).
However, the easiest way test if the client entered an integer is to use either exceptions or the TryParse function.
Something like this...

string input = Console.ReadLine().Trim(); //get rid of whitespace on each endint res;if(Int32.TryParse(input, out res)){//res contains the integer that was typed}else{//not a valid integer}

I mean, why would you get your medical advice anywhere else?

foolios

133

August 03, 2007 02:11 AM

What you showed me is great. I want to ask you about the keyboard numbers as a decimal.
So you would read the input as string, then convert it to decimal and then check to see if the decimal fell between 48-57 inclusive?

Thanks so much.

Also, I have a question about this conditional. I have this feeling it's not running it the way I would think because it's possibly short circuited:

            string strHeight = Console.ReadLine().Trim();            // Create an integer variable to hold the converted string            int mazeHeight;            // Try the casting of the string in strHeight to int and return it to the int variable            if (Int32.TryParse(strHeight, out mazeHeight))            {                // Variable mazeHeight contains the integer that was typed                // Check that the number chosen was between 2 and 50 inclusive                if (mazeHeight >= 2 || mazeHeight <= 50)                {                    // Code to continue when number is 2 - 50                }                else                {                    // The number is not 2 - 50                    Console.WriteLine("Please follow instructions.");                }            }            else            {                Console.Write("Not a valid number");            }

Right at the line:
if (Int32.TryParse(strHeight, out mazeHeight))

I think it's bringing in and then returning and then not following the rest of the code in that block below it. It's not meant to go into a block is it for this particular case?

I rate users. Its just not having much impact as my rating is low...

GameDev Doctor

166

August 03, 2007 03:07 AM

Now I'm not really sure what you're asking.
48-57 are the ascii codes, so they only matter before parsing to an int.
Afterwards you can just do what you did in your code segment.
If you do want to check before parsing it into an integer, you would compare to characters directly.

string input;//get inputforeach(char c in input){if(c => '0' && c <= '9');    //character is a digit}

As for comparing to a real number, I can see no reason to do that without parsing it to an int first.
And your bug is that you used || when you meant && - mazeHeight >= 2 || mazeHeight <= 50 is always true :)

I mean, why would you get your medical advice anywhere else?

foolios

133

August 03, 2007 08:24 AM

DOH!

Thank you.

string input = Console.ReadLine().Trim();        // Get input        foreach (char c in input)        {            if (c >= '0' && c <= '9')            {                // Character is a digit            }        }

This wouldn't be any good anyhows since we have to go up to 50. This would only check single digit numbers right?

I rate users. Its just not having much impact as my rating is low...

Spoonbender

1,258

August 03, 2007 11:16 AM

Yeah. Of course you could then just do it twice, but int.Parse() is probably a better option [wink]

EternalNewbie

207

August 03, 2007 11:24 AM

Parse is a better option, but the above would work as it goes through all the characters in string. You just need to handle parsing the characters yourself.
Which would start by minusing '0' and then multiplying the number by 10.
But there are number of details you would need to handle (e.g. whitespaces). int.parse does most of these for you so why complicate things?

foolios

133

August 03, 2007 11:43 AM

That's great. I was just asking so I understood.

You guys explained it very well.

Thanks a million!

I rate users. Its just not having much impact as my rating is low...

🎉 Celebrating 25 Years of GameDev.net! 🎉

C# Workshop - Project 1: Maze Generator

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

🎉 Celebrating 25 Years of GameDev.net! 🎉

C# Workshop - Project 1: Maze Generator

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines