The best solution I found was to get rid of objects and allocation entirely and instead store the state of the game in per-type tables like in this article.
Then I realized that I didn't need per-type tables at all, and if I used what amounted to a union of all types I could store all the game state in a single table, excluding graphical data and textures.
Next I realized that since most objects had properties like position and velocity, I could update those with a single method by iterating through the table.
That led to each "object" being a collection of various properties acted on by independent methods which were things like gravity and collision detection. I could specify that a particular game entity was subject to gravity or not, etc.
The resulting performance was fantastic and I found I could have many thousands of on-screen objects at the time with no hiccups. The design also made it really easy to save and replay game state; just save or serialize the single state table and input for each frame.
The final optimization would have been to write a language that would define game entities in terms of the game components they were subject to and automatically generate the single class that was union of all possible types and would be a "row" in the table. I didn't get around to that because it just wasn't necessary for the simple game I made.
I was inspired to do this from various articles about "component based game design" published at the time that were variations on this technique, and the common thread was that a hierarchical OO structure ended up adding a lot of unneeded complexity for games that hindered flexibility as requirements changed or different behaviors for in-game entities were added.
Edit: This is a good article on the approach. http://cowboyprogramming.com/2007/01/05/evolve-your-heirachy...
The reason it worked in my case was that for a 2d game, the state of even the maximum sized entity was very small. For animated objects I had a per-entity integer that stored what frame to display. The texture and animation data was stored elsewhere outside the table, but that was also loaded before the game started so there was no allocation after that point.
For a 3d game with complex animations it would be foolish to try to store all the animation and texture data in the same table, but I'd probably do something very similar for the game state.
It took until the late 90's and some overenthusiastic misfires with class inheritance-based designs(they don't compose cleanly) for the modern component-driven styles to start emerging. The tradeoff being made in current engines is basically one of late vs early binding - it's easier to write tooling against a late binding system where you can attach more nodes arbitrarily(e.g. Godot's scene system), but your optimization potential is better if you can compute exactly the data structures and containers needed for each category of entity and asset(there's a talk from Handmadecon about how Destiny went too far down this path and worked themselves into a corner).
Edit: Also, the biggest sticking point for working a GC in games isn't really with the entity and asset management since pooling will suffice for guaranteeing the quantities of elements needed for any given scene; it's with algorithms that work with standard functions that expect a GC environment, like string manipulation.
Of course, I also didn't consider any extra space wasted since it could potentially be used for recycling new components.
I then took it to the furthest extreme I could (everything in a single table) just to see if it would work well, and it did. Almost a purely functional approach to game architecture.
Frame State 0 -> Collection of composable functions to modify state -> Frame State 1
I found that to be vastly simpler and more effective than the OO approach of segregating state and functions into individual opaque objects. At that point OO seemed like such a brain-dead way to make things more difficult for myself I wondered if the entity-component idea wouldn't be more universally applicable to systems other than games. It is.
This was one of those rare cases where taking something to a logical extreme had an architectural benefit (all state in one easy-to-reason about table) that matched up really well with the performance benefit (memory locality). For systems where the system state is too large or varied to fit in a human's head, the benefits wouldn't be as apparent. But game states are, by definition, something that should be fairly easy to reason about because that's what the player is seeing and interacting with.
For instance, you could a physics system that loops over all of the velocity and position components and increments the positions by the velocity and a collision system that loops over the position components and handles collision.
The system you're describing has less memory locality than the ECS system described above. That's the main benefit of the added complexity of storing components separately. Another big benefit is that you can store different components in different types of data structures depending on how you need to access them.
Don't get me wrong, I'm not saying the ECS I'm talking about is necessarily better. It's not normally needed, and it's almost definitely overused by games that don't need it.
The idea behind it is that you can have a "WorldPosition" Component which stores all world positions as a flat array, and a "Gravity" System which acts upon WorldPosition components and makes them move. The idea is that since your data is tightly packed, it's easier to update.
A lot of people get this confused, though, so no worries.
> polymorphic django models using automatic type-field downcasting
> The actual type of each object is stored in the database, and when the object is retrieved it is automatically cast to the correct model class
> the common thread was that a hierarchical OO structure ended up adding a lot of unneeded complexity for games that hindered flexibility as requirements changed or different behaviors for in-game entities were added.
So, in order to draw a bounding box for an ensemble of hierarchically/tree/graph-linked objects (possibly modified in supersteps for reproducibility), is an array-based adjacency matrix still fastest?
Are sparse arrays any faster for this data architecture?
Interesting, never came across it. But I've got a Django GitHub library (not yet open source, because it's in a project I've been working with on and off) that does the same for managing GitHub's accounts. An Organization and User inherit the same properties and I downcast them based on their polymorphic type field.
IDK how to do partial indexes with the Django ORM? A simple filter(bool, rows) could probably significantly shrink the indexes for such a wide table.
Arrays are fast if the features/dimensions are known at compile time (if the TBox/schema is static). There's probably an intersection between object reference overhead and array copy costs.
Arrow (with e.g. parquet on disk) can help minimize data serialization/deserialization costs and maximize copy-free data interoperability (with columnar arrays that may have different performance characteristics for whole-scene transformation operations than regular arrays).
Many implementations of SQL ALTER TABLE don't have to create a full copy in order to add a column, but do require a permission that probably shouldn't be GRANTed to the application user and so online schema changes are scheduled downtime operations.
If you're not discovering new features at runtime and your access pattern is generally linear, arrays probably are the fastest data structure.
Hacker News also has a type attribute that you might say is used polymorphically: https://github.com/HackerNews/API/blob/master/README.md#item...
Types in RDF are additive: a thing may have zero or more rdf:type property instances. RDF quads can be stored in one SQL table like:
... with a few compound indexes that are combinations of (s,p,o) so that triple pattern graph queries like (?s,?p,1) are fast. Partial indexes (SQLite, PostgreSQL,) would be faster than full-table indexes for RDF in SQL, too.