Hacker News Reader

The general approach described by the author is the one used by many game enginges. The main reason, however, the refactor that you've described here isnt used is that it bloats memory by a significant factor (which thereby reduces performance). Since you have to allocate for each array index the size of the largest item in the union, there is a lot of wasted space when you have lots of smaller items. If you have fewer than a couple billion points, a triangle will fit in 12 bytes, a game object can easily have 10 fields for a total of 30 bytes. Thats a massive expansion of your triangle array which will result in more cache misses.

Of course, this isn't a general solution to every problem and I wouldn't use it if there was a huge distribution in entity sizes like you described.

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.

I've tried a lot of ways of structuring game data but I basically agree with this assessment. Simple game logic can usually be premised on a single "God Object" type of deal that contains every possible property, or if you're in a language that supports it, is just a form of dynamic type. In old 8-bit games bit packing and unions would be used to conserve memory, but the games generally weren't complex enough in architectural scope to require a generalized approach to custom data structures and containers - just a few for optimization's sake.

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.

Shows what I know... I came around to the same conclusion as drblast with my own ecs project and assumed it would perform better than multiple arrays being a single array of the same type.

Of course, I also didn't consider any extra space wasted since it could potentially be used for recycling new components.

Reminds of some assembly (!) source code I read once for, I think it was, Super Mario brothers as ported to the TI-89 calculator. Every object in the game had the same bit structure (position, velocity, weight, width, some others), with the final word being a pointer to an "update" function. The game loop was a very straightforward physics update on each object followed by a call to its update function.

Sounds like you discovered the Entity-Component System.

Pretty much. The fact that it solved a specific performance problem (avoiding GC pauses) in a tiny game I was making, along with the ease of reasoning about and debugging game state was really interesting to me. Most of the articles about it were about managing large code bases which didn't apply to my little toy game project.

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.

This is a bit pedantic, but this type of entity component architecture, isn't really the architecture that "Entity Component System" has come to describe. ECS usually refers storing the components separately and looping over each one (or small groups of them) separately.

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.

>memory locality

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.

Quick rant: it's "Entity Component Systems". The "System" doesn't describe the approach in general, it describes an object called a "System". Entities are IDs (equivalent to indexes into his array), Components are property bags (values in his array), Systems are things that act on components (his update loop could be considered a System).

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.

> 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

django-typed-models https://github.com/craigds/django-typed-models

> 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?

> django-typed-models https://github.com/craigds/django-typed-models

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.

ContentType.model_class(), models.Model.meta.abstract=True, django-reversion, django-guardian

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:

_id,g,s,p,o,xsd:datatype,xml:lang

... 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.

Under XNA, the garbage collector on PC was rudimentary compared to the generational garbage collector on Xbox 360. I had the same problems when working on a game in 2008.

I think you got it backwards, the GC was rudimentary on the Xbox.

Ugh yeah, you're right - I had to look this up again, it's been that long. Makes sense as we always ran it on the machine as running it on PC would run fine.

ECS style is nice from a design perspective but as far as GC goes it was the pooling objects into tables that really solved your issue. You can pool objects in many different styles. Preallocation is a good idea as well as stack allocating what you can.