using System; using System.Collections.Generic; using System.Drawing; using System.Linq; using System.Text; namespace xnafan.MazeCreator { /// /// Class to create random mazes with tiles as walls /// Jakob Krarup (www.xnafan.net) /// Use, alter and redistribute this code freely, /// but please leave this comment :) /// public class MazeCreator { #region Events and related /// /// Event is fired whenever a tile is deleted in the maze /// public event EventHandler MazeChanged; /// /// Called to fire an event whenever a tile is deleted in the maze /// /// The Point where the deleted tile was protected void OnTileDeleted(Point p) { if (MazeChanged != null) { MazeChanged(this, new PointEventArgs(p)); } } #endregion #region Variables and properties /// /// Defines whether all corridors should stay with one tile separation, keeping to neat horizontal and vertical lines /// public bool DiagonalTunnelingAllowed { get; private set; } /// /// The maze as it looks now. Empty Points are zeroes and walls are ones /// public byte[,] Maze { get; private set; } //The stack of points not tested yet private Stack _tiletoTry = new Stack(); /// /// The list of offsets to use to get the tiles above, below, to the right and the left of a specific tile /// private List NSEW = new List { new Point(0, 1), new Point(0, -1), new Point(1, 0), new Point(-1, 0) }; /// /// Used to generate random values /// static Random rnd = new Random(); private int _longestPathSoFar; /// /// This variable stores the accessible point which is furthest from the starting point. /// This can be used to store the position to place the target object or goal, which will give the biggest challenge for a player /// public Point FurthestPoint { get; private set; } private int _width, _height; private Point _currentTile; /// /// The width of the maze /// public int Width { get { return _width; } private set { //must be larger than two if (value < 3) { throw new ArgumentException("Width must be larger than two for the generator to work"); } _width = value; } } /// /// The height of the maze /// public int Height { get { return _height; } private set { //must be larger than two if (value < 3) { throw new ArgumentException("Height must be larger than two for the generator to work"); } _height = value; } } /// /// The tile where development of the maze is currently at /// public Point CurrentTile { get { return _currentTile; } private set { if (value.X < 1 || value.X >= this.Width - 1 || value.Y < 1 || value.Y >= this.Height - 1) { throw new ArgumentException("CurrentTile must be within the one tile border all around the maze"); } if (value.X % 2 == 1 || value.Y % 2 == 1 || DiagonalTunnelingAllowed) { _currentTile = value; } else { throw new ArgumentException("The current square must not be both on an even X-axis and an even Y-axis when DiagonalTunnelingAllowed is false, to ensure we can get walls around all tunnels"); } } } #endregion #region Constructors /// /// Creates a new mazegenerator with mazes starting at (1,1), and no diagonal tunneling. /// /// The number of tiles across in the mazes to generate. Must include the two ekstra tiles for a wall in both sides. /// The number of tiles from top to bottom in the mazes to generate. Must include the two ekstra tiles for a wall both at top and bottom. public MazeCreator(int width, int height) : this(width, height, new Point(1, 1)) { } /// /// Creates a new mazegenerator with mazes starting at the requested startingPosition, and no diagonal tunneling. /// /// /// /// public MazeCreator(int width, int height, Point startingPosition) : this(width, height, startingPosition, false){} /// /// Creates a new mazegenerator with mazes starting at the requested startingPosition, and no diagonal tunneling. /// /// The number of tiles across in the mazes to generate. Must include the two ekstra tiles for a wall in both sides. /// The number of tiles from top to bottom in the mazes to generate. Must include the two ekstra tiles for a wall both at top and bottom. /// Where to start tunneling from /// Whether the tunneling should allow diagonal routes, e.g. up, left, up, left public MazeCreator(int width, int height, Point startingPosition, bool diagonalTunnelingAllowed) { this.Width = width; this.Height = height; DiagonalTunnelingAllowed = diagonalTunnelingAllowed; Maze = new byte[Width, Height]; //initialize all fields as taken for (int x = 0; x < Width; x++) { for (int y = 0; y < Height; y++) { Maze[x, y] = 1; } } //start the excavation from the current position CurrentTile = startingPosition; //add the beginning position to the tiles to try _tiletoTry.Push(CurrentTile); } #endregion #region CreateMaze /// /// Creates a new maze with the current size and starting position /// /// A freshly generated, random maze public byte[,] CreateMaze() { //local variable to store neighbors to the current square //as we work our way through the maze List neighbors; //as long as there are still tiles to try while (_tiletoTry.Count > 0) { //excavate the square we are on Maze[CurrentTile.X, CurrentTile.Y] = 0; //notify anyone interested that the tile was removed OnTileDeleted(CurrentTile); //get all valid neighbors for the new tile neighbors = GetValidNeighbors(CurrentTile); //if there are any interesting looking neighbors if (neighbors.Count > 0) { //remember this tile, by putting it on the stack _tiletoTry.Push(CurrentTile); //move on to a random of the neighboring tiles CurrentTile = neighbors[rnd.Next(neighbors.Count)]; } else { //if there were no neighbors to try, we are at a dead-end //test to see if this dead end will be the furthest point in the maze UpdateFurthestPoint(); //toss this tile out //(thereby returning to a previous tile in the list to check). CurrentTile = _tiletoTry.Pop(); } } return Maze; } private void UpdateFurthestPoint() { if (_tiletoTry.Count > _longestPathSoFar) { _longestPathSoFar = _tiletoTry.Count; FurthestPoint = CurrentTile; } } #endregion #region Helpermethods /// /// Get all the prospective neighboring tiles /// /// The tile to test /// All and any valid neighbors private List GetValidNeighbors(Point centerTile) { List validNeighbors = new List(); //Check all four directions around the tile foreach (var offset in NSEW) { //find the neighbor's position Point toCheck = new Point(centerTile.X + offset.X, centerTile.Y + offset.Y); //make sure the tile is not on both an even X-axis and an even Y-axis //to ensure we can get walls around all tunnels if (toCheck.X % 2 == 1 || toCheck.Y % 2 == 1 || DiagonalTunnelingAllowed) { //if the potential neighbor is unexcavated (==1) //and still has three walls intact (new territory) if (Maze[toCheck.X, toCheck.Y] == 1 && HasThreeWallsIntact(toCheck)) { //add the neighbor validNeighbors.Add(toCheck); } } } return validNeighbors; } /// /// Counts the number of intact walls around a tile /// /// The coordinates of the tile to check /// Whether there are three intact walls (the tile has not been dug into earlier. private bool HasThreeWallsIntact(Point pointToCheck) { int intactWallCounter = 0; //Check all four directions around the tile foreach (var offset in NSEW) { //find the neighbor's position Point neighborToCheck = new Point(pointToCheck.X + offset.X, pointToCheck.Y + offset.Y); //make sure it is inside the maze, and it hasn't been dug out yet if (IsInside(neighborToCheck) && Maze[neighborToCheck.X, neighborToCheck.Y] == 1) { intactWallCounter++; } } //tell whether three walls are intact return intactWallCounter == 3; } /// /// Find out whether a tile is inside the maze /// /// The coordinates of the tile to check /// Whether the tile is inside the maze private bool IsInside(Point p) { return p.X >= 0 && p.Y >= 0 && p.X < Width && p.Y < Height; } #endregion #region ToString /// /// Returns a textmap of the maze. /// /// A textual representation of the maze public override string ToString() { string representation = " "; StringBuilder sb = new StringBuilder(); for (int y = Height - 1; y>= 0 ; y--) { for (int x = 0; x < Width; x++) { if (Maze[x, y] == 0) { //if it is the current tile, represent it with an "O" if (CurrentTile.X == x && CurrentTile.Y == y) { representation = "O"; } else { //if it is still one to test if (_tiletoTry.Contains(new Point(x, y))) { representation = "."; } else { //been there - nothing to see representation = " "; } if (FurthestPoint.X == x && FurthestPoint.Y == y) { representation = "*"; } } } else //it is unexcavated (wall) { representation = "X"; } sb.Append(representation); } sb.AppendLine(); } return sb.ToString(); } #endregion #region ToBitmap public Bitmap ConvertToBitmap(int tileSizeInPixels) { //create a new bitmap with a pixel extra for each tile +1 for drawing a grid around all tiles Bitmap bmp = new Bitmap(1 + (tileSizeInPixels + 1) * this.Width, 1 + (tileSizeInPixels + 1) * this.Height); Graphics g = Graphics.FromImage(bmp); //fill the grapics with grey g.FillRectangle(Brushes.DarkGray, new Rectangle(0, 0, bmp.Width, bmp.Height)); //get the current maze as a string, and replace any newlines string mazeString = this.ToString().Replace(Environment.NewLine, ""); //store a fillBrush as white Brush fillBrush = Brushes.White; //for each tile, get a brush that is the correct color for (int y = 0; y < this.Height; y++) { for (int x = 0; x < this.Width; x++) { switch (mazeString[x + y * this.Width]) { case 'X': fillBrush = Brushes.Black; break; case 'O': fillBrush = Brushes.Red; break; case '.': fillBrush = Brushes.CornflowerBlue; break; case ' ': fillBrush = Brushes.White; break; case '*': fillBrush = Brushes.LightGreen; break; } //draw the tile in g.FillRectangle(fillBrush, 1 + x * (tileSizeInPixels + 1), 1 + y * (tileSizeInPixels + 1), tileSizeInPixels, tileSizeInPixels); } } //dispose of the Graphics object g.Dispose(); return bmp; } #endregion } }