Math for Game Programmers: Dark Secrets of the RNG
ฝัง
- เผยแพร่เมื่อ 12 ส.ค. 2024
- In this 2017 GDC talk, Dire Wolf Digital's Shay Pierce discusses techniques and considerations when using random generation in games.
Register for GDC: ubm.io/2yWXW38
Join the GDC mailing list: www.gdconf.com/subscribe
Follow GDC on Twitter: / official_gdc
GDC talks cover a range of developmental topics including game design, programming, audio, visual arts, business management, production, online games, and much more. We post a fresh GDC video every day. Subscribe to the channel to stay on top of regular updates, and check out GDC Vault for thousands of more in-depth talks from our archives.
Good talk that introduces some real problems. But it starts falling apart towards the end. He pretty much admits that he wasn't finished solving the problem he's talking about there.
Could kinda feel it too. Good breakdown on the mechanics of loot tables though
Definitely agreed.
Shay doesn't seem to have any issues with explaining the theory and maths behind the number generation, the problems that arise, or how to solve them, but it does feel like he did the whole ZombieUniverse example as a last-minute addition to the talk and didn't really have time to practice it. It would have been shorter without that but come across stronger.
no it's a good talk. He takes an experimenting attitude and it's clear there is no end to this matter.
Even though the solution is easy if you have an index chain. Sad.
I always make blood sacrifices to RNGesus to ensure the drops I want.
I chuckled at the 'updated' loot 2.0 from D3. We can easily find 200 legendaries and hour now.
if you use hash stuff anyway
have a global register for "unique" used seeds. any X that generates, will check if a X has already generated with that seed, if no, it registers itself and generates. if yes, it changes its seed (by incrementing? regenerating? requesting next random from parent?) and tries again
15:30 Mindblow!
I wonder if this would be a good situation to use a salt (such as used in cryptography) alongside the seed. Generate the salt as a concrete lookup table, and hand them out in order of generation. It would not solve "echoes" completely but it would reduce collisions while keeping it deterministic, without having to generate all the seeds initially.
Personally, I like to salt with world coordinates. No idea if this is a good practice or not, but it seems to give me decent results.
If you can make the occurrence rare enough having duplicated cities in a universe can be a 'unique feature' of that seed and be interesting in its own way.
Is not a bug, is a feature!
3:12. counting cards isn't cheating. When should taking the best strategy available to you given all the information you have be considered cheating? Casinos just call it cheating because it's one of the few games that they let you play where the player can actually do something that will tip the odds in their favour.
I agree that "cheating" is poor word choice. From a design perspective, though, you generally don't want to force people to feel like they *have* to count cards to play optimally, though -- so making it impossible is a good way to do that.
have the generator keep track of "combos" and make sure every generated set first checks against the database of already existing sets. yes, this means you have to decide on an upper limit to your range. IE, you have to limit the size of the intended array (100000 galaxies or something. pick a stopping point) AND it means the generator is going to get slower and slower as it builds up the database. But, you could, at the studio before release, build a program that will take a few months to basically sift through a million seed numbers and verify which ones have high diversity. Then the only thing you have to ship with the game is a list of all the "verified" seed numbers, and have the generators only pull from those seeds.
Amazing, thanks for this talk, this is a must for devs and gamers alike!
This may be obvious to someone more experienced with RNGs, but:
How about using an RNG with a seed that gets generated on game startup to create the seeds for all other RNGs? Sure, your seeds are going to repeat at some point, but they should repeat for RNGs of "arbitrary types" (in the example used in this talk, the repetition would "wander" over galaxies, planets and cities), so the repetition shouldn't really be noticable?
RNG's do have a seed, it's an offset in the hardware. Check out Cassino hacking and security.
Here's the relevant part of my StaticRandom class (c#)
using System.Security.Cryptography;
///
/// This serves as both a lock object and a random number generator whenever a new thread needs its own random class
///
///
/// RNGCryptoServiceProvider is slower than Random, but is more random. So this is used when coming up with a new random
/// class (because speed isn't as important for the one time call per thread)
///
private static RNGCryptoServiceProvider _globalRandom = new RNGCryptoServiceProvider();
private static ThreadLocal _localRandom = new ThreadLocal(() => new RandomWrapper());
public Random Random
{
get
{
_elapse--;
if (_elapse < 0)
{
// Create a unique seed (can't just instantiate Random without a seed, because if a bunch of threads are spun up quickly, and each requests
// its own class, they will all have the same seed - seed is based on tickcount, which is time dependent)
byte[] buffer = new byte[4];
_globalRandom.GetBytes(buffer);
_rand = new Random(BitConverter.ToInt32(buffer, 0));
// Figure out how long this should live
_elapse = _rand.Next(400, 1500);
}
return _rand;
}
}
I had the same thought. I also thought walking the full chain was kinda obvious. The two techniques are similar - you're seeding using the constantly changing adjacency context.
Oh nice, Dire Wolf Digital. I interviewed there last year. Fun times. They didn't go with the idea I pitched, but luckily I'm working on it in grad school as my thesis now. =)
Interesting talk. Thank you
I would love Monster Hunter 3 Ultimate’s charm rng system to be changed/updated to something more tolerable
The desire sensor is real.
Fantastic talk. Really pulling back the curtain. Great job, sir!
This is a high quality and informative talk, the MMO examples were quite illumnative, and I always felt like the Hearthstone RNG felt weighted, it always felt to favor the player (which isn't a negative) rather than be purely random. It would be really nice to get a link to squirrel's talk here though since Shay references it multiple times. edit: the link in question: www.gdcvault.com/play/1024365/Math-for-Game-Programmers-Noise
Thanks for finding the link!
The 15 minutes spent going into "Deep Echoes" could have been better spent... Why would you use 20 bits of randomness for your seeds? Just switch everything over to UUIDs and the problem is dealt with
Gamers are saying when will everything be 4K, and looking to the distant future of 8K.
But we're here wondering when we'll see 1080p GDC uploads.
Just as soon as the public decides that visual fidelity is what they need more of in their life when watching disheveled neckbeards talk about code.
@@warpzone8421 I'm pretty sure I've seen one or two GDC vids where someone decides to use an intricate chart or try to show 3 images on one slide, and you just can't make out a thing they're explaining at the youtube 720p bitrate.
good stuff, ty
Could you use Cantor's diagonal proof to guarantee a new seed number? Line them all up and check each digit, and if it's a match, increment by 1. That would guarantee that each and every seed will be unique.
linkmandrew this is an actually really interesting idea.
For the "broad echoes" problem, I feel like the main issue is having a single seed for everything... so I'm thinking of having a RNG system that takes multiple seeds and cycling between them each time it generates a number. Then simply give multiple independent seeds to every entity that needs generating. (I.e. a sloppy random number from the standard RNG, a hash of its unique address, and a random number from an array of unique numbers). Even if there is a collision in one of the seeds, it's very unlikely all three have a collision.
GameDevYal
Frankly I find the whole matter rather shallow and pedantic.
It depends what you want the seed for and how you are generating your world. If you are doing something like minecraft where sections of the map can be generated in different orders, you need a single seed that decides the whole world in any order it might be generated. So to extrapolate to minecraft from the talk, you could use the chunk coordinates instead of the index in the example so that each chunk will always generate the same no matter when the player generates it.
U know whats a problem?) "Very unlikely" means it WILL happen. Many times. In a row.
But thats the fun isnt it?
The problem of using multiple seeds is reproducibility.
in order to test and debug properly the PRNG (especially using players' data and feedback), using one seed is the best choice, since you can just force feed that seed into your system and you'll be able to reproduce perfectly the problem (it's a rather smart solution used by the devs of Slay the Spire, which shows, for every game run, the seed used).
Still no answer for the question I was looking for, why are some players so damn lucky with their rolls while others have to try tremendously more often to achieve the same result XD
Groove theory sounds like a feature, not a bug. Why patch that? add more weird rituals to affect RNG. Its basically a magic system. Exploits give fans something to gossip about.
talking about Loot in Diablo 3 .... which had absolutely terrible drops. So many epics/legendaries... just... they dont even feel legendary... they feel so common.
Thanks for the handy tips and insight, and well spoken. This makes me think if true rng is so hard then the real world might suffer from such echoes too, albeit in a broader scale. It makes a acase that life is more “programmed” than we think. Maybe there is another earth and us somewhere and other companion moments that are the same, just based on a a seed that generated repeated results somewhere else. The pseudo randomness of rng could kind of explain parallel world theories:) anyways loved it and will be trying some of these tips in my next game.
No. Very different processes
A real random thing don't exist even on real world, maybe only on quantic scale but nobody is sure if that is really random or anything else that we don't know yet...
@@SrIgort That's what i'm sayin :)
Does Diablo 2 have a pity timer? It sure doesn’t feel like it
dc universe. it's free!
Don't really get the code in 13:01 when is the weight setting getting called?
I presume it will be in the Pick method. The code is effectively describing the diagram in the next slide. The legendaryLookup, etc. will be the items in that category that could appear. So it will be something like picking a number from the seed, comparing it against the lookup item objects to determine which one to choose, then if that lookup item is chosed call the onpicked handler, otherwise call the onnotpicked handler.
Merkle Tree?
There're problems with that. Merkle Trees are binary trees. This would imply that each "Universe" could, at most, have a maximum of 2 galaxies, each galaxy a maximum of 2 solar systems, each system a max of 2 planets, etc. Their hashes are also meant to be used for cryptographic purposes, which makes them very slow for a game.
@@code-dredd Merkle trees are not limited to 2 child nodes; you can append any number of child hashes together to get the value for the parent.
@@edwardfanboy I suppose you could make it an N-ary tree, but if you're appending slow crypto hashes, perf may not be great (unless you change that too).
Space might also be an issue. If each hash is M = len(hash(node)), and N = number of nodes in tree, then space would be O(M•N), but if you _append_ parent hashes on each child, then you're also growing hash lengths for each tree level, i.e. tree level H will have H+1 hashes (H parents + 1 for the child's own).
Wouldn't that still be an issue?
I'm no merkle tree expert, so I could be missing things here.
@@code-dredd The CPU requirements would increase for some tasks, but the memory usage would actually decrease as more levels are added to the tree. If it was an N-way tree, and there were N data items, you would only need N+1 hashes, compared to 2N-1 hashes in a binary tree. But I don't think Merkle trees are that relevant for game design RNG anyway.
Interesting, but he literally killed every single joke.
How does one _"literally"_ kill a joke?
@@ChristianNelsonn Just like in the video.
Secret 1: It's not random.
Secret 2: We can use the fact that it's not random to make the game more fun.
Secret 3: We don't. Instead, we make the game deliberately un-fun to force you to pay an infinite amount of money on top of a $60 purchase to make the pain stop.
www.lostgarden.com/2014/12/loot-drop-tables.html
blogs.unity3d.com/2015/01/07/a-primer-on-repeatable-random-numbers/
10:10 interesting but I don't completely agree.
You first create a deck of all the common and uncommon and legendary ids (flyweight). Then draw randomly. Don't roll for commonness, because the design is not prepared for adding new legendary items or new types (say uniques or sets) without touching the code.
Any card drawn is moved to an array containing the drawn ids. So you will never have nothing to draw from.
Use any idle time to keep generating new items. If you hit memory limitations, simply remove older and already used items. So the focus is on making items with good randomized stats from ranges. Which brings us to RNG:
Your RNG should be based on something that is guaranteed not to repeat for a long long time. the decimals of pi for example. You can download the first 10 billion decimals online anywhere, and use time() to find the start point, then simply walk that path. This enables you to simulate AND be sure to have unpredictable results (perceived as random).
Your pity timer can simply be count whatever was thrown to the player whenever it was not legendary type, say, and if it is legendary reset the counter, and it it reaches 100 or whatever, draw again from the item deck, and throw that at the player. After 100 the player can keep being unlucky, but since the deck to draw from will have less and less non-legendary items left, eventually he will get one. This also keeps your pity timer code clean and simple.
I'm baffled that programmers don't get this.
18:52 having deep echoes is a clear sign your approach is wrong.
Using pi your your random numbers is a terrible plan. There are plenty of good (P)RNGs out there; you just need to use them.
For gameplay-impacting randomness (rather than just like effects randomness, which just needs to be fast not good), you can use something like SHAKE-256 as a CSPRNG that can be seeded from something arbitrarily complicated and will give something like 2⁵¹² bits without repeating.
@@pfeilspitze Care to explain why pi is a terrible plan? Because I don't see at all how that could be.
I don't really need fast but if I need more than 100 million digits, which pi has in a table, O(1), I can consider your shake thing. 2^512 = 1.3407807929943E+154
(roughly the known universe + dark matter + dark energy)
The pity timer is actually similar to what RNG system Warcraft 3 had, it's called Pseudo RNG. Basically any chance starts off low, and increases to twofold, then threefold, etc. every time it doesn't trigger, so it will eventually reach 100%. Dota 2 inherited this system and this allowed the game to be more RNG based without feeling unfair. But because Blizzard people did sloppy math, it starts to lose accuracy after 25% (a 25% Pseudo RNG chance listed is actually mathematically 24.9%, and a 60% PRNG chance equates to about 53%).
and now show this to gamblers so they can finaly understand they can never win its programmed to not allow you to ever win
Eternal is a dope game.
The dark secret is RNGesus is really, and we made him.
One of the things I've heard about RNG is, that the further the player is in the game, the less RNG should be used.
Why do they upload conferences from years ago, years late?
Better late than never
@@kattenelvis1778 Better soon than late
GDC is a huge business: it costs thousands of dollars to get in to the various conferences (many tiers of pricing) and hundreds of dollars to get access to all their videos online. I assume they don't want to upload too much recent or cutting edge talks because they want you to pay for the GDC Vault subscription. Too bad because the talks themselves are gems and it disproportionately hurts indies and people who aren't saturated with cash.
$$$
@@blackdragoncool I see. That's messed up.
Tool what tools you guys cant even set to even/fair numbers
Maths*
Humans can't handle real RNG. Spearman beats tank WTF game broken!
'pity-timer' is a cute name for gambling-fraud.
What are you talking about? A pity timer guarantees a beneficial result eventually instead of possibly never. I doubt EA games have a pity timer.
@@aaefvacce You can use a pity-timer until the first few times the user gets a top tier reward and then gradually remove it as they develop a spending habit. That's also gambling fraud.
@@dirkmaes3786 Perhaps, but then you're slipping into the same issue as loot boxes.... is it still "gambling" when you earn the loot-boxes via gameplay rather than purchase?
Also nobody is suggesting you *remove* the timer. Its added to "improve the player's luck" so they don't complain about a 1/50 thing not happening after 50 attempts and, as Shay said, actually occurs naturally in a deck of cards even if you do shuffle in more decks (its less prominent but mathematically still there).
There are other GDC talks and Game Developer Toolkit videos on this matter as well. Its generally accepted in design that a player shouldn't be PUNISHED for being SUCCESSFUL. It makes the game less fun, giving the game and developer a bad rep, something that I find most developers generally don't want. Only the scummiest of people are going to see this numb-fudging and think "I can scam people with this" rather than "I can help players who are struggling!".
@@cyqry I can't speak for the legal definition because they're different for every country, but as a game-mechanic it is gambling 100%.
It doesn't matter how many layers of abstraction you put between purchase and consumption of the bet.
Why use rng ? Just manually program every possible case
Some things are to big to do by hand :)
lulz
@@SvenWM whoosh
@@SvenWM Ever heard of Daggerfall? I would not want to be the poor sod who has to design a map the size of the UK by hand.