Comment by o11c | Hacker News Reader

Comment by o11c | Hacker News Reader

Unrelated to the specific game:

Note that the "can't parallelize AI/scripting" is a consequence for a design choice that many people make without thinking - namely, that all actors should, internally, have perfectly accurate and up-to-date knowledge of the world, using the same in-game global objects.

If each actor makes a copy of the world for what they know, there's nothing preventing parallelism. This does imply quadratic memory, but you can just cap this - if there's a lot going on, it makes sense for an actor to lose track of some of it. And once you're working with imperfect knowledge, you can just ... throttle the AI's think time if it's doing too much.

Another thing you can do, assuming you already have suspendable scripts, is "merge" the thread affinity of two scriptable objects when you know they need to interact (only really needed for transaction-like things; often you can just emit some async state to be resolved later). Actually, you don't need to suspend if you have enough static analysis, but suspending is probably actually the easier thing to do.

Related to this, IMO it's a mistake to expose functions to the scripting API that access state implicitly. It's a better design to expose objects (that can only be accessed/mutated if passed as an argument) - and to expose a different set of objects depending on what context the script is called in. A type-checker is really useful here.

> If each actor makes a copy of the world for what they know, there's nothing preventing parallelism

Unfortunately not that easy.

If two scripts consume an item, decrement a variable (hit points, credits, count) then it’s not as simple as giving each script a copy of the world. You get double spending, duplicated items, etc.

The point of the copy is that they can't actually change anything outside of their local world. They can only send out an async request for global state to change, or send a request to be scheduled on the same executor.

And this specifically introduces transactional boundaries, which can introduce a lot of complexity. Especially in games where the domains (thus boundaries) may change a lot during development as the game design is being figured out.

This! One of the fun things about writing programs in Rust is that it really makes you aware of ownership of data inside the program. If you try to write a game where the game loop owns the game state, then loops over the actors letting each actor also modify the game state, then the compiler will complain. The exact error messages may vary, since there are a number of variations that the compiler might notice first. For example, an actor that spawns another actor will trigger an error when it tries to mutate the list of actors, and so on.

After going around and around for a while trying to satisfy the compiler, you’ll eventually conclude that either the game loop must hold no mutable state at all or that the actors must not get mutable access to the game state. The easiest solution is to give actors a read–only view of the world and have them produce a list of changes that they would like to make. Then the whole thing becomes trivially parallelizable. It doesn’t matter how many threads you scatter the actors out over because none of them are modifying the world. You just gather up the list of changes and merge them. Even merging them can be incremental and spread over multiple threads if your merge is associative.

Of course for some game designs you may still need or want the actors to be more serialized than that. For example in Factorio there are dependencies between inserters and belts and power networks and circuit conditions and so on. The inserters cannot be updated before the power networks or circuit conditions have been computed, and so on. But that just means that you have multiple steps where you scatter the computation for some set of actors across all available cpus, gather the results into a single list of changes to the world, then update the world based on those changes.

Another model may be that all actors read from frame N-1 and write to frame N. Then there's not many copies, just one.

Two, surely? The previous one still being used and the new one being written.

(Note that this is how most rendering artifacts were fixed long ago - the on screen and the off screen buffers were swapped, so nobody would "see" in progress scenes)

1 copy + the original = 2 instances in memory.

That's fine if actors are not doing much (e.g. just pathfinding and shooting), but is likely to fall apart long before scripting becomes a thing, since there are a lot of tasks where different actors do want to mutate the same object.

This is AI, having multiple actors plan to gather the same resource etc isn’t necessarily a flaw. It does however result in meaningful game design decisions getting tided up in how the game engine is designed.

This is a great example. It's probably pretty insignificant from a players perspective in most contexts. And you could most certainly design some acceleration structures to specifically handle AI convergence specific to your use case.

Can you share an example where this model falls apart?

Reply on news.ycombinator.com