Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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.

share|improve this question

closed as too broad by Anko, Vaughan Hilts, Byte56 May 23 at 13:15

There are either too many possible answers, or good answers would be too long for this format. Please add details to narrow the answer set or to isolate an issue that can be answered in a few paragraphs.If this question can be reworded to fit the rules in the help center, please edit the question.

    
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) –  Kaj Aug 5 '10 at 5:12
1  
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 –  anthony-arnold Aug 5 '10 at 5:15
    
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. –  Kaj Aug 5 '10 at 5:44
    
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. –  Adam Harte Aug 5 '10 at 6:46
8  
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. –  Heath Hunnicutt Aug 6 '10 at 20:14
show 2 more comments

3 Answers 3

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.

share|improve this answer
add comment

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).

share|improve this answer
    
+1 for Perlin-Noise –  ninesided Aug 5 '10 at 10:47
add comment

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!

share|improve this answer
add comment

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