Deterministic RNG

[LegNeato]

RENDERED

Feedback is welcome from users at all levels! Do you think this design easy-to-understand, useful and correct? How could the proposed API be improved?

TL; DR

• A new default plugin, bevy_entropy.
• The plugin adds a new Entropy resource to the world.
• The plugin can be completely disabled if no source of entropy is required, the default entropy from the OS can be used if randomness is needed but deterministic execution is not, or a world seed can be specified for deterministic random number generation.
• ~~Currently uses rand in implementation but not in public API.~~
• Currently uses rand_core and rand_chacha in implementation but not in public API.

Prototype

• The PR is ready to be tested: https://github.com/bevyengine/bevy/pull/2504.
• The examples are updated in the PR if you want to see how this changes existing code, for instance https://github.com/bevyengine/bevy/pull/2504/files#diff-c76005a618f4ae31713a70cd68f5715ef672e582b5e940a20b2cfe94432404b0.

[alice-i-cecile]

Awesome, I'm looking forward to naming this. A couple of organizational things to make things easier for reviewers:

1. Could your rename this PR to Deterministic RNG?
2. Could you add a PR description following the example set in e.g. https://github.com/bevyengine/rfcs/pull/45?

[LegNeato]

Sure, I thought we wanted to use the RFC doc as the source of truth but I can pull some stuff up here! Thanks for the quick response 🚀

[alice-i-cecile]

Yep, the doc should be the source of truth, but the PR description makes it more reviewer friendly :) The real solution would be to have a dedicated interface for this, but eh, Github is very convenient.

[alice-i-cecile]

First pass. Substantive thoughts:

1. I really like the initial implementation model of "just provide a source of entropy". I think this is an important and relatively uncontroversial first step.
2. Bevy definitely needs a first-class solution for RNG ala rand in the long-term: it will be immediately useful in examples, will likely be eventually useful internally, and like you said, it's very helpful to avoid an explosion of RNG dependencies in real projects.
3. rand is too heavy, in terms of compile times / memory. If we include it, many users will simply disable bevy_entropy. If we can strip down to getrandom instead I'd be very happy with this proposal.
4. I want to see some an example of a game that uses entropy across systems, with each one acquiring a ResMut<Entropy> in turn to ensure deterministic evaluation.
5. I want to see an example demonstrating how you can use the seed with several different RNG crates.
6. Per-system entropy is trivial and can be quickly addressed in this RFC: just store Local<Entropy>. This should be explicitly discouraged in ecosystem plugins that have gameplay effects though due to the downstream effects on determinism. Seems great for particle effects though!

Stylistic comments:

1. Ooh, those footnotes and text-hiding sections are cool! Nice work.
2. Try to split your lines in markdown at the sentence boundaries; it really does make the commits easier to read.

[Vrixyz]

Per-system entropy is trivial and can be quickly addressed in this RFC: just store Local<Entropy>.

Can we consider using a Component for Entropy rather than a Resource ?

I've seen several kinds of entropy mentioned within the RFC, but I want to point out several kinds of "entropy"/randomness seed can exist in a same application:

• non-deterministic seed for playing animations for player inputs
• deterministic seed from user input to load a game map
• security protocols for networking might also want their own Entropy system

Using Local<Entropy> sounds like a rather impractical way to circumvent that use case ?

Or maybe consider the same approach as Timer to be able to embed it in another Resource or a Component depending on user needs ?

[LegNeato]

The thinking here is other entropy pools would be seeded from this main pool, giving a single place to control all downstream (and plugins, I guess that is upstream?) determinism.

I'm not opposed to different entropy pools being built in for specific purposes, but I'm not sure of the benefit of having X top-level nodes/pools vs 1 pool that has X subpools created from it. I'm also not an experienced game developer though--I'm coming at this from the simulation side.

[LegNeato]

I got busy, hope to address feedback later this week.

[infmagic2047]

I think eventually we want to be able to seed from arbitrary-length &[u8], which is useful in games that use a user-provided string as the seed (very common among games with seeded world generation). This can be pretty complex, so probably not in the initial version though.

[infmagic2047]

3. rand is too heavy, in terms of compile times / memory. If we include it, many users will simply disable bevy_entropy. If we can strip down to getrandom instead I'd be very happy with this proposal.

Going getrandom only would be difficult. Here we have the problem of producing an arbitrary-length random value (to seed the downstream RNGs) from a user-provided seed, which needs some form of RNG or hashing I think, and is not something we should implement from stratch.

A bad seed for the downstream RNG can have real consequences: some RNGs have bad behavior when using non-random seeds. We should try to protect users against these problems.

IMO the best choice here is to find a small crate to get the work done.

[bjorn3]

What about only using those rand subcrates we need? Rand consists of rand_core which defines some traits and error types, rand_chacha and rand_pcg which contain PRNG's, rand_dist for generating non-uniform distributions and then the rand crate for glueing everything together and defining a couple more things. I expect rand_core + rand_pcg or rand_chacha to be much lighter than the whole combination. I don't think we need the rest anyway.

[LegNeato]

That makes sense to me.

[ValorZard]

I generally like this, but I find the name “entropy” for this crate to be kinda confusing. I think just calling it bevy random would be better

[james7132]

I'm generally behind the goals here, but this only covers how we're going to seed new PRNGs, not how said PRNGs are stored, managed, and advanced. Things like query iteration order, thread assignment for systems, multithreaded access, command execution order, platform-specific ordering for types like HashMap, etc. all affect the way game simulation drives the advancement of these PRNGs. Even if we have a deterministic source, a strategy for making the use of those PRNGs is ultimately going to make or break determinism. Particularly if the PRNG or it's results are coming from a first party official crate.

[superdump]

I'm generally behind the goals here, but this only covers how we're going to seed new PRNGs, not how said PRNGs are stored, managed, and advanced. Things like query iteration order, thread assignment for systems, multithreaded access, command execution order, platform-specific ordering for types like HashMap, etc. all affect the way game simulation drives the advancement of these PRNGs. Even if we have a deterministic source, a strategy for making the use of those PRNGs is ultimately going to make or break determinism. Particularly if the PRNG or it's results are coming from a first party official crate.

^ this! You need to have deterministic order of requests for random numbers from the seeded random number generator. The random bits from the generator would be in the same order, but if you request generation of random scale factor and a random index, versus a random index then a random scale factor then the bits are being used for different purposes in a different order and your determinism of the random values just broke.

I'm not initially sure it makes sense to try to build determinism into the engine itself, if it is even possible. It seems more like something one has to consider in the design of one's application.

From hacking on some procedural generation stuff, I would also say that rand will likely not be fast enough for some purposes where a large number of random values are needed. Then other crates will be needed. I suppose it does make sense that the engine could offer a random number generation API, but it is also very easy to just add whatever crate you want and use that. The downside of not offering an API is that every plugin that needs random numbers could/would make their own choice of what crate to use, which introduces bloat.

[alice-i-cecile]

Worse than bloat, the lack of a coherent standard makes ecosystem level cooperation on determinism much more challenging. If you have five plugins that use RNG, each with their own dependency, can the app developer get to determinism or do they need to vendor all of them?

If rand isn't fast enough, I'm very alright with choosing a different base. Speed is the goal here, not security.

[james7132]

I'm not initially sure it makes sense to try to build determinism into the engine itself, if it is even possible. It seems more like something one has to consider in the design of one's application.

It depends. We should certainly not impede a developer's efforts to do so. Too many other engines make this an impossibility. It is indeed scoped strictly to anything that affects game simulation. Systems like rendering, audio, etc. where the focus is on presentation clearly do not need to be concerned with it. However, anything that could possibly affect the core game state that drives that presentation (i.e. Transforms) should be deterministic and we should make an effort to keep it that way. With this said, a very conservative line in the sand doesn't just include core systems like transforms, but also animation, AI, etc. as they can impact the game state in a significant way. Hell, particle systems might be in the simulation hotpath depending on how the data is used.

When it comes to PRNGs, the design of Bevy really do not allow for global PRNGs to be used deterministically. The sequence of generated values forces a global PRNG to be used sequentially, which prohibits any form of parallelization, which is unacceptable from a performance perspective. This means we need scoped per-Entity or per-Component PRNGs that need to be consistently seeded, regardless of the rest of the ECS state. It's not particularly possible to force this via Rust's type system, but at least in first party crates, we can enforce certain usage patterns of these PRNGs.

[LegNeato]

Some non-scientific numbers, on my machine the current implementation PR with rand_core and rand_chacha adds .5-1 second to debug builds vs main (dfe969005264fff54060f9fb148639f80f9cfb29):

MAIN Finished dev [unoptimized + debuginfo] target(s) in 27.72s Finished dev [unoptimized + debuginfo] target(s) in 28.65s Finished dev [unoptimized + debuginfo] target(s) in 28.23s Finished dev [unoptimized + debuginfo] target(s) in 27.80s Finished dev [unoptimized + debuginfo] target(s) in 27.71s Finished dev [unoptimized + debuginfo] target(s) in 27.23s Finished dev [unoptimized + debuginfo] target(s) in 28.19s Finished dev [unoptimized + debuginfo] target(s) in 27.61s ENTROPY Finished dev [unoptimized + debuginfo] target(s) in 30.18s Finished dev [unoptimized + debuginfo] target(s) in 30.16s Finished dev [unoptimized + debuginfo] target(s) in 29.84s Finished dev [unoptimized + debuginfo] target(s) in 29.30s Finished dev [unoptimized + debuginfo] target(s) in 29.07s Finished dev [unoptimized + debuginfo] target(s) in 29.31s