49
\$\begingroup\$

How would I go about using a random seed to generate a game level? The same seed should always generate the exact same level.

For this example it would be a Worms style level. So each level would have a theme (grasslands, snow etc), base terrain, different objects such as trees.

So where would I start to create this kind of level generator? What would be involved? What concepts does it use?

Bonus points for any any good links (bonus bonus points for anything related to how it was done in worms or similar).

Thanks.

\$\endgroup\$
7
  • \$\begingroup\$ Random level generation is also known as Procedural Content Generation (PCG). And here's a wiki dealing with just that. pcg.wikidot.com Should give you some ideas! :o) \$\endgroup\$
    – Kaj
    Aug 5, 2010 at 5:12
  • 1
    \$\begingroup\$ Chris Crawford has an article which you might find interesting. It was written in the early 90s but still relevant. How to Build a World \$\endgroup\$
    – Anthony
    Aug 5, 2010 at 5:15
  • \$\begingroup\$ If you use any form or algorithm that uses the same random number generator (except one that somehow sneaks in an invariant like system time), the same seed will generate the same level, there's really no way around it. \$\endgroup\$
    – Kaj
    Aug 5, 2010 at 5:44
  • 1
    \$\begingroup\$ Yes, but I think the trick is actually using a seed in the first place to generate the level from. I have built random level generators before, but they didn't use a single seed. Often I would choose random points, then for each point choose a random asset to place there. Doing it this way there is no ONE true seed that will always generate the same level, as there are a bunch of things generating there own random numbers. \$\endgroup\$
    – Adam Harte
    Aug 5, 2010 at 6:46
  • 10
    \$\begingroup\$ Are you sure you know what "seed" means? This is the "initial vector" passed in via, e.g., srand(int). Subsequent calls to rand() will return sequential values that are always calculated in the same order, based on this seed. You set the seed once in your program. After that, if the algorithm depends only on the results from rand, you will get the same result every time. \$\endgroup\$ Aug 6, 2010 at 20:14

3 Answers 3

8
\$\begingroup\$

The key to this is using your own custom pseudo-random number generator that you initialize with the known seed value. The "Mersenne Twister" is a popular algorithm, here is the Wikipedia entry and some sample source. This, and other, PRNG algorithms actually produce a (very long) fixed series of numbers for which the seed value serves as a starting point.

So long as you follow the exact same procedure for generating your world every time, each value will represent a unique reproducible world.

\$\endgroup\$
4
\$\begingroup\$

Here's a PRNG (pseudo random number generator) implemented in ActionScript (available in AS2 or AS3). It's lightweight and fast, ideal for games: http://lab.polygonal.de/2007/04/21/a-good-pseudo-random-number-generator-prng/

The above implementation is based on the Park-Miller-Carta PRNG. This site will give you some more insight about the math behind all this.

To build a worms-like level, I would probably use a Perlin-Noise function though. If you generate a perlin noise image with the height of 1px and the width of your game-world, then you basically get a height map, ready to use. Perlin noise functions also always generate the same map with the same seed.

You can then use the PRNG mentioned above to determine where to place random Objects on the map, or where to create a hole in the ground. For holes you could also take advantage of perlin noise again. Just create a perlin-noise image with the size of your map (x, y), and then create a hole in your map where the pixel-value is below a given threshold (eg. 0.2).

\$\endgroup\$
1
  • \$\begingroup\$ I'd use perlin noise, but a bit differently, use it to create a 3D height map, put the map on a slope and remove all the pixels lower than your threshold. ( if pixel.height - (pixel.distanceToBottom*slopeFactor) < treshold) pixel = transparent) \$\endgroup\$
    – Niels
    Feb 23, 2016 at 13:18
2
\$\begingroup\$

Theoretically if you can use a pseudo-random number generator (such as Perlin-Noise or Marsenne Twister) to share maps via

seed numbers then you can also create custom maps and reduce them to seeds, solving the issue of not being able to create

custom maps when using PRNGs. This however is built on a few presumptions. Namely that pseudo-random number generators are

a reversible process and that ANY data fed backwards into a PRNG will produce a valid seed, let alone a seed at all!

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Generally speaking, these generation processes aren't easily reversible. This is, in part, due to the fact that when generating larger, more complex levels, there will almost certainly be many valid custom maps which do not correspond to any possible seed. Of course, this entirely depends on implementation, but true reversible level generation may be more effort than it's worth. \$\endgroup\$
    – user139729
    May 17, 2020 at 16:46

Not the answer you're looking for? Browse other questions tagged .