CODEWITHSUNDEEP
pythonrandom
Sophie Swett
Sophie Swett

Reputation: 3390

A random noise function in Python

I'm writing a game in Python in which the environment is generated randomly. Currently, the game's "save" function works by writing out all parts of the environment which the player has explored. The result is that save files are larger than they need to be—why write random data to disk when you can just generate it again?

What I could use is a random noise function: a function noise such that noise(x) returns a random number, and always the same number whenever it's called with the same value of x. Now, for each point (x,y) in the game's environment, instead of generating a random number using random() and storing the result in env[(x,y)], I can generate a random number using noise((x,y)), throw it away, and generate the same number later.

Upvotes: 3

Views: 7843

Answers (3)

dbr
dbr

Reputation: 169563

Not quite sure if I'm stating the obvious, but using some variation of a Perlin noise generator is a common way to do this. This post is a nice description of doing exactly this (as mentioned in the comments, it's not exactly Perlin noise)

For a given position, the Perlin function will return a random value (the position can be 2D, 3D or any dimensionality).

There is a noise module, and this page has a implementation of it

There's a similar thread on gamedev.SE

Upvotes: 5

abarnert
abarnert

Reputation: 365707

First, if you need it to be true that noise(x) would always return the same value for the same x, no matter what, even if it's never been called, then you can't really use randomness at all. A good hash function is the only possibility.

However, if you just need to be able to restore a previous state consisting of the values for all of the previously-explored points (never-explored points may turn out different after save and load than if you hadn't quit… but how can anyone tell without access to multiple universes?), and you don't want to store all of those points, then it might be reasonable to regenerate them.

But let's back up a step. You want something that acts like a hash function. Is there a hash function you can use?

I'd imagine the algorithms in hashlib are too slow (md5 is probably the fastest, but test them all), but I wouldn't reject them without actually testing.

It's possible that the "random period" of zlib.adler32 (or zlib.crc32) is too short, but I wouldn't reject it (except maybe hash) without thinking through whether it's good enough. For that matter, even hash plus a decent fixed-side blender function might be good enough (at least on a 64-bit system).

Python doesn't come with anything "between" md5 and `adler32' out of the box. But you can find PyPI modules or source recipes for hundreds of other hash algorithms. For that matter, if you're familiar with any particular hash algorithm that sounds good, most of them are trivial—you could probably code up, e.g., an FNV hash with xor-folding in less time than it takes you to look through the alternatives.

Also, keep in mind that you can generate a bunch of random bytes at "new game" time, store that in the save file, and use it as salt to your hash function.

If you've exhausted the possibilities are you really do need more randomness than a fast-enough hash function with arbitrary salt can give you alone, then:

It sounds like you'll already need to store a list of the points the user has explored (because how else do you know which points you need to restore?). And the order doesn't really matter. So, you can store them in the order of exploration. That means you can regenerate the values deterministically (just by iterating the list). Which means you can use the suggestion by @delnan on your own answer.

However, seed is not the way to do that. It isn't guaranteed to put the RNG into the same state each time across runs, Python versions, machines, etc. For that, you need setstate:

  • To save, call random.getstate(), and pickle and stash the result.
  • To load, read and unpickle the state, and call random.setstate(state).

See the docs for full details.

If you're using a random.Random instance, it's exactly the same, except of course that you have to construct a random.Random before you can call setstate on it.

This is guaranteed to work between runs of your program, across machines, etc. Even with a newer version of Python. However, it's not guaranteed to work with an older version of Python. (That is, if the user saves a game with Python 2.6, then tries to load it with 2.5, the state will not be compatible. I believe the only problems come with 2.6->older and 2.3->older, but of course there's no guarantee there won't be additional ones in the future.) I'd suggest stashing the Python version, and if they've downgraded, show a warning saying "This save file requires Python 2.6 or later. You have Python 2.5. The load may fail. Continue anyway?"

This is only guaranteed for random.Random and for the random module itself (since the top-level module functions just use a hidden random.Random). In particular, random.SystemRandom are explicitly documented not to work.

Practically speaking, you can also just pickle a random.Random directly, because the state gets pickled in. It seems like that ought to work, or what would be the sense of pickling a Random object? And it definitely does work. But it isn't actually documented to work, so I'd stick with pickling the getstate, for safety.

Upvotes: 2

Sophie Swett
Sophie Swett

Reputation: 3390

One possible implementation of noise is this:

import random

def noise(point):
    gen = random.Random()
    gen.seed(point)
    return gen.random()

I don't know how fast Random.seed() is, though. In addition, Random may change from one version of Python to the next, causing the players of my game to find that the environment changes when they upgrade.

Upvotes: 1

Related Questions