Building Mazes

Happy New Year!

From NetHack to Civilization to Diablo to MineCraft, lots of games have used procedural algorithms to generate semi-randomized levels. For a one man shop like myself, its a way to generate lots of gameplay without a ton of gruntwork.

So how to go you about building mazes?

One site that really helped me out was PCG.Wikidog.com - Procedural Content Generation. It contains algorithms for some of the classic roguelikes, including Angband.

A maze itself can be generated with a pretty simple iterative or recursive algorithm. The psuedocode is as follows:


1. Start out with a 2D array of size nxn.

2. Fill each cell in the grid with character '?' (undefined)

3. Carve out a random cell.
   a. Define function Carve: make the input cell empty '.'
   b. Make the surrounding four cells "maybe" ','.
   c. Add these surrounding cells to a coordinate list called Frontier

4. Iterate or Recurse through the Frontier list until it is empty.
   a. pick a random cell from Frontier. You can use weighted algorithms to pick near the front or back of the list, which lead to different styles of maze (tight and claustrophic vs long empty passages)
   b. Run function Check on the random cell. Define check (Note, this is the most complex part of the algorithm, so you may need to follow along the actual code below)
     i. get the EdgeState of the cell - sum up the cells surroundind the current cell. Empty to the north = 1, south = 2, west = 4, east = 8.
     ii. If we're not up against the side of the map, set the diagonal spaces adjacent to the input space as empty, and return false. Otherwise return true. This basically makes the maze have corners.
   c. If Check was true, Cave out the cell. Otherwise Harden the cell - turn it into a wall '#'
   d. Remove this cell from the Frontier list.

5. Once the Frontier list is emtpy, go through the entire map and change "maybe" cells ',' into empty cells '.' . Turn unknown '?' cells into walls '#'


Full Code:

private char[,] maze; //field
private List frontier;

private int height;
private int width;

private void BuildMaze()
{
 maze = new char[height, width];

 //traverse the maze and fill in unknown blocks
 for (int i = 0; i < height; i++)
 {
  for (int j = 0; j < width; j++)
  {
   maze[i, j] = '?';
  }
 }
 //carve out a random spot
 Carve(r.Next(width-1),r.Next(height-1));

 while (frontier.Count > 0)
 {
  double pos = Math.Pow(r.NextDouble(), Math.Pow(Math.E, branchrate));
  int index = (int)(pos * frontier.Count);
  Coord c = frontier[index];
  if (Check(c.x, c.y))
   Carve(c.x, c.y);
  else
   Harden(c.x, c.y);
  frontier.Remove(c);
    
 }

 for (int i = 0; i < height; i++)
 {
  for (int j = 0; j  0)
 {
  if (maze[y - 1,x ] == '?')
  {
   maze[ y - 1,x] = ',';
   frontier.Add(new Coord(x, y - 1));
  }   
 }
 if (y < height - 1)
 {
  if (maze[y + 1,x] == '?')
  {
   maze[y+ 1,x ] = ',';
   frontier.Add(new Coord(x, y + 1));
  }
 }
 if (x > 0)
 {
  if (maze[y,x - 1] == '?')
  {
   maze[y,x - 1] = ',';
   frontier.Add(new Coord(x - 1, y));
  }
 }
 if (x < width - 1)
 {
  if (maze[y,x + 1] == '?')
  {
   maze[y,x + 1] = ',';
   frontier.Add(new Coord(x + 1, y));
  }
 }
 //shuffle frontier?
 
}

private void Harden(int x, int y)
{
 maze[y,x] = '#';

}

private bool Check(int x, int y)
{
 int edgestate = 0;
 if (y > 0)
 {
  if (maze[y - 1,x ] == '.')
   edgestate += 1;
 }
 if (y < height - 1)
 {
  if (maze[ y + 1,x] == '.')
   edgestate += 2;
 }
 if (x > 0)
 {
  if (maze[y,x - 1] == '.')
   edgestate += 4;
 }
 if (x < width - 1)
 {
  if (maze[y,x + 1] == '.')
   edgestate += 8;
 }

 if (this.noDiagonals)
 {
  if (edgestate == 1)
  {
   if (y < height - 1)
   {
    if (x > 0)
    {
     if (maze[ y + 1,x - 1] == '.')
      return false;
    }
    if (x < width - 1)
    {
     if (maze[y + 1,x + 1 ] == '.')
      return false;
    }

   }
   return true;
  }
  else if (edgestate == 2)
  {
   if (y > 0)
   {
    if (x > 0)
    {
     if (maze[y - 1,x - 1 ] == '.')
      return false;
    }
    if (x < width - 1)
    {
     if (maze[ y - 1,x + 1] == '.')
      return false;
    }
   }
   return true;
  }
  else if (edgestate == 4)
  {
   if (x < width - 1)
   {
    if (y > 0)
    {
     if (maze[y - 1,x + 1 ] == '.')
      return false;
    }
    if (y < height - 1)
    {
     if (maze[ y + 1,x + 1] == '.')
      return false;
    }
   }
   return true;
  }
  else if (edgestate == 8)
  {
   if (x > 0)
   {
    if (y > 0)
    {
     if (maze[y - 1,x - 1 ] == '.')
      return false;
    }
    if (y < height - 1)
    {
     if (maze[y + 1,x - 1 ] == '.')
      return false;
    }
   }
   return true;

  }
  return false;
 }
 else
 {
  if (edgestate == 1 || edgestate == 2 || edgestate == 4 || edgestate == 8)
   return true;
  else
   return false;
 }

}

And that's it. You end up with something like this:

.#.##.#.#.#....#.#.#
....#.#.#.#.##.#....
###.#...#...####.###
#...###...#..#.#.#..
..#.#.##.#####.....#
###.#.#........###..
.#..#.##.#####...###
.#.##..#.....#.####.
....#.##.#######..#.
#.###.#...#...###...

The trouble is that the passageways are only a single tile wide or tall, which would make it very hard for our hero to navigate the game world, since he's two tiles tall! So we can scale the maze, simply by take a tile and copying it to 3 tiles to the east, south and south east. This doubles the size of the board. We can continue to double until the maze feels right - for my game it's a factor of 2, which is 4 times the size. You end up with something like this:

....########....####........####....####........########....####....########....
....########....####........####....####........########....####....########....
....########....####........####....####........########....####....########....
....########....####........####....####........########....####....########....
........................########....########........####....####........####....
........................########....########........####....####........####....
........................########....########........####....####........####....
........................########....########........####....####........####....
####################....................########............########....####....
####################....................########............########....####....
####################....................########............########....####....
####################....................########............########....####....
........................################################....########............
........................################################....########............
........................################################....########............
........................################################....########............
################....########....####....####....####............####....########
################....########....####....####....####............####....########
################....########....####....####....####............####....########
################....########....####....####....####............####....########

The world is still pretty boring, so one thing we can do is generate "rooms". These are large areas of empty space that we can later populate with platforms, elevators, traps and enemies. Generating rooms is pretty easy. Prior to building the map, select a few cells and expand them by random dimensions, changing them to type the "maybe" type ',' We don't want to completely empty them out, so the maze algorithm will still work. So now we have something like this. Better, but still not a game world:

....................########............########....####....####....####....####
########....####................############........................####........
########....####................############........................####........
########....####................############........................####........
########....####................############........................####........
....####....####....####....########............################............####
....####....####....####....########............################............####
....####....####....####....########............################............####
....####....####....####....########............################............####
....####################....################................####....####........
....####################....################................####....####........
....####################....################................####....####........
....####################....################................####....####........
....########............................####....................................
....########............................####....................................
....########............................####....................................
....########............................####....................................
........########....########....############....................................
........########....########....############....................................
........########....########....############....................................
........########....########....############....................................

The next step is to place special characters. These are tiles that will represent platforms, traps, enemies, elevators, items, powerups, etc. Once we have our fully scaled map, we can traverse through and check for certain patterns in which to place our special tile. For example, to place a platform '-', we want to be in a large empty room. So before we place a platform, check to see that the 5 spaces above and below are empty:

........................####............
........................####............
........................####............
........................####.......A....
....####................####....########
....####..............-.####....########
....####................####....########
....####................####....########
############............####............
############........-...####............
############...-........####............
############............####............
......................-.........####....
................................####..-.
................................####....
..A......A...-..................####....
############....-...........########....
############................########....
############................########....
############................########....

Lastly, we want to add some challenge and progression to our maps. We can do this with locked doors and keys. The easiest way is to generate lots of smaller maps, place a random key 'K' inside, enclose the entire thing with a wall and a single locked door as the exit 'D'. Connect all the smaller maps together, and we have a maze that requires some thinking to complete!

############################################################
#..................#............####...#............####...#
#....K.............#.....K......####...#.....K......####...#
#.A........A.......#..A.........####...#..A.........####...#
################...#########...........#########...........#
################.-.#########...........#########...........#
################...#########.-.........#########.-.........#
################...#########...........#########...........#
#..................D............####...D............####...#
#..................#............####...#............####...#
#..................#............####...#............####...#
#.A.............A..#...A........####...#...A........####...#
########....################....################....########
########....################....################....########
########....################.-..################.-..########
########....################....################....########
#..................#...................#...................#
#..................#...................#...................#
#..................#...................#...................#
############################################################

The fun thing about maze generation is that the possibilities are endless. You can instantly generate a new world to explore and jump around in.



Next time I'm going to look into minimaps, and "fog of war". We don't want to be able to spoil the entire maze in one glance!