log in | register | forums
Show:
Go:
Forums
Username:

Password:

User accounts
Register new account
Forgot password
Forum stats
List of members
Search the forums

Advanced search
Recent discussions
- What was that game (Games:7)
- Wakefield RISC OS Computer Club Remote Membership (News:1)
- Null modem link (Gen:9)
- Home wanted for old Acorn stuff (Gen:6)
- Sound DMA / emulating IOC device 9 (Prog:26)
- QuizMaster - New RISC OS Program released by ArchieSoft !!! (Gen:3)
- Broken Directory (Gen:2)
- Beginners Guide to Interfacing @ ROUGOL 21st July 2014 (Gen:1)
- Gaming on the Pi (Games:54)
- Pesky Muskrats crash (Games:1)
Related articles
- Building the Dream 4 - Random city basics
- Building the Dream 3 - Random map generators, redux
- Bob and Trev: Resurrection: Just in time
- Monster AI
- Combat
- Visibility and pathfinding
- The level generator
- Static game data
- How to fit a roguelike in 32k
- Bob and Trev: Resurrection
Latest postings RSS Feeds
RSS 2.0 | 1.0 | 0.9
Atom 0.3
Misc RDF | CDF
Site Search
 
Article archives
The Icon Bar: News and features: Random map generators
 

Random map generators

Posted by Jeffrey Lee on 15:00, 9/1/2007 | , ,
 
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 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 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
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
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.
  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.
  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.
  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.
  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.
 

  Random map generators
  pnaulls (15:22 9/1/2007)
  nunfetishist (17:12 9/1/2007)
    monkeyson2 (17:20 9/1/2007)
      VincceH (18:57 9/1/2007)
        SimonC (11:29 10/1/2007)
          Phlamethrower (11:37 10/1/2007)
            Loris (18:28 19/1/2007)
              Phlamethrower (18:48 19/1/2007)
  flypig (18:50 9/1/2007)
 
Peter Naulls Message #96888, posted by pnaulls at 15:22, 9/1/2007
Member
Posts: 317
You missed out a classic type - random terrain generators - usually just for the effect rather than any game. One appear in Acorn User many moons ago, and others can be seen in screen savers.
  ^[ Log in to reply ]
 
Rob Kendrick Message #96892, posted by nunfetishist at 17:12, 9/1/2007, in reply to message #96888
nunfetishist
Exposing morons since 1981

Posts: 446
Wasn't the universe in Elite also randomly generated, to save space?
  ^[ Log in to reply ]
 
Phil Mellor Message #96894, posted by monkeyson2 at 17:20, 9/1/2007, in reply to message #96892
monkeyson2Please don't let them make me be a monkey butler

Posts: 12380
An interesting point about Elite was that Acorn recommended that Bell & Braben deliberately restricted the number of galaxies to 8. Originally they were going to have millions of them, but that made it look too obviously fake.

The trouble with random/automagic content is that you can lose interest in playing with it once you realise how it works. I never got into Elite because it was too much like playing against a random number generator - yet I rarely felt that with Angband.
  ^[ Log in to reply ]
 
David Llewellyn-Jones Message #96902, posted by flypig at 18:50, 9/1/2007, in reply to message #96888
Member
Posts: 17
Interesting article :) Even though GAIO is still in progress, I find it surprisingly addictive wandering around the corridors.

In relation to the creation of random maps, this post about an impressive-looking city generator might also be of interest:

http://forums.introversion.co.uk/introversion/viewtopic.php?t=586
  ^[ Log in to reply ]
 
VinceH Message #96903, posted by VincceH at 18:57, 9/1/2007, in reply to message #96894
VincceH
Lowering the tone since the dawn of time

Posts: 1557
The trouble with random/automagic content is that you can lose interest in playing with it once you realise how it works.
Heh - like the Space Invaders console my uncle had when I was a kid; we spent a while doing it, but we eventually worked out how to get maximum points from the seemingly random points awarded for shooting the UFO; it was something along the lines of after firing the first 23 shots, don't fire any more until the UFO appears, and use the 24th to shoot that, and thereafter for the level, it would be the 16th shot.

What fun. :)

Back to the subject at hand, though, I used fairly simple random map generator while writing Escape from Exeria - the actual levels in the released game were designed by me, but rather than spend ages designing a base screen to test code as I wrote it, a random map was the obvious way to go.

It only needed to be fairly simple because the logic of the game was fairly simple; the 'ghosts' always carried on until they hit a wall, then turned right (until the end of the level when they chased the player), and as for the mazes themselves, the only constraint was that the crystals of each colour couldn't be accessible until the previous colour had all been collected and that colour of doors/rocks had been opened.

Properly designed screens were more appropriate for the final game, though - but I'm not entirely sure if I removed the random map logic from the program. If anyone still has the original version it might be worth looking. (That said, it was a nasty mess of BASIC, including GOTOs and everything, so maybe not!)
  ^[ Log in to reply ]
 
Simon Challands Message #96929, posted by SimonC at 11:29, 10/1/2007, in reply to message #96903
Elite
Right on, Commander!

Posts: 398
I think the Exile map was randomly generated, as was the Zarch landscape.

With Elite the seed is stored within the saved game position, so if you edit the save file you can get new galaxies.

On and off for a while I've been trying to come up with a suitable random terrain generator to get a realistic landscape (i.e. proper valleys and ridges and generally Lake District-type topography) for my almost certainly will never be written mining simulator. In the unlikely event I succeed there I'll then have to move on to randomly generated geology.
  ^[ Log in to reply ]
 
Jeffrey Lee Message #96932, posted by Phlamethrower at 11:37, 10/1/2007, in reply to message #96929
PhlamethrowerHot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot stuff

Posts: 15031
Yeah, Exile is another good example of a random map generator (even if an overview map of the game world doesn't make the algorithm look very advanced!)

Sometime soon I'm hoping to write my own city generator.
  ^[ Log in to reply ]
 
Tony Haines Message #97449, posted by Loris at 18:28, 19/1/2007, in reply to message #96932
madbanHa ha, me mine, mwahahahaha
Posts: 1025
I think the Exile map was randomly generated, as was the Zarch landscape.
Yeah, Exile is another good example of a random map generator (even if an overview map of the game world doesn't make the algorithm look very advanced!)
For a long time now this has been a fascination of mine. I think it is a rather different proposition to create an interesting 'randomly seeded' but fixed level, like Exile's, than a landscape generator. For two related reasons.
Firstly, it has much more of a bearing on the gameplay than a simple landscape does. And secondly, because it uses an algorithm which allows a 'keyhole' of the level to be generated, rather than an interacting structure which requires effectively the whole level to be generated and held in memory in order to view any bit.
Exile is particularly interesting in that the level is effectively defined by the algorithm, rather than through the random seeds supplied. (Although in theory the two may be effectively the same, in practical programming terms they are not.)
I've been thinking about writing an article on this subject for a while, but would like to write my own level generator to back it up. Actually I did write a simple one, putatively for a small coding competition, but never got round to populating it with monsters.
  ^[ Log in to reply ]
 
Jeffrey Lee Message #97450, posted by Phlamethrower at 18:48, 19/1/2007, in reply to message #97449
PhlamethrowerHot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot Hot stuff

Posts: 15031
I've been thinking about writing an article on this subject for a while, but would like to write my own level generator to back it up.
Well, feel free to send it to us for publishing once it's finished :)
  ^[ Log in to reply ]
 

The Icon Bar: News and features: Random map generators