Random looking item placement that's deterministic?

Question

I'm working on a sidescrolling game and I want to generate a forest for the background. I want the background to be the same for every one to make sure the quality is the same. I don't have access to a seeded random number generator either, so I can't find a good seed and go from there.

Ideas?

Answer 1

The most obvious way would probably be to write a random number generator of your own. Especially since you don't need to meet any particularly high standards for randomness (just lack of obviously visible patterns) it's pretty easy to write a pretty reasonable one in under a half dozen lines of code.

Answer 2

Try this. Iterate from numbers 1 to n, where n is the number of trees you want to draw. Compute a hash on each number. Use the hash as input for the function that draws or positions the elements in the background. For instance, you could use the first 8 bits of a 128-bit MD5 hash as the x percentage, the next as the y percentage, the next as some sort of x scaling, etc. If you use the same hash function, and give the same inputs, each time you run it you will get the same output.

This should absolutely give both good randomness and will be deterministic.

Also, if this is not a good answer, please leave a comment explaining why.

Just looking at wikipedia, this method looks promising:

http://en.wikipedia.org/wiki/Random_number_generation#Computational_methods

Answer 3

If you have access to any sort of hash (like MD5) or checksum (like CRC32), you could just hash a sequence of numbers.

Otherwise, the simplest PRNG would probably be the Linear Congruential Generator. It has a complicated-sounding name, but writing one is extremely simple:

Choose three constants, m, a, and c.
Begin by setting x_prev to your seed.
Then every time you want to generate a new value x_next, just do

xnext = (a*xprev + c) mod m  
xprev = xnext

Some good choices for m, a, and c can be found here.

Answer 4

You could apply the cicada principle (use prime numbers for intervals).

Answer 5

Given that a seeded random number generated is essentially just a look up table with the seed being the offset (starting index), you can set up a simple one by reading in a CSV (comma seperated values) file of numbers.

As long as all instances use the same seed, it will be deterministic whilst maintaining it pseudo-randomness.

Answer 6

One possibility is to use an algorithm called simplex noise, invented by Ken Perlin (known for Perlin Noise). One nice feature of simplex noise (like Perlin noise) is that it can be tiled - ie, only a small region out of the potential area needs to be calculated and this can be repeated over the entire area without visible seams.

For the noise function to be repeatable, i.e. always yield the same value for a given input point, gradients need to be pseudo-random, not truly random. They need to have enough variation to conceal the fact that the function is not truly random, but too much variation will cause unpredictable behaviour for the noise function

Simplex noise can be generated faster than Perlin noise and does not require a random number generator. It is not arbitrary to implement just by knowing the theory, but there is some source code to help you along (referenced from Wikipedia).

Other options for generating pseudo-random noise are fractals and wavelets.

On your situation you would use one of these techniques to generate a series of data in one dimension, and then apply a threshold to determine whether a tree should be placed at that position.

Answer 7

Simplest answer: Make your program load a file with pre-generated numbers in it and write a simple utility to generate random (or algorithmic in any case) numbers to save into that file.

In this way you can generate files that are mostly-good and hand tweak the remaining parts of it that suck without getting into the problem where every random seed you try has some problem with it.