Noise-Based RNG

[Music] good morning welcome to gdc 2017. thank you for getting up on monday morning and coming to see us this is the math for game programmers tutorial we're going to be doing sessions throughout the day on various topics in math in games so feel free to join for whichever sessions you like i'm supposed to ask you and remind you please silence your phones or your pagers if you're a drug dealer and at the end of the session if you haven't been to gdc before or if you have it's good to be reminded you'll be getting an email that asks you to review the session please do uh the review it just takes a second and we really appreciate and read the feedback that you give so um so today's schedule we're gonna be doing uh two one-hour talks this morning with myself and then mike acton and then

we're going to break for lunch and then we're going to have a number of half hour talks in the afternoon and we'll have this schedule up as we go okay so first i just want to get a sense of who's in the room so um please raise your hand if this is your first gdc ever awesome that's about half two-thirds of the room and then put those hands back up please and also if you've been to gc but you've never been to this tutorial before okay so that's mostly first-timers uh please raise your hand if you're a student only a few an educator a couple as well uh or if you work in games full-time okay the vast majority of them okay so my talk is space-based random generation um more like why be random when you can be noisy or i'm going to make a claim that anything random can do noise can do better

so i'm a game designer programmer i've been coding since the apple ii my background's in physics i've been doing this professionally a long time and i present regularly at the gdc and i teach now at smu guild hall which is a grad school for game development i've worked at a bunch of companies i was a tech director or lead programmer at each of those companies and i've worked with a bunch of companies on a bunch of projects so today we're talking about number generators right from rand to whatever else we're going to talk about some noise functions and i'm going to get into that a little bit just a couple of revisions of smooth or fractal noise like purlin noise or simplex noise i'm going to make a case that i think noise is more valuable in some cases than random or can even supersede random and then we'll of course try to give some application and context for all this stuff so the talk is for anyone who's interested in procedural content generation that's been a hot topic lately of course anyone who's just rolling dice

for random outcomes in general if you're using ran this talk is definitely for you even if you're using the mercen twister or something you think is more sophisticated this talk is for you or if you're doing any sort of noise or hash functions and you're using something like md5 or sha or something you found on stack overflow this is definitely a talk for you okay so some example use cases just to frame um what is this because everything context is king right uh depends on what we're doing so uh one of the most popular things we're going to use random numbers for and noise is for generating procedure worlds right and everyone thinks about you know height maps generating mountains and lakes and yes we can do that or generating random dungeons for roguelikes or something yes we can do that there's a lot more we can generate though right we might generate planets or villages spaceships flowers random npcs with random genders and personalities and backgrounds and professions random quests right so

there's a lot of other things we might want to do with generation other than just mountains there are some harder problems that are more nuanced too and uh shay pierce is going to talk about this a little bit this afternoon where we might want to um create uh discreet and distinct things uh in a near infinite world or we may want to place objects in a really large world right and so for example in minecraft you can run forever but every now and then there are periodic trees or periodic villages and how do we decide where to place those if we can't figure out where to place them all the time because the world is infinite right so we need to do all this kind of on the fly we might want to do particle effects we might have a million particles each one doing a random thing that can get really weird if we're doing it badly um there are a lot of ai algorithms nowadays that require algorithm uh randomness whether it's markov chains genetic algorithms uh monte carlo circle and and again going back to the minecraft example we might want to

have chunks that generate in random order right so if the player runs to the west he discovers a mountain great there's a mountain there he then only sees half of the mountain so only half of the mountain's been generated he then runs away from it goes south comes all the way back around and approaches the mountain from the other side the mountain better still be there and the west side better match for the east side we may want to trade seeds right i may want to tell my friend hey you should try this map try this seed from this word or this number it's a really cool map it's got a tower in the middle of the jungle something like that generation and noise can also be the ultimate form of network compression right if i have 22 gigs of data that i generated i can send it to you with an almost infinite to one compression if i just send you right so that's a huge advantage that's the same with disc compression right if i generate some mountain as long as the mountain's unchanged i don't need to save it on disk i can just throw it away and regenerate it on demand so it's the ultimate form of

compression as well all right so briefly i want to talk about what we actually want out of our number generators which ones should we actually use or not use we keep hearing different things a couple of limitations of random number generators i talk about noise functions as an alternative and entertain the possibility of can we make a random number generator that's based on noise or noise that's based on random number generators uh and then a couple of tidbits so that's where we're gonna go with this so first of all what do we wanna look for in a random number generator um what makes one good well i think academics would start answering well it depends on the period of the blah blah blah no no it really depends who's asking right if you're at the nsa you have very different needs for your random algorithms than if you're working on minecraft then if you're working at a casino game right so it really depends who's asking so what do i want in an rng as a game developer who's interested in

procedural content generation do i want fair statistical distribution right it's kind of it's random enough yes i very much want that and 99 fair and statistical is much better and more important than 95 percent fair it doesn't have to be absolutely perfect but we really start noticing the differences with fall off we want it to not repeat right for flipping heads tails tails heads heads heads heads heads heads heads heads heads we don't want that to happen except actually we do in the sense that it can and will happen and we so we want it to happen as much as it should right do we want some really long repeat period where if we run the random number generator it will only finish its cycle after the sun has long burned out and died that's really important right probably that doesn't matter so much as long as it can go you know billions or something really who cares at some point i'm going to make this point in a different way later however we probably

do want to make sure that it doesn't repeat too too quickly so as long as we can get millions billions out of the sequence we're probably in the ballpark of okay and most of the random number generators you'll deal with have a sequence length a period of in the billions so probably not a big deal we want to be able to seed it right we want to be able to say i'm going to give you the seed of 15 and then go go go generate a world and that's totally different than if i give it a 17 and i said generate the world so we want to be able to seed it i want to be able to use uh more than just a few seeds so maybe 32 bit that would give me 4 billion seeds that's plenty right there's a lot of random number generators that have pickiness about seeds like use any seed you want oh except don't use even numbers please use large primes and definitely don't use zero so i'd rather not have that if i can warm it avoid it some rngs have this sort of uh warm-up period where you get some lousy

values before you start getting really good values and actually some of the most well-known generators are some of the worst at this this is not something that i want because oftentimes i'm going to want to seed something and then generate five numbers and seed something else and generate 20. so it's those numbers at the beginning of the sequence that i want the most so i don't want this warm up statistically it is important for me that the bits are independent right if i look at if you give me 32 random bits then there should be a 50 chance that any one of them is on or off at any time and a 50 chance that any one of them agrees or disagrees at any time right there shouldn't be correlated with each other spatially and then um temporally meaning that the next result and the next result shouldn't have anything to do with the previous result at least not recognizably platform independence i definitely definitely definitely want this if i have an android client and an ios client and a mac and a pc client all connect to

something and they're trading seeds over the network that thing i generate from the seed you sent me better be the same as this thing you sent even though you have a totally different cpu than me right you might be on a 32-bit um arm or whatever and i might be on a 64-bit intel it could be quite different i would love to have order independence random access right where i could just sort of jump ahead in the sequence and jump behind i want to say give me the 75th random number in this sequence unfortunately that's something random number generators do not do very well we'll talk about that more and then of course i need this reproducibility this determinism right if i give you the seed 17 i better get the same results as the next time i give you the seed 17. and this is crucial to most of the purposes we're going to do with this how important is speed we may end up wanting to generate a lot of random numbers like a lot a lot a lot and we may want to do it in real time some of the most

interesting algorithms we can do require us to generate millions of random numbers so this does matter and we also may want to have thousands or tens of thousands of random number generators that we're going to instantiate that each one is feeding us different numbers so we may also care about the ability to whip up another generator and have it start cranking on numbers memory footprint how much memory does each rng have if i've got 10 000 of them am i going to care am i going to notice is that going to be megs and megs of memory or not can i run it in parallel right if i have multiple threads can they all be rolling random numbers at the same time um is this thread safe can i use one rng one generator that multiple threads are saying hey give me numbers give me numbers or does each thread have to create its own generator which is not the end of the world okay so which rngs are out there what can we use

i'm going to go really quickly through this but just a sense of what kinds of things there are so the simplest random number generators like these are literally boiled down to if you can see the code on the bottom here some internal state say some number and we multiply it by some weird number say a big prime and then that's our new state oh and then we return it to you and then the next time you call it we take that new state and we mudge it some more and then we return it to you so we kind of are constantly chewing and mangling our state and returning it this sucks because if i put in a seed of zero meaning i start the state off at zero then it will be zero times i don't care because zero is zero and then it will just be stuck at zero forever right in the numerical recipes they improve this and these are called mixed congruential generators where they just multiply by something and add a number great and supposedly this i thought was what rand was but

my results later in this tell me that it's doing something even more sinister okay so that's great why not just use rand it's been the standard forever everyone knows how to use it well probably you know that rand only gives you so many numbers right zero to thirty two thousand um okay well if i wanted a 32-bit ram i'll just mash three rands together right maybe bit shift so i could make something called triple rand right where i take these see if you can see my mouse cursor these 15 bits that it's giving me and actually the bottom two bits are a little bit statistically wonky no problem we'll just generate rand shift it over from some bits generate rand shift it over and then mash those together now we get 32 good bits of random unfortunately ran's not that fast when we start doing millions and millions of calls and of course it's not going to get any better if we call it three times just to try to get better results and rand does not do well at all

statistically in terms of how evenly distributed the random numbers are those triple rand can do fine also random maintains a global state so if i have 16 different threads i can say s rand to seed it to number 17 and then i call rand rand rand if some other thread is doing that as well it's fighting with me and it's disrupting my sequence right so it's absolutely the worst thing for me to have in terms of multi-threading and that's just the beginning of rand's problems so let's look at a couple of uh sort of quantitative grades of how well these things do and how fast they are so identity here is a random number generator where every time you say give me another number it says okay one two three four five that's all it is so obviously that doesn't do very well uh and i have these different tests and we could talk about them later if there's time but on average are the bits 50 percent on or off

on average are bits independent from each other is the next number more more likely to be higher that should be true 50 of the time when i look at each byte are the bytes distributed over the different possibilities nicely and then if i mod by all the different numbers from one to a million and do that a ton of times does it statistically mod you know spread nicely so if i do this rand mod 7 do i tend to get about even results across the seven buckets and you can see here uh these early and common random number generators most of them do not do well at all on these statistical tests this triple rand does much better thankfully if we look at the call time this is the top here you can see i can make quite a number of calls per millisecond but triple rand is down to 10 000 calls per millisecond which seems pretty fast unless again we're going to be doing millions of them

so not bad i would say uh you're fired for all of them except for this triple ran so far okay there's some other ones to consider i'm not gonna go in too much detail but uh if you have to leave in this talk right now i would say the one takeaway is at least use something like this xor shift one it's like rand that doesn't suck um and it's a simple algorithm where you just sort of um bit shift around and xor with yourself and you do that enough times surprisingly it has very good statistical results and there's various other variations of it now by now probably many of you are thinking well geez why don't you just get with the program we all know there's mere sand twister and that's the best thing right and it's in the simplest standard now let's take a look first of all it's not simple right if i call rand on the right it does a bunch of stuff and one of those things is every now and then it calls twist which is a bunch of stuff on the left with a for loop right branches this

doesn't smell that fast to me and sure enough it's not we'll go more into that in a second here's another one that's intel actually has some really cool random generates on generators on their website this is one i took from their website everyone can obviously understand this code right so you'll see what's going on there so let's look at how these do when i look at these different number random number generators you can see now everything triple random below is scoring pretty well mercen twister actually only scores a 98 there's another set of tests you can apply to these which i'll talk about at the end if there's time but these are more simple and direct to what i wanted so actually mercen twister was not the strongest these xor shifts were slightly better and if you look at the time to run them mercen twister's pretty fast but the xor shifts are better quality and they're faster all right that's interesting um there's

another thing that's interesting here to note is mercen twister notice it takes to seed it uh it's hundreds of times slower than any other thing it's so complicated to see the structure and it's also got a lot of memory okay all of these functions are based on the central idea of a recurrence relation function and that's basically just to say any rng just pick one it's basically amounts to this take your state do something funky to it and return that and then that's your state for next time and then you do something funky to that and so as long as you pick the right funky this thing will create a long chain of interesting things hopefully okay so lastly i'll just mention there's std random device it's a new thing i don't know if it was c plus plus 11 or something added this is something you should not use for your random number generation this is meant to be physically actually really random right

like i don't know if it's based on the temperature of the core or something like that i don't know how you do that on a computer but it's meant to be an actual random not a pseudo-random for games that's not really useful at all unless perhaps you want something super random-y just to kick off your random number generator okay so i want to talk about the limitations of these random number generators all of the ones we just discussed many of them have restrictions on the seeds like i said if you use a seed of an even number or seed them with zero half of them break right off the gate and a lot of them have even weirder rules like you should use a seed that's a prime or a seed that's a prime that's one less than a power of two or something like that that's no use for me if i want to have different planets with id numbers or npcs with id numbers and this npc is id number 12. please generate yourself based on that seed right well what if that c doesn't play well with

the random number generator am i just going to get a really lame npc or i'm going to get a lot of clones of the same npc there's a bigger complaint i have which is that when we say seeds in these random number generators um i i think it's kind of misleading they're not really giving us a whole new set of random numbers they're just jumping us into a different starting point in that same sequence right so if the sequence is a billion numbers long we might start halfway into it if we use one c we might start a third of the way into it if we use a different seed and this is why the mathematicians get us all excited about something like marissa and twister having a ridiculously long sequence a period before it repeats is because when you sort of jump into it you're not likely to sort of find familiar territory that you were in before hopefully but the seeds are not really a different set of random numbers they're just a different starting point i mentioned the slow warm up right meristem twister included

produces weak values before it starts getting statistically strong and that's fine if you're doing scientific programming you want to have 250 million uh random results and you want them to be statistically sound it's not fine if you want to just make an npc and you need six die rolls and they're all bad thread safety is important uh something like mercen twister and most of them uses an internal state so it's not thread safe every call to it modifies the random number generator however you can instantiate a different generator on each thread and then you can each thread can hammer on its own generator no problem however you can still have the case where this thread seeds with the number five this set thread seeds with the number seven and this thread is pulling numbers uh and this one faster than this other one and actually because we're still all pulling out of the same sequence and numbers we can kind of sort of sync up and so i can pass you or lap you or even come in sync

with you in the same part of the number sequence and of course rand we said do not use across threads because it has this global state order to dependency this is the my single biggest objection to these random number generators every call affects the next one so whatever you generate has to be generated in a strict order if i give you the seed 17 that's not enough you have to generate the same npcs tiles maps weapons loot drop whatever particles in exactly the same order that i did or else the sequence gets disrupted right so it's very sequential it's highly ordered this sucks when say we want to generate infinite number of things out of order so just to illustrate that point so let's say i have some world that's an infinite world right and i can go as far as i want and the world just keeps generating over and over and over and over well if i see that there's a island over

here let me get some island okay so i don't know if you can see in the distance there's an island that's kind of half generated and i'm going to back away from it and then i'm going to go around here and now i'd go exploring i'm going faster than the thing can catch up at the moment but if i then approach from the east instead of from the south i still have to come up with that same island that i would have before right so i can't roll a bunch of random numbers ahead of time and just figure out where all the islands are because there's an infinite number of them and i need to be able to encounter them in random order so we have poor random access how do you jump 100 numbers ahead in the sequence in any normal traditional random number generator you just have to roll 100 times right to skip ahead for some reason if you needed to do that you want to jump back three in the sequence sorry can't do it maybe if you knew oh i was generated from seed

2261 and i'm 1400 calls in you could reseed and then call 3 1397 right that's ridiculous so we have terrible random access we also have non-trivial instantiation like i said there's a lot of interesting algorithms that happen in procedural generation that require us to have thousands or tens of thousands or even hundreds of thousands of different random number generators instantiated so if we can't make them fast and if they're not small in memory that actually takes tons of tools away from us takes tons of algorithmic interesting procedural content options off the table and then there's the lack of temporal and spatial coherence and by that i just mean if you want to have a slope that's random heights and you're kind of smoothing it out between them you have to generate the numbers ahead of time and remember them in order to smooth between them right you can't go back and say wait wait what was the number before too late

so it means you have to end up writing all this extra code and storing all this extra data and if you're still really really jonesing on percent twister i'll just quote wikipedia places a load on memory caches somewhat slow fails tests not appropriate for monte carlo simulations outputs nearly the same sequence for many iterations all right so i'm not saying mercen twister is bad i'm saying when you talk to anyone on the street a game developer you ask them what do they know about random numbers they'll say oh rand is bad you should use mere satin twister that's the one thing they know and i'm saying that's not necessarily true it's heavy weight every rng you instantiate is 2k of memory which i still can't believe uh it's slow to instantiate i'm sure in part because of running mucking around and all that memory it has a lumpy cost amortization right we said uh we roll a random number random number random number and then every now and then it has to say hold on

a sec and then go spin up a whole another batch of numbers for us right so the times are even inconsistent it's got these cold starts where it gives us crappy numbers at first it's strictly sequential it's got sensitive seeds right don't put a zero in the seed don't put some other numbers in there even just seeds with a lot of zeros and the bits can confound it and it's super cash unfriendly when you're mucking around this 2k of memory and your cache lines are 64 bytes you're going to be not going to be cash hot even for something as simple as a random number generation call at least its quality is amazing right okay not so much so let's look at noise functions and compare them so a noise function uh what i mean by that is uh like an infinite table with a bunch of numbers in it right i put in the number seven and i get out the number point zero nine and then if i put in the number four i

get this if i put in a seven again i will again get point zero nine so it's just a lookup table effectively but since it's a function it's just math it's like an infinitely large table that takes zero bytes other than the code and basically these work uh all more or less like this when you put in a position the number seven it mangles the bits around mashes matches matches and returns something that's random but it was based on that seven it started with those bits so it's always going to give the same result so all these noise functions are basically the same in the sense that they take what you give them and they mash it up great it has zero state so we can instantiate millions of them no problem in fact we don't even have to instantiate them their functions right we just call them um there's no recurrence relation it's not taking a state and eating itself and and then that's the next state right there's no leftover or state which means it's totally thread safe

you can call it from a thousand threads all at once no one's bothered by it at all and now we have true random access right you want to jump forward no problem just ask what's at 107 in the table you want to jump back three just ask what's at slot four you can ask any slot anytime any order no problem lastly we can integrate true seeds into this where it's not just the same sequence and we're like kind of looking at a different part of the table each seed can give us a totally different set of an infinite near infinite set of numbers okay whoops so we can also do two-dimensional noise three-dimensional noise and the same idea is the same the basic idea is the same imagine again an infinite or near infinite table of x and y and i can plug in any x and y like 2 comma 0 and i'll get a 0.05 or i can plug in a 0 comma 2 and get a different number so i wanted a different number for every xy combination more or less and i always want the same

number for the same x y so again it's like an infinite two-dimensional table for no bytes unfortunately noses noise is only good for certain things right we don't use it for very much maybe if we had an rpg and we have different grass tiles we might have the position of the tile look up into noise to say oh i'm grass tile number three or i'm grass tile number two now that's nice if you've used purlin noise uh you'll know that a noise function is the basis of that so we have to have one for that um and that's usually all people use these things for we can do more so first of all like the grass example we can use noise to make things more organic right if you have 10 000 orcs if each orc uses noise based on his own unique id to determine is he a little bit more slouched are his forearms stretched is his skin a little bit redder are his teeth a little bit longer now you have an army of all orcs all different right

even if i have this say this grass here i love this picture from chris berkey um if i just apply some noise to it it looks organic right just mild moderate small variations that's totally predictable okay fortunately because we can skip ahead and behind and anywhere in the sequence this is super useful for generating world chunks planets villages npcs we can generate them in any order it doesn't matter whether the player in your rpg goes to this village first and talks to these people and then this other village second and we generate them on demand the result will be the same if he goes to the villages in the opposite order because each village is not generated from a sequence but from these uh noise functions so it also means that if we want to know where things are going to be no need to generate everything up front we can always generate the numbers on demand

and they're always going to be consistent right and because we can generate them in a new order that means in x order or in y order that's a really hard problem for rngs and there's no need to store massive amounts of data we can always just reproduce it in fact your computer just keeps getting faster and faster and faster and memory is not keeping up so in many cases it's faster to compute something than it is to even to look it up nowadays especially if the lookup tables are really big so don't be afraid of letting the cpu do a little work and it's also really useful for placing scattered objects within an infinite space and this is a very hard problem but it's one that you're going to encounter if you do a lot of procedural generation so let me give an example of that so um here is i don't know if you can see that a random function right i'm just showing a bunch of different random values and if you're familiar with purlin noise which we've done talks on in the past

parallel noise is like a fancier version of this which takes let me do it like that it takes a simple smoothed function that's based on it's going up slope or down slope based on some random noise and it layers noise upon noise upon noise and you get these really interesting sort of crunchy cool results okay so if we have this and this is an infinite landscape right this goes on forever um much like minecraft so now let's say i need to place things throughout the landscape like i need trees every so often i need villages every so often well one of the best ways you can do that is if you're using a noise function or especially a smooth noise function you can look for wherever there's a local maxima like a peak of a mountain can everyone see those blue stripes so if i zoom out a little bit you can see there's going to be mountains pretty

regularly here but as i increase the noisiness of the noise i'm going to get more peaks right now i have kind of a double peak at the top of that mountain and so i can easily say i want to have fewer trees i want to have more trees i want to have trees that are moderately spaced um and i can even say oh you're going along there are scarce scant trees in the plains but as you get into the foresty areas i'm going to slowly crease increase the tree density knob and we're just going to get more trees and this is infinite trees mathematically predestined from no matter which way you go we just know where they're going to be and we can ask any piece of the world where the trees where the villages so this local maxima trick is really nice again only really works with noise but you can still do it with um let me uh um even with flat noise right just like this we could still decide to say hey

there's a tree anywhere where the noise value of where some squares noise value is higher than all of the guys around it so this would be a tree and this could be a tree and this could be a tree and that algorithm again works even better if we've got smooth noise like purlin noise and we can just locate the local maxima right so all the mountain tops here i can highlight so i can make the noise as crunchy or as smooth as i like to get more dense force or less dense force and this just goes on forever right so i can use this local maxima with trick which is really nice and it works even better with smooth noise it's easy to adjust the density so you can say there's a lot of treasure chests spawning in this area and we have real seeds we're not just jumping to a different place in a sequence if i give you a seed 17 you have a totally different in infinite table of numbers you're pulling from

than my infinite number uh table of numbers i'm pulling from which totally eliminates that problem of i might catch up with you just through bad luck in the sequence okay so let's now try to relate rngs and noise and see how are they the same and how are they different okay so pretty much all rngs look like this top thing it's a thing that has state you say give me another number i'm calling that function rand and it mangles its internal state and returns that to you more or less this is what basically all of those random number generators do the noise function is almost the same but the difference is subtle there is no state there's no class there's no object right we just pass in a position and then we do that same funkiness but then we just return it right away that's really the only difference nothing mystical here right

so can we build random number generators if we do want numbers in sequence that are based on noise could we build a noise function sorry could we build a noise function out of random number generators that's what i'm asking first so this is kind of like pretending something that you're not to be something you're not so here is a random number generator and it does exactly what i said right it does funcifies its state and then returns the state to you i can make a noise function out of this it's a little ghetto but i can basically say okay hold on i'll construct a random number generator and i'll seed it with that position you gave me and then i'll return the first number in the sequence from that seed this totally works so using this you could use rand or mersan twister or xor shift to generate those minecraft worlds it's not fast right you're constructing these things all the time and if you don't want to construct it

you could make this be like a local static or something but now you've ruined it now there's state that's lingering and it's not a strict noise function so yes we can do that but it's not pretty and it's not fast right we have to pay for the construction the initialization the seeding as well as the rand itself of whatever rng we used and we said for something like mars and twister that's not fast at all okay can we go the other way around can we make uh rngs that are based on noise so again we're kind of present pretending to be something we're not let's see how it goes so this is now a thing it's a class an object it's an rng and this is going to be my special rng i made that's based on noise let's say that it has one piece of state which is the current position into the noise and we'll say that starts off at zero and then it has a function rand and what does rand do it just says

do something funky based on my position and then advance so basically this is just like you're looking at the table that infinite table from the noise and you just say give me another random number give me another random number give me another random number and i'm just surfing down the table no problem and actually that's pretty fast and tiny and it won't repeat right because it's not munging itself it can't get into some weird cycle where zero be gets zero or anything like that or even one we get seven begs two because one because seven begins two because it's based on this ever increasing position it's extremely unlikely to be cyclic since it's not based on this self-munging function right okay it's tiny it's fast how tiny how fast like it's not faster than an actual rng right well obviously that would depend on the noise function so let's go back to noise functions i want to give you a couple of

examples so if i have some noise function i'm going to say for this talk i'm going to frame them all like this you put in a position and you get out some mangled random bits like you looked it up in that in imaginary table so there's a lot of ways you can do this one way is to multiply by some big prime number y prime well if i multiply by 12 then i know that the result will be a multiple of 3 and 4 right if i multiply by 2 or any even number then i'm guaranteed to only get even numbers out so generally we want to only multiply by prime numbers we like big prime numbers because they're going to just mash all the bits there's going to be crazy carries everywhere it's going to massively overflow no problem we love that it's going to smell unrecognizable we could add something to it that changes it up a little bit it doesn't have as much effect as the big prime multiply we could square it right this helps make it whatever the

result is it's not likely to be linearly related to the input because it's squared we can as we saw with xor uh random member generators we could uh xor yourself with your own bits shifted over this is surprisingly effective for mangling things so whatever we do we're going to mangle mango mango mangle and then return some unrecognizable thing that's strictly based on what you put passed in right all right so you're like cool i love this i'm going to go i forgot what he said stack overflow give me a noise function this is what you get on stack overflow um only returns odd numbers yes good lib noise i go look up lib noise it's a nice really awesome sql source library what's their noise function it's the exact same function with a different shift and different constants when you think about it noise functions really are just kind of like a very

special hash function right so a hash function traditionally is i put a um a paragraph of text in or a bunch of file of a bunch of data and it chews on and choose on choosing it and comes up with a big mysterious number right this could be like a crc or something like that really if we want to just put in an int and get out a mashed up number we could just think of that as a hash in a sense all right there's a bunch of hash numbers we can look at uh when perlin ken perlin posted his perlin noise originally this is the hash function he recommended so there's a bunch of numbers that's the numbers zero to 255 scrambled twice and then he does a bunch of things where he looks up just to help you understand what's going on here this p is this table so it's a lookup in the table with an offset and a lookup in the table nested nested nested lookups right so if this table is 512 bytes right away we might be having a bunch of

l2 cache misses right something like that all right so let's look at how these do there's a identity we said is the most boring one of all and bernstein lib noise stack overflow purl and hash you can see they all got d's or f's pretty much i'm impressed that bernstein got lower than identity in terms of quality that's that's tough to beat purlin hash was the best out of these but you can see it's painfully slow by comparison to the other ones all right we can do better aha right we have some real hash functions why are we monkeying around with this home brew crap right let's use md5 let's use sha1 we just had the first real 128-bit collision of sha-1 i think like this week um that's what these look like right start instead of saying i have some big file for you to hash mr md5 you just say oh i got all i got for you is a little integer please hash that and then it

does its magic and these are complex algorithms right there i think sha at least came out of the nsa or something great see how they do so there's a ton of these guys and if you look at them if i look at the quality of them i've kind of mostly ish sorted them by quality so you can see there's a bunch of ones that suck especially the ones you'd get from libnoys or stack overflow and in the searches i've done there's some other ones uh md5 does great pretty good at least sha does pretty good crc does great and then this murmur thing does pretty great so there's some interesting ones when you look at md5 and sha1 which are the ones the hash functions i think of when i think of a proper hash function they're slow right not just like twice as slow they're 100 times as slow as some of the other hash functions and for something if i can already get a pretty darn good quality with something else why would i use that and the reason is that md5 and sha are like way over engineered for our simple

purposes right they're to be cryptographically sound across any body of data of any size we don't need that we just need putting it in get out something cool so don't use those it's way overkill unless you are actually hashing something for security so of course thinking that you know the world doesn't have enough hash functions i had to write my own because i'm masochist so i took my stab at this and tried a couple different things i finally came this is my third one and i'd use just a combination of these are prime numbers so multiplying bit shifting et cetera after i wrote that of course then as c plus 11 came out and they introduced std hash into the language that's a little simpler than this so maybe i should have used that let's see how those do okay so cpp hash at the bottom you can see actually does quite well and they're much faster they're three

times faster than any of these other good ones and then the one i wrote also does very well and is even faster than those so so far it's pretty good might great i'll use my own hash function but note to self if you don't want to do that or you don't want to download my stuff or trust my code or whatever you can probably trust the people who wrote std hash it's fast it's good if you want a good noise function i would say that's a really good go-to and out of all the ones that don't suck uh pretty much tied for fastest are mine and cpp hash so of the hash or noise functions that don't suck these are mostly tied for fastest and then again these massive heavy-duty industrial grade hash functions you really don't need and you don't need to be spending 200 times as long to get basically the same quality slightly better results i use mine

because i know what it does and i absolutely know for sure that on all the platforms it does the same thing now if i go and read the specs which i haven't bothered to do because i'm lazy on std hash maybe it's guaranteed that it will never change the algorithm i seriously doubt it maybe it's guaranteed that it works the same across all platforms no questions asked i seriously doubt it i know mine works that way so there is some merit to be able to control those things yourself okay so we said that we could have seeds in our noise functions right and we said not just are they seeds they're really really good seeds where one seed can give you a totally different table of numbers so really with a noise function the seed is quite simple instead of setting up some state of a random number generator we're just involving it in the mangling process and for me experimentation has shown again if i

insert the seed pretty early in the sequence so it gets plenty mangled but not as the first thing otherwise it just has the same effect as a position it ends up giving me very good results so that's what i use for all my stuff of course if we wanted to use std hash we could easily seed it as well the cool thing about hash is that it can hash anything and so you can just make a hasher that takes both the position and the seed and it will hash them together and this actually produces pretty good results too all right so we said we want 2d noise 3d noise right for perlin noise or anything else or for determining where those trees are on our landscape so assuming we have some 1d noise function that has a position and maybe an optional seed um how would we get a 2d position well there's a lot of different ways and we could write custom different ones that weave in the x and y

and z positions in different ways but one of the standard practices that again you would find on stack overflow or something is just to take the x-coordinate and add it to the y-coordinate that's been multiplied by some massive prime number and actually that turns out to be quite good it's almost impossible to have anything that's recognizable along x versus y so that really basically munches the x and y together into a single one-dimensional position which we then look up in the table by the table i mean the noise function same thing with 3d we could just munge the x and the y and the z using different prime numbers right and we want them to be orders of magnitude different so that they're not even coming close so that's just any small change in x or y or z will have a dramatic effect okay so can we build a random number generator out of a noise function hell yes we can and it's fast

tiny non-cyclic thread safe ish how tiny how fast depends on that noise function let me now build that rng out of cpp std hash and out of my own hash and let's see how they compare to the other random number generators like mercen twister you can see at the bottom here on the quality scale we've got 99s for a lot of these the cpp hash doesn't do quite as well when you ask for numbers in sequence which is what this is going to do so it's not quite as statistically good unfortunately but but it's still pretty good and if you look at the speeds up here so this column here is the speed of how many rands i can call per second again the one that i wrote is the fastest out of all these it's fast to seed it's fast to rand and obviously it's fast to get noise from because that's what it was built off of and again with mercen twister if i did that

trick where i seed to jump to a place and then say give me a value and then i seed to jump to a place and give me a value to give this random access that's pathologically slow right a thousand times slower okay so let's wrap this up some tidbits and takeaways noise is awesome that's my takeaway for you noise is awesome love it things that rng simply can't or can't do at least without bending over backwards to pretend it's noise which it isn't and it's bad at coincidentally noise happens to make better rngs than the rngs themselves and i'm not an academic researcher so but this blows my mind that this seems like such an obvious thing so i would love if there are researchers in the room to contact me afterwards and we can talk more about this if there's something i'm missing here that's obvious but i've generated tons and tons

and tons of stuff with this and it does great another takeaway just don't use rand i know it's convenient but um i mean for this demo here i was using glbegin right so who am i to say don't use something but um don't use it it's just bad it's lousy you can do so much better and faster and it would take you five minutes to set up a function that smells just like rand but outperforms it in every way honestly mercen twister for all it's cooked up to be isn't the silver bullet that i thought it was and uh i got excited about it and i'm not really anymore i'm not sure you really need it my advice in general is keep things small simple fast and flexible control them so you know exactly what they do noise for the win so um i will put some code if you're interested in any of this stuff uh by maybe the end of next week uh all of the slides from all the talks today will be on math4gameprogrammers.com

including this i'll just give you a quick look at this so here's the basic noise function and then i have a library of simple convenience functions like give me 2d noise 3d noise 40 noise give it to me as floats give it to me as floats from negative one to one whatever you want it i also have that little rng i built on top of it which can you can seed it you can change the seed you can fast forward or rewind it or you can just uh tell it give me a random float give me a random bite give me a random direction vector whatever role random chance there's a lot of little things like this you put them in your your math libraries they take nothing to write they take nothing to call and you're going to use them all the time real random chance just you pass in the probability of it returning true right useful how many times have you written where you roll a number and then you check the thing right why not just check something in the code reads more simply that is all i have thank you guys very much

i think we have time for just a couple questions if anyone has any uh if you do please come on up to this mike and please again don't forget to fill out your feedback forms we really appreciate it and be back in 20 minutes for mike acton to talk about the coding game challenge math yes hi i make a learning game so it's really important for me to know the um the problems that the k that the kids saw during their play experience and i have them set up so that they're deterministically random but i'm running into a problem where certain games the problems that the kids are doing affect outcomes of future problems and so i came to this talk kind of looking to see if noise could help me to be able to replay their whole levels without having to know exactly what they

did at a certain point yeah and this is your software that you you guys control yeah absolutely if you just effectively you just have each puzzle generate itself uh or each game completely independent of the others and so when if they're doing one game and it affects the other outcome of the other that means typically you have one random number generator and you're pulling numbers off of it and then you leave it alone and then you just continue pulling numbers off of it so at the very least without changing anything you could reseed the random number generator with a new puzzle and then the pass will have no effect but noise would also be a solution but in your case probably just seed more often is my my advice hey hi um i was wondering if i'm just missing something is there any reason not to just use the seed as another dimension in the function yeah that's a great question really [Music] for me i wanted the seed to have

so i'll say the short answer is no there's no reason not to the longer answer is i like to have the seed that gets mangled more deeply in the noise whereas for me i'm a little bit kind of lazily mashing the xyz together in kind of a simple way whereas i want the seed to be more deeply involved in the random number generation so the number the table feels drastically different as opposed to just kind of shifted i haven't done thorough testing with it but that was my intuition on it okay thanks yeah but i suspect you could do that just fine in fact i've used 2d purlin noise all the time where i'm striping across it and if i want a different set i just stripe across it differently and that works yeah hi uh i was wanting to ask you how do you select like good co-prime numbers for special hashing like 2d 3d etc because if they're too big then the overflow it starts

like getting influenced into the results so how do you select them and uh you are specifically talking about if i'm combining the x and the y how much should i multiply y by um because i had problems uh i had that in big numbers because they overflow and then it's like it starts creating a pattern as well well if if you're multiplying by primes the overflow actually just throws the extra bits off the end and actually most of the common random number generators as well rely on the fact that multiplying by primes with overflow stays random and stays interesting so as long as those are largest prime numbers my understanding is that it won't be a problem i think if there's if it's non-prime then you're making forcing it to be odd or even and if it's small then it could be recognizable so in fact if it doesn't overflow you should be suspicious that like you might be able to tell where it came from does that make sense okay yeah like

multiply with overflow is really hard to track i guess in hindsight okay yeah any other questions all right thank you guys and be back here in 20 minutes