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
    
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
4  
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
    
The subversion blog has some interesting examples of generated levels. In particular the movie for part 7. It doesn't have any code or algorithms but it shows how you can build up the detail in the generated level. –  Luke Quinane May 6 '11 at 12:29
add comment

7 Answers

up vote 37 down vote accepted

Random level generation is also known as Procedural Content Generation (PCG). And here's a wiki dealing with just that.
http://pcg.wikidot.com/
Should give you some ideas! :o)

share|improve this answer
    
Oh wow, a whole wiki! I will take a look –  Adam Harte Aug 5 '10 at 5:15
    
Guys!! Ffs stop upvoting this answer!! It's just a link!! What is wrong with everybody?? –  bobobobo May 13 '12 at 14:38
3  
You're complaining on a two year old answer.. And so what if it's only a link? This is a broad question, so pasting relevant sections into the answer is a bit hard. People have upvoted because they found the link useful. It's as easy as that. –  Matsemann May 13 '12 at 15:23
3  
@bobobobo This is a good answer to what is a fairly open question. This answer provides a term to represent the concept, which means Googling for resources is now much more realistic for anyone who finds this, and the wiki has a lot of excellent information. It fits the question nicely. –  John H May 13 '12 at 16:03
add comment

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

Chris Crawford has an article which you might find interesting. It's nearly 20 years old but still relevant. How to Build a World

share|improve this answer
add comment

You may be interested in some of the answers to Games that feature procedural generation of content? at gaming.SE as reference or inspiration.

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

I had a bunch of bookmarks on the very topic or worms style map generation, unfortunaly the site with the best tutorial seems to be long gone, but archive.org has a snapshot. its missing the screenshot, but luckily some of those are preserved in a gamedev.net picture of the day :)

also in that bookmark folder ive got this on terrian destruction and some info on how physics work in worms.

share|improve this answer
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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