5 ms·

This is good to think about! Often when programming games that need certain properties, I'll write my own toy PRNG, but I'll admit I'd love to learn more about

by danbolt 11y ago

This is good to think about! Often when programming games that need certain properties, I'll write my own toy PRNG, but I'll admit I'd love to learn more about the craft. Would you have any suggested reading material on the topic?

resc1440 11y ago
As an outsider to the field, I really enjoyed reading this paper: http://www.pcg-random.org/paper.html http://www.pcg-random.org/paper.html It's advocating for a particular new kind of PRNG, but it also includes a lot of great explanations and citations for more reading.
- yoklov 11y ago
  As a shameless plug, I wrote a JS port of this RNG algorithm a while back: https://www.npmjs.com/package/pcg-random https://www.npmjs.com/package/pcg-random .
PhantomGremlin 11y ago
any suggested reading material on the topic? The Art of Computer Programming, Vol. 2, (c) 1969, by Donald Knuth, has quite an extensive discussion of random numbers, their properties, algorithms, and tests. It's about 160 pages in my edition. It's very readable, and even if you skip all the exercises you will still get a very good grounding. I don't know how much has changed in his more recent editions. And I don't know how if there are better books. But, in general, you can't go wrong by starting with Knuth. He's one of the all time greats!
yoklov 11y ago
For games, the most important features (other than the features of an RNG that all applications desire, such as good performance, high period, etc.) are being able to seed the state, and save/restore the state (required for save game support if you need seeding and want that to work after they save and restore the game).
- zeveb 11y ago
  For a modern game, is there any particular reason why 'seed = SHA256(seed + "reseed"); return SHA256(seed + "value")' isn't a good enough, performant enough RNG?
  - vonmoltke 11y ago
    For starters, there is nothing random about it.
    - zeveb 11y ago
      > For starters, there is nothing random about it. Yes, since the original post wanted seedability: > > For games, the most important features (other than the features of an RNG that all applications desire, such as good performance, high period, etc.) are being able to seed the state, and save/restore the state (required for save game support if you need seeding and want that to work after they save and restore the game). Given that restriction, what's wrong with the generator I suggest?
      - vonmoltke 11y ago
        It's not random. It's not a generator. You are just returning a different representation of the seed you already have.
        zeveb 11y ago
        > It's not random. It's not a generator. No, it's a pseudorandom generator. It's a key attribute of a cryptographically secure function like SHA256 that its output is indistinguishable from random bits. > You are just returning a different representation of the seed you already have. I'm returning a function of the seed, yes. That's the whole point of a seeded PRNG: that seed(x); rng(); rng(); rng() will always return the same sequence of results. This is used for example in procedural generation, to ensure that a dungeon level or map chunk is always generated the same way (a cool hack, then, is to just store the seed instead of the level itself, and rerun the level-generation algorithm with the seed when one wishes to regenerate the level). In such an application one wants the appearance of randomness, but with repeatability. Which was what the original post asked for. What I suggested is not secure for generating keys or for other cryptographic purposes.
malingo 11y ago
This is a great 2-part article: http://www.drdobbs.com/tools/fast-high-quality-parallel-random-number/231000484 http://www.drdobbs.com/tools/fast-high-quality-parallel-rand...

by danbolt 11y ago

resc1440 11y ago

As an outsider to the field, I really enjoyed reading this paper: http://www.pcg-random.org/paper.html http://www.pcg-random.org/paper.html It's advocating for a particular new kind of PRNG, but it also includes a lot of great explanations and citations for more reading.

yoklov 11y ago
As a shameless plug, I wrote a JS port of this RNG algorithm a while back: https://www.npmjs.com/package/pcg-random https://www.npmjs.com/package/pcg-random .

PhantomGremlin 11y ago

any suggested reading material on the topic? The Art of Computer Programming, Vol. 2, (c) 1969, by Donald Knuth, has quite an extensive discussion of random numbers, their properties, algorithms, and tests. It's about 160 pages in my edition. It's very readable, and even if you skip all the exercises you will still get a very good grounding. I don't know how much has changed in his more recent editions. And I don't know how if there are better books. But, in general, you can't go wrong by starting with Knuth. He's one of the all time greats!

yoklov 11y ago

For games, the most important features (other than the features of an RNG that all applications desire, such as good performance, high period, etc.) are being able to seed the state, and save/restore the state (required for save game support if you need seeding and want that to work after they save and restore the game).

zeveb 11y ago
For a modern game, is there any particular reason why 'seed = SHA256(seed + "reseed"); return SHA256(seed + "value")' isn't a good enough, performant enough RNG?
- vonmoltke 11y ago
  For starters, there is nothing random about it.
  - zeveb 11y ago
    > For starters, there is nothing random about it. Yes, since the original post wanted seedability: > > For games, the most important features (other than the features of an RNG that all applications desire, such as good performance, high period, etc.) are being able to seed the state, and save/restore the state (required for save game support if you need seeding and want that to work after they save and restore the game). Given that restriction, what's wrong with the generator I suggest?
    - vonmoltke 11y ago
      It's not random. It's not a generator. You are just returning a different representation of the seed you already have.
      - zeveb 11y ago
        > It's not random. It's not a generator. No, it's a pseudorandom generator. It's a key attribute of a cryptographically secure function like SHA256 that its output is indistinguishable from random bits. > You are just returning a different representation of the seed you already have. I'm returning a function of the seed, yes. That's the whole point of a seeded PRNG: that seed(x); rng(); rng(); rng() will always return the same sequence of results. This is used for example in procedural generation, to ensure that a dungeon level or map chunk is always generated the same way (a cool hack, then, is to just store the seed instead of the level itself, and rerun the level-generation algorithm with the seed when one wishes to regenerate the level). In such an application one wants the appearance of randomness, but with repeatability. Which was what the original post asked for. What I suggested is not secure for generating keys or for other cryptographic purposes.

malingo 11y ago

This is a great 2-part article: http://www.drdobbs.com/tools/fast-high-quality-parallel-random-number/231000484 http://www.drdobbs.com/tools/fast-high-quality-parallel-rand...