Motivation

Treasure of Tarmin is one of my favorite Intellivision games, it's something I still play semi-frequently today. You may know it by the title "Minotaur" which is how it appears on Intellivision collections due to licensing reasons. It's infinitely replayable because every game is different. It relies on randomly generated dungeons with randomly placed items and enemies.

The dungeons themselves are a 12x12 grid with a fixed perimeter. After mapping out a level for the first time I was surprised to find that every room in the grid can be accessed:

Yes, I created that in a spreadsheet program. Also please note that I intentionally left the doors as open spaces to make this map easier to understand.

Going through and mapping a level got me thinking - what would it take to generate a similar random maze?

Breaking it down

I suppose a good place to start would be to decompose this into collections of rooms and walls:

So what we have here is:

[12,12] array for room data

[12,13] array of x-walls

[13,12] array of y-walls

We could also use a [12,26] array for the walls. I never took linear algebra in college but was forced to learn it over a weekend when I made the mistake of taking a course that had it as a prerequisite. I didn't think they really meant it but I was wrong. So I get less of a headache picturing this as two arrays than trying to mesh them together into one. It's easy to understand why many early game developers were math majors. There's no memory difference in using either approach so it doesn't really matter.

So now that I'm done over-analysing that, there's the much more challenging part of how to randomly generate a dungeon where every space is accessible.

I have to assume that rather than randomly generate everything they mashed together a set of fixed rooms or patterns. It doesn't take long to see rooms repeat in Treasure of Tarmin and this would also get around the problem of orphaned rooms.

The map generation algorithm would go something like this:

1) Randomly select template for level

2) Randomly select pre-made maps for each segment of the template

So in this example, the top left corner is a 5x5 grid. A map to fill it would need 60 walls. They also may have just stored entire maps at 312 walls each. A wall has four possible states (getting to that later) so each needs 2 bits. So one byte could store 4 walls. Plus the outer perimeter is fixed so when all is said and done an entire map only uses a lean 66 bytes of data. Treasure of Tarmin was a whopping (for the time) 16K so I'm thinking a small chunk of that was to store maps one way or another. Maybe I should have disassembled the ROM before starting this endeavor.

And yes, I know, there are actually 5 types of doors but one is rarely used and only appears when there's a specific treasure behind it. However, if there were 5 different types of walls then 3 bytes are needed which adds a lot of dead space since 99% of the time only 2 are used. So I figure this was handled as a special case to minimize memory use. Sometimes I think I was born 10 years later than I should I have been because I bet I would have been an awesome assembly programmer. Anyway, yeah, I guess we don't have to worry about all these minute optimizations since we'll be using some fancy new interpreted language.

Generating the maze

So regardless of the original implementation, I'm going to look at a few ideas for generating random maps. For these experiments I'll be using C# because it's the most fun language to program in that's not called "Visual Basic 6". If this ever turns into a real project I'll move it to Android which is not nearly as much fun for experimental ideas.

Let's first define the five possible wall states:

    enum Wall {Solid, Clear, Door, HiddenDoor, EnemyDoor}

As noted before, the outer perimeter is fixed so that logic looks a little something like this:

x[*,0], x[*,12] = Solid

x[(1-2,4-7,9-10),1], x[(1-2,4-7,9-10),11] = Solid

x[(0,3,8,11),1], x[(0,3,8,11),11] = Clear | Door | HiddenDoor

y[0,*], y[12,*] = Solid

y[(1-2,4-7,9-10),1], y[(1-2,4-7,9-10),11] = Solid

y[1,(0,3,8,11)], y[11,(0,3,8,11)] = Clear | Door | HiddenDoor

Here's the code more or less:

private void createPerimeter() 
{
    //top and bottom border
    for(int xColumn=0;xColumn<=11;xColumn++) 
    {
      xWalls[xColumn,0]=Wall.Solid;
      xWalls[xColumn,12]=Wall.Solid;
      rooms[xColumn,0].reachable=true;
      rooms[xColumn,11].reachable=true;
    }
    //open spaces in the perimeter
    xWalls[0,1]=Wall.Clear;
    xWalls[1,1]=Wall.Solid;
    xWalls[2,1]=Wall.Solid;
    xWalls[3,1]=getRandomOpenWall();
[... and so on  ...]

Here's what it looks like using a rather crude PictureBox and Pen implementation. "Rather crude" is the best way to describe my artistic abilities in general:

The gray lines are open spaces, black lines are solid walls, blue lines are regular doors, and green lines are hidden doors.

In addition to the fixed perimeter there are a couple other rules for generating this random dungeon:

1) Every room must be reachable. By default the map has 52 reachable rooms so a quick test would be to say that a room is reachable if it has an at least one open wall to another reachable room.

2) Corollary to the first rule, a room must have between 1-3 walls. The maximum of 3 is obvious. The minimum of 1 is there to avoid wide open rooms since we're trying to build a maze comprised of narrow corridors.

So let's look at a few ideas for generating these random walls. If this sounds a little like a steam of consciousness it's because it is to a degree. I'm not 100% sure what's the best way to accomplish this. My first inclination is to go room by room and randomly add 1-3 walls then do a sweep of the map to correct any orphaned rooms.

//generate random walls
for(int x=1;x<=9;x++) 
{
  for(int y=1;y<=9;y++) 
  {
    //count the current walls for this room
    int wallCount=0;
    if(xWalls[x,y]!=Wall.Clear) { wallCount++; }
    if(xWalls[x+1,y]!=Wall.Clear) { wallCount++; }
    if(yWalls[x,y]!=Wall.Clear) { wallCount++; }
    if(yWalls[x,y+1]!=Wall.Clear) { wallCount++; }
    int targetWallCount=rand.Next(1,4);
    int wallsToGenerate=targetWallCount-wallCount;
    while(wallsToGenerate>0) 
    {
      bool setWall=false;
      while(setWall==false) 
      {
        int wallDirection=rand.Next(0,4);
        switch(wallDirection) 
        {
          case 0://north 
            {
              if(xWalls[x,y]==Wall.Clear) 
              {
                xWalls[x,y]=Wall.Solid;
                setWall=true;
              }
              break;
            }
          [... repeat for each direction ...]:
        }
      }
      wallsToGenerate--;
    }
  }
}

That approach works but leaves a couple problem areas:

So there are three things to correct - open spaces, disconnected walls, and blocked rooms. All are relatively straightforward I hope. Let's start with these open spaces, by open space I'm referring to any vertice that doesn't have a wall touching it. We're going to correct that by looking for all open x-walls then checking if they are open on all directions at either end. If we find one, randomly put a wall in one of the four open spaces.

//fix axes without any walls (yes, axes is the plural form of axis)
for(int xColumn=1;xColumn<=9;xColumn++) 
{
  for(int xRow=2;xRow<=10;xRow++) 
  {
    if(
      (xWalls[xColumn,xRow]==Wall.Clear)&&
      (xWalls[xColumn+1,xRow]==Wall.Clear)&&
      (yWalls[xColumn+1,xRow-1]==Wall.Clear)&&
      (yWalls[xColumn+1,xRow]==Wall.Clear)) 
    { 
      //randomly set one of the walls to solid
      int wallToSet=rand.Next(0,4);
      switch(wallToSet) 
      {
        case 0:
          {
            xWalls[xColumn,xRow]=Wall.Solid;
            break;
          }
        case 1:
          {
            xWalls[xColumn+1,xRow]=Wall.Solid;
            break;
          }
        case 2:
          {
            yWalls[xColumn+1,xRow-1]=Wall.Solid;
            break;
          }
        case 3:
          {
            yWalls[xColumn+1,xRow]=Wall.Solid;
            break;
          }
      }
      
    }
  }
}

After doing that we need to address the next problem - disconnected walls:

By "disconnected" I mean an x-wall, or series of connected x-walls, that do not join a y-wall at any point and vice versa. I suppose we could get by just fine not doing this but I think it takes away from the mazeiness of the map. Correcting this is a matter of scanning each continuous x-wall to see if it meets a y-wall at any point then repeating the process for all y-walls.

//fix xWalls that never connect to yWalls
for(int xRow=2;xRow<=10;xRow++) 
{
  int xColumn=0;
  bool wall=false;
  int wallStart=-1;
  int wallEnd=-1;
  while(xColumn<11) 
  {
    if(wall)
    {
      //check if the wall has ended
      if(xWalls[xColumn,xRow]==Wall.Clear)
      {
        wallEnd=xColumn-1;
        wall=false;
        //now check if this call connects to a yWall
        bool yConnect=false;
        int wallIndex=wallStart;
        while((wallIndex<=wallEnd)&&(yConnect==false)) 
        {
          if(
            (yWalls[wallIndex,xRow]!=Wall.Clear)||
            (yWalls[wallIndex,xRow-1]!=Wall.Clear)||
            (yWalls[wallIndex+1,xRow]!=Wall.Clear)||
            (yWalls[wallIndex+1,xRow-1]!=Wall.Clear))
          {
            yConnect=true;
          }
          else 
          {
            wallIndex++;
          }
        }
        if(yConnect==false) 
        {
          int yWallX=rand.Next(wallStart,wallEnd+2);
          int yWallY=rand.Next(xRow-1,xRow+1);
          yWalls[yWallX,yWallY]=Wall.Solid;
        }
      }
    }
    else 
    {
      /check if a new wall is starting
      if(xWalls[xColumn,xRow]!=Wall.Clear)
      {
        wallStart=xColumn;
        wall=true;
      }
    }
    xColumn++;
  }
}
[... repeat for yWalls ...]

Once that's all done we're left with fixing all the blocked rooms:

The best thing I can think of is something that goes a little bit like this:

private void fixBlockedRooms()
{
  ArrayList crawlQueue=new ArrayList();
  ArrayList blockedQueue=new ArrayList();
  //initialize the crawl and blocked queues
  [... loop through all rooms ...]
  //make sure something stupid didn't happen
  if(crawlQueue.Count<1) 
  {
    throw(new Exception("fixBlockedRooms() -> at least one room needs to be reachable!"));
  }
  //keep working until all blocked rooms are covered
  while(blockedQueue.Count>0) 
  {
    //crawl all open rooms
    while(crawlQueue.Count>0)
    {
      [... read and remove first item from queue ...]
      //add open, uncrawled neighbors to the queue
      //north
      if((y>0)&&(xWalls[x,y]!=Wall.Solid))
      {
        if(!rooms[x,y-1].reachable) 
        {
          rooms[x,y-1].reachable=true;
          [... add to crawl queue, remove from blocked queue ...]
        }
      }
      [... repeat for all other directions ...]
    }
    //is there anything left to unblock?
    if(blockedQueue.Count>0) 
    {
      //warning in advance - this is not a particularly efficient algorithm but it is really random
      while(crawlQueue.Count==0) 
      { 
        [... pick a random room ...]
        //pick a random wall to open
        int direction=rand.Next(0,3);
        switch(direction) 
        {
          case 0: //north
            {
              if((y>1)&&(xWalls[x,y]==Wall.Solid))
              {
                xWalls[x,y]=getRandomDoor();
              }
              break;
            }
            [... repeat for all other directions ...]
        }
        //did this open up the room?
        if(isRoomReachable(x,y)) 
        {
          rooms[x,y].reachable=true;
          [... add to crawl queue, remove from blocked queue ...]
        }
      }
    }
  }
}

And here's how a map looks with all the blocked rooms fixed and some minor color adjustments:

So that's it for now. If I work on this again I think I'll go after randomly placed items.

Related