Why didn't Casey just combine all the possible data into one big discriminated union and have multiple of those in each entity? Then it would get the benefit of having duplicate data. For example, imagine a boss which has some data about its movement (speed, direction, animation, sfx, etc). The boss has multiple phases and each phase uses different movement data (different speeds, animations, etc). If you use a discriminated union then the boss can easily have multiple of those to store all the different values of the same type. Here's the example code:
Each entity will take less space and can have multiple fields of the same type.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 | struct MovementData
{
float speed;
// Other field
}
struct Data
{
DataType type;
union
{
MovementData movement;
// Other data
}
}
struct Entity
{
Data* data; // an array of data. Each entity will have different sets of data.
}
void MoveEntity(Data* data)
{
if (data.type == Movement) { /* Move the entity*/ }
}
// Someplace else in the code
Entity boss = CreateBoss(/*params*/) // Create a boss with multiple MovementData correspond to each phase.
// Phase 1:
MoveEntity(boss.data[0]);
OtheStuff1(boss.data[0]);
// Phase 2:
MoveEntity(boss.data[1]);
OtherStuff2(boss.data[1]);
|
Each entity will take less space and can have multiple fields of the same type.
Edited by longtran2904
on
Reason: Initial post
Unions are trickier to view in a debugger
and shrinking data is only useful when there is something to be gained from that shrinking.
You end up needing to check the tag every time you access the union and the one time you forget is the time you corrupt the data.
Having a mega struct instead means that the debug view of the struct is less obtrusive and you can be sure that if you mess with a field no other fields will be messed with.
Having better tooling to deal with discriminated unions would alleviate a bit (at the cost of more runtime checks) that but that's not the case in C.
and shrinking data is only useful when there is something to be gained from that shrinking.
You end up needing to check the tag every time you access the union and the one time you forget is the time you corrupt the data.
Having a mega struct instead means that the debug view of the struct is less obtrusive and you can be sure that if you mess with a field no other fields will be messed with.
Having better tooling to deal with discriminated unions would alleviate a bit (at the cost of more runtime checks) that but that's not the case in C.
So what if I flip the question, why bother to use discriminated union at all and don't just put all possible values in a single type, like this:
Assuming that I don't care about memory space and I already have an optimized system to store and compress/decompress it when needed. Now I get an advantage in situations when I need both of foo and bar. It also gets all the benefits above.
Edit: We also don't need to use the DataType field at all. We can choose when we need it and when not. That will somewhat make it easier to do write code because we don't need to check for the type constantly.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 | struct Foo
{
int a;
float b;
}
struct Bar
{
bool c;
char* d;
}
struct BarOrFoo
{
DataType type
union
{
Foo foo;
Bar bar;
}
}
struct BarAndFoo
{
DataType type; // We still can keep the DataType field for situations when only one of them is initialized.
Foo foo;
Bar bar;
}
void DoFoo(BarAndFoo baf)
{
if (BarAndFoo.type == Bar) /* Do something with baf.bar */
}
void DoFoo(BarAndFoo foo)
{
if (BarAndFoo.type == Foo) /* Do something with baf.foo */
}
void DoBothFooAndBar(BarAndFoo baf)
{
// We can just use the baf and assume that it all initialize correctly or we could add FooBar to DataType and check it or for some other situations both.
}
BarAndFoo CreateBar(params...) {}
BarAndFoo CreateFoo(params...) {}
BarAndFoo CreateBothBarAndFoo(params...) {}
AddBar(params..., BarAndFoo* baf) {} // We can add values to it at runtime and don't need to worry about anything.
|
Assuming that I don't care about memory space and I already have an optimized system to store and compress/decompress it when needed. Now I get an advantage in situations when I need both of foo and bar. It also gets all the benefits above.
Edit: We also don't need to use the DataType field at all. We can choose when we need it and when not. That will somewhat make it easier to do write code because we don't need to check for the type constantly.
Edited by longtran2904
on
There isn't a right answer. It depends on the situation and what coding style you like. If there are no performance implications, do whatever you like. At some point you might find reasons to do one thing or the other and you might want to try the other way. Doing an abstract example can help you choose at first, but only after actually using the system for a while will you be able to judge the advantages and disadvantages of the solution you choose.
Edited by Simon Anciaux
on
Reason: typo
A big drawback I've found with the discriminated union approach in the past is that it requires a ton of code. This is simply because you cannot assume anything about the data format. When using a flat struct, you can assume the way data is packed/stored in some memory looks identical across all instantiations of the type.
Additionally, I've found compressing data with a union to often be very premature, and it turns out that a "fat struct" approach can actually end up being relatively small and compressed also (but the compression happens later). This of course depends on the problem at hand, this is just my experience working with this style with many problems (not just entities in a game).
Given some Foo type:
A very important part about having Foo around is that it lets code make assumptions. Having a Foo *foo passed to you is like having a "receipt" about what the data is, and how it is stored. Once you turn Foo into a big discriminated union, no such assumptions can be made, so you need to start checking the discriminator, which is probably some enum, all the time.
I am not saying you never use unions or have discriminated unions to build sum-types, but they lead to a lot of code, and when they're at the core of a system, and you want lots of combinatoric interactions between a bunch of instances of this type, the code bloat becomes magnified exponentially. So, I've had much more success just assuming the data format to be identical, and finding ways of packing the entity information I need into a uniform struct (or a data structure built out of them).
This way, every codepath you write over that struct will work for all structs of that type. As long as something you need can be packed into that struct, all the codepaths written for it are now tools that are available to you.
Additionally, I've found compressing data with a union to often be very premature, and it turns out that a "fat struct" approach can actually end up being relatively small and compressed also (but the compression happens later). This of course depends on the problem at hand, this is just my experience working with this style with many problems (not just entities in a game).
Given some Foo type:
1 2 3 4 5 6 | struct Foo
{
int x;
int y;
int z;
};
|
A very important part about having Foo around is that it lets code make assumptions. Having a Foo *foo passed to you is like having a "receipt" about what the data is, and how it is stored. Once you turn Foo into a big discriminated union, no such assumptions can be made, so you need to start checking the discriminator, which is probably some enum, all the time.
I am not saying you never use unions or have discriminated unions to build sum-types, but they lead to a lot of code, and when they're at the core of a system, and you want lots of combinatoric interactions between a bunch of instances of this type, the code bloat becomes magnified exponentially. So, I've had much more success just assuming the data format to be identical, and finding ways of packing the entity information I need into a uniform struct (or a data structure built out of them).
This way, every codepath you write over that struct will work for all structs of that type. As long as something you need can be packed into that struct, all the codepaths written for it are now tools that are available to you.
Ryan, I'm not sure I understand what you mean about reducing code by not using unions. If the data is eligible to be packed into a union, it's because only one of the union types is active at a time, and accessing any of the others is logically wrong. Storing the union's members separately instead of in a union doesn't change the logic, only the data layout, so you'd still have to check the type in all the same situations you did before. So I assume you're talking about something more than just a data layout change, but it wasn't clear to me what that is specifically.
You're totally right that you still have to check the discriminator often, particularly because---within this model---entities are considered as being certain "kinds", or "sub-types", and those "kinds" are used as ways to refer to bundles of behavior. So, when making sure that certain codepaths light up for certain bundles (entities), and don't light up for other bundles, you have to perform a check on the discriminator (or several checks, but more on this in a bit).
But I'd say it's not quite true that you always have to check the discriminator regardless of which situation you're in. In some cases, you don't actually need to, because you do have the guarantee that any data manipulations you make to entity data will not be destructive to other important data in the entity. Or, similarly, any data reads you make assuredly map to a single interpretation. This guarantee is not true with unions because of the data layout, so the data layout is not irrelevant.
For these reasons, with a naive "fat struct" equivalent to a union, it isn't actually logically wrong to access or mutate data that isn't explicitly considered as being part of a "kind". The discriminator is used more of a way to guard certain codepaths behind certain curated bundles of features, but not to enforce that model across all codepaths that might read or write entity data.
The aspect of this that leads to more code is the strict enforcement of the model of sub-types across all such codepaths. When you do not have that strict enforcement, certain codepaths end up being freed up, purely because they can make assumptions about the format of any Entity they see, instead of having nearly everything guarded behind a kind check (which was necessary with the union). With the naive ("naive" meaning I don't think it's the fully correct option) "fat struct" equivalent to a discriminated union, it's much easier to have data flow freely in-and-out of being relevant for certain features, and it's much easier to write code irrespective of whether or not certain data is considered "logically wrong" or not. I think, what you'll find within this slight, naive adjustment to the discriminated union model, that what you end up with is not actually a "type tree" shape at all.
But, I don't actually think any of that matters, because I think "entity kinds" is the wrong model to begin with. The idea of a "type discriminator" does not seem helpful for entities, in my opinion/experience. This is because you're not actually dealing with "types" of entities, you're dealing with bundles of behaviors, or more specifically, bundles of codepaths. Before, entity "kinds" were ways of grouping certain features together.
Let's say you have N possible features in your game. These features correspond directly to important codepaths that implement useful features you want in your game world. Let's also say that these features are orthogonal, meaning they don't overlap at all. Each feature is unique and is only written once (which seems obviously preferable). Finally, to express any effect you need, you just bundle these features together. So, a few toy examples:
On the left, you can see what we would've called "entity kinds" before. But this mapping is explicitly stating that those "kinds" were really just features we wanted matched together---codepaths that we wanted to be turned on for certain instances of stuff in the world.
What we can appreciate here is that N features leads to 2^N possible combinations. So, for example, in the case where N = 4:
So 16 cases, not that bad. But most games don't have 4 features, they have a much larger number than that. And 2^20, let's say, is already in the millions.
What I think is a much more productive model for entities, which naturally follows from the "fat struct" approach, is this: Instead of checking "entity kinds" to guard against certain codepaths, or trigger certain codepaths, just check a bit that turns that codepath on or off. So now, there is a direct mapping from a single piece of data---one bit---to a particular codepath running or not, for any given entity. And, now, you have a way to bundle these codepaths together, because you'd just store these in flags:
or in a bit array if you want a lot:
This doesn't mean you can't still talk about "kinds", but they're just not the thing you're storing. An "entity kind" is actually just a helper function:
And now, you have one type, one way of interpreting that type, and an entire 2^N-size space of feature combinations you can explore as a designer. You can even build a UI for exploring that 2^N-size space quite trivially (just loop through the EntityProperty values), which could be useful.
Because there's only one way to interpret the type, you can write codepaths that are actually not specific to any entity "kind" at all, but still work with all of the data of an entity. The entity "kind" just doesn't really matter in many codepaths, while the data often still does. This is where the code savings comes from, as well as the fact that the work you have to do managing these "bundles" doesn't scale like O(2^N), and instead scales like O(N).
---
Now, a couple extra points that I'll make in anticipation of objections (not responding to anyone in particular, just for people who are reading who may have these common questions/objections):
---
How do you prevent non-meaningful bundles of features? Isn't the point of entity kinds to curate them?
In my opinion this depends on the use-case. In many games, there's just no point to preventing meaningless bundles. In an authored game, for example, you just don't make meaningless bundles, just like you don't make nonsensical maps where the player falls to their death immediately. In procedurally generated games, the first thing I'd say is that suddenly it starts being a lot more obvious how you'd procedurally generate anything (by coloring certain combinations in the 2^N-size set as either valid or invalid). But, obviously, that coloring work needs to be done, but doing it one "kind" at a time is asking for trouble, because now you're doing O(2^N) work.
---
What about the size of entities?
Three points here.
The first point is just a practical one; in more-or-less every case, this pales in comparison to the size of other things you're storing, so whatever.
The second is this: When all entity data is living side by side, in a plain struct, together, and when features are truly being orthogonalized, it's much easier to start collapsing data down, and compressing it by using the same data to encode a variety of things (while not increasing the number of interpretations). So when using this style in a number of problem-spaces (entities, but also UI, parsers/ASTs, etc.) I've noticed things actually getting quite small, much smaller than you might expect when you first encounter an initial naive "fat struct" transformation from the traditional inheritance-tree-like discriminated union model.
The third: Having a single type, with only a single interpretation, matters a lot, particularly because you can start building data structures quite easily out of them. In the context of entities, this means building a structure of entities to get the effects you want, instead of just one entity per thing in the world. For example:
So, the meaning of "entity" can shrink to be something a bit more granular, which lets you start piecing entities and combining features that way. This also means that a single Entity is actually small. It's the entire data structure of them---for complex entities---that gets meaningfully large, but for those cases, you needed the size anyways.
Note that getting rid of the idea of "kinds"---which assumes a particular granularity---is necessary here. The "fat struct", mapping single bits to single codepaths directly, is exactly how you'd start doing this. It doesn't make any sense to say a Tree has a Player parent (unless it's used for simple things, like transform hierarchies). But when you ditch "kinds", it starts being much more useful to start building structures out of entities.
I used precisely this idea in a small-scope game I've been working on (when I find the time). You can see some of the effects here:
https://handmade.network/snippet/351
https://handmade.network/snippet/336
---
Anyways, that's what I mean, hopefully it cleared things up. I'm still trying to figure out how to communicate these ideas more clearly (my theory on this stuff, which came about largely because of working on Dion, goes fairly deep and is hard to condense/compress well), so forgive any weird explanations or lack of clarity. It's also an extremely dense subject that's hard to compress into language, but I'm hoping I sort of got the idea across.
But I'd say it's not quite true that you always have to check the discriminator regardless of which situation you're in. In some cases, you don't actually need to, because you do have the guarantee that any data manipulations you make to entity data will not be destructive to other important data in the entity. Or, similarly, any data reads you make assuredly map to a single interpretation. This guarantee is not true with unions because of the data layout, so the data layout is not irrelevant.
For these reasons, with a naive "fat struct" equivalent to a union, it isn't actually logically wrong to access or mutate data that isn't explicitly considered as being part of a "kind". The discriminator is used more of a way to guard certain codepaths behind certain curated bundles of features, but not to enforce that model across all codepaths that might read or write entity data.
The aspect of this that leads to more code is the strict enforcement of the model of sub-types across all such codepaths. When you do not have that strict enforcement, certain codepaths end up being freed up, purely because they can make assumptions about the format of any Entity they see, instead of having nearly everything guarded behind a kind check (which was necessary with the union). With the naive ("naive" meaning I don't think it's the fully correct option) "fat struct" equivalent to a discriminated union, it's much easier to have data flow freely in-and-out of being relevant for certain features, and it's much easier to write code irrespective of whether or not certain data is considered "logically wrong" or not. I think, what you'll find within this slight, naive adjustment to the discriminated union model, that what you end up with is not actually a "type tree" shape at all.
But, I don't actually think any of that matters, because I think "entity kinds" is the wrong model to begin with. The idea of a "type discriminator" does not seem helpful for entities, in my opinion/experience. This is because you're not actually dealing with "types" of entities, you're dealing with bundles of behaviors, or more specifically, bundles of codepaths. Before, entity "kinds" were ways of grouping certain features together.
Let's say you have N possible features in your game. These features correspond directly to important codepaths that implement useful features you want in your game world. Let's also say that these features are orthogonal, meaning they don't overlap at all. Each feature is unique and is only written once (which seems obviously preferable). Finally, to express any effect you need, you just bundle these features together. So, a few toy examples:
1 2 3 4 | Player = { RenderSprite, ControlledByUser, HasPhysicsShape }
Tree = { RenderSprite, HasPhysicsShape, IsStatic }
Jelly = { RenderSprite, ChasePlayer, HasPhysicsShape, Hostile }
PartyMember = { RenderSprite, ChasePlayer, HasPhysicsShape }
|
On the left, you can see what we would've called "entity kinds" before. But this mapping is explicitly stating that those "kinds" were really just features we wanted matched together---codepaths that we wanted to be turned on for certain instances of stuff in the world.
What we can appreciate here is that N features leads to 2^N possible combinations. So, for example, in the case where N = 4:
So 16 cases, not that bad. But most games don't have 4 features, they have a much larger number than that. And 2^20, let's say, is already in the millions.
What I think is a much more productive model for entities, which naturally follows from the "fat struct" approach, is this: Instead of checking "entity kinds" to guard against certain codepaths, or trigger certain codepaths, just check a bit that turns that codepath on or off. So now, there is a direct mapping from a single piece of data---one bit---to a particular codepath running or not, for any given entity. And, now, you have a way to bundle these codepaths together, because you'd just store these in flags:
1 2 3 4 5 6 7 8 9 | typedef U64 EntityProperties;
enum
{
EntityProperty_RenderSprite = (1<<0),
EntityProperty_ChasePlayer = (1<<1),
EntityProperty_ControlledByUser = (1<<2),
EntityProperty_HasPhysicsShape = (1<<3),
// etc.
};
|
or in a bit array if you want a lot:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | enum EntityPropertiy { EntityProperty_RenderSprite, EntityProperty_ChasePlayer, EntityProperty_ControlledByUser, EntityProperty_HasPhysicsShape, // etc. EntityProperty_COUNT }; struct Entity { U64 properties[(EntityProperty_COUNT + 63) / 64]; // other data... }; B32 EntityHasProperty(Entity *entity, EntityProperty property); void SetEntityProperty(Entity *entity, EntityProperty property); |
This doesn't mean you can't still talk about "kinds", but they're just not the thing you're storing. An "entity kind" is actually just a helper function:
1 2 3 4 5 6 7 8 9 | Entity *MakePlayer(void)
{
Entity *entity = AllocateEntity();
SetEntityProperty(entity, EntityProperty_ControlledByUser);
SetEntityProperty(entity, EntityProperty_RenderSprite);
entity->sprite_info = ...;
// etc.
return entity;
}
|
And now, you have one type, one way of interpreting that type, and an entire 2^N-size space of feature combinations you can explore as a designer. You can even build a UI for exploring that 2^N-size space quite trivially (just loop through the EntityProperty values), which could be useful.
Because there's only one way to interpret the type, you can write codepaths that are actually not specific to any entity "kind" at all, but still work with all of the data of an entity. The entity "kind" just doesn't really matter in many codepaths, while the data often still does. This is where the code savings comes from, as well as the fact that the work you have to do managing these "bundles" doesn't scale like O(2^N), and instead scales like O(N).
---
Now, a couple extra points that I'll make in anticipation of objections (not responding to anyone in particular, just for people who are reading who may have these common questions/objections):
---
How do you prevent non-meaningful bundles of features? Isn't the point of entity kinds to curate them?
In my opinion this depends on the use-case. In many games, there's just no point to preventing meaningless bundles. In an authored game, for example, you just don't make meaningless bundles, just like you don't make nonsensical maps where the player falls to their death immediately. In procedurally generated games, the first thing I'd say is that suddenly it starts being a lot more obvious how you'd procedurally generate anything (by coloring certain combinations in the 2^N-size set as either valid or invalid). But, obviously, that coloring work needs to be done, but doing it one "kind" at a time is asking for trouble, because now you're doing O(2^N) work.
---
What about the size of entities?
Three points here.
The first point is just a practical one; in more-or-less every case, this pales in comparison to the size of other things you're storing, so whatever.
The second is this: When all entity data is living side by side, in a plain struct, together, and when features are truly being orthogonalized, it's much easier to start collapsing data down, and compressing it by using the same data to encode a variety of things (while not increasing the number of interpretations). So when using this style in a number of problem-spaces (entities, but also UI, parsers/ASTs, etc.) I've noticed things actually getting quite small, much smaller than you might expect when you first encounter an initial naive "fat struct" transformation from the traditional inheritance-tree-like discriminated union model.
The third: Having a single type, with only a single interpretation, matters a lot, particularly because you can start building data structures quite easily out of them. In the context of entities, this means building a structure of entities to get the effects you want, instead of just one entity per thing in the world. For example:
1 2 3 4 5 6 7 8 9 | struct Entity
{
Entity *first_child;
Entity *last_child;
Entity *next;
Entity *prev;
Entity *parent;
// other data ...
};
|
So, the meaning of "entity" can shrink to be something a bit more granular, which lets you start piecing entities and combining features that way. This also means that a single Entity is actually small. It's the entire data structure of them---for complex entities---that gets meaningfully large, but for those cases, you needed the size anyways.
Note that getting rid of the idea of "kinds"---which assumes a particular granularity---is necessary here. The "fat struct", mapping single bits to single codepaths directly, is exactly how you'd start doing this. It doesn't make any sense to say a Tree has a Player parent (unless it's used for simple things, like transform hierarchies). But when you ditch "kinds", it starts being much more useful to start building structures out of entities.
I used precisely this idea in a small-scope game I've been working on (when I find the time). You can see some of the effects here:
https://handmade.network/snippet/351
https://handmade.network/snippet/336
---
Anyways, that's what I mean, hopefully it cleared things up. I'm still trying to figure out how to communicate these ideas more clearly (my theory on this stuff, which came about largely because of working on Dion, goes fairly deep and is hard to condense/compress well), so forgive any weird explanations or lack of clarity. It's also an extremely dense subject that's hard to compress into language, but I'm hoping I sort of got the idea across.
I've never done a complex entity system, so I'm trying to understand your points. I'm not trying to prove you wrong.
Could you provide a (if possible) real example of "using the same data to encode a variety of things" as it sounds like what a union would help with ?
I don't understand why "single interpretation" matters here ? Am I correct in understanding "single interpretation" as "I can always read the data from the "flat struct" even if that part of the struct isn't used by the entity (e.g. reading the health value even if the entity doesn't use health) " ? If that's the case than why is it important to creating a tree of entities like in your example ?
Is the following code somewhat doing what you meant, but using unions ? (no entity kind, you don't have to check for behavior type if you know the entity uses the behavior, but you can add any behavior to an entity and it should work with "generic" entity functions).
I would like if possible to see the code of the entity system of your small game, because I find it hard to get the real benefits from "imagined" system.
Is the array count correct there ? If so why ? If there are 100 items, you have (100 + 63) / 64 = 2. So we have 2 u64 but each property is a u32 (since those are not flags) so we could only store 4 properties ?
Delix
The second is this: When all entity data is living side by side, in a plain struct, together, and when features are truly being orthogonalized, it's much easier to start collapsing data down, and compressing it by using the same data to encode a variety of things (while not increasing the number of interpretations).
Could you provide a (if possible) real example of "using the same data to encode a variety of things" as it sounds like what a union would help with ?
Delix
The third: Having a single type, with only a single interpretation, matters a lot, particularly because you can start building data structures quite easily out of them. In the context of entities, this means building a structure of entities to get the effects you want, instead of just one entity per thing in the world.
I don't understand why "single interpretation" matters here ? Am I correct in understanding "single interpretation" as "I can always read the data from the "flat struct" even if that part of the struct isn't used by the entity (e.g. reading the health value even if the entity doesn't use health) " ? If that's the case than why is it important to creating a tree of entities like in your example ?
Is the following code somewhat doing what you meant, but using unions ? (no entity kind, you don't have to check for behavior type if you know the entity uses the behavior, but you can add any behavior to an entity and it should work with "generic" entity functions).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 | typedef enum behavior_type_t { behavior_type_none = 0, behavior_type_health = 1 << 1, behavior_type_physics = 1 << 2, ... } behavior_type_t; typedef struct behavior_t { u32 type; union { struct { ... } health; struct { ... } physics; ... }; } behavior_t; typedef struct entity_t { /* Indexes in a array/free list of behaviors storage, but could be anything else (pointer array, link list... ). */ u32 behaviors[ 10 ]; u32 behavior_count; u64 behavior_mask; struct entity_t* first_child; struct entity_t* last_child; struct entity_t* parent; /* Maybe next/previous if you need more than the number of behavior allowed by the array. */ } entity_t; void player_initialize( entity_t* entity ) { entity->behavior_count = 0; entity->behaviors[ entity->behavior_count++ ] = get_free_behavior_index( behavior_type_health ); entity->behaviors[ entity->behavior_count++ ] = get_free_behavior_index( behavior_type_physics ); entity->behavior_mask = behavior_type_health | behavior_type_physics; } void player_do_stuff( entity_t* entity ) { behavior_t* b_0 = get_behavior( player->behaviors[ 0 ] ); b_0.health.in_love = true; behavior_t* b_1 = get_behavior( player->behaviors[ 1 ] ); b_1.physics.can_fly = true; } void behavior_update_health( behavior_t* behavior ) { assert( behavior->type == behavior_type_health ); if ( behavior->health.in_love ) { ... } } void behavior_update_physics( behavior_t* behavior ) { assert( behavior->type == behavior_type_physics ); if ( behavior->physics.can_fly ) { ... } } void entity_update_behaviors( entity_t* entity ) { for ( umm i = 0; i < entity->behavior_count; i++ ) { if ( entity_has_behavior( entity->behavior_mask, behavior_type_health ) ) { behavior_update_health( get_behavior( entity->behaviors[ i ] ); } if ( entity_has_behavior( entity->behavior_mask, behavior_type_physics ) ) { behavior_update_physics( get_behavior( entity->behaviors[ i ] ); } } } int main( int argc, char** argv ) { ... player_initialize( player ); ... player_do_stuff( player ); entity_update_behaviors( player ); ... return 0; } |
I would like if possible to see the code of the entity system of your small game, because I find it hard to get the real benefits from "imagined" system.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | enum EntityPropertiy { EntityProperty_RenderSprite, EntityProperty_ChasePlayer, EntityProperty_ControlledByUser, EntityProperty_HasPhysicsShape, // etc. EntityProperty_COUNT }; struct Entity { U64 properties[(EntityProperty_COUNT + 63) / 64]; // other data... }; |
Is the array count correct there ? If so why ? If there are 100 items, you have (100 + 63) / 64 = 2. So we have 2 u64 but each property is a u32 (since those are not flags) so we could only store 4 properties ?
Edited by Simon Anciaux
on
mrmixer
Could you provide a (if possible) real example of "using the same data to encode a variety of things" as it sounds like what a union would help with ?
Yep. The simplest example I have is the idea of an entity being "toggled". I was working on a prototype at some point that had a number of entity features. There were levers, which could cause electricity in the world when turned on, there were doors that produced collision if they were closed, there were lights that could be turned on or off, etc. Turns out, all of this can be expressed with a uniform "toggled" bit, plus a set of behaviors that occur when something is "toggled". For example, you might have properties like: ToggleLight, ToggleCollision, or ToggleElectricity.
When writing the actual code to do anything interesting when something is toggled, you do of course need to do a check for each of those flags, but they map one-to-one with behavior, so you're still doing O(N) work for N features, which is what you want.
A slightly more complicated example is something in the game I linked GIFs of, which is the idea of a "trigger volume". A trigger volume looks like this:
1 2 3 4 5 6 7 8 9 10 11 | struct Trigger
{
TriggerKind kind;
Input input;
Shape shape;
ItemKind collect_item_kind;
Item *collect_item;
EntityHandle source_entity;
f32 seconds_to_allow_source_entity;
AttackFlags attack_flags;
};
|
Every entity, in that game, has one of these. Notice the TriggerKind part, which is used to distinguish between a number of "trigger features" (notice that, even though it's still a "discriminator" of a sort, we're still in one-to-one-mapping-with-codepaths land). So this could be a hitbox, a way to start crafting, a way to open a chest, or an item-collection.
The general pattern is that it's the same data, but it maps to a number of features. But because it maps to a number of features, it makes more sense to always have it available, which means you only really need the type-checker to know it's there. You don't need to start doing your own type-checking by checking a discriminator.
That leads pretty nicely into your next question:
mrmixer
I don't understand why "single interpretation" matters here ? Am I correct in understanding "single interpretation" as "I can always read the data from the "flat struct" even if that part of the struct isn't used by the entity (e.g. reading the health value even if the entity doesn't use health) " ? If that's the case than why is it important to creating a tree of entities like in your example ?
Yep, that's what I mean, and the reason you have entity trees is so that:
(1) You can combine entities to get the features you need. So for example, if one piece of data---while always being there---maps to only one feature, you can combine multiple entities to get a combination of those features.
(2) Entities become smaller, generally, and can piece together to form a larger structure.
(3) You can choose the granularity at which you want to consider things in the world. If you want to pick out the player's left hand for some feature (maybe per-body-part health... or maybe not! maybe just use the root entity's health), you can. If you don't need that, no need. The tree allows you freedom over exactly which structure you need.
mrmixer
Is the following code somewhat doing what you meant, but using unions ? (no entity kind, you don't have to check for behavior type if you know the entity uses the behavior, but you can add any behavior to an entity and it should work with "generic" entity functions).
I think this avoids the O(2^N) problem that entity "kinds" gets itself into, which is good. It still means you start needing a check any time you want to access or manipulate data, which is unfortunate, but I think it avoids the worst of the problems. Another issue I have with it is that it assumes there's a clean mapping between behavior and data, but as I discussed in the first part, sometimes data corresponds to multiple behaviors. And, similarly, sometimes behaviors don't require data at all. So I don't know that it's useful to couple those two things (this is one reason why I think "entity components" aren't really a useful model either).
Don't get me wrong, sometimes behaviors do map very clearly to a specific set of data, but sometimes they also don't.
I don't know that the generic "behavior" idea is winning you very much, though. It seems like it requires more minutiae than the simple alternative, which is just having bits on the entity that guard certain codepaths, right?
mrmixer
I would like if possible to see the code of the entity system of your small game, because I find it hard to get the real benefits from "imagined" system.
For sure! Here's some of the code: https://hatebin.com/oykukwtnoo
mrmixer
Is the array count correct there ? If so why ? If there are 100 items, you have (100 + 63) / 64 = 2. So we have 2 u64 but each property is a u32 (since those are not flags) so we could only store 4 properties ?
Yep, correct. The property enum values themselves are U32's, but here's what EntityHasProperty and SetEntityProperty look like:
1 2 3 4 5 6 7 8 9 10 11 12 | internal b32
EntityHasProperty(Entity *entity, EntityProperty property)
{
return !!(entity->properties[property / 64] & (1ull << (property % 64)));
}
internal Entity *
SetEntityProperty(Entity *entity, EntityProperty property)
{
entity->properties[property / 64] |= 1ull << (property % 64);
return entity;
}
|
I'm not sure I understand what data is combined in the trigger example. It looks like you've a "trigger" (TriggerKind kind, Input input, Shape shape) which I think is the combined part, and a "trigger response" (the rest of the struct) that is the "flat struct", contains all possible response for a trigger but only one is used at a time. But that would come from "compression oriented programming", not particularly from the flat struct vs union things (I think).
My question about "single interpretation" was not about "why create a tree", but "why is the flat struct single interpretation important" to create the tree ? You said
But we can create trees, chain entities... independently of how the data is laid out, so what are the benefits of flat structs compare to union in this context ?
Thanks for the game example. After looking into it, it seems to me (I haven't implemented it, so I don't know for sure) that the API using unions would be quite similar and the benefits would come mostly in the API implementation. I sort of see a few benefits, but I would have to try it for real to be sure.
Thanks for EntityHasProperty and SetEntityProperty, it makes sens and I'm sure it will be useful to me at some point.
My question about "single interpretation" was not about "why create a tree", but "why is the flat struct single interpretation important" to create the tree ? You said
Delix
The third: Having a single type, with only a single interpretation, matters a lot, particularly because you can start building data structures quite easily out of them.
But we can create trees, chain entities... independently of how the data is laid out, so what are the benefits of flat structs compare to union in this context ?
Thanks for the game example. After looking into it, it seems to me (I haven't implemented it, so I don't know for sure) that the API using unions would be quite similar and the benefits would come mostly in the API implementation. I sort of see a few benefits, but I would have to try it for real to be sure.
Thanks for EntityHasProperty and SetEntityProperty, it makes sens and I'm sure it will be useful to me at some point.
Thanks for the writeup, it did clarify things for me.
In Sir Happenlance, our entities have a union of structs which directly or indirectly inherit from a base SimObject struct (we don't use C++ dynamic dispatch, it's just for data layout). We did end up splitting up some logical objects into multiple entities, although in our case it wasn't to save space, it was to ensure that every entity corresponds to at most one physics body in the physics engine, because that significantly simplifies the physics networking code. And the netcode is some of the most complex and naturally-hard-to-debug code in the game, so it's important to simplify there.
In Sir Happenlance, our entities have a union of structs which directly or indirectly inherit from a base SimObject struct (we don't use C++ dynamic dispatch, it's just for data layout). We did end up splitting up some logical objects into multiple entities, although in our case it wasn't to save space, it was to ensure that every entity corresponds to at most one physics body in the physics engine, because that significantly simplifies the physics networking code. And the netcode is some of the most complex and naturally-hard-to-debug code in the game, so it's important to simplify there.
One thing that I still do not quite understand is the performance-related problem with a big flat struct array. For example, if I want to loop through an array to do some kind of pattern matching, it would have a lot of cache miss, right?
I'm not an expert on that, but I generally find it works better to make the system that is simple and works for you and only address performance issue when they arise. Depending on the game you're making, the performance issue might never happen. If the performance becomes an issue, you can extract the part that is the issue and keep the rest simple. It depends on the game.
Even unioned entity structs easily get larger than 64 bytes in my experience, which means you'd be loading a new cache line for every entity you visit anyway, regardless if the struct is flat or packed. That said, there may still be other performance penalties from using overall more memory for entities. But if you want to improve cache usage, it would likely be much better to adopt an SOA data layout, rather than packing things into a union.
In your recent Handmade Seattle talk about metadesk, you made a comparison between datadesk and metadesk (great talk btw). Datadesk is implemented by using a discriminated union system while metadesk is implemented by using a "flat struct". Here are some questions that I'd like to ask:
- What was your discovery process like? How did you go from using discriminated union to a flat struct (for programming general, not necessarily specific to metadesk)?
- Let's imagine that I want to add a weapon system to my game. There are two ways that I can do it: either I just add a new entity called weapon which is the player's child entity (using existing members in the struct like
position,sprite,animation, etc but also adding new members likeweaponDamageorweaponRange), or make a newstruct Weapon { ... }and add it into the flat struct. What should I use? What "measurements" should I take into account?
Replying to ryanfleury (#24632)