Question regarding "assemblage buckets" idea back in 2013

[slimsag]

Hello, hope this is an OK place to reach out. I realize it's not quite on topic.

I got anonymously tipped off to a post you had asked on the gamedev StackExchange many years ago (back in late 2013):

https://gamedev.stackexchange.com/questions/58693/grouping-entities-of-the-same-component-set-into-linear-memory/

Through this, I found your profile, and this repository (incredible you're still developing this to this day!) where that idea posted on StackExchange was referenced in this GitHub issue: #9

I dug through this repository's earliest commits, but wasn't able to find if you had ever made an actual implementation of this idea or not. I am interested broadly in whether or not you have any more code, notes, ideas, etc. written around this time with dates regarding this same general idea.

The reason I am asking all of this is because that StackExchange question appears to be one of (if not perhaps the only) pieces of publicly available information on the internet which describes (almost to the letter, and with diagrams) some of the key/critical claims made in Unity's infamous ECS patent (US 10,599,560), specifically around "assemblage buckets" / grouping entities of the same component set ("archetype") into linear memory. I'm looking to collect this information should it ever be needed by those less fortunate in the future to defend themselves.

Appreciate your time,
Stephen

[geneotech]

Hello @slimsag,

Wow, I never knew about Unity's patent! Thanks a lot for reaching out and letting me know!
I'm afraid I've never brought this concept to fruition, but let me try to recall the past to the best of my ability.
By looking at the commit history:

• In the earliest commit available (7e3eab0, anything earlier can be considered gone after my numerous HDD migrations) I had a simple ECS design wherein you just dynamically added components to an entity. There was no concept of assemblage buckets or recognizing component sets. I just had a pool for each component type, and within these pools, components of the same type were always kept linearly in memory.

• (Key part) I wanted something better, so I came up with the idea of assemblage buckets. I described it on StackExchange in detail and attempted implementation, but unfortunately, I distinctly remember ditching it halfway as I considered it too complex at the time (would be a piece of cake with all the C++ template magic available today). In short, I have never made this truly work for my game. I might have pushed some work-in-progress commits to this repository, but I'm certain I've never built a working binary of the game with assemblage buckets, and I had a really bad habit of force-pushing if I wanted to delete commits I didn't need - so it might be hard to find these WIP commits (I will later try to find out if it's possible to recover them from GitHub).

• I do have comments from a later time (e.g. in 2015) in the issue you linked, however I often just save my ideas in GitHub Issues and they are not always accompanied by any serious attempts. I perhaps thought I could revive the concept in the future.

• In 2016, commit c038d75 first mentions "aggregates", but this was merely an alternative name to an "entity", and after a while, I went back to the original nomenclature.

• In 2018, it dawned on me that I could trivailly implement assemblage buckets defined in compile-time, I've been successfully using these since. It appears that I've first successfully built this concept in b944a8c, on Feb 11, 2018, so before US 10,599,560 was filed (on 2018-06-12) - and were later only bugfixing. If we assume that the programmer knows all posible signatures (to use my terminology from 2013) beforehand, they are functionally the same as the original assemblage buckets, except that components cannot be removed or added dynamically, nor can new types of assemblage buckets be defined after the game is built. Well.. these two features are probably critical in Unity's infrastructure and the patent itself - but they were completely unnecessary in my case. These being known in compile-time additionally has some positive implications for optimization. Since 2018:

  • I keep a header called "all_entity_types" that defines all possible tuples of components for a given game (in this case, Hypersomnia). Tuples hold their heterogenous elements next to each other in memory.
  • Every entity type defined this way gets its own pool, and the pool is designed to hold them linearly in memory as well. I've been using the same pool design since 2013 that erases/inserts/accesses elements in O(1), exactly as described in the StackExchange post.
  • This sounds complicated, but if we strip all the template metaprogramming magic regarding ECS, this is exactly the same as if we had something like

struct player {
	components::transform transform;
	components::health health;
};

struct box {
	components::transform transform;
	components::physics physics;
};

struct game_world_state {
	std::vector<player> players;
	std::vector<box> boxes;
};

A layout which I'm sure would be used throughout many simple games even way before ECS was talked about.

I'll take a look again through my archival notes to be sure, but I don't want to get your hopes up. If I find something I'll certainly post it in this issue.

[slimsag]

Awesome! Thanks for digging all of that info up @geneotech, I really appreciate it!

Also, just to be clear, the SE post itself is enough to prove prior art of the concepts/ideas described in the post specifically, and so could be used to defend against any lawsuit making claim against those ideas. An implementation is not necessarily a requirement, per-say. I just opened this issue in case you had any other notes/references about this idea since the more documented proof of it existing before Unity patented it the better :)

Needless to say I think myself and many others will find the fact that you had posted about this idea on StackExchange to be.. quite useful! 😅