The Dungeon

Today I opened a git for the project at https://github.com/gbush235711/elm-telengard.  To view the interactive map, click here.

Probably the most interesting feature of Telengard is its procedurally-generated map.

It is huge.  Compared to other games of its time like Wizardry and Ultima whose dungeon levels were usually about 20x20, Telengard features 50 levels of 200x200 dungeon maps for a total of 2 million rooms.  Assuming one byte of storage per room, that is closing in on 2 MB of storage needed to hold the map.  That would have required about 12 floppy disks and a whole lot of load time and disk swapping during the game.

This is not necessary, though, since the map is not stored anywhere.  Instead, it is generated by an algorithm.

The inputs are an x, y and z coordinate, where the x and y coordinates represent a location on a particular level of the dungeon and the z coordinate is depth in the dungeon.  Moving to the right on the screen increases the x coordinate (I'll call this east) and moving down on the screen increases the y coordinate (I'll call this south).  Descending a stairway increases the z coordinate.  New players begin their journey at (25, 13, 1) and are restricted to the cuboid with corners at (1, 1, 1) and (200, 200, 50).

From a room's coordinates a value is calculated that can be used to determine what the room's boundaries are and what feature it contains.

q = x * xo + y * yo + z * zo + (x + xo) * (y + yo) * (z + zo)

where xo = 1.6915, yo = 1.4278 and zo = 1.2462.

The basic idea behind the rest of the algorithm is that the fractional part of q will vary in unpredictable seeming ways as the inputs change.

So to continue, the fractional part of q is multiplied by 4694 and truncated, resulting in a 13-bit positive integer from 0 to 4693.

h = floor(frac(q) * 4694)

The lowest order bits determine what the north and west boundaries are (the south and east boundaries are just the north and west boundaries of the adjacent rooms).  The highest order bits are used to determine if a feature is present in the room.

12 | 11 | 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0
     feature?        |    unused     |  west | north

00 = Empty
01 = Empty
10 = Door
11 = Wall

If the feature field is zero or > 5, then there is no feature in the room.  Otherwise q is used again to determine what the feature is.

ft = floor(frac(10 * q) * 15) + 1

This generates a number between 1 and 15 which is decoded as follows:

1 = Elevator
2 = Pit
3 = Teleporter
4 = Stairway down
5 = Altar
6 = Fountain
7 = Gray misty cube
8 = Throne
9 = Small box with buttons
10 = Elevator
11 = Pit
12 = Teleporter
13 = Stairway down
14 = Altar
15 = Fountain

Notice that cubes, thrones and boxes only occur once while the others occur twice, which will make them about half as common.

This is not quite the end of the story.  The room still needs some fix-up to match up and down staircases between levels and handle the edges of the dungeon cuboid.

West walls are added to all rooms on columns 1 and 201, and north walls are added to all rooms on rows 1 and 201.  This will effectively create a square wall surrounding the user-accessible area between (1, 1, z) and (200, 200, z).  (The west walls at (201, y, z) are (200, y, z)'s east walls and the north walls at (x, 201, z) are (x, 200, z)'s south walls.)

For dungeon levels beneath level 1, the next level up at the same (x, y) is checked for a stairway down.  If it exists, then the room's feature will be be overwritten with a stairway up so it matches.  The exception is if the room's feature is a stairway down.  In that case its feature will be a stairway that goes both up and down.

On dungeon level 1, all elevators are converted to stairways up.  (And these are the only stairways up on level 1, since no linking with stairways down on the higher level is done on level 1).

On dungeon level 50, all stairways down are removed and pits are converted to elevators.

Most of the dungeon is varied in random-seeming ways, but the algorithm does have some patterns that appear.  In particular, some rows and columns can have long stretches of the same feature.  Check out this area of the level 4 map, for instance:

Both the row and column here continue across the map with long stretches of repeated features.  Others can be found like this.  Try finding some like this using my interactive map if you want.

Next up, I will probably implement the movement and line-of-sight rules in order to allow a hero to explore the dungeon, but with no monsters or treasure yet (awwwww....).