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.
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 local map|
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).
First person shooters
|A simple Slige level|
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.
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).
There are several distinct stages to the map generator algorithm:
- 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
- A single room, the size of the map, is created, and placed in an 'active' room queue
- 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.
- 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.
- 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:
- An arbitrary room is selected and marked as 'linked'
- 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.
- If all rooms have become marked as 'linked', then the algorithm stops.
- Else a 'wall' edge is selected at random and changed to a 'door' edge.
- 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.
- 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.
- 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.
- 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.
- 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.
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.