UPDATE 2014-09-15: The second part of this series is here.

I regularly get asked how the overworld is generated. I actually started writing it up in a series of blog posts here on bytten-studio.com last year, but it became difficult to keep this up to date with the implementation. The implementation was changing too much and too often!

Things have stabilized somewhat now, so in this two-post series I’ll give an overview of how the procedural generation in Lenna’s Inception works. I’ll skip over some of the details to keep the length down, but if you need more detail on something specific for your own project(s), I’m more than happy to help you. Feel free to contact me on twitter or by email, but please try to understand that my time is very limited!

How is Lenna's Inception different?

Procedural map generation in contemporary video games tends to fall into two categories:

  • Sequential levels with limited procedural generation, e.g. rectangular rooms and long-thin corridors (Rogue), or stitching together hand-designed templates and setpieces (Binding of Isaac, Spelunky).
  • Open, non-linear worlds with very few setpieces, but where the procgen system has a huge degree of freedom and can automatically produce variety (Minecraft).

Lenna’s Inception doesn’t really fit neatly into either of those, because while it’s linear, it doesn’t rely heavily on hand-designed room templates. It takes the linear gameplay of the first category and and increases the degree of freedom of the procgen system to a level comparable to the second category.

Let’s start by taking a look at the design of some of the most closely-related games that use procedural generation and randomization.

Binding of Isaac

The Binding of Isaac plays as a linear sequence of dungeons. While the layouts of the dungeons are randomized, the designs of rooms are randomly selected from a set of 1000+ hand-designed rooms, with the enemies and items randomized.

Binding of Isaac - randomized dungeon layouts Binding of Isaac - templated room designs

It’s a clever design - replayability is provided by the randomized dungeon layouts, while the variety is provided by a human designer, and all of this is stitched together by a small procgen system.

Spelunky

Spelunky has some similarities to Isaac, but takes the procedural generation a bit further. I recommend reading tinysubversions’ Spelunky Generator Lessons, but I’ll summarize here.

The map is divided into a 4x4 grid of rooms. Generation starts with the solution path, analogous to Isaac’s dungeon layout. This path - the standard route from the start room to the end of the level - of one level is shown in red below.

Spelunky - solution path

Once the solution path is down, the generator knows which rooms need to be connected by gaps. It uses this knowledge to select templates for each room. (Rooms not on the path are assigned a template randomly.)

These room templates allow the procgen system more freedom than in Isaac. They contain ‘probabilistic’ tiles, which have a chance of becoming a wall.

Probabilistic tiles are often arranged in large blocks, and their probabilities are independent. This means that sometimes the generator can produce rooms divided by a large column of wall from templates that were intended to allow the player to travel across:

And sometimes the gaps in two adjacent rooms may not line up with each other, creating an unintentional wall between two rooms.

Thanks to Spelunky’s design though, the player can usually still get through these because the terrain is destructible.

Do we need templates?

If the system knows where the entrances to a room need to be, it should be possible to randomize the contents of the room without blocking them. Then every tile could be a probabilistic tile…

Lenna’s Inception does away with the templates that Binding of Isaac and Spelunky rely on. It keeps the dungeon layout / solution path idea, although extended with lock and key puzzles (explained later). Once the generator knows what the exits and connections between the rooms have to be, it can work out how to create a room with those exits, without templates.

One non-obvious advantage of throwing away templates is that rooms can be almost any size, and need not be one per screen. This makes it possible to generate more of the variety procedurally:

In the following sections I will explain how the extended solution path and non-templated room generation fit together:

  1. Terrain generation
  2. Lock and key generation
  3. Spatially-aware room content generation (in the next post)

Terrain generation

Terrain is the first thing generated by the game. As in many other games, Perlin noise is used to generate a continuous heightmap of the terrain.

This heightmap is discretized (flattened) into six height values, which causes the terrain height to look more like a staircase than a smooth gradient. This makes it fit with the Gameboy-style tile maps.

The six height values correspond to:

  • Sea level
  • Beach
  • Plains / grassland / forest-like areas
  • and 3 values for mountainous areas

You can find more detail about the terrain generation in some of my previous posts, including how the river is created without climate/weathering simulations.

After terrain generation, the world looks like this:

Lock and key generation

Why lock and key puzzles?

Part of what makes Lenna’s Inception a good game, and not just a good procedural generation system, is how it applies a particular game design principle: flow. Explained briefly, difficulty, or tension, should increase at exactly the right rate. If it increases too quickly, the player gets frustated. Too slowly, and the player gets bored. If you keep the player in ‘flow’ - in the channel between frustration and boredom, where they face challenges they can overcome - they will play a lot longer.

Lenna’s Inception increases tension by making the enemies more difficult as you progress.

Many RPGs treat your character’s level and experience points as progress, and scale enemy levels accordingly. Personally, I don’t think this always works out. You can’t always rely on the player to challenge themselves. If it’s possible to go straight to the final boss and beat it by leveling up from fighting 50,000 rats (of scaled difficulty) in the starting area, players will do this, and it makes the game grindy.

A different way you can tackle this problem of making tension increase is to divide the world up into separate areas and only allow progress into the next after completing something in the current one. What you have then is a linear sequence of areas, which lets you increase the difficulty of enemies as the player progresses through them.

A nice way to do that, while also giving an “open world” feeling is with lock and key puzzles. These need not be literal locks and keys - a lock could be for example a bush, and the correspond key would be a sword that can cut bushes. You can only open a lock with the right key - you can only get past the bush with a steel sword.

To be clear - these are keys more like DOOM’s colored keys than Zelda’s small keys. You can use each key as many times as you want in as many locks of the right color as you want. Zelda’s small keys are known as Interchangeable Antimatter Keys. I think that these would be harder to implement well in a procgen system, but I’m sure someone smart could figure it out.

The great thing about this sort of lock and key puzzle is that it rewards the player with more freedom as they progress. Each time you get a new key item, there are more areas open to you, more routes back to previous important areas, and more ways to travel, until at the very end when you actually are in an open world. So it often doesn’t feel very linear to a player. ;)

Lock and key puzzles are central to Lenna’s Inception’s design. I don’t know of any other games that use them for the same purpose in procedural generation, but there is a neat logical abstraction that makes it relatively simple to generate random instances of them.

A graph data structure can be used to represent the layout of a “dungeon”. For the purposes of lock and key puzzle generation, overworlds are a generalization of dungeons I’ll explain later.

Here we have 7 rooms laid out in a grid. Each room is indicated by a circle, and the doorways between them are shown as lines connecting the circles. The goal room, which could be a final boss or a treasure room, is indicated by the double-bordered circle.

Locks and keys are represented by letters. The lock E, written on the line between the two rooms it locks, is opened by the item E, written in the circle for the room it is found in.

How the puzzles are generated

There are many ways to generate these puzzles, but the method I use goes like this:

  1. Create the entrance room (or spawn area).
  2. Choose an empty space adjacent to the entrance room, put a room there and link it to the entrance room.
  3. Choose an empty space adjacent to one of the rooms you've already placed, put a room there and link it to the adjacent pre-existing room.
  4. Repeat 3 until you have as many rooms as you need.

This gives us a “tree” of linked rooms:

By tree, I mean that it has branches without loops, not that it grows from a seed and photosynthesizes. The fact that there are no loops among these branches means that there is only one path to each location, and play frequently involves a lot of backtracking, which is not very fun. But before solving that, we make it into a lock and key puzzle.

Periodically while adding rooms, we can decide to put all following new rooms behind a new lock. We call the current number of unique locks the “key level,” and record the current key level in each room we place. This tells us how many keys the player will need to reach that room:

Then to place keys, we simply have to make sure that the first key is placed in a room with key level 0, key 2 is placed in key level 1, etc.

We can also make it less “tree”-like at this point by linking up random adjacent rooms, such as in the example below:

Here is where the “key levels” come in useful - where the rooms we link have different key levels, we need to place a lock. The lock we choose is the one corresponding to the highest key level we’re linking. So in the diagram above, the top two red lines would be locked with the third key, and the bottom one with the first key.

While the diagrams shown so far have laid rooms out in a grid for simplicity, the same algorithm can be used to generate the non-grid-based designs that suit overworlds best:

I released my implementation of this as an open source library (BSD-3 license, so you can use it in commercial projects). The full details of the algorithm can be found here. (The generalization to non-grid-based designs is currently on a development branch.)

Fitting this into the terrain

The size, shape and positions of rooms that are possible are dictated by the terrain that was generated earlier. Cliffs form natural walls between adjacent rooms, and where the lock and key generator decides they need to be linked, we can replace the cliffs with staircases. The edges of a screen are also treated as potential borders between rooms.

The following diagram shows a 16x16 screen overworld map, with each individual “room” within it bordered by a vivid color:

When the lock and key algorithm has decided which rooms are linked, walls can be placed in the map (trees and immovable rocks). With the line-and-circle diagram superimposed over it, it could look something like this:

The colors and numbers represent the difficulty of each area, and thanks to the locks and keys, will roughly correspond to the order the player will pass through them. :)

What's next?

So far we’ve seen how terrain is generated and how the procgen system decides each area in the world will be connected, controlling the progression of the player through the game. We haven’t yet seen how the contents of those distinct areas are filled. As mentioned earlier, while Binding of Isaac and Spelunky use hand-designed templates to generate this content, Lenna’s Inception takes a different approach.

I’ve described the terrain and lock and key generation portions of Lenna’s Inception’s procgen system before, but these room generation tricks have been my secret sauce for a long time.

Look forward to the second part on Monday next week!

Supporting Lenna's Inception

You can support the development of Lenna’s Inception (and my procedural generation projects) by purchasing it here or here:

See also

Not all of these links are directly related to the procgen in Lenna’s Inception, but you may find them interesting while you wait for the next post in this series:



blog comments powered by Disqus

Published

08 September 2014

Tags