# Random looking item placement that's deterministic?

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?

-

## migrated from stackoverflow.comSep 20 '11 at 5:18

This question came from our site for professional and enthusiast programmers.

Why don't you have access to a seeded random number generator? – templatetypedef Sep 19 '11 at 23:42
It's a game maker like program and it doesn't have one :( – Whitney Shabaamaz Sep 19 '11 at 23:50
What game maker doesn't offer a seeded random number generator? Weird. – Patrick87 Sep 20 '11 at 0:01
Tagging it with the engine you're using would help us be more specific in the answers. – Martin Sojka Sep 20 '11 at 7:18

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.

-
This algorithm produces very good quality (as in "cryptographic" good) sets of random numbers (and even using 0 as your seed doesn't break it) -- it has been ported to many different languages (source included), and it's fast: burtleburtle.net/bob/rand/isaacafa.html – Randolf Richardson Sep 20 '11 at 15:08

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.

Just looking at wikipedia, this method looks promising:

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

-
I'm not the one downvoting it just trying to figure it out still :) – Whitney Shabaamaz Sep 19 '11 at 23:59
Thanks. Just a little frustrated how hard it is to earn 50 points so I can contribute comments... – Sky Kelsey Sep 20 '11 at 0:03
This is rather high overhead (computing a secure hash function for each element) for something that would work fine with a PRNG. (I'm not downvoting you, just explaining why I don't think it's the best solution.) – Nick Johnson Sep 20 '11 at 3:13
Agreed. Perhaps it could be made more efficient to use a fast but bad hashing algorithm, and implement it as a bit stream so as not to waste any? – Sky Kelsey Sep 20 '11 at 3:20

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 xprev to your seed.
Then every time you want to generate a new value xnext, just do

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

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

-

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

-

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.

-

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.

-

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.

-
I think this, coupled with any of the approaches given as answers for generating the numbers, is going to be the easiest for you to implement in the off-the-shelf engine you're using. – technomalogical Sep 23 '11 at 21:06

Another approach:

Use a block cipher to "encrypt" a series of numbers from 1 to N, using a fixed key. TEA is easy to implement and fairly fast.

One advantage of this approach is that if you don't like the series of "random" numbers which you get back, you can try a different encryption key and get a whole different series back.

-