February 04, 2005

The Ramble Chronicles: Maze Generation 2

In Maze Generation 1 I discussed how to generate a rectangular "perfect" maze using the recursive backtracker algorithm, and gave a detailed implementation in Tcl. Here's a maze I generated in this way:

Perfect mazes can be fun to solve, but they really don't make very good dungeon levels. A perfect maze can be described as a tree: there's exactly one path from any given cell to any other cell, and there are no cycles--that is, you can't walk in a circle anywhere in the maze, and there are usually lots of dead ends, some of which are so short they're just annoying. On top of that, two cells on opposite sides of a wall might end up being quite a long walk from each other. This is frustrating if a detection spell has shown you a treasure hiding on the other side of the wall--which can be a good thing, actually, but not all the time. The dungeon's going to be frustrating enough, what with fierce beasts and horrible monsters and all, and so the dungeon itself should usually be just a bit friendlier, with fewer dead ends, especially short ones, and a fair number of cycles. So in this essay I'm going to describe several operations that can be performed on a perfect maze to make it more suitable for use as a dungeon level.

Sparsification: Building the maze involved carving out new rooms and adding them to the maze one by one. Sparsification--which I suppose could also be called pruning, though I like the word "sparsify"--is the process of removing all of the dead-end cells from the maze. The process can be repeated as many times as desired. The result is a maze with few short dead ends and many longy twisty passages. The basic algorithm is as follows:

  • Do the following n times:
    • For each cell {i j} in the maze,
      • Add the cell to the Dead Ends list if it's a dead end, that is, if it has exactly one wall removed.
    • For each cell {i j} on the Dead Ends list,
      • Restore the missing wall, thus removing the cell from the maze.

You can also make the removal conditional, e.g., add the dead end cell to the Dead Ends list only 25% of the time.

Here are two views of the same maze, first as it was originally generated, and next after being sparsified twice. The effect on a larger maze is even more dramatic.

Connectification: Sparsification eliminates some short dead ends, and adds some dead space, which gives the maze an interesting texture; however, it doesn't add any cycles. For that we want to connectify the maze.

Like sparsification, connectification focuses on the dead ends in the maze; but instead of closing them off, it instead removes one of the three closed walls, connecting the room to another part of the maze. I find I get the best results if I usually pick the wall opposite the entrance to the cell. If that wall can't be used, then I pick one of the other walls randomly. The algorithm is as follows:

  • For each cell in the maze,
    • If the cell isn't a dead end, go on to the next cell.
    • Examine the three closed walls, and determine which of the three could be opened. A wall can be opened if:
      • It's not on the edge of the maze.
      • The cell on the other side is connected to the maze. (If we've sparsified, it might not be.)
    • Of the three, if the opposite wall from the entrance can be opened, open it.
    • Otherwise, randomly pick a wall that can be opened, if any, and open it.
    • If no walls could be opened (again, this is quite possible in a sparsified maze) leave it as a dead end.

Here are two views of a maze, first as it was originally generated, and then connectified. As you'll see, it's much easier to get around in, but still nicely twisty.

As I hinted above, you can get interesting results by combining the two operations. Here are before and after shots of a maze which was sparsified twice and then connectified:

To my eye, that's really quite nice. Lots of long, snaky corridors that feed into one another, and one big dead-end at the lower left.

Now, if you've been paying attention there's a question that should have occurred to you; indeed, it should have occurred to you in my previous essay on mazes as well. The walls in these mazes I've been showing you are mere lines, separating square cells. But Ramble is a tile-based game--walls are represented by wall-tiles, which are necessarily one tile wide. In order to use one of these mazes as a dungeon level, then, I need to somehow convert it from a maze to a tile map.

As I explained in Maze Generation 1, a maze is a matrix of integers; the value in each cell indicates which walls have been opened. A tile map is also a matrix, but in this case each cell contains a value that indicates what kind of tile it is.

Now, there are many ways in which I could generate a tile map from any of the mazes I've shown in this essay; the most obvious is to add a floor tile for each room in the maze, a row of wall tiles for each horizontal wall in the maze, and a column of wall tiles for each vertical wall. If the original maze had size m*n, the new tile map will have size (2m+1)*(2n+1). The mazes shown above were all 10*20; the resulting tile map would then be 21*41.

Just to make it clearer, here's a picture of a tile map that's equivalent to a blank maze, that is, a maze in which none of the walls have been removed. As you can see, each room is separated from each adjacent room by a wall that's one tile wide:

The algorithm for converting a maze to a tile map is then as follows:

  • Initialize the tile map to all wall tiles.
  • For each cell in the maze,
    • Identify the corresponding cell in the tile map.
    • Put a floor tile in that room.
    • If the maze cell is open to the east, put a floor tile in the tile map cell to the east.
    • If the maze cell is open to the south, put a floor tile in the tile map cell to the south.

It's that easy. Here's a picture of a maze, sparsified twice and connectified, and the corresponding tile map:

Now that's just plain lovely, and a delight to wander about in. In a larger maze I'd probably want to add some large rectangular open spaces, just to connect things up even more.

I've got individual Tcl procs for each of these operations, naturally, but mostly I use a single command called tilemaze, which generates the maze and then modifies it as desired. It looks like this:

tilemaze M N ?options?

Where M and N are the number of rows and columns in the finished tile map (both must be odd), and the options allow you to:

  • Specify the specific wall and floor tiles to use.
  • Specify whether the tile map has a border of wall tiles or not.
  • How many times the maze should be sparsified.
  • Whether the maze should be connectified.
  • How many "plazas"--open spaces--should be created.
  • The minimum and maximum plaza size, in rows and columns.
  • Whether the maze should have doors in it.

The implementation of that last option is a bit of a hack, but it effectively what happens is that each wall removed during connectification gets turned into a door in the tile map.

And then when I actually want to generate a dungeon level, I call tilemaze with random options:

  • The wall tile is usually "rockwall", but 25% of the time it will be "water". (The tile maps shown above use "rockwall".)
  • The floor tile is usually "tilefloor", a hexagonal pattern, but 25% of the time it's "sand". (The tilemaps shown above use "sand".)
  • 20% of the time, the maze is sparsified twice, and 20% of the time its sparsified four times.

  • The maze is connectified two-thirds of the time if there are no doors, and always if there are doors.
  • There are doors 25% of the time.

Every so often I modify these parameters a bit, but I find that they generate a nice wide range of tile maps. Water maps are especially interesting, because although water blocks movement, it doesn't block sight.

Did I mention that I've implemented incomplete visibility in the current development version?

Posted by Will Duquette at February 4, 2005 08:16 PM