Several computer games rely on random map generators to create worlds for the player to explore. Apart from providing a near infinite source of new content for the player, random map generators can also be used to reduce the development time needed for a game. Why spend weeks designing levels yourself if your computer can do it for you?
 
This article will discuss a few different games that use randomly generated maps, and how those maps are used. I'll also go into detail about the (relatively simple) map generator I wrote for one of my own games.
 

Rogue

Rogue 3.6

Rogue is perhaps one of the earliest and well-known examples of random map generators (beyond simple maze games). Rogue was one of the first dungeon crawling games, and it used a random map generator to generate each floor of the dungeon as the player descends. Using ASCII graphics, each level was 80x21 in size, the perfect size for an 80-column screen. Each level of the dungeon contains a series of rooms connected by passageways. Monsters and items are also placed into the map by the generator. As the player descends deeper, the weaker monsters such as rats are replaced with tougher monsters such as dragons.
 
The appearance of important items such as magic scrolls is also randomized at the start of each game, so that the player is forced to experiment with them if he wants to know what they are. This ensures that each new game is unique and different from the last, helping to increase the difficulty of the challenge of reaching the bottom of the dungeon, stealing the treasure, and escaping back to the surface alive.

Elite

Elite local map

Elite is perhaps the second oldest and well-known example of random map generation. Although the layout of the Elite galaxies is identical each time you play, this doesn't change the fact that it was all generated by a computer (see here). As the game loads, a map generator using a fixed seed is used to generate the locations and types of the solar systems. This algorithm was used for several reasons - not only did it save important development time, but it also helped to give the world a 'natural' and 'random' feel that would have been almost impossible to obtain by hand. I suspect that memory constraints also played an important role - being able to generate galaxies on-the-fly would free up valuable bytes, and using an algorithm as opposed to pre-generated data would also allow the game to run without tape or disk access once fully loaded.
 
Many other space-based games use or used random map generators, including Exodus (Each time you start a new game), and the MMORPG EVE Online (When the initial layout and content of the galaxy was generated, see here).

Strategy games

SimCity terrain

Real-time and turn-based strategy games also take advantage of random map generators. For example, SimCity games use a random terrain generator to create the initial landscape when you start a new city, and the Heroes of Might and Magic 2 level editor can generate a fully random map for immediate play (Although it is unlikely to be well-balanced for multiplayer).

First person shooters

A simple Slige level

With the advent of Doom and Quake, attempts were made to produce map generators for first person shooters. With a more freeform environment of polygons and surfaces (as opposed to a regular grid of map tiles, or fairly arbitrary coordinates in space), more advanced algorithms were required. Not only do the maps need to be valid, but they also needed to look pretty, and be possible to complete (e.g. enough health and ammo for the player, any locked doors must have an accessible key, and all corridors must be wide enough for the player to fit through).
 
Slige is a good example of a map generator for Doom. As input it reads configuration files that describe the basic texture groups and level architecture, and as output it will produce a random map with the right amounts of monsters, weapons, health and ammo to provide a level of difficulty appropriate to the difficulty level the player chooses when starting the game.

An example

I'll now take you through the operation of the map generator that's currently in use for my in-progress game 'GAIO'. The requirements for the generator were fairly simple - fill a 2D grid with a maze of rooms and corridors, in the style of a gargantuan spaceship. As with most algorithms, there were two basic approaches to choose between - top-down or bottom-up. Top-down would involve starting with one big room, and then subdividing it into smaller rooms, until a certain limit is reached. Bottom-up would involve starting with a regular size room and adding regular size corridors and rooms to the edges, until the grid is filled. To ensure that the entire grid is filled, and to minimise potential backtracking in the algorithm, I went for the top-down approach.

The anatomy of a room

At the most basic level, a room in GAIO is just a list of rectangles. These rectangles must all touch each other (Otherwise it would be two rooms and not one). The game itself makes no distinction between a room and a corridor - the player will make that distinction himself when he sees the shape of the room in the game. Initially each room is just a single rectangle, but the map generator will make them into more interesting shapes by joining some of the adjacent rooms together.
 
The game also maintains a list of edges. An edge is simply the wall that seperates one room from another (Or, more accurately, a wall that seperates one rectangle in one room from a rectangle in another room). Each edge has a 'type' - it can be either a solid wall, a wall with an opening, or a wall with a door. The door can either be a regular door, or can require a specific key to be opened (see later).

The algorithm

There are several distinct stages to the map generator algorithm:

1. The generator is initialised with the width and height of the map to generate, and the number with which to seed the random number generator
2. A single room, the size of the map, is created, and placed in an 'active' room queue
3. For each room in the 'active' queue, that room is subdivided. It can either be divided horizontally or vertically, and the division point is chosen randomly. However if either of the child rooms is too small (Less than 3 cells wide or deep), the room will be left alone and moved to the 'inactive' queue. If the division succeeded, the two new rooms will be added to the 'active' queue - thus these two new rooms will be subdivided again at a later point in time.

   Click to see the map at this point in time

4. Once the 'active' queue is empty, the map will contain a series of simple rectangular rooms. A random number of those rooms are now selected for 'joining' - each selected room will be joined with a random neighbour, and then with another neighbour, etc. to produce irregular shaped rooms and corridors. In the current implementation, every tenth room of the map will be merged with 3 of its neighbours.

   Click to see the map at this point in time

5. The next stage is to link all the rooms with doors so that it's possible for the player to visit every room in the map. First, every room is marked as 'unlinked', and all the edges are set to type 'wall'. Then:
   1. An arbitrary room is selected and marked as 'linked'
   2. From that room, a graph traversal algorithm is activated, travelling to each adjacent room that has a 'door' edge between it and the current room. Each room is marked as 'linked' as it is visited.
   3. If all rooms have become marked as 'linked', then the algorithm stops.
   4. Else a 'wall' edge is selected at random and changed to a 'door' edge.
   5. If that edge happened to be on the boundary between a 'linked' room and an 'unlinked' room, go to step 2, continuing the graph traversal in the newly-linked room. Else, go to step 4.
   Edges are chosen for door conversion at random so that the resulting map is still random. It's possible to write other algorithms - for example only choosing edges that lie on the boundary between a linked room and an unlinked room - but that will reduce the randomness of the layout (In fact, it will produce a traditional maze in which there is only one path to the exit).
6. The next step is to choose the start and end point for the level. I wanted these points to be as far apart as possible. To do this I could have simply placed them in rooms at opposite corners of the map, but I decided to write a real algorithm for it instead:
   • Firstly, a room is selected at random.
   • Then, the furthest room from that room is selected (based around the number of doors that must be travelled through). This will be the start point of the level, and will most likely be a room near a corner of the map.
   • Finally the furthest room from that room will be selected, which will be made the exit room of the map. This is most likely to be in the opposite corner of the map to the first room.

   Click to see the map at this point in time

7. Locked doors and keys are then added to the map. Unfortunately all my algorithms for this have produced buggy levels, which can leave the player trapped if they take the wrong turning (Since each key is consumed when used to open a door).
    
   Although it should be possible to write a generator that doesn't make maps like this, my long-term solution (if any) is likely to be a rewrite of how keys are handled, to introduce more variety in the levels (e.g. instead of merely collecting keys, you have specific goals such as restoring power to sections of the ship or deactivating defence systems).
    
   If you look at the source code to GAIO, you can see two different algorithms I've tried writing for door and key placement, along with a verification algorithm that fails to verify the maps properly.

   Click to see the map at this point in time

8. The next step is to add monsters and items. Currently these are placed randomly, although future versions will choose the correct item distribution based around the chosen difficulty level and the types of monster present. If you clicked on the image above, you'll have seen that the map already contains some monsters. That's because they are also added by the previous step, to all rooms immediately behind a locked door.
9. The final step is to copy the list of rooms and edges into a 2D grid of map tiles. This grid is used by the game for rendering and collision detection. A lookup table is also kept, which will allow the game to instantly calculate what room an object is in based around its coordinates.
    
   Decisions about where to place doors are also made at this stage - before it was just a case of 'there is a door in this wall', but now the algorithm pins the door down to a specific location (Which is chosen as a random point along the edge). Finally the correct items and monsters are placed in the rooms. Bigger rooms get more monsters.

Initially I thought that the room and edge data structures would only be of use to the map generator, and could be disposed of afterwards. But then I realised that they can be reused for important tasks such as monster pathfinding and the storing the 'visited' flag that controls whether the room appears on the minimap. This is another situation where using a map generator has advantages over manual design - if I'd made the levels manually, I would have probably done it without using any 'room' data structure, and would have had to find alternate solutions to the above problems.

Conclusion

There are many situations where a random map generator can be useful. But there are also many situations where a random map generator can't be useful. Ultimately it will be down to you to decide what content can and cannot be randomly generated, and which algorithms to use. Even when you've got a good algorithm, you can expect to spend a good deal of time tweaking it to produce output that has the right level of difficulty or is fun to play on. Random map generators can be used as part of almost any game, but only use them if you're sure it's the right thing to do.