How did Rogue Generate its Random Dungeons?

How did Rogue’s generation work? I dug into the C code to find out. If you follow this article you’ll be able to build a Rogue-style dungeon generator yourself.

Michael Toy and Glenn Wichman were both 19 when they built Rogue’s dungeon generator. As Wichman recalls in 2019 “We landed on it early because we weren’t smart enough to know how to do anything clever”, however this procedural generator defined a genre the - roguelike - the computer could now create maps straight from a Dungeons and Dragons campaign.

High Level Algorithm

Rogue’s algorithm works like this:

1. Divide the level into nine equally sized rectangle cells. Think a tic-tac-toe grid.
2. Randomly declare up to 3 cells as “gone”; meaning no room can be built there.
3. For each valid cell, place a room that fits in the cell (allowing for a one-character border on the edges).
4. Link up the cells with corridors.

Using Rogue’s code the room distribution from this is:

So Rogue’s levels are limited in terms of room count and how varied the levels can be.

Properties

This algorithm isn’t overly complicated, it’s fast and produces reasonable-looking dungeons. However every level is recognizably “nine-ish boxes on a grid”. These are the properties of the levels the generator makes:

• Maximum of nine rooms, with a minimum of six.
• No room can be larger than 1/9th of the level space.
• Rooms never overlap, touch or share a wall.
• Rooms are always axis-aligned rectangles.
• All rooms are linked by one or more corridors.
• Corridors link adjacent cells.
• Each single corridor can have at most two bends.
• Empty cells can give rise to junctions and dead-end corridors.
• Doors mark every corridor / room meeting point - there are no open doorways here.

This algorithm could be generalised to bigger levels pretty easily, though I think the grid would start to become more and more apparent. That said, it’s a good starting point for your own generator explorations.

Step-by-Step

Details time. Let’s go through how to implement this. We won’t use Rogue’s code directly because it’s quite terse C that needs a certain level of familiarity to read easily. Instead we’ll use a high-level C#-ish type language to cover how it’s put together.

The Field

Rogue was a terminal game. The terminal had a fixed size of 80 columns by 24 lines. If we used x and y notation we might say X: 80 by Y: 24. Each of these little cells can contain any ASCII character.

Let’s start with an abstraction called Field to describe the terminal-sized workspace we’ll build in.

1Field field = new Field(80, 24);

This is all pseudo-code and we can assume any useful functions and properties we need already exist. The only requirement for the pseudo-code is that it’s easy to read and understand, so it can easily be translated to your programming language of choice.

This field is divided into a grid with each cell being X: 26 by Y: 8, so we’re going to imagine these areas already exist in an array field.cells and in named fields field.topLeftCell, field.topMidCell, field.topRightCell and so on.

The top left address of the field is X: 0, Y: 0.

1print(field.topLeft) -> 0,02print(field.topLeftCell.topLeft) -> 0,034print(field.cellWidth) -> 265print(field.cellHeight) -> 8678print(field.botRight) -> X: 79, Y: 239print(field.botRightCell.botRight) -> X: 77, Y: 23

One thing to note here, the bottom right cell isn’t flush with the field’s bottom right. This is because of integer division. We want to break these 80 cells into 3 parts = 26.67 but you can’t have 0.67 of an ASCII character, so we round down to 26.

The Field and Cells Visualised

Here’s the terminal workspace split into cells and with the leftover cells on the right marked in grey.

Cell Death

In order to generate more interesting levels up to three cells may be chosen to be marked as “gone” i.e. no room can be placed there. Here’s the code that follows how Rogue did it:

1goneCount = random(0, 4); // 0-323for i in goneCount:4  cell = pick(field.cells, x => x.canPlaceRoom);   // can't pick the same cell twice5  cell.canPlaceRoom = false;

Cells without rooms may still have corridors pass through them.

Room Placement

Rogue chooses the room size before it tries to place the room. Rooms are a random size up to one less than the cell width and height. So

1Room room;2room.width = random(4, field.cellWidth);   // 4-253room.height = random(4, field.cellHeight); // 4-7

The smallest possible room is 4x4, which would give you this:

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

and the largest room is one tile less than the full grid cell size.

Once the size has been decided, it’s time to determine the position and this is done by working out how much difference there is between the room and its parent cell so

1slackX = field.cellWidth - room.width;2slackY = field.cellHeight - room.height;

This value tells us how much the room can be moved around inside the parent without going out of bounds. To randomly position the room within the cell we use a random offset. All rooms are smaller than the cell so we know it can fit in the top left corner, but how much smaller it is determines how much slack we have to move it about within that cell.

Room Slack

The small interactive widget illustrates the idea of slack. From this you should be able to imagine how a room would be randomly positioned in a cell.

Rogue has additional restrictions about where a room can be placed. Here’s Rogue’s room placement code:

1room.x = cell.left + 1 + random(0, slackX); // 0 to slackX-12room.y = cell.top + random(0, slackY);      // 0 to slackY-1

In Rogue the leftmost column of the cell is always kept clear. To enforce this there’s +1 that pushes the room one column right, leaving an empty gutter on the left. The rooms right side can’t breach the cells boundary because the maximum the random number can be is slackX - 1.

On the vertical position the last row of the cell is always kept clear. Together these rules ensure that no two rooms can share a wall and there’s always some space for a corridor. The last row being clear is enforced the same way: you can never fully use the entire vertical slack.

Guaranteed Gutters

The clear left column and bottom row of each cell forms gutters between the cells as shown below:

These guaranteed borders of free space make it easier to add corridors later.

Here’s a map with all the rooms at max size. Rogue reserves the top line of the terminal for messages - “The Hobgoblin hits you etc.”

THIS IS THE MESSAGE LINE
 ######################### ######################### #########################
 #.......................# #.......................# #.......................#
 #.......................# #.......................# #.......................#
 #.......................# #.......................# #.......................#
 #.......................# #.......................# #.......................#
 ######################### ######################### #########################

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

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

That’s the room placement in theory. Now let’s write some pseudo-code to implement it.

1for i in field.cells.len:2  cell = field.cells[i];34  if !cell.canPlaceRoom:5    continue;67  Room room;8  room.width = random(4, field.cellWidth);   // 4-259  room.height = random(4, field.cellHeight); // 4-71011  slackX = field.cellWidth - room.width;12  slackY = field.cellHeight - room.height;1314  offsetX = random(0, slackX); // 0 to slackX-115  offsetY = random(0, slackY); // 0 to slackY-11617  room.x = cell.left + 1 + offsetX;   // +1 keeps a leftmost gutter in the cell18  room.y = cell.top      + offsetY;   // offsetY's max is slackY-1, keeps a bottommost gutter in the cell1920  // The top line of the terminal is used for message text21  // This needs to be kept clear.22  if room.y == 0:23    room.y = 1;24    room.height = min(room.height, field.cellHeight - 2);2526  field.AddRoom(room);

And that’s it! At this point this code, if it were executable, could generate random rooms in each valid cell with a guaranteed gutter. Next is to move on to connecting these rooms up.

Passages

The first thing we do is set up random connections between the cells.

1. Pick a random cell. Mark it connected.
2. Find a connected cell that sits next to one that isn’t.
3. Link them, and mark the new cell connected.
4. Repeat until every cell is connected.

This will result in a link graph that has at least all the cells linked to each other and additional links on top of that.

1List<Link> CreateCellLinks(cellList):2    links = new List<Link>();34    connected   = [ pick(cellList) ];                  // seed the network with one random cell5    unconnected = cellList.Except(connected);          // every other cell67    // 1. Grow one network until no cell is left out8    while !unconnected.IsEmpty():9        cellA = pick(connected);10        unconnectedNeighbours = Neighbours(cellA).Where(x => unconnected.Contains(x));11        cellB = pick(unconnectedNeighbours);1213        if cellB != null:14            links.Add(new Link(cellA, cellB));15            connected.Add(cellB);16            unconnected.Remove(cellB);1718    // 2. Add a few extra links so the map has loops, not just one path19    extraLinks = random(0, 5); // 0-420    for i in extraLinks:21        cellA = pick(cellList);22        unlinkedNeighbours = Neighbours(cellA)23            .Where(x => !LinkExistsBetween(links, cellA, x));24        cellB = pick(unlinkedNeighbours);2526        if cellB != null:27            links.Add(new Link(cellA, cellB));2829    return links;

Digging Passages

For each of the links between cells with rooms, the following steps are taken:

1. If one room is left of the other, then:
   • a: Call that roomA and find a random start point on its rightmost wall.
   • b: The other room is roomB. Find the finish point on its leftmost wall.
   • c: Start digging right.
2. If one room is above the other, then:
   • a: Call that roomA and find a random start point on its bottommost wall.
   • b: The other room is roomB. Find the finish point on its topmost wall.
   • c: Start digging down.
3. Partway along, stop at a random turn point and dig sideways until lined up with the finish point.
4. Keep digging in the original direction until the finish point is reached.

Not all cells have rooms. When there’s an empty cell, a random point within it is taken as the link point.

Digging Corridors

How the rooms are oriented to each other is all done at the grid-cell level. If one room is in grid x:0, y:0 and the next is in x:1, y:0, then they’re on the same row and considered next to each other.

1DigCorridor(link):2    (c1, c2) = link.cells;34    vec2 start, end, digDir, turnDir;5    int  axisDistance;6    int  turnLength;   // distance needed to line up the doors78    // LinkPoint gives a random spot on the named wall of the cell's room,9    // or a random point inside the cell if the cell is gone and has no room.10    if c1.y == c2.y:11        (cellA, cellB) = SortByCellX(c1, c2);12        start        = LinkPoint(cellA, vec2.right);13        end          = LinkPoint(cellB, vec2.left);14        digDir       = vec2.right;15        turnDir      = end.y < start.y ? vec2.up : vec2.down;16        axisDistance = end.x - start.x;17        turnLength   = abs(end.y - start.y);18    else:19        (cellA, cellB) = SortByCellY(c1, c2);20        start        = LinkPoint(cellA, vec2.down);21        end          = LinkPoint(cellB, vec2.up);22        digDir       = vec2.down;23        turnDir      = end.x < start.x ? vec2.left : vec2.right;24        axisDistance = end.y - start.y;25        turnLength   = abs(end.x - start.x);2627    outLength = random(1, axisDistance); // 1 to axisDistance-128    inLength  = axisDistance - outLength;2930    cursor = start;31    cursor = Dig(cursor, digDir,  outLength);32    cursor = Dig(cursor, turnDir, turnLength);33    cursor = Dig(cursor, digDir,  inLength);3435    PlaceDoor(cellA, start);   // a gone cell has no room, so it gets a corridor tile36    PlaceDoor(cellB, end);     // instead of a door

Bringing It All Together

Here’s the dungeon generator, with all the steps animated to give a better idea of how all the pieces fit together.

You should now have a good grasp of how Rogue generated its levels and be able to implement a simple generator. There’s a C# implementation I’ve made available here - Rogue Dungeon Gen.

Here’s a screenshot of a real Rogue level with monsters and the player.

You may note the walls are different. In this article I used the more modern roguelike glyphs for walls - all # characters, which make things a little simpler.

“[what] We were never happy with was the way rooms were laid out on the dungeon level - always between 6 and 9 rooms in a tic-tac-toe pattern. We wanted to have the levels much more free-form, but we just couldn’t figure out how to do it.”

Glenn Wichman, 2002

Hack, the first roguelike, did figure out how to have more free-form levels and if you’re curious how then check this page about its level generator.