I tried to comment the code as much as possible, not only for someone else's benefit reading the code but also for my own. It took me two days to complete this project(if I take away the fiance factor it may have taken me one [grin]). Most of my time was spent in the initial design phase and then the debug/run/debug etc. phase after implementation. Very little time was actually spent writing the framework to C# code. Of course as I did the code construction I would notice ways I could improve upon the design which I would implement immediately.
If anyone does happen to take the time to analyze my code and sees better ways of doing something or would like to provide some insight into doing something different but not necessarily better, please give me the criticism! [smile]
Thanks!
PerfectMaze.cs
using System;using System.Collections.Generic;using System.Linq;using System.Text;namespace Perfect_Maze_Generator{ struct MazeAttributes { public int columns, rows, totalWalls; public Wall[] walls; } class Wall { private bool isUp; private Room[] connectingRooms; int num; public Wall(int num) { this.num = num; isUp = true; connectingRooms = new Room[2]; } // get the wall's assigned number public int Num { get { return num; } } // two properties that retrive the first and second room being seperated by the wall public Room FirstRoom { get { return connectingRooms[0]; } } public Room SecondRoom { get { return connectingRooms[1]; } } public bool IsUp { get { return isUp; } } // join two rooms together by this wall public void Join(Room room1, Room room2) { connectingRooms[0] = room1; connectingRooms[1] = room2; } // knock the wall down! public void Knockdown() { isUp = false; SecondRoom.AddToSet(FirstRoom.Set); } public override string ToString() { return String.Format("{0}", num); } } class Room { int num; List<Room> itsSet; public Room(int num) { this.num = num; } public void AddToSet(List<Room> set) { // determine if we are initializing or have already been initialized if (itsSet != null) { // if we aren't initializing, move all rooms from the set this room is in to the // newly specified set passed in to the function // first take care of rooms other than this one foreach (Room r in itsSet) { if (r != this) { r.Set = set; set.Add(r); } } // and then take care of this room foreach (Room r in set) itsSet.Remove(r); itsSet.Remove(this); itsSet = set; set.Add(this); } // otherwise, we are just initializing to a default set else { itsSet = set; set.Add(this); } } public List<Room> Set { get { return itsSet; } set { itsSet = value; } } public override string ToString() { return String.Format("{0}", num); } } class PerfectMaze { Wall[] walls; Room[] rooms; List<Room>[] sets; int numOfRooms, verticalWalls, horizontalWalls, totalWalls; int columns, rows; public PerfectMaze(int columns, int rows) { this.columns = columns; this.rows = rows; numOfRooms = CalculateRooms(); totalWalls = CalculateWalls(); // allocate memory for walls walls = new Wall[totalWalls]; for (int i = 0; i < walls.Length; i++) { walls = new Wall(i); } // allocate memory for rooms rooms = new Room[numOfRooms]; for (int i = 0; i < rooms.Length; i++) { rooms = new Room(i); } // allocate memory for sets sets = new List<Room>[numOfRooms]; for (int i = 0; i < sets.Length; i++) sets = new List<Room>(); // add each room to it's own default set for (int i = 0; i < numOfRooms; i++) { rooms.AddToSet(sets); } // finally, assign each wall two rooms that it seperates AssignWalls(); GenerateMaze(); } // assigns two rooms to each individual wall that it seperates private void AssignWalls() { // assign vertical walls with the following formula: // room is the current room to the left of the wall // wall is the /vertical/ wall being assigned // colCount is the column to the left of the wall being examined, this allows us to determine // if the wall is a vertical wall or horizontal for (int room = 0, wall = 0, colCount = 1; wall < totalWalls; room++, colCount++) { // if the columnCount is equal to the total amount of columns in the maze, // this means we have hit the last vertical wall for that row if (colCount == columns) { colCount = 0; //colCount is reset to 0 and will be set to 1 beginning at the next iteration wall += columns; // we must cycle through all the horizontal walls until we reach another // vertical wall, there are as many horizontal walls as there are columns continue; } // assign the wall's connectingRooms with the room to the // immediate left(room) and the right(room+1) walls[wall].Join(rooms[room], rooms[room + 1]); // always remember to increment wall to look at the next one, we have to do this here instead // of in the for loop initialization because of the colCount skipping walls wall++; } // assign horizontal walls, somewhat of a reverse of assigning verticals for (int room = 0, wall = columns-1, colCount = 1; wall < totalWalls; room++, colCount++) { if (colCount == columns+1) { colCount = 0; wall += columns - 1; room--; // because room will be increased upon the next iteration, we need to ensure // that it remains the room on top of the wall being examined continue; } walls[wall].Join(rooms[room], rooms[room + columns]); wall++; } } // get the attributes of the maze for drawing classes and the like public MazeAttributes GetAttributes() { MazeAttributes attributes = new MazeAttributes(); attributes.columns = columns; attributes.rows = rows; attributes.totalWalls = totalWalls; attributes.walls = walls; return attributes; } int CalculateRooms() { return columns * rows; } int CalculateWalls() { verticalWalls = (columns - 1) * rows; horizontalWalls = (rows - 1) * columns; return horizontalWalls + verticalWalls; } // randomly permutate the walls and knock them down creating exactly one // and only one path to any point in the maze void GenerateMaze() { // randomly permutate walls... probably not the best way of doing it // but it is all I could think of List<Wall> permutatedList = new List<Wall>(); Random rand = new Random(); while (permutatedList.Count < walls.Length ) { int i = rand.Next(walls.Length); if (permutatedList.Contains(walls)) continue; else permutatedList.Add(walls); } foreach (Wall wall in permutatedList) { // if the seperated rooms are in the same set, that means they are connected somewhere somehow // so we must disregard this wall if (wall.FirstRoom.Set == wall.SecondRoom.Set) continue; // otherwise, they do not yet have a path between them, so we knock the wall down and // then add the second room to the first room's set else { wall.Knockdown(); // the wall takes care of adding the second room to the first room's set } } } }}
Maze Drawer.cs
using System;using System.Collections.Generic;using System.Linq;using System.Text;namespace Perfect_Maze_Generator{ // Originally the code for drawing the maze was contained in the maze generation // class itself... however the maze shouldn't be responsible for drawing itself in // my opinion. This is the result of that refactor, a class soley responsible for drawing // the maze. class MazeDrawer { Wall[] walls; int columns, totalWalls, rows; public MazeDrawer(PerfectMaze maze) { MazeAttributes attr = maze.GetAttributes(); walls = attr.walls; columns = attr.columns; totalWalls = attr.totalWalls; rows = attr.rows; } public void Draw() { Console.WriteLine(" {0}", new String('_', columns + (columns - 1))); // draw top border // invariant: r = row we are drawing, vwall is always a vertical wall in that row, // hwall is always a "floor" wall in that row for (int r = 0, vwall = 0, hwall = columns - 1; r < rows; r++) { Console.Write('|'); // draw leftmost border //invariant: c is a valid textual column for (int c = 0; c < columns + (columns - 1); c++) { // to determine if we are looking at a floor wall or a vertical wall, we simply // determine if the column being looked at is even or not. // all horizontal walls will be an even number, and all verticles will be odd! if (c % 2 == 0) { // if the horizontal wall we are keeping track of is // greater than the total number of walls, it must be a floor // permimeter wall that we are supposd to draw if (hwall >= totalWalls) Console.Write('_'); // otherwise if it is up, we draw it else if (walls[hwall].IsUp) Console.Write('_'); // and if not, we draw a space else Console.Write(' '); hwall++; } else { // if the vwall is up, we draw a | if (walls[vwall].IsUp) Console.Write('|'); // and if not, we draw a floor else Console.Write('_'); vwall++; } } Console.WriteLine('|'); // draw the right-most border and drop a line // since we are dropping a wall, we must increase our counts accordingly to keep // our invariant for the loop true hwall += columns - 1; vwall += columns; } } }}
Program.cs
using System;using System.Collections.Generic;using System.Linq;using System.Text;namespace Perfect_Maze_Generator{ class Program { static int GetNumber(string prompt) { Console.Write("{0}: ", prompt); int num = 0; if (!int.TryParse(Console.ReadLine(), out num)) num = -1; return num; } static void Main(string[] args) { Console.WriteLine("Welcome to the C# Random Maze Generator!"); Console.Title = "Welcome to the C# Random Maze Generator!"; int rows = 0, columns = 0; bool quit = false; Console.SetWindowSize(150, 58); while (!quit) { while ((rows = GetNumber("Enter the number of rows (2-50)")) < 2 || rows > 50) Console.WriteLine("Sorry, that is an invalid number. Please try a number between 2 and 50."); while ((columns = GetNumber("Enter the number of columns (2-50)")) < 2 || columns > 50) Console.WriteLine("Sorry, that is an invalid number. Please try a number between 2 and 50."); PerfectMaze maze = new PerfectMaze(columns, rows); MazeDrawer mazeDrawer = new MazeDrawer(maze); if (rows > Console.BufferHeight && columns > Console.BufferWidth) Console.SetBufferSize(columns, rows); mazeDrawer.Draw(); Console.Write("Would you like to generate another maze? ([y]es|[n]o): "); bool endLoop = false; while (!endLoop) { string input = Console.ReadLine(); switch (input) { case "y": case "yes": Console.WriteLine("Ok!"); endLoop = true; break; case "n": case "no": Console.WriteLine("Goodbye!"); quit = true; endLoop = true; break; default: Console.WriteLine("Invalid input!"); Console.Write("Would you like to generate another maze? ([y]es|[n]o): "); break; } } } } }}