More and more games contain randomized elements these days. By shaking up some parts of your game – be it the map, the loot or the encounters – you can keep things fresh for much longer and keep players coming back. Everybody likes surprise and novelty.
But randomness is a wily beast. When people think of randomness, they usually think of a lack of patterns. But truly random output actually does contain a lot of patterns (or more accurately, the appearance of patterns). This is why gambling is so addictive. Often you’ll get nothing, but sometimes you’ll get several payouts in a row and you could mistakenly believe that it’s because you’ve discovered a secret pattern.
It’s in the nature of true randomness to have these wild, unpredictable variance swings. But in games this could mean you get a huge surplus or drought in something important, pushing things out of balance. Too much treasure can make a game trivial, whereas too many hazards could make it impossible.
To combat this, most procedural generation in games isn’t truly random. There are usually checks and balances in place to make the output look believable and feel fair (this is the “procedure” in procedural generation).
In this article I’ll be sharing some simple techniques to improve your generation – using Patch Quest, my own game, for examples.
Many procedurally generated world are large – containing rivers, forests and even towns. Generating something this complex from scratch can be very difficult. You’d probably need hundreds of rules to specify how all these elements can be spawned relative to each other.
A simple way of reducing this complexity is to subdivide your map into chunks, each of which can be generated independently. Now you only have to think about a smaller subset of your generation rules at one time. You can even subdivide your chunks again if they’re still too complicated to think about.
Let’s see an example. Patch Quest’s world is subdivided 3 times. At the top level (level 0) I draw a coarse map of the whole island on a grid. I specify which habitats go where and also place down landmarks like buildings and rivers. This is the only level that I author myself, and it doesn’t take long to edit because it’s so zoomed out.
Each cell in the level 0 grid represents one screen’s worth of the island. This screen can further be divided into a 3×3 grid of Patches, and each Patch can be divided into a 3×3 grid of tiles. A tile can’t be divided any further. Below, we can see an example screen.
Level 1 specified the habitats and the river. Level 2 distributed the contents of these habitats to the Patches. Level 3 distributed the Patch contents onto the individual tiles.
I have so many levels because it reduces the complexity of each subdivision. To divide a screen into Patches, I just distribute different game entities to the various Patches. To divide a Patch into tiles, I just place that Patch’s entities on random tiles (I also apply some rules at each step to keep variance in-check, but we will cover this later). Each subdivision is simple, but by chaining them I can quickly go from a small, coarse map to a large, detailed world.
My subdividing system is quite unique to how Patch Quest works, but there are countless other ways a map can be divided. Old-school roguelikes subdivide a map into rooms and corridors. Spelunky subdivides its map into 8×8 chunks, rather than 3×3 Patches. It’s worth considering how your own map could be sensibly divided into self-contained chunks.
Here’s another simple trick that can be used in a wide variety of situations. Instead of using a pure random number generator, use a bag.
Imagine that you took all the objects you wanted to randomise and you put them in a bag. You then shook the bag, shuffling its contents, and proceeded to pull the objects back out – one by one.
The objects would come out of the bag in a random order. But once the bag has been emptied, you can guarantee that each object was drawn exactly once. This is because once you’ve pulled an object out the bag you can’t pull it out a second time. Only when the bag has been fully emptied do you put everything back in the bag, shuffle it again and start over.
Let’s compare this to true random generation – which often returns duplicates. If you generated 26 true random letters of the alphabet you might, for example, see A appear 3 times and B appear zero times. You can’t predict how many times you’ll see each value, unlike with bag random where you’d see each letter exactly once.
Bag random was invented quite some time ago and in my own project I don’t refer to things as ”bags”. Instead, I refer to them as decks. This is because very few of us pull things out of lucky dip bags in daily life but we all have experience playing card games. So in the context of game design I find it more intuitive to think of a “deck of cards” that you use for generation rather than a “bag of objects”. For the rest of this article I’ll be calling them decks.
Decks are most useful in situations where you have many common drops and some very rare drops. Suppose that each time you mine a rock you have a 50% chance of iron, a 45% chance of copper and a 5% chance of striking gold. Under a true random generator, some players might get lucky and find gold very quickly while many other players go a long time without seeing any of it. But under a deck generator you would guarantee that each player gets one gold per 20 mining attempts on average (the deck would contain 10 iron cards, 9 copper cards and 1 gold card).
Here’s an example of how I use decks in Patch Quest. Each habitat is split into 3 layers: Terrain, Scenery and Creatures. Each layer has a deck that can contain duplicates.
During generation, every Patch is assigned a card from the deck. This is done once for each layer – so each Patch will have a Terrain, Scenery and Creature card. If a deck runs out, it’s refilled and reshuffled. Below, you can see an example of how this deck might be distributed over a screen’s worth of patches (for clarity, I haven’t drawn scenery or terrain cards on this image, but they would be distributed in a similar way).
Note: This image shows a level 2 subdivision (distributing creature cards to the Patches). To finish this generation we still need to be subdivide into level 3 (for each Patch, choose which tiles the creature will spawn on).
Using a deck means that even my rare cards have a good chance of showing up. This technique is very versatile; whenever you generate random values you could consider using a deck to sand off the harsh edges of luck swings.
Decks have a problem, though. If you only draw a small fraction of your deck (like 10 cards out of 100) you could still draw an unrepresentative hand. An average Magic the Gathering deck is nearly half filled with land cards, but sometimes the player will draw no lands and sometimes they will draw all lands.
There’s a similar problem with decks that are far smaller than your hand. Let’s consider a deck that has only one card.This deck will just keep returning the same card forever (since we refill and reshuffle the deck whenever it runs out). This one card would fill up our entire game map!
You can fix both problems by setting a cap for how many times you’ll accept each card type. To do this, first record the last N cards you drew from the deck. This information lets you see if any card type has reached its cap, allowing you to reject any further cards of that type.
Let’s go back to our Patch Quest example. Each card is assigned a rarity as it’s added (I’m using Rare, Uncommon, Normal, Common, Extra Common – but they could be divided in any number of ways). Each rarity corresponds to a number of duplicates: Rare is one, Uncommon is two and so on.
Each rarity is also given a cap – a number that limits how many times it can appear on one screen’s worth of patches (for simplicity I just use the ‘duplicate’ values for my caps, but you could also make them larger).
Suppose we had a small deck like this, with a rare card and an uncommon card.
Using uncapped generation we could end up with the output below. The deck has repeatedly placed the same cards, even though we intended them to be rare and uncommon.
But under capped generation we see something much more sensible. Once a card reaches its cap it won’t be placed any more times. Now, rare cards will always be rare regardless of what else is in the deck.
Card caps prevent us from getting far too much of something in our output. This is a bit different to decks, which help up ensure we get enough of everything in our output (particularly the rarer things). Taken together, we can now smooth out our variance swings from above and below – making our output much more consistent.
A quick tech note: Your capper should be a separate class to your deck class. This way, you can share one capper between several decks (by passing the capper into each deck as it attempts to draw out the next valid card). In Patch Quest, when you are on the boundary of two habitats you will see a mixture of patches from each habitat. This means we need to assign some patches from one deck and some patches from another deck. By sharing the capper, I can control the variance of both these decks at the same time.
Thus far, we’ve looked at how to reduce variance. But if we reduce variance too much the game will become too repetitive and predictable – defeating the whole point of procedural generation in the first place! Variety is the spice of life, as they say.
With that in mind, we can spice our generation by adding lucky (or unlucky) swings back into the game. But by doing this in a controlled manner, we ensure that the game is still fair when taken as a whole.
This is pretty simple to do; let’s return to Patch Quest. Before subdividing from level 0 (the authored minimap) to level 1 (“screens” of Patches) I randomly place “special features” in some cells. The first area of the game has two special features:
- Bullfrogs, a boss creature that blocks your path (but can also be tamed). These create a negative variance swing.
- Seahorses, a creature you can mount and ride for a while, boosting your mobility. These create a positive variance swing.
Bullfrogs block the central patch of the screen, making it hard to get past. They also attack you once every 3 turns (but with careful play you can dodge these attacks). Each of the 4 adjacent patches are guaranteed to have Bullpoles and Sinkweed. The left and right patches also have Toad Turnips – the food you can use to tame the Bullfrog.
These features are distributed over the map randomly in every N’th cell (I use N = 5, currently). I also have a few extra conditions, like they cant be spawned directly next to another special feature of the same type – or next to a Checkpoint. This, again, helps things feel more random.
Spicing is a versatile technique. You can occasionally give players an extra treasure or occasionally put up a few extra obstacles. Any random element in your game could be spiced, if you want some extra variety.
But the key benefit is that spice is controlled in a way that true randomness is not. By spicing, you can ensure that every player sees their fair share of variance spikes.
We’ve looked at 4 techniques that can be applied to a wide variety of procedurally generated worlds.
- Subdividing a large map into smaller chunks makes generation easier to think about.
- Decks (bag random) let us ensure that rare options will show up their fair share of the time.
- Caps let us ensure that nothing shows up too much, flooding the output.
- Spicing lets us add back in some of the variance we removed using decks and caps – but to a degree we can control and that feels fair.
These techniques let us avoid the harshest swings of randomness, but without also stripping your game of excitement. It’s a bit counter-intuitive, but making your game less random (by placing all these rules and restrictions on generation) can actually make it feel more random.
If you liked this article, why not read some of my other ones? (like this one on how your inventory system could be unbalancing your game)
In other news, the Patch Quest Wildlife Update released today! In this update you’re given a scanner that lets you learn about all the creatures, plants and minerals you come across while exploring. It also features several new areas to explore, containing new things to scan. You can watch this video to see the full changes:
Patch Quest is completely free right now, so I suggest you grab it while you can! Here’s the link (for PC).