46
\$\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\$

closed as too broad by Anko, Vaughan Hilts, MichaelHouse May 23 '14 at 13:15

Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer. Avoid asking multiple distinct questions at once. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • \$\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 '10 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 '10 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 '10 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 '10 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\$ – Heath Hunnicutt Aug 6 '10 at 20:14
7
\$\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\$
  • \$\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 '16 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\$

Not the answer you're looking for? Browse other questions tagged or ask your own question.