Jump to content

  • Log In with Google      Sign In   
  • Create Account

- - - - -

Generating Seeds

Posted by , 19 August 2014 · 705 views

A seed is a number used to initialise a random number generator. They are important because it allows a generator to give the same sequence of random numbers again. In fact the sequence of numbers generated is typically deterministic, so the seed is a bit like giving it a starting point in this long sequence.

Without a seed you wouldn't be able to have a save game in a procedurally generated world and guarantee it would be the same world when you load it up again. (Unless this game saved all the generated data the first time it made it. But mesh!)

I'm using seeds as part of how I uniquely identify generated objects of a particular type. For example, let's say I'm generating seeds for cars. A car with seed 5 is different to a car with seed 6. Every time I generate car 5 though its identical to every other car 5 (I will be using auto tests to ensure as such). Next I generate planets. If a planet has seed 5 too it's fine, it doesn't matter that it shares a seed with a car. The seed is used to ensure the generation process makes the same result, that's all.

OK, let's say we're generating a solar system and we're making seeds for each planet. We want each solar system to be different so we make random seeds to fill them. If by chance our random number generator produces the same number twice then we'd have two identical planets. Totally identical planets in the same system. Down to the cities and forests and blades of grass. Not cool. Sometimes it's OK if you get the same thing made multiple times in a set, like trees in a forest, but not here.

A naive approach to solve this would be to check a newly produced seed against the set of seeds we've already produced to see if any are the same. If it's a duplicate then we make another. In small lists this may be OK but with larger lists things start to crawl, and even worse it will slow down unpredictably because its random as to when you'll make a new number that's OK.

My plan to deal with this is to use a Linear Feedback Shift Register (LFSR - http://en.wikipedia.org/wiki/Linear_feedback_shift_register). These can be used to create sequences of pseudo random numbers which generate each possible number within a finite range once before repeating. By using this you'll never have repeating planets within the same solar system Posted Image Its not all perfect though, depending on what you need from it. Also this doesn't solve having the same planet appear many times within a galaxy, or in fact the same sequences of planets in different solar systems. But I'll discuss that more in future post.

Do note however that having your PRNG (which is then really a pseudorandom permutation) go through all the integers in a given range once does not necessarily guarantee all your worlds will be unique, depending on how you use the seed you may end up with two seeds that generate the same, or almost identical worlds! One other possibility to deal with this is to also make the player spawn in a random place dependent - or not - on the seed. Interesting nonetheless! Procedural universes are always awesome.

December 2016 »

4 5678910

Recent Entries

Recent Comments