🎉 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!

C# Workshop - Project 1: Maze Generator

Started by
35 comments, last by Telastyn 16 years, 9 months ago
Quote: Original post by Spoonbender
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]



Well, I didn't have much time to work on it, but I got the bits setup perfectly in a nice class! :D
Now all I need to do to see a wall is to call

char MazeFinder::GetWall(int side, int roomN);
void MazeFinder::SetWall(int side, int roomN);

Now it's time to make a maze :D
Advertisement
heh I've done it

Just got to get the finer points sorted like the console buffer etc

It's a completely bonkers program & takes around 15-20 minutes to process a 20 x 20 maze [grin]
It works though -a perfect random maze in little under the time it'd take to read War & Peace.

I think I ought to look at the project brief again though and try to design it properly now.

ps. Who else is getting grief from their other half due to the hours spent on this workshop? lol I reckon I'll be homeless by the end of the month [grin]
I hear ya. I'm making the sacrifice too.

And it's really appreciated of the tutors and JWalsh for making the sacrifice too to offer this while using up their free time.

Family won't leave me alone. They think everything anyone does on the computer is for play.

I get no respect because of it...

Keep at it brotha
I rate users. Its just not having much impact as my rating is low...
Quote:
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.


Ok, at first when I searched I ran into directx information:
http://msdn.microsoft.com/archive/default.asp?url=/archive/en-us/directx9_m_Oct_2004/directx/ref/ns/microsoft.directx.directsound/c/buffer/buffer.asp

But then found this:
http://msdn2.microsoft.com/en-us/library/system.console.aspx

Ok, so the buffer is the region that the console window occupies? And what you were saying in that paragraph is that we are going to need to modify the dimensions of the console screen based on how big the maze is going to be right? That this is what the buffer is for?

On this page:
http://msdn2.microsoft.com/en-us/library/system.console_members.aspx

I see buffer width and buffer height properties.
C#

public static int BufferHeight { get; set; }

But I also see under methods SetBufferSize.
C#

public static void SetBufferSize (
int width,
int height
)

Ok, so this is how you'd get a start at using something new. Just like using this buffer with the console is new to me. Look up System.Console in the MSDN. Then I found stuff about the Buffer and went into it looking for things to work with. So those two sets of things I mentioned above are what look like to me to be what I need to play with.

That right so far? Anything I am missing, well besides that there is some code examples on those pages that I am going to look through to see if I can figure out how to use these things. What would you suggest to be better to work with? The properties or the method?

Thanks in advance.
I rate users. Its just not having much impact as my rating is low...
I thought I'd comment: I don't know to what extent this helps or not, but you can think of the problem in (perhaps) slightly different terms that possibly may make it slightly easier to understand. If nothing else it's just another perspective on the problem and possible solutions.

Basically the observation is this that you don't need to think of/track all the different sets of rooms. You can simply tag/flag each room with a flag that describes whether that room "isReachable" (from e.g. the starting room), and that's all you need. So the basic process of generation is then something as follows: Each time you pick a random direction to extend the maze in (from the "current" room), you check if the room behind the wall in the chosen direction is already reachable via its flag. If it is, then it follows that you can't actually break down that wall since you'll cause a loop (since the flag says it's already reachable.) So in that case you pick another dicrection. If the room in that direction is *not* flagged as reachable yet, then predictably you break the wall down, "move" to this new room so the "curernt" room becomes the new room, and flag this current room as reachable. And then the process repeats. Eventually the current room will paint itself into a dead end, where all 4 sides will have been flagged as reachable and so no further extension from that position is possible.

At that point you have to pick a new extension point for the maze in some way. I'll list a few thoughts/options on that. The simplest/most obvious approach is to randomly pick a new room until you find one that is is adjacent to at least one non-reachable room. Then the process starts all over again as above. This method has a few problems, chiefly that it gets slower the closer it gets to completion and is not deterministic. (In computer science terms, it's also not a proper algorithm, because it's not guaranteed to terminate after a finite number of steps, the latter attributes being part of the definition of an algorithm.)

The second alternative is to not pick the next extension point randomly, but to backtrack to the previous room you were in, and try that. If that's also fully surrounded by reachable rooms then backtrack again, which you keep doing until eventually you have at least one non-reachable room next to your current room. This latter method is very well suited to a recursive solution of th problem. If you don't know what recursion is then don't worry about it. It is also deterministic and guaranteed to terminate.

A third alternative that combines aspects of the previous 2 (and that in fact brings us somewhat back to JWalsh's suggestion/algorithm) is possible if we do away with flagging each room independently as I suggested and instead flag rooms by putting locating them in one of 2 distinct sets of interest, one for indicating "reachableRooms" and one for "validExtensionPoints". The idea is that everytime you move to a new "current" room, you check if the room you're leaving is a valid extension point (after having broken the wall down.) If it is, then add it into the valid extension points set. If it is not, then you remove it if it's there already. Eventually when you get into a dead end, you simply pick a room at random from the "validExtensionPoints" set and start generating the maze again. Obviously here, the valid "validExtensionPoints" set will start out empty, will grow quite quickly in the begining as every move results in another possible extension points being added into the set, but will eventually start diminishing and will return to being empty when the maze is completed.

Right that's it for now. I hope that helps etc and is understandable. If it's not please ask (or just ignore it :-) )

Project 1 is almost over. Of the 450 or so people signed up for the workshop, less than 25 completed Project 1 so far. Those who completed it, or even gave a concerted effort should congratulate yourselves for having the ambition necessary to pursue your own interests.

*See my quote below for the true meaning of being a game programmer*

I do, however, recommend that people complete the Maze Generator Project whether on time or late, as it will appear again in Project 4, as well as the Final Project.

If you have questions, don't hesitate to ask. As well, over a dozen people have now submitted source code for their completed or partially completed project. I'd highly recommend looking them over, and seeing what you're doing wrong if you're unable to complete the project.

Cheers!
Jeromy Walsh
Sr. Tools & Engine Programmer | Software Engineer
Microsoft Windows Phone Team
Chronicles of Elyria (An In-development MMORPG)
GameDevelopedia.com - Blog & Tutorials
GDNet Mentoring: XNA Workshop | C# Workshop | C++ Workshop
"The question is not how far, the question is do you possess the constitution, the depth of faith, to go as far as is needed?" - Il Duche, Boondock Saints
I haven't read any of the answers yet, but I wanted to make sure I was on the right track.

I've made some "calculations" on how I should determine the rooms and walls that connect rooms.
walls = columns * (rows - 1) +  rows * (columns - 1)5 rows by 5 columns = 5 * 4 + 5 * 4 = 403 rows by 3 columns = 3 * 2 + 3 * 2 = 123 rows by 4 columns = 4 * 2 + 3 * 3 = 174 rows by 3 columns = 3 * 3 + 4 * 2 = 17rooms = rows * columns - - - | | | |  - - - | | | |  - - -  | | | | - - - := means holdsvertical wall := wall number & wall number + 1horizontal wall := (wall number - number of vertical walls) & (" ") + number of columnsexample - Wall 0 := room 0 & room1; Wall 3 := room 1 & room 4


Am I making this too complicated?

[Edited by - Alpha_ProgDes on August 18, 2007 11:16:09 PM]

Beginner in Game Development?  Read here. And read here.

 

Alpha you calculate the number of walls the same way I did, assigning the walls - it looks pretty clear to me what you are trying to achieve, I think the way I did it was much messier.
How about them apples?
I've already posted my project, but I thought I'd dump the maze generation class here in case anyone wants to compare and is too lazy to download the zip.

using System;using System.Collections.Generic;namespace MazeRaider.MazeGeneration{    public class PerfectMaze : IMaze    {        // Constants        public const int MINIMUM_HEIGHT = 3, MINIMUM_WIDTH = 3;        // Types        private struct Wall        {            // Fields            private readonly int itsID;            private readonly int itsRoom0, itsRoom1;            private bool isUp;            // Constructor            public Wall(int id, int room0, int room1)            {                itsID = id;                itsRoom0 = room0;                itsRoom1 = room1;                isUp = true;            }            // Properties            public int ID            {                get { return itsID; }            }            public int Room0            {                get { return itsRoom0; }            }            public int Room1            {                get { return itsRoom1; }            }            public bool IsUp            {                get { return isUp; }                set { isUp = value; }            }        }        // Fields        private readonly int itsHeight, itsWidth;        private Wall[] itsWalls;        private List<int>[] itsRoomSets;        private Tile[,] itsTileMap;        // Constructor        public PerfectMaze(int height, int width)        {            if ((height < MINIMUM_HEIGHT) || (width < MINIMUM_WIDTH))            {                string message = String.Format("Invalid dimensions: minimum size is {0}x{1}.", MINIMUM_HEIGHT, MINIMUM_WIDTH);                throw new Exception(message);            }            else            {                itsHeight = height;                itsWidth = width;                // Compute number of rooms and walls                int numWalls = (itsHeight - 1) * itsWidth + (itsWidth - 1) * itsHeight;                int numRooms = itsHeight * itsWidth;                itsWalls = new Wall[numWalls];                itsRoomSets = new List<int>[numRooms];                // Compute dimensions of tile map (additional tiles are for the outer walls)                int mapHeight = itsHeight + (itsHeight - 1) + 2;                int mapWidth = itsWidth + (itsWidth - 1) + 2;                itsTileMap = new Tile[mapHeight, mapWidth];                Generate();            }        }        // Methods        public void Generate()        {            Initialize();            PermutateWalls();            KnockDown();            CreateTileMap();        }        private void Initialize()        {            int wall, room;            // Add each room to its default room set            for (room = 0; room < itsRoomSets.Length; room++)            {                itsRoomSets[room] = new List<int>();                itsRoomSets[room].Add(room);            }            // Assign two rooms to each vertical wall            for (wall = 0, room = 0; wall < itsWalls.Length; wall += itsWidth, room++)            {                for (int end = wall + (itsWidth - 1); wall < end; wall++, room++)                {                    itsWalls[wall] = new Wall(wall, room, room + 1);                }            }            // Assign two rooms to each horizontal wall            for (wall = (itsWidth - 1), room = itsWidth; wall < itsWalls.Length; wall += (itsWidth - 1))            {                for (int end = wall + itsWidth; wall < end; wall++, room++)                {                    itsWalls[wall] = new Wall(wall, room - itsWidth, room);                }            }        }        private void PermutateWalls()        {            Random rand = new Random();            for (int swap = 0; swap < itsWalls.Length; swap++)            {                int index0 = rand.Next(0, itsWalls.GetUpperBound(0));                int index1 = rand.Next(0, itsWalls.GetUpperBound(0));                SwapWalls(index0, index1);            }        }        private void KnockDown()        {            for (int wall = 0; wall < itsWalls.Length; wall++)            {                // Knock down wall if its rooms are not in the same room set                if (!IsInSameSet(itsWalls[wall].Room0, itsWalls[wall].Room1))                {                    itsWalls[wall].IsUp = false;                    AddRoomsToSet(itsWalls[wall].Room0, itsWalls[wall].Room1);                }            }        }        private bool IsInSameSet(int room0, int room1)        {            for (int set = 0; set < itsRoomSets.Length; set++)            {                if (itsRoomSets[set].Contains(room0) && itsRoomSets[set].Contains(room1))                    return true;            }            return false;        }        private void AddRoomsToSet(int room0, int room1)        {            int set, index0 = 0, index1 = 0;            // Find the index of the target room set            for (set = 0; set < itsRoomSets.Length; set++)            {                if (itsRoomSets[set].Contains(room0))                {                    index0 = set;                    break;                }            }            // Find the index of the source room set            for (set = 0; set < itsRoomSets.Length; set++)            {                if (itsRoomSets[set].Contains(room1))                {                    index1 = set;                    break;                }            }            // Copy all of the rooms in the source room set to the target room set            foreach (int room in itsRoomSets[index1])                itsRoomSets[index0].Add(room);            // Nuke the contents of the source room set            itsRoomSets[index1].Clear();        }        private void CreateTileMap()        {            SortWalls();            int height = itsHeight + (itsHeight - 1);            int width = itsWidth + (itsWidth - 1);            int row, col, wall;            // Construct the top outer wall            for (col = 0; col <= itsTileMap.GetUpperBound(1); col++)                itsTileMap[0, col] = Tile.Wall;            // Construct the body of the maze            for (row = 1, wall = 0; row <= height; row++)            {                // Append the left outer wall                itsTileMap[row, 0] = Tile.Wall;                for (col = 1; col <= width; col += 2)                {                    // If the current row is composed rooms and vertical walls                    if ((row % 2) != 0)                    {                        itsTileMap[row, col] = Tile.Room;                        if (col < width) // If the next wall is not the right outer wall                        {                            itsTileMap[row, col + 1] = itsWalls[wall].IsUp ? Tile.Wall : Tile.Room;                            wall++;                        }                    }                    else // If the current row is composed of horizontal walls                    {                        itsTileMap[row, col] = itsWalls[wall].IsUp ? Tile.Wall : Tile.Room;                        wall++;                        if (col < width) // If the next wall is not the right outer wall                        {                            itsTileMap[row, col + 1] = Tile.Wall;                        }                    }                }                // Append the right outer wall                itsTileMap[row, itsTileMap.GetUpperBound(1)] = Tile.Wall;            }            // Construct the bottom outer wall            for (col = 0; col <= itsTileMap.GetUpperBound(1); col++)                itsTileMap[itsTileMap.GetUpperBound(0), col] = Tile.Wall;        }        private void SortWalls()        {            for (int pass = 0, minIndex; pass < (itsWalls.Length - 1); pass++)            {                minIndex = pass;                for (int index = (pass + 1); index < itsWalls.Length; index++)                {                    if (itsWalls[minIndex].ID > itsWalls[index].ID)                        minIndex = index;                }                SwapWalls(minIndex, pass);            }        }        private void SwapWalls(int index0, int index1)        {            Wall temp = itsWalls[index0];            itsWalls[index0] = itsWalls[index1];            itsWalls[index1] = temp;        }        // Properties        public Tile[,] TileMap        {            get { return itsTileMap; }        }    }}


Quote: Original post by Alpha_ProgDes
Am I making this too complicated?


That's precisely how I implemented it. As long as you process the horizontal and vertical walls in separate loops when assigning rooms, it shouldn't be too complicated.

Well, I know for me at least, C# has been simply a syntactical change from other OO languages, and I haven't really hit an area where I have been put out of my element.

I understand it must be disappointing for you, JWalsh, to have so few complete the project -- but something as simple as a 'maze generator' isn't a test of language features, but rather of algorithmic development. I could just as easily write the code in Java, C, C++, Ruby, et cetera. Therefore, it didn't have a very high priority for me -- it wasn't extending my knowledge of C#. C# for me will be interesting when we get into areas where the language differs. I don't actually care about C#'s syntax -- syntax is easy enough to pick up. I care about its constructs and paradigms.

I wonder if others feel similarly.

This topic is closed to new replies.

Advertisement