How did Rogue Generate its Random Dungeons?

The book<br>Make your game.

How to Make an RPG takes you from zero to a finished game.

Get the book $46 →

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.

HTML 5 figure.<br>If you're seeing this, your browser may not support HTML5.

Generate Dungeon

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:

Divide the level into nine equally sized rectangle cells. Think a tic-tac-toe grid.

Randomly declare up to 3 cells as “gone”; meaning no room can be built there.

For each valid cell, place a room that fits in the cell (allowing for a one-character border on the edges).

Link up the cells with corridors.

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

Rogue leaves between zero and three cells empty and the four possible room counts are equally likely.

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.

The C source has code that scales the map to the dimensions of the terminal but it still uses the same 9 cell grid.<br>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.

CSHARPCopy

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.

CSHARPCopy

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.

HTML 5 figure.<br>If you're seeing this, your browser may not support HTML5.

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:

In the Rogue C code this is written as left_out = rnd(4);. See here.

CSHARPCopy

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

CSHARPCopy

1Room room;2room.width = random(4, field.cellWidth);...