Noise-Based RNG

[@dotaportalvideo]

These are the videos I'm here for.

[@kjpg7413]

Some super useful information here. Two pain points though: Perlin isn't good default to keep promoting for noise due to squareness, and Simplex/Perlin != Fractal noise. Squareness, or more generally visual anisotropy, runs principally counter to the nature-emulating goals of noise. Noise should look, to a reasonable degree, probabilistically the same in all directions. Simplex(-type) noise is better about that and, while mentioned in the talk, it was given an unfair backseat position. Fractal noise ("fractal Brownian motion" / fBm) is the process of adding together multiple layers of some base noise to produce the so-termed "crunchy" result. It's incredibly useful, but also worthwhile to understand as separate from any individual noise function. That way we can better convey the versatility of noise, and avoid invoking the name of a specific algorithm when we may not need to. Hash (integer "Noise") -> Smooth Noise (e.g. Simplex) -> Fractal Noise (+ many other formula options!), each a building block of the next. Once you move past this, this talk does a great job at covering important fundamentals.

[@ciberman]

Squirrel3 is at 44:34. And Squirrel3 with seed is at 51:52

[@KKomalShashank]

Squirrel Eiserloh was my game programming professor at SMU Guildhall. He was the best teacher I ever had. The most amazing person, who explained complex concepts in such a cool, interesting and easy-to-understand manner. Everyone has their No. 1 teacher that they remember fondly for the rest of their lives. For me, that teacher is Squirrel Eiserloh.

[@juanchis.investigadorsonoro]

Thanks for the presentation. 😀 00:00:00 Intro 00:02:00 Who is Squirrel Eiserloh? 00:02:30 What will we be talking about? 00:06:00 Talk Overview 00:06:30 What do we want in an RNG? 00:11:56 What RNGs should we consider? 00:19:20 Limitations of traditional RNGs 00:26:45 Noise functions 00:36:00 RNG-based Noise 00:46:30 Seeding Noise functions 00:47:35 Multidimensional Noise functions 00:50:18 Noise and RNG Takeaways

[@yivo3689]

Perfect timing~ That was a very impressive and detailed talk. I find it quite fascinating how RNG can be influenced, kinda predicted and willingly manipulated.

[@GameDevNerd]

This was a huge help to me as a game/engine programmer and answered a lot of questions I had about this subject without spending many long months going down the rabbit hole of researching and implementing these things and then exhaustively unit testing them

[@juyas6381]

52:00 not sure what the mistake is, but a prime should cleary end with a 1 in binary - BIT_NOISE1 does not - so its not actually a prime number - but like I heard from the talk, it is supposed to be at least.

[@BradenBest]

Put more simply: all primes (except 2) are odd, but not all odds are prime.

[@StianF]

None of them are prime numbers. I think he misspoke, I believe the objective of these numbers is to have "interesting bits" for a proper mangling process.

[@bonehelm]

I noticed the exact same thing and was very confused.

[@daveyhu]

46:33 is the algorithm, also at 51:59

[@Kindred192]

This makes the Factorio world generator make A LOT more sense (among other things). Thanks so much for this.

[@StianF]

44:32 He states "These are prime numbers", but none of them are. So what is the reason for this particular selection? As they're part of a larger set of operations of multiplication and bit shifting, is the purpose just to have "interesting bits"? If so, he just misspoke/misremembered, but then - what is considered "interesting bits"? And if not, then there's a pretty big issue with this code, for none of these numbers are prime numbers..

[@AltayHunter]

47:22 I'm disappointed to discover that he's wrong about std::hash being able to hash anything. In fact the code shown doesn't compile. std::hash is only defined with a single template argument, so the complier complains about the type std::hash.

[@VladyVeselinov]

I'm shaking, this is crazy good, thanks Squirrel!

[@brianviktor8212]

I wanted to transition from generating all data and saving and loading it from a database to using procedural generation. I had to work on the ideal RNG and I created a tool to create many iterations of RNGs with different parameters. They were a mix of bitshift, XOR, XAND and algebra operations (it also had +/-/*) from which I created random and varying amounts, but also varying amounts of bitshift-masks generated from its own RNG, and evaluated them at the end. So I created samples, each contained 100 RNG with varying seeds (0 to 999, or randomly picked, or in steps of ~1000, etc). But I had a special criteria, besides the usual - the FIRST result of each seed had to be measured too. I created a normal version of it, a light version, and I created a BitScrambler - which had the purpose of taking in coordinates (x,y,z) and creating differing numbers. It is like a RNG, but always starting from its zero-state (it only takes the input into account). Imagine that the input 0,0,0; 0,0,1; 0,1,0; 1,0,0 all had to create different numbers (for seeds), and it might go up to thousands or millions. At the end I did a tiny twist and it improved the output by at least a factor of million. Some generated seeds were still increments to each other. Each identical starting seed would mean that a certain coordinate was generating the SAME content as another one. In my early tests with my procedural galaxy generation I had very weird patterns, sometimes even grid-like structures. Now, as I am finished with all this, my galaxy looks exactly the way I want. Btw, storing 10.000.000 solar systems with all planet and moon data required 5gb. Now I can not only have galaxies of basically any size, but also any amount of galaxies. My system for positions is precise up to meters or even better and can map the entire observable universe.

[@danielrhouck]

This is very interesting, but I do want to point something out: the `std::hash` function is implementation-defined, and identity is completely compatible with the spec. I donʼt know if any implementations actually use it.

[@bonehelm]

I don't think this should be called noise, since that term is usually attributed to "organized noise" algorithms such as simplex, voronoi, etc. His algorithm is more like a stateless RNG to me. As you can use his stateless RNG to generate simplex noise, etc. His argument, to me, boils down to stateless RNG is better than stateful RNG.

[@vkessel]

If you parameterize the noise function by a seed, does that statistics suite account for different seeds? For example a noise function may work great at seed 0 but be highly correlated and fail tests at seed 255.

[@jameshood790]

Just watched this for the first time. A notable takeaway from this talk for me is that the random number generation aspect should be separated from the visual, organic aspect ("smooth noise.") We could and maybe should be comparing the quality and efficiency of noise smoothing algorithms in the same way that Squirrel compares the grade of the randomness of the numbers. And the two aspects should be separate, or at least clearly apparent and changeable in the source for those smooth noise generators.

[@Tesserakt8]

Second time watching this video in 48 hours, it's that good.

[@robbydomino]

Does anyone know how much of his speed measurements translate well when the RNG function is implemented on the GPU? For example I suppose the PerlinHash at 41:48 is way faster on a GPU and does not get stuck on some L2 Cache misses. I have many GPU based noise function implemented in fragment shaders. But i have no good way of measuring there performance. So any advice is welcome. Also any recommendation on how you would assert the performance of a fragment shader is welcome. I know counting the raw instructions is a thing but that would take a lot of time and manual work.

[@krisztianszendrodi7057]

Why not just render a quad? First render it with a basic shader, just outputing white, measuring the render time. Run it for a 1000 frames, get the average time. With that you can run measure the time it takes for say a 1000 frames of random data , substract the first result from it and then you get the time for the noise without other factors like draw calls or any driver or dx/gl level code. Of course you have to divide with the resolution. Also the performance would differ greatly if the framebuffer is too small and much time taken outside of your fragment shader

[@ColinPaddock]

It would be awesome if some math or CS savant would put up a table of large prime numbers with non-boring bits. Preferably, labeled as “good for 16/32/64 bits.”

[@ColinPaddock]

So… what are the licensing rules for using the squirrel hashes?

[@skyblazeeterno]

good presentation - well thought out arguments for using noise

[@cargorunnerUK]

Fantastic tutorial. Most of it makes great sense. Would have been nice to have a clear definition of what the speaker means by "noise functions" at the start. By the end I think he is calling the MD5 function a noise function. Where as generally discussions about noise functions discuss gradient noise functions (smoothed random numbers). It is really critical in your code to know if your sequence of random numbers are totally random or smoothed.

[@jonohiggs]

AFAIK in a discrete sampling they are random, the smoothness is just applied to make a continuous sampling without it looking like a step function

[@Spillerrec]

The problem is that the speaker does not have a theoretical background in the subject (he mentions this himself), and just defines for himself that "noise functions" are RNG's that satisfies his requirement of being random access. I think he came up with that naming because he has been using perlin/simplex noise which tends to be implemented that way, as they have structure/correlation over time/position. Hash functions have entirely different design goals as well, so pretending a hash function is more like a "noise function" than a seeded RNG doesn't make sense, he appears to be biased here. The solution he presents here is probably quite good for procedural generation (and I will consider using it myself), but I would do a proper evaluation before just applying it for other random stuff.

[@jonohiggs]

@@Spillerrec given the noise functions can be adapted to look like a noise function, then if the resulting sequence of numbers fulfils all the same statistical tests of randomness then I don’t see any reason not to think and use it like the other sources of random numbers. The ability to index into the sequence is actually super useful for Monte Carlo sims because if you have some degenerate case that breaks the model and need to debug then you don’t need to run the sim from the start but can just jump to that case directly (so long as the noise position is recorded and returned with the error reporting)

[@Spillerrec]

@@jonohiggs I meant his Squirrel3() function specifically (and I guess the std::hash version as well), not the concept. He did some automated tests, but I wouldn't trust that he hasn't overlooked something or might have an insufficient test of randomness. (Or as he mentioned, that std::hash might not be consistent across implementations.) I'm just saying, don't just let this be the Mersenne Twister replacement that is used without any considerations. I fully agree that sequential algorithms like most RNGs aren't that desirable anymore, as we push for more and more parallelism.

[@LeDabe]

I find quite strange that his Squirrel3 _and some other hashes_ are faster than the identity (aka increment an integer)

[@LeDabe]

See at 45:11 for instance. But this is not always the case for all is "benchmarks", depends on the slides..

[@LeDabe]

std::hash is generally implemented as "just return the given input integer". I don't know how he compiled his code, but I'd say that libc++ and libstdc++ and msvc have been implementing std::hash as just a return for a while now(forever ?), in this case it's a noop and the noise value returned should be bad (like his identity rng test). He may have cast the ints as bytes and ran std::hash on theses but that's not what he showed nor recommended.. Also, I'm not aware of std::hash taking 2 template arguments (47:22).

[@LeDabe]

A reason why most prng have state is that it prevents (or helps to prevent) backtracking resistance: csrc.nist.gov/glossary/term/Backtracking_Resistance . For gameplay related stuf its not necessary BUT it is as soon as you want a cryptographically sound system (dont encrypt your packets with FNV1a(incremented integer) key stream).

[@tupoiu]

​@@LeDabe They aren't. The only one that's faster is StackOverflow - which is admittedly very weird.

[@TheAIEpiphany]

you mentioned that int (positionX) overflowing easily is a feature not a bug, but given that int overflow is UB how can we know the behavior across platforms is what we expect it to be?

[@Sparrow420]

I love your talks man, great stuff!

[@legofan2284]

This is great, not just for games

[@tupoiu]

I bet the guy at 55:48 was throwing off the smaller part of the multiple of the large prime, rather than the bigger part. If you do this, the process is equivalent to multiplying by a smaller non prime.

[@Komagb]

That was intensely good!

[@MikePatterson8831]

Well, the std::hash code snippet doesn't work at all - it just returns the identical position it's fed. How is that at all useful for a random number generator? I don't want to have to feed a new string or object for every new random number. I don't really see how std::hash could be used in a similar way as the Squirrel3 method.

[@FelixTang32]

Thank you for the talk!!

[@naphipps28219]

pcg-random is also a really nice family of random generators. Edit: I would recommend looking up the randutils gist from the same author to get pcg32 and pcg64 with fixed entropy. It’s super easy after that. Edit2: I made a gist that I think sums it all up nicely: gist.github.com/naphipps/9784df722d45c8e1bbe7108d182c466a Let me know if you have any questions. (I hope that link works!)

[@fortesoft530]

I couldn't find the gist . Could you publish the link ?

[@naphipps28219]

@@fortesoft530 KZbin's fighting me replying to comments, but I updated my original. Let me know if you have any questions!

[@Alche_mist]

Godot Engine uses PCG32 as of now.

[@punpckldqd4322]

Very good talk! Sadly, slides and code aren't available on mathforgameprogrammers.com/ (maybe author no longer maintains it, i dont know)

[@Ziplock9000]

@Luc Bloom Nobody said it was hard, it's just convenient to copy and paste or use a repo

[@daveyhu]

@Luc Bloom he's just tweeted this month that there's at least one flaw in his algorithm btw

[@a1ivh]

Maybe someone can help me out with this. How exactly the noise function providing the random access? Through position or seed? For example in the example has been mentioned, if you have multiple NPC with a set of characteristics then NPC id would be the position and characteristic id would be the seed, right? Or vise versa or I got it totally wrong?

[@TechnoFreud]

The random access comes from the "position." As long as each NPC has an ID that remains constant, you can use one noise generator (e.g. Squirrel3), use one seed to get tooth length, a different seed to get how far they slouch forward, etc. These seeds could be hard-coded if you want them to be the same each time, or randomly generated using e.g. Mersenne twister when the world is first created. You have to scale the minimum and maximum values in a way that makes sense, or you could transform how they are distributed if you want 10% of your orcs to have super long teeth. It's probably more intuitive to think of literal x,y,z positions generating the likelihood of a bush growing there, etc.

[@Kakerate2]

16:00 17:30 27:40

[@barthpaleologue]

This is awesome !

[@ddotbuk]

Interestingly the new Unity Mathematics library uses a similar method.

[@muzboz]

What method is that, out of interest? I'm trying to use Squirrel Noise in my Unity project, and trying to get my head around quite what I should use it for, and whether it can replace Perlin Noise (smooth noise) or not. I'm a designers turned programmer, so my brain is smoking a bit trying to figure out exactly what and how I should be using this (in order to achieve deterministic results across a large procedurally generated game). I mainly want to get away from the sequential generation of random numbers messing with determinism. Do you think I should just be using Squirrel Noise to basically set up the initial SEED or starting point for my generators, but then just continue to use my existing Perlin Noise calls and everthing as they are (as I guess they're already deterministic)... ?

[@ddotbuk]

​@@muzboz IIRC at the time of the comment I was working with the new Maths library and I had noticed they were either using squirrel noise directly or at least something analogous to it. If you want non ordered determinism, then noise can do that for you if you seed properly. The bit at the end of the talk where he goes through uses as RNG and comparing against others is probably most applicable. If you're using this as terrain or similar, it will have a different visual quality to perlin but it will still be noise all the same. If you want it to be smoother you can reduce the sampling frequency and interpolate too.

[@muzboz]

@@ddotbuk Thanks for your thoughtful response! :)

[@jerrygreenest]

Let's pray to RNG god for a second, for letting us make the PCG

[@alexxkrehmen772]

Great stuff here :) What would be the most efficient piece of code to convert this int function to return a random float between 0 and 1 inclusive ? (and keeping the balance of the results)

[@vitorbalbino8024]

Once you get a value, knowing the min and max you can get, just make ( (result - min) / max ) + min.

[@DaveLeCompte]

Do you really need the _most_ efficient? I would imagine that masking off 24 bits of a 32-bit random integer and jamming them into a float32's mantissa bits would be one of the faster ways to get a random float, no divides necessary. Depends on how expensive divides are on your machine.

[@alexxkrehmen772]

@@DaveLeCompte In cases where you need to generates millions of random values quickly, the most efficient way seems appropriate 😅 Would you have an example of what your are describing please ?

[@DaveLeCompte]

@@alexxkrehmen772 If you look up IEEE floating point representation, you can see that a single-precision 32-bit float has a big block of bits for the mantissa, which you could copy from the output of a 32-bit integer noise function to get what you want. Shifting bits is probably faster to execute (as opposed to a subtraction, a divide, and an add), but would take you longer to understand the underlying formats, which might not be an efficient use of your programming time. en.wikipedia.org/wiki/IEEE_754 en.wikipedia.org/wiki/Single-precision_floating-point_format If you're using a fixed-point representation, you probably already know how your bits are laid out, and might be even simpler than loading the significand in a floating point representation. Depends on the specifics of your system(s).

[@alexxkrehmen772]

@@DaveLeCompte Ok thanks ! I'll try to dig into this 😁

[@TheGreatAtario]

…The man's name is _Squirrel?_

[@RiversJ]

Errr... Compute shader the noise function?

[@quantumoverlord4413]

I can pass my finals now :)

[@Svamenzi]

Didn't know that Ben Affleck got into gaming. :D Jk, great talk :)

[@gilleswalther5964]

Super interesting

[@petersmythe6462]

Re: trillions+ becomes masturbatory? I kinda disagree. Let's say you have 10000 areas and you examine each area for 100000 cycles of the RNG? There's a near certain chance one of those 10000 areas will contain duplicate "terrain" to another for an RNG in the low trillions sort of repeat time.

[@MrNotSpecified01]

Who would have thought just getting some numbers could be so difficult. Is there anything truly random in the universe?

[@AddGaming.]

yes. Quants. If you want some, there are simple python tutorials for accessing a companies quantum computer via API. just google it. "Qiskit" from IBM should be one of those

[@icorbrey]

@@AddGaming. Lmao we really be going RNGaaS

[@MyCarllee]

It's real randomness in the quantum realm, at least as far as current science knows. Anything entangled with quantum phenomenon is truely random, like our consciousness.

[@rafaelbordoni516]

If there were no true randomness in the universe, that would mean our own thoughts and ideas aren't random, they're predetermined. On another level, if they are predetermined by a seed but we don't have access to it, then we can't predict things and thus, by definition, it makes them random. Weird stuff, huh? I guess if we could at least determine if things are random or seeded, then we could at least work towards getting the seed. I know it doesn't answer the question, but it has interesting and scary philosophical implications.

[@dayanrodriguez1392]

"turn off your pager, if you're a drug dealer" lol

[@unvergebeneid]

In Soviet Russia, random numbers don't generate noise, noise generate random numbers.

[@TomNCatz]

this is a better summary of the talk

[@patrickj]

Not quite what I expected from the title, but the mention of a "noise function" kept me interested... and at the end slightly disappointed.

[@pfeilspitze]

TLDR ~~for the first 30 minutes~~: Use a hash function instead of a pRNG. You're welcome.

[@Ziplock9000]

It's ironic that he talks about data not repeating itself when he repeats the same concepts over and over! Good talk though.

[@phlegios]

For 50 something minutes, one programmer boasts about how he managed to come up with a better hash function!

[@thorham1346]

I like how he thinks noise functions are near infinite 🤣

[@beepboop9176]

Combing techniques of creating values out of nothing can create a lot of immersive experience. Minecraft was made based off noise generating math.

[@Ziplock9000]

Games have been using it 20-30 years before Minecraft.

[@gower1973]

Well that was a waste of an hour of my time the take away is use std::hash

[@cm5754]

The C++ standard allows std::hash to return the input as the hash for the input.