Math for Game Programmers: Dark Secrets of the RNG

[Music] this is the sessions dark secrets of the RNG as you can see on the screen squirrel introduce you to some concepts with random number generation earlier I'm going to expand on some of those his was more theoretical and mine is going to be the more based on application and focused not just on some of the non-obvious problems you'll run across with random number generation and game development but with some of the non-obvious tools you have to solve those problems when you come across them the the title dark secrets may be a bit of a misnomer I feel like squirrel got into the the dark complex math of a quite low level but we're going to focus on how you use that math so Who am I and why should you listen to me here's some games I worked on there's a lot of them at big studios yeah I worked on hearthstone on the prototype that would say that was the

best known game I've worked on I was only there for a year but of course on digital CCGs quite a bit of random number generation I've worked on a variety of games to my career I've done some indie stuff over land in the bottom right there I'm not working on but was a roguelike that definitely you know randomly generated levels is a consideration there and yeah still working on digital CCGs at direwolf digital in Denver Colorado these days maybe you've heard of them maybe not but let's get into using RNG and let's start with something pretty basic about the types of problems and decisions you'll be you know you typically have to solve as a gameplay programmer in this area so I made this game connect row to puzzle game my wife was a big fan of it and playing the prototype of it back in 2011 when I was working on it and she came to me with a big complaint that she had it's kind of a Tetris style game it spawns a random

piece each turn you have to place it on the board and I heard only one night she got in the same piece 9 times in a row and I realized I needed to fix that bug which I did the same way the tetris fix which is to use what's sometimes called bagging so this is a pretty basic approach or consideration of randomness in your game if you're doing a simple dice roll every turn like I was to decide which of the six random pieces to spawn every turn you're gonna get streaks you're going to get a very random distribution and sometimes you don't want your randomness to be that random so a simple thing it's kind of a design decision really in a way our decision a board game designer would make is to say well that shouldn't be a die roll that should be a deck of cards or in math the distinction would be to roll a die is to sample from a random set with with replacement it doesn't change this set too you know sample one from it whereas the deck of

cards you take one out of it doesn't go back and you're then guaranteeing in your distribution that that won't show up again as a repeat immediately has a streak or or for a while most games that use bagging would say have a bag a bag of your random set think of it as a deck of cards shuffle it you could take three decks of cards actually Vegas does this these days to break up people trying to cheat at blackjack and such is to take three decks of cards or more and shuffle them together and you can no longer it changes the distribution of the randomness right specifically so yeah it you will see if your speed streaks have the same thing showing up over and over if that's important consideration as it was in that case for me and you will even out the distribution but of course there's an edge case so how so if you shuffle three decks of cards together and reshuffle it when empty off the top

of your head you might think that that means the maximum streak of the same thing you could ever get is three people three aces of spades out of a deck of cards like that in a row but actually given that you then reshuffle a new deck and put it in there the truth is there's an edge case literal edge case at the edge of or the end of one bag you could get three aces of spades and then at the start of the next bag you have three more so that edge case is worth considering especially in the case of randomness because I was my first dark secret of RNG yeah every random edge case that can happen eventually will happen and to a live player in a ship game potentially if you haven't planned for it and made it impossible and yeah you as the gameplay programmer are the last line of defense for for that you have to sometimes think like the designer and think about these considerations that would normally I'm currently working

with these CCG designers at direwolf and they're extremely mathy but i've also worked with designers who aren't terribly aware of the mathematical implications of this kind of thing especially and so sometimes this program it's your job to step up and say have you considered this and this even though it might normally fall to a design so yeah that leads us to the yeah I'm referencing here at the top there's a play called Rosencrantz and Guildenstern are dead where the character flips the coin over and over and over and throughout the play it always comes up heads I believe and that's extremely unlikely but again it will happen in a live game that you get like a hundred bad rolls in a row for some player if it is mathematically possible it'll happen eventually and oops you have to consider it and that the solution of that this is a blue post from a blizzard developer not one I know or anything but this is

how they solved it on Diablo 3 a very loot driven game and a game like that this kind of consideration is a big deal so they added what I call a pity timer that they're describing here basically if there's a low chance of rolling random loot at every chance you have to get loot and for some players that just never rolls that way for them for hours at a time right so they put in a fallback essentially to say you know make sure that that does eventually drop for the play or make it work the way you would expect it to work that the player will eventually get the Darry drop no matter how bad their look is I want to go over yeah I had the biggest dark secretive RNG that you'll kind of keep running into I was gonna expend more on this but kind of scaled back this part of the talk is just human brains aren't great at dealing with probability in general in many cases

they misunderstand it easily and some of our things like the pity timer are there to make a player might know oh there's a 1% chance for this random thing to drop and still go out and kill it 200 times and logically they could tell you they know it's possible for it to not drop in all those times but they'll still complain very loudly about it they don't expect that way usually unless they sit down and think through the math and a lot of our tricks of RNG are there to emulate what SPECT and make randomness work in the way that yeah we expect they expect it to work even though it's not mathematically true so the pity timers definitely examine an example of that of course players will still always complain that the RNG is unfair and hates them and that they're cursed in some way or something actually I have an interesting story here that I ran across which was a game called urban dead which

I used to play a lot it was a web-based MMO and it had random roles when you hit the attack button it rolled rolls the dice and decides if you land the head and a player post a player positive this theory that he could get into a groove if he hit the attack button and hit that if he waited 8 seconds and hit again at that time that groove stayed in that groove of hitting at every eight seconds that he would always hit it would always come up in his favor and this is from the talk page then on the wiki of the developers saying that's not possible I'm using a random number generator if you're in squirrels talk earlier maybe this isn't such a surprise but turned out the player was right that every eight seconds he was simply taking the current time in seconds and putting that into R and I think in PHP but that pie holes that probably calls C++ Rand function and I actually scroll the you had a note that liked the lowest two bits of that were unreliable so every eight seconds

maybe something odd was going on and coming up I thought that was pretty hilarious especially that the developer ended up catching it after first denying it but yeah you can't seed trivially and there's and there are cases where we get it wrong so it's worth thinking through thoroughly so you don't have a bug like this in your live game and players were superstitious enough basically without bugs like this leaf sneaking in and the RNG actually being broken but they'll always be convinced it is whether or not it is alright here's a dark secret of gameplay programming I'm about to tie all these concepts together the designer will always change their minds about everything possible this yeah is relevant because specifically to loot loot drops so my point here is that if you're designing a game where loot friends where loot for instance is a

major consideration designers are going to want to tweak that because that is a big difference on the player experience and on some other things that you may not may not expect that I'm about to get into yeah the player experience of Legendary's is obviously a big deal they want to be sure that pity timer is there and that they will eventually get their legendary after they kill the boss enough times but so a tool I think I put this not in the order I expect it but the tool I'm trying to relight here is a tool that will let you control a loot drop I'm specifically a lookup table so yes a lookup table it can describe a die roll it can describe a deck of cards or anything else a weighted lookup table could be created with a weight say 52 elements each or a

card and each card starts with a weight of 1 if the weights can be modified turns out to be a powerful tool you can reduce the weight to zero once the card is drawn and then reset them later but you could represent a lot of other things too of course here I'm representing dropping a loot drop for a boss common loot has a weight of one uncommon loot has a weight of 0.5 so half is likely to drop and then here what I'm trying to do is implement a pity timer the legendary lookup is its own so first of all this is nesting look-up tables in lookup tables which is very useful and gives you to the point of being able to respond to the design asks gives you a lot of flexibility to refactor or wework one element of the loot drop and add detail to it as we've done with the the Pitti timer here for the legendary case and I'll get into an even more complex case on the next slide

but yes the dynamic weighting is the other powerful tool of a weighted lookup table because in this case I'm changing the weight in order to implement the Pitti timer and make it so that eventually the legendary will drop here I'm passing in you can see my cursor right I'm passing in basically callback functions and this second one is saying each time the legendary is not picked it's weight actually increases this by the way still kind of violates my rule that you should always check out for every edge case like mathematically you couldn't be 100% sure that the legendary would eventually drop unless you're also decreasing the weights for the other elements which would be another way to implement this but in this case I'm just increasing the weight for the legendary each time it is missed and then when it is finally hit I reset the weight to the beginning it's a simple but nice way elegant way and kind

of maintainable which is always a consideration with code to implement something like this so to continue tying this all together one of the games I showed back there was excuse me an indie game I developed angry Henry and the escape from the helicopter Lords part 17 the rewrite is the full title which I'll try not to say again I don't think we have time to say it too often so in this example I'm imagining that walrus copier the boss from that game is that let's I'm making an angry Henry and the helicopter Lords in ammo in this example walrus copter is my boss he drops sorry he drops loot either common uncommon or legendary so this is the naive initial implementation and now I've added you saw the previous example of adding the idea of pity timer to the legendary case and making it dynamic here I'm also adding another consideration that I've heard of real

mmo's running into with loot drops which is hey that loot drop is an important input to the economy of a game if the distribution so in this example the first naive approach we basically run this for a while on our MMO and then design comes to us with a problem and says we have a problem because the the loot legendary loot for the night class is worth a lot more on the auction house than the legendary loot for the ninja class and we need to change that so suddenly how do you respond to that ask I would suggest you use the weighted lookup table and make a new sari the nested nature of look-up tables and make a new sub lookup table for the legendary case that also says not only do we have this pity timer element but we have a way to wait the loot for the different classes based on the player distribution the popularity of those classes because

of course supply and demand you're controlling the supply of loot to an economy and the demand goes up that's a real case I've run into and there can be you can respond to unexpected cases with cleanly and elegantly and with maintainable code by using something like a way to the lookup table so I recommend them as a tool and here I kind of run through an example of ok we're hitting we're hitting and you're seeing the weight go up on the legendary case until eventually it finally hits the legendary case who knows how long it would take but the chances get higher and higher the longer they keep missing it and then it would step through to the next level of look up and say roll another random number each of these diamonds basically represents a random number roll so finally it resolves and once it does the weighted sorry the weight of the legendary lookup presents so weighted lookup tables gonna be a

really powerful tool they can really represent any other type of randomness you'd want to do including the simpler cases so they can be fit into this nested tree like structure very cleanly and again in a maintainable way alright so I wanted to expand on something that squirrel touched on which is he was giving some examples of using his squirrel squirrel noise library to do different random hashing and sand specifically had some impressive examples of randomly generating a world yeah and I wanted to we decided that I could get into how hashing could be a solution to solve a specific problem in RNG or an orangy related problem which is the possibility of having deep echoes in that kind of world and I should I'll explain what that means so here's

another live case of something strange in a live game some players commenting on the fact that they're wandering through the different random worlds and they came across a city that looked familiar that they had come across in some other random world this is possible because usually in these games you roll a seed and give that to the city and the city generates its content from its random seed puts that into a random number generator and generates all of its content in this case we have a universe so I have an example I called it a zombie universe where I said at the top level will have a seed on the universe of course such as 42 as a nerdy reference it uses that to generate a series of children the next layer down which are galaxies which then generate solar systems which each generate

planets within the solar system and then cities and there's another layer not shown here in my example of villagers so what I'm highlighting a red here is the odd case you could run across if you're doing this first of all to make it clear the seed on the top level on each level is used in the generation of the seeds for the members of the next level the random galaxies each each random galaxy has a seed and that comes out of the RNG of the level above it so the problem that happens there is that eventually there's a chance of the random seed being used twice in two different cases and if everything beneath it is also generated as a product of that seed you're going to start to see that everything is the same so in this case everything in these two different solar systems is identical on all the planets in that solar system all the cities and them all the cities have the villagers with the same name and occupation

however we would be randomly whatever we would be randomly generating we now have an echo in a game it's supposed to be noisy and random and unpredictable suddenly we have the exact opposite so we spent I was working on this even last night that we finally got to what I consider a to a solution a resolution there are still some caveats with it but I want to share some of what we discovered trying to dig in and solve that problem specifically using random hashing as a tool which did end up being the best solution for our purposes so essentially let me show you real fast I have step out into unity and I have an example of project running with this problem hope everyone can see this okay takes a second to generate most of that time is going to the checks I'm doing for random echoes so yeah nested structure solar systems

contain planets planets contain cities cities contain villagers it's zombie universe so they're all named Rob ah ah gah ergo I can just keep reading these if it makes you laugh that much BRR that must be a cold must be on the North Pole so yes I we spent a lot of time trying to get around this problem and you'll see that there are still cases of cities that have the same seed well I think cities that have the same name or seed in this case here's a check I was doing that they might have the same seed and I won't try to get it working again right now the point was that we ended up following a different algorithm to generate the layer below it which is not based solely on the seed or any other

data given to it by the layer above which presents prevents the echo from carrying down so we go ahead and use say I'm generating a planet I go ahead and generate the content that planet in this example that's just the name based on the seed to generate the child elements I want to use some other seed that it are some a seed that is a product of something actually unique to that planet or other element so in this example you can also see there's these seed values but there's also an index value very simple I have three children they have indexes of zero one and two but then I can use that to uniquely identify say this planet in fact yeah here's two planets that came out with the same name oh but not the same

seed okay I won't worry about looking for one but the point is that you can use the index of your layer recursively up the chain up to the top layer to say well this uniquely identifies me now at first my solution to this that I had 24 hours ago but that we weren't quite happy with was to say let's pre generate all the seeds everywhere upfront and guarantee uniqueness with a brute-force approach that wasn't something I wanted to resort to for one thing we also put a restriction on how many children each layer could have a max index and then we could unique as long as we didn't achieve an overflow we could take the unique indices and essentially add them together multiplying basically treat it as a base instead of a base to number our base ten number a base masses max index number and build a unique integer

that represented the unique address the index the recursive index of that element and then once we had that we could look up use that as a lookup to a bunch of again unique random numbers that was clumsy because it put some restrictions in place what we found was better was to take a random hash and to go ahead and take this n dimensional address as you call it based on the things index and go ahead and put that into a hash function one specifically one of the ones that scroll showed you earlier the yeah here I yeah this code may not be obvious or self explanatory if you don't know like link in c-sharp but this is too taking all the layers put them together into an array and passing that into a hash function that can take an arbitrary number of intz and a seed and give you an output that is

similar to a big random lookup of unique numbers a big unique yeah a big lookup of unique random numbers but uniqueness is not guaranteed in this case so there is still a possibility of collision but by making it so that I as a planet generate my content but based on the seat I was given by my parent but when I generate the next layer down I'm not using something that came down the chain I'm using something unique to me when I generate the next layer that breaks the deep echoes from propagating down the hierarchy and here's the initialize children method that actually goes and gets that seed actually here I'm using the seed from the top level of the universe whenever I generate the seed for a particular thing say a planet this type could be planet or villager or whatever but villager wouldn't call this function

because it doesn't have any children but in actuality when I was using it I found well my yeah I needed to change these seeds per have a unique seed per layer that I did pre generate for each type of thing so basically my planets would end up with the same name if they had the same if they were the very first planet or had the zero index okay so here's an example of yeah of what you get now which is hey there can be two solar systems that have the same random seed on them but they don't have the same content under them the echo does not persist and I should explain why that's significant because now of course you don't want the same thing appearing in

different parts of your universe now you can have the same thing collisions are going to occur unless you have a perfect hashing function which doesn't really exist you're going to end up with the same seed existing on the same object somewhere in the world what you want is for it to not persist and especially it's all about player perception in the end right if they don't perceive it as random or say me then it's not specifically so I could generate a city maybe it has the same layout of roads but if it its contents are completely different the player might not even notice that this one superficial thing that makes the city unique is the same as this other city because everything outside of it is different on a higher level and everything inside of it is different because we've now broken up to deep echo so that's important and it is a problem I don't think there's a so I forgot to explain an important part of this example I'm showing you you may have notice all the seeds are very low and of course trying to force this problem to happen by limiting all the seeds to be between 0 and 64 or 0 and 63

I should say so that exacerbates the problem and really makes it clear that essentially well first of all I should let you know the caveat of this solution of using random hashes once we moved away from a true unique lookup table we had a new problem which is that essentially when I generate that lower layer yes I'm generating a seed from and I'm getting it as a hash or I'm getting it from a hash function but again there can be collisions in that hash function so we now do have a possibility that two solar systems can contain a set of planets that are basically the same they have the same name in my example they would have the same position in some other example again hopefully yeah this seems pretty bad like for a planet to have the same set of cities with the same names is pretty obviously say meat

to me so it seems like yeah for the broad echoes problem as I call this I'm leaving the solution as an exercise for the viewer which means we ran out of time I literally got to this point last night and digging through the problem I don't think that there is not a perfect solution for the problem because of essentially the mathematical nature of if you have a function with a larger number of potential inputs than the potential outputs you're always going to have the pigeonholing problem if you have more pigeons than you have holes eventually two pigeons are going to go in the same hole so one way or another you're going to deal run into this pre generating either at startup or at compile-time a list of a bunch of seeds that you can be certain our unique works although again if you have a need for more output numbers given the limits of like a 32-bit end if that's beyond your limitations you're still going to run into collisions but I think we've shown here how you can keep

a technique for using the uniqueness of the thing itself to keep the hierarchy from persisting down it looks like I'm about out of time but I do want to recommend to other articles I run across that we're very useful and pointing out these tools and recommend they recommend some other ways to use these dan Cooke of his lost garden blog had a really good post about loot drop tables and how they could be nested and he did them more justice than I go there for more details on that technique there was also a great blog on a on unities blog about using repeatable random numbers and noise and hashing which it really opened my eyes to how powerful that tool was and you can go there to find out more about those yeah and I will put I'll go ahead and share this example on what's the name of the website math for game programmers comm

yeah thanks a lot you