5 ms·
PCG32: The Perfect PRNG for Roguelikes (2018)
- gliptic 5y agoHow is "stream" not just half of the seed? This is a property of every PRNG with large enough seed.
- jsheard 5y agoThe difference is when you're using many PRNG instances in parallel for SIMD, or threaded, or distributed applications, randomly seeded PRNGs might land close to each other in the sequence and end up correlated with each other, but if you ensure each one has a unique stream that's guaranteed not to happen.
- searealist 5y agoThe choice is not "randomly seeded" vs "streams". If you have a 64 bit seed + 64 bit stream, then it's trivially the same as a 128 bit seed. Just use the top 64 bits of the 128 bit seed as the "stream id".
- jsheard 5y agoPartitioning the seed into "seed + ID" only protects you from using the exact same seed for multiple generators, those unique seeds can still begin close to each other in the sequence and overlap their outputs as they step through it. With proper streams every generator has a different sequence so no matter how the seeds are generated, or even if the seeds are the same, they won't overlap each other at any point. For a game it probably doesn't matter, but for more statistically demanding applications it's a nice property to have.
- CGamesPlay 5y agoI'm very confused by what you're saying. It seems you're saying that knowing the state of stream 1 teaches me some information about stream 2, specifically that it's guaranteed not to overlap outputs to the first stream. Why is that desirable?
- searealist 5y agoYeah, I guess you really just need a jump function and then streams are just partitioning the space by whatever distance.
- attractivechaos 5y agoYes, it works, if you can jump 2^64 iterations quickly. This is how xoroshiro achieves multiple streams. The PCG32 or the xoroshiro method guarantees independent streams. Using high bits in seeds doesn't have the guaranteed behavior. When you have many streams, stream collisions may become an issue.
- fpgaminer 5y agoRight? I'd also be concerned about hash collisions causing one to accidentally generate the same level twice. Seems better to use something like ChaCha; plenty fast and a much large seed space.
- irskep 5y agoHi, I wrote this post and I've come to agree with you. That's all. :-)
- zackees 5y agoThe problem this seems to be solving, which is that the seeded random number used to generate the level is mixed with the seeded random number used to affect combat. It just seems trivial to solve though... or maybe I'm getting something wrong... but the solution seems to be to use the seeded random number to generate the level, and then copy the the last output of the random number to seed a new random number controlling combat. That is, the random number generating the level is immutable with respect to the combat random number? What am I missing?
- hexmiles 5y agoI also don't understand, i solved (what i think is) the same problem by having a master rng whose output seeded individual rng, one for map generation, one for enemy ai, one for loot, etc...
- attractivechaos 5y agoThis depends on what RNG you are using. If the master and the secondary RNGs use the same algorithm without extra internal states (e.g. splitmix or LCG), you will be generating the same stream over and over with small shifts. The end result may not be obvious in your use case, but can be a catastrophe for statistical simulation or the implementation of dropout. PCG32 is a proper solution. Xorshiro provides another solution by using one simple function to advance the internal state by 2^64 iterations.
- 37ef_ced3 5y agoBTW, xoroshiro should not be used. See the last section of this: https://lemire.me/blog/2017/09/08/the-xorshift128-random-number-generator-fails-bigcrush/ https://lemire.me/blog/2017/09/08/the-xorshift128-random-num...
- attractivechaos 5y agoI was aware of that blog post as well as the counter argument by the xoroshiro author against PCG. I am not studying RNG and can't say which is more correct. To me, I use xoroshiro mainly because PCG64 is complex to implement. My applications do not need extreme randomness so far.
- 37ef_ced3 5y agoTo give you a sense of how tiny and simple this excellent pseudorandom number generator is, here is a stand-alone implementation of PCG32 in Go: package pcg32 type Src [2]uint64 func New(bits1, bits2 uint64) *Src { return &Src{bits1, bits2 | 1} } func (s *Src) Uint32() uint32 { var ( x = s[0] y = uint32(x >> 59) z = uint32((x>>18 ^ x) >> 27) ) s[0] = s[1] + x*6364136223846793005 return z>>y | z<<(-y&31) } func (s *Src) LessThan(n uint32) uint32 { for min := -n % n; ; { r := s.Uint32() if r >= min { return r % n } } }
- aappleby 5y agoI predict that prng will totally fail the DieHard tests.
- 37ef_ced3 5y agoAnd you'd be wrong Here: https://www.johndcook.com/blog/2017/07/07/testing-the-pcg-random-number-generator/ https://www.johndcook.com/blog/2017/07/07/testing-the-pcg-ra...
- aappleby 5y agoI could very well be wrong, I haven't checked yet. That said, I have done a bit of work with these sort of things.
- aappleby 5y agoI'll read the paper.
- aappleby 5y agoAh, I missed that there was a data-dependent rotation applied in the output. So it's a lcg plus xorshift plus ddr. Still weaker than I'd like, but if it passes DieHard etc then it passes.
- 5y ago
- aappleby 5y agoYou can get the same result by hashing seed+level_id+some_counter, you don't really need a prng.
- aappleby 5y agoThe _advance function in this prng is also way too weak, purely linear with a tiny bit of output mixing. Replacing self.state with the (64-bit) result of the xorshifts would help a lot.
- irskep 5y agoHi, I wrote this. I'm very surprised it made the front page and I'm a bit embarrassed. People pointing out you can just hash the seed for different "streams" are completely correct, and in video games, people generally don't care about whether two PRNGs are correlated. I originally found PCG32 because I needed to implement a pure-Swift, cross-platform PRNG for a game jam so my game would run on Linux as well as Mac. For that purpose, it was great.