Wonderful inductive reasoning from why object oriented programming of a game is challenging in Rust to some larger lessons about managing large type systems. I felt the discussion of crossing the barrier to Lua hinted towards some larger truths about types in distributed systems.
Could someone help me understand how "generational indexes" differ from usual indexes? Does this have to do with how you allocate the indexes or with how you use them? Are there run-time tests to check if the index is stale? (For example, check if the generation of the index I am holding matches the generation of the object stored in the entity array).
One interesting property of the current implementation is that you can use an Index across multiple IndexLists. That may or may not be what you want. There's a way to add a compile-time check to prevent this, but I haven't implemented it yet (https://github.com/steveklabnik/indexlist/issues/7)
Each generation represents a new ‘giving out’ of the index. As you say this provides a runtime check against accessing a stale value. It’s a common pattern for ‘object pool’ allocators in game engines.
I can understand the fast lookup, but if I understand correctly, every object in the game is an entity, and every entity is represented in every vector? So if you have a hundred game properties, an object that only utilizes three properties still has to be allocated a hundred times over?
Also I'm not sure how a system is meant to recognize which entities to do its work on, without iterating over the entire associated vector, every frame?
It seems like there's a lot of waste in this model
I'm also not sure why struct of arrays is better than an array of structs, where each struct implements each component as a trait (but still relies on the system to do the work), at least logically. It would definitely be more memory efficient if there's a high number of components that are rarely used, if I understand things correctly
The talk presents a fairly simplified version of what game engines actually do.
Components that are only used by a minority of entities can be kept in a map. The talk refers to `specs`, which is an ECS system implemented in Rust. It allows you to use different backends (a vector, a couple types of map, etc.) and it uses bitsets to optimize determining which entities have which components: https://slide-rs.github.io/specs/05_storages.html
As to why "struct of arrays" might be preferred to "array of structs", it's all about locality of data. Game Programming Patterns explains it way better than I possibly could: http://gameprogrammingpatterns.com/data-locality.html
> I can understand the fast lookup, but if I understand correctly, every object in the game is an entity, and every entity is represented in every vector? So if you have a hundred game properties, an object that only utilizes three properties still has to be allocated a hundred times over?
For any properties that are stored in a linear list, yes. Typically, values that are found in almost every object, and values that are small are placed in simple vectors. Values that are more rare and/or large enough to care about can be placed in a different, denser data structure.
> Also I'm not sure how a system is meant to recognize which entities to do its work on, without iterating over the entire associated vector, every frame?
For a lot of things you do in a game, iterating over the entire vector is substantially faster than deciding on what items you need work on. Linear access is really fast, cache misses are slow, and if the work done per entity is low enough, it can legitimately be faster to do it for everything and then just use a conditional move to only store the valid values, instead of eating branch prediction failures when choosing what to work on. Especially as SoA layout makes vectorizing code really easy.
Are the arrays untyped? If all enemies are the the same struct with various data components (state, speed, etc.), how would you implement different behaviors based on enemy type? Function pointers/references? Does the game loop have a 20-enemy-long switch statement which calls 20 different functions based on which enemy type is present? Does the game store 20 optional behavior components per enemy, and run 20 different if-component-present tests per frame per enemy?
If behavior is controlled from the top level(as is suggested by the cases where the main loop grows to 10's of thousands of lines) your behavior branching also appears there. The data is still driving everything, but if the data model is inherently complex it bubbles up to the surface. And you can use sum types(whether provided by the language or in less structured "match a magic constant" type deals) to check your coverage. During prototyping, you can lean on dynamic types instead and get a similar outcome with more fluidity in model changes and lower debuggability.
That feels instinctually wrong if you're dosed up on polymorphism and expect a kind of "ultimate abstraction" where any of the enemy types could be totally different and you just write to an interface, but - the thing you want, and that is the practical situation in most gameplay logic, is not "wholly bespoke behavior per type of enemy, hide everything behind a facade and either duplicate code or use a complex indirection to reuse it where it's the same" but "98% of the behavior is on the same code path and reads top to bottom, except for the one or two important pieces of business logic that isn't". The latter is both more compact in total SLOC and by being surgically precise, gives more visibility into what the code does at the moment you try to debug or extend it - which is what we're really aiming for.
And if you have really complex behaviors, you do end up with Turing-complete script logic embedded in the data, just naturally growing out of data model extension to cover FSM logic. That indicates that you are never really "giving up power" at any point in this process - you're just gradually moving things up the abstraction chain in a controlled fashion, until your main loop is really an interpreter that deals with "opcodes" and "commands" more than it does any particular algorithm or data layout.
And then when you get there, you can go, "well, now that I have a virtual machine, let's optimize around that..." and then you start writing some tech to lower the overhead of the interpreter...and it just goes from there. You never have to jump off that train, but you can usually ship something well before you get it even to the Turing-complete level of programmability, too.
> But damn, when will the gaming community realize they need something like GC?
I-- what does this even mean??
On the one hand, they don't need something like GC, as this clearly shows. Many larger games can't afford it, and wouldn't really benefit if they could, since they've already worked out more special-purpose access patterns.
And on the other hand, those games that can afford it often do use it already- Unity games are written in C#, UE4 has a limited GC for game objects, Minecraft was written in Java, tons of games use scripting languages like Lua for gameplay logic.
The SQL bit is also good. Basically somebody needs to bring capability ideology (highly related to magic pointer types in Rust, btw) to relational data organization to limit access patterns (no arbitrary joins) which will both allow for more modularity and perhaps distributed DBs that actually scale.
Your suggestion reminds me of Eve [1]. I remember when I first read the design/explainers, the closest analogy I could make was "all variables are backed by a database, and all manipulations are SQL". Not a very accurate statement, but it's how I wrapped my head around it.
