In the old days of cartridge gaming, games were often limited to a paltry 4K or 8K of space on an entire cartridge. That entire block of ROM had to hold the game code and any associated data. To say games were primitive would be an understatement, but a lot of great games were made out of that primitive structure.

Games then were basically limited to a few simple formats:

• A few basic levels that repeat, possibly with some altered enemies, faster speed, etc. This is the approach taken by Pac-Man and Donkey Kong. It worked pretty well for those games, but it was simplistic.
• Near-total randomness. Berzerk was a classic example. It didn't remember where you were, you had no goal except to survive, and every room was random. This was a great game, but again very simple.
• Many consistent levels. This was rare because to get this, you usually had to break out of the cartridge format and use a disk.

Consistent levels without repetition were hard to come by, but one game I recall fondly did just that: River Raid. The lay of the land, the enemies you would face, and even the scenery were always the same whenever you'd reach certain levels, so you could remember that level 17 has a particular tough spot and in 26 you can run out of fuel if you're not careful. River Raid built its levels using a pseudorandom number generator, or PRNG for short. Levels were "seeded" and then grown out of the generator so they would turn out a certain way each time. As a result, levels didn't take up any space on the River Raid cartridge.

In reality there's no such thing as a true random number generator in a computer. Computers are glorified calculators; they take what you give them and crunch numbers. All random number generators are "pseudo". But using your own has some distinct advantages over relying on whatever BYOND gives you, and the same is true of other languages.

This article is about bringing two great things together: procedurally generated content, and your very own PRNG. The PRNG provides the numbers; procedural content generation is the technique to turn those numbers into playable game space.

Making Your Own Randomness

Several different methods exist for making PRNGs. For BYOND, a simple one will do nicely. The simplest kind is called a linear congruential generator, and it works like this:

next_seed = (seed * A + C) % M

The values of A, C, and M all need to be chosen carefully to return decent results. Fortunately, a bunch of smart people have already found good values for a lot of situations. Since BYOND uses simple 4-byte floating point numbers, we're limited to 24 bits of integer accuracy, so that means the total value of seed*A+C needs to come in under that. For producing 16-bit random numbers, a good set of numbers is A=171, C=0, M=30269. All the results therefore are going to be in the range of 0 through 30268. 30268*171 is well within our limits, so it'll do nicely.

next_seed = (seed * 171) % 30269

It should be obvious here that a seed of 0 will do us no good, so we need to start with a seed above 0. To use this in a BYOND game, a datum will help us out a lot. By using datums, we can use multiple PRNGs simultaneously, so you can use one for the layout of a dungeon and another one for placing treasure.

random
  var/seed
  
  New(seed = 1)
    src.seed = seed

  // rnd() is equivalent to rand()
  // rnd(n) is equivalent to rand(0, n-1)
  proc/rnd(n = 0)
    seed = (seed * 171) % 30269
    . = seed / 30269
    if(n) . = round(. * n)

  // equivalent to prob(percent)
  proc/chance(percent = 50)
    return (rnd() * 100 < percent) 
  
  // equivalent to roll("[dice]d[sides]")
  proc/roll(sides = 6, dice = 1)
    . = dice
    while(dice-- > 0)
      . += rnd(sides)

To get a PRNG going, just create a new /random object with the seed you want. Then call the random.rnd() proc to get a random value. This will either be a raw decimal number from 0 to 1 if you call rnd() by itself, or if you use something like rnd(10) you'll get an integer from 0 to 9. A handy roll() proc has also been added, for rolling dice. Now for an example:

// shuffle a deck
var/list/deck = new
var/i
for(i=1, i<=52, ++i)
  L += i

// create the randomizer; use 1000 as a seed
var/random/R = new(1000)
for(i=52, i>1, --i)
  // swap the i-th card for any card from 1 to i
  L.Swap(i, R.rnd(i)+1)

If you've played Freecell before--and if you have a job in an office, you have--then you know that each game is numbered. If you put in the same number you get the same game. This is why. Freecell uses the game number as the seed for its PRNG, and uses the PRNG to dictate how it shuffles the deck.

By now you should see what I've been driving at. If you can use a single seed number to shuffle a solitaire game the same way every time, the same technique can be used to make level 22 of your game always have the same layout every time, and it can do level 3,073 just as easily. You didn't have to personally create over 3,000 levels, though, to make that possible.

As far as PRNGs are concerned, your choices don't end here. Linear congruential generators are one of the simplest kinds. The one presented here has a relatively short period, meaning the numbers will eventually start repeating. You can string two such generators together to get a longer period, but there are even better generators available. The Mersenne Twister is an algorithm that's speedy and delivers excellent results over a very long period.

Using the Generator

Now comes the fun part: procedural content generation. How would you plug your PRNG into a level generator? Let's look at a rough sketch.

proc/CreateLevel(z, level)
  var/random/R = new(level)
  for(var/turf/T in \
      block(locate(1,1,z), locate(world.maxx,world.maxy,z)))
    if(R.chance(80))        // 80%
      T = new/turf/dirt(T)
    else if(R.chance(95))   // 20% * 95% = 19%
      T = new/turf/tree(T)
    else                    // 20% * 5% = 1%
      T = new/turf/rock(T)

Okay, so that's not a very good level generator, but you see how it works. If you break down the probabilities, 80% of the turfs are dirt, 19% are trees, and the remaining 1% are rocks. Using prob() instead of R.chance() would produce similar results--but only this one will produce the same layout for level 4 every time. The cool thing, though, is that you can mix "totally" random content in with this.

River Raid used a PRNG like this one to build its levels, but it still had the console's own, more "random" number generator to control when enemies would start moving. That meant that while level 3 always had the same layout from game to game, the first helicopter you encountered could sometimes get in your way at a crucial time, and sometimes not. Your game plan for level 3 had to factor in that helicopter as an X factor.

Let's try something a little more complex. BYOND isn't really good at sidescrollers for obvious reasons, yet they're a great way to illustrate this technique, so for the moment disregard any technical limitations. Say you wanted to create the next great platform sidescroller and you wanted practically unlimited level content. How would you do it?

To build a sidescrolling level, you'll need to start by breaking it up into sections. So we'll start by writing out a list of possible sections in a level:

• Flat surface, with several platforms
• Upward stairs leading onto a platform over a sheltered nook
• Broken surface with pits to jump over; no platforms
• Broken surface with pits; platform available
• Split screen; flat surface, with one platform above that can't be reached from below
• Split screen; same as above but with gaps above and/or below
• Moving platforms over wide gap

That simple list is just 7 possible section types; you can think of more, I'm sure. There are a few places where it's clear that a powerup could be hidden in such a way as to require memorization and strategy. In section type #2, that sheltered nook could have a powerup requiring you to fall off the platform and then backtrack to reach it. The split-screen sections can be chained together in such a way as to force a decision from the player whether to take the high branch or the low branch. As you see, these can be fitted together like puzzle pieces. You may need some transition elements, too, like a trampoline or spring just before one of the split screens so you can reach the upper branch, or a mid-level platform.

This is what a rough sketch of the level generator might look like:

proc/CreateLevel(level)
  var/random/R = new(level)
  var/list/sections = new
  var/list/powerups = new
  var/i, j
  var/const/nsections = 8

  // create sections
  for(i=0, i<nsections, ++i)
    sections += R.rnd(7)+1  // choose 1-7

  // choose 1-3 powerups (usually 2) and put each in its own section
  var/lastpowerup = 0
  for(i=R.roll(2,2)-1, i>0, --i)
    // if placing 3 powerups, put first somewhere in 1st third
    // next somewhere in first half of remaining section, etc.
    // this biases powerups toward beginning of level
    j = round((nsections-lastpowerup)/i, 1)
    lastpowerup += R.rnd(j) + 1    
    powerups += lastpowerup     // add this section to the powerup list

  // now send our list of sections, and which ones have powerups, to the
  // actual turf builder
  BuildSections(R, sections, powerups)

This algorithm begins very simply, by choosing the section types and filling in a list. It doesn't build them yet; that's saved for the BuildSections() proc. At this point we just want a blueprint: A split-screen without gaps, followed a set of moving platforms, then a flat section. Into this blueprint we'll sprinkle some powerups. This algorithm makes them occur early on, because otherwise there's little point. Each one is in a separate section. When that's done, the section numbers containing powerups are sent to BuildSections() too. It's up to that proc to figure out where the best place is for a powerup in any given section, and for that matter where to place enemies and which kinds. We pass along the PRNG object so it can keep using predictable numbers.

If this whole level builder sounds more complex than I make it out to be, that's because it is. Procedural content generation isn't easy, but it is incredibly powerful--and if you approach it a piece at a time, it's definitely possible for you to do. What's more, it can produce parts of the game that you, the author, have never seen and can enjoy like any other player.

Obviously even this rough blueprint can be refined, too. You can make some sections more likely than others. Some sections might not appear or may be less frequent in the early levels, or you might make every 5th level a water theme. (In fact patterns like that are a great way to get players trying to figure them out.) The types of sections available can be changed by theme. You might create a "tough" version of each section and then choose one of the sections to be tougher than the others, to present a specific challenge spot in the level. The number of sections is even up for grabs; you could make, say, 10% of the levels have 12 sections instead of 8, but reward the players with a special bonus and with more powerups.

Exploring Out of Order

As an experiment, picture Shadowdarke's game Darke Dungeon with this technique in place. When researching in the library for a new dungeon, it might instead produce a random number hashed from the name of the dungeon. That number then produces a particular dungeon layout, with all its attendant monsters and treasures. What would Shadowdarke need to save after the dungeon has been explored? Only which doors have been destroyed, which chests looted, which items found (seen while in reach of the player), and which one-shot traps sprung.

So this concept works not just for content where you progress from one level to another, but it also lets you skip around within its "generation space" (all of the possible seeds) to explore new places. When I was younger and this new-fangled Internet thing wasn't really going strong yet, I used to dial up to a local BBS and play some of their games. My favorite game was Tradewars, in which you'd explore different parts of the galaxy, trade in the three major goods, and develop planets for profit. Finding the stations with the best prices available that would be buying or selling what you wanted could be tough, and it was easy to exhaust a trade route. There were 1,000 sectors in the game, starting with sector 1, and they interconnected almost randomly. Some sectors might have only one exit; others had multiple exits. And not all routes went both ways. Exploring was crucial; you could be the one person to find a nice safe backwater with a set of space stations buying and selling exactly what you could carry.

Imagine this as a BYOND game. You could have over 30,000 unique solar systems with the algorithm above. In each one you could determine the star type, numbers and types of planets in orbit, their level of development, preferred imports and exports, any space stations present, etc. With such a layout, the game would strongly reward explorers. Information would also be a valuable commodity; you could even set up NPCs to do the exploring for you and provide clues to vital systems, though they might leave out crucial details like the fact that a pirate fleet took up residence on the biggest moon of the large gas giant. Only a small savefile is needed for each system after its discovery, to track any changes to prices, local attitudes toward players, etc.

Lots of people remember Gauntlet fondly. That could easily be done with procedural content. Even a game like The Legend of Zelda would be doable with procedural content; you'd just have to decide how to place certain dungeons and items so they can't appear until the player has earned other certain items. To keep things fresh you might want to consider a wider pool of helpful items to find/buy and associated puzzles they can solve. So not every game would have to include a raft, for instance, if you had no areas that were only accessible over stretches of water. And if one of the items is a magic harp that splits certain kinds of rock, you should use that kind of rock to hide some special areas and maybe access to part of the map that couldn't be reached before.

Go Forth and Create

There are lots of techniques for generating procedural content. But by taking the reins of the PRNG, you can make your otherwise random content replayable. That's really pretty cool. Now with a game like Rogue, granted, the total surprise each time is what makes the game most interesting, but not all games will benefit from that. In a big, persistent multiplayer game, "seeded" content can create a truly rewarding experience.

What kind of game would you rather play? One with limited space to explore or one with practically boundless horizons? Having an actual map designer can give your game some truly great scenery and puzzles, without doubt, but one person, or even ten people, can only do so much. Procedural content can be made quite creatively; if you provide the algorithm lots of variety in its options, it will give you lots of variety in the output. Professional games are starting to realize the power of this technique too. It's time for you to discover that power in your own games.