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.

These are the videos I'm here for.

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

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.

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.

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

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

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

I love your talks man, great stuff!

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

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.

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

good presentation - well thought out arguments for using noise

Thank you for the talk!!

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.

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

2 жыл бұрын

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.

This is great, not just for games

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

That was intensely good!

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

3 жыл бұрын

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

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.

This is awesome !

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

2 жыл бұрын

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

2 жыл бұрын

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

2 жыл бұрын

@@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

2 жыл бұрын

@@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.

Super interesting

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.

Interestingly the new Unity Mathematics library uses a similar method.

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

2 жыл бұрын

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.

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 😁

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.

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

3 жыл бұрын

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

@naphipps28219

3 жыл бұрын

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

@Alche_mist

2 жыл бұрын

Godot Engine uses PCG32 as of now.

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

@Ziplock9000

3 жыл бұрын

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

@daveyhu

2 жыл бұрын

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

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..

16:00 17:30 27:40

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

@LeDabe

3 жыл бұрын

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

@LeDabe

3 жыл бұрын

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

3 жыл бұрын

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.

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

I can pass my finals now :)

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.

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.

…The man's name is _Squirrel?_

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

Errr... Compute shader the noise function?

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

@AddGaming.

3 жыл бұрын

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

3 жыл бұрын

@@AddGaming. Lmao we really be going RNGaaS

@MyCarllee

3 жыл бұрын

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

2 жыл бұрын

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.

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.

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

@TomNCatz

3 жыл бұрын

this is a better summary of the talk

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

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

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

I like how he thinks noise functions are near infinite 🤣

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

@Ziplock9000

3 жыл бұрын

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

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

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

@cm5754

3 жыл бұрын

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