Evaluating the Entity Component System model for DDA

[kevin.granade]

Brought up here was using an ECS in DDA. The resulting discussion was off-topic for github, so I’m moving it here as I’m interested in evaluating it, as a mental exercise if nothing else.

Sources:
basic intro to ECS
A specific C implementation
A series of blog posts about ERC
A (IMO better) outline of the rationale for ECS
Wikipedia page

Combined list of benefits of ECS:
No programmer required for designers to modify game logic
Circumvents the “impossible” problem of hard-coding all entity relationships at start of project
Allows for easy implementation of game-design ideas that cross-cut traditional OOP objects
Much faster compile/test/debug cycles
Much more agile way to develop code
Data-driven composition of objects
Safe managing of dependencies

I’m planning on following up with an outline of how ECS could be used in DDA. Feel free to pitch in.

[Coolthulhu]

One problem I see here is that our objects are generally incompatible.

Consider the interface of position:

• Creatures are entities on a list
• Terrain and furniture are IDs on a grid
• Vehicles are multi-tile objects vaguely centered around some point
• Projectiles exist for less than a turn and thus don’t need tracking

I can’t really think of a good way to globally employ this paradigm. There are many specific use cases where extracting a common interface would work, but then there are more where the interfaces wouldn’t be common.

Good examples I see:

• Crafting requirements for crafting, constructions and vehicle parts
• Stat/roll changes interface for bionics, mutations, martial arts and effects (this one would be a lot of work, but also greatly improve interoperability)
• Shooter structure for characters, vehicles and monsters

[kevin.granade]

Keep in mind, if we did go this way it would be MASSIVELY invasive to the existing system, and not something I’d want to tackle any time soon even if it did look like a good idea. This would be tantamount to a total redesign and reimplementation of all affected code, though it could proceed incrementally.

Consider the interface of position:

• Creatures are entities on a list
• Terrain and furniture are IDs on a grid
• Vehicles are multi-tile objects vaguely centered around some point
• Projectiles exist for less than a turn and thus don’t need tracking

This is a great example, just briefly it might look like this:
Creatures, terrain, furniture, and vehicle segments would all have coordinate components, which means they would have entries in a coordinate tracking container that has a reference to the entity.

To retrieve the entities at some coordinate, you’d retrieve components from the grid, which would probably be a 3d array of lists of entity ids, now you have a list of entity id’s to operate on. You’d then iterate over that list, retrieving some other component of each entity to evaluate, for example if you’re evaluating a projectile moving through the square, you’d retrieve the “ballistics” component of each entity to evaluate whether the projectile hit that entity, if one results in a hit, you’d retrieve other components if that entity to apply the effects of the projectile impact, up to and including destroying the entity.
Likewise when drawing, the renderer would retrieve IDs at some coordinates, then use that to retrieve “sprite” components, which would contain both glyphs or sprites to render as well as metadata like render order.
In both cases, the code didn’t care whether the data it was handling was from a furniture, item, creature, or vehicle entity, just that it had the components it cared about.

Good examples I see:

• Crafting requirements for crafting, constructions and vehicle parts
• Stat/roll changes interface for bionics, mutations, martial arts and effects (this one would be a lot of work, but also greatly improve interoperability)
• Shooter structure for characters, vehicles and monsters

These examples make me think you’re thinking of composition, faceting, and related OOP concepts. ECS is not OOP. It took me a while (days of reading) to figure out what this meant. It does have some of the features of building objects out of components, but it goes much further than that.

Surprising aspects of ECS:
There is no entity object.
Components do not own code.
Systems are not OOP either, they’re just code.
Components mostly live in arrays or lists, and actually live there, not references to them.

[kevin.granade]

Side issue, I was thinking about a data structure for insuring cache locality between components, what I came up with is a system for issuing ids that act as ids, and if used as array indices for components induces very good cache locality.

This is effectively a memory manager with weird constraints.

external methods:

/* Anywhere that says int would need to be scaled based on the number of component types and/or the number of entities supported. */

/* reserve finds an availaible identifier in a block of entities with the same components
 * component_mask enumerates the components the new entity will use as a bitmask.
 */
int reserve( int component_mask );
/* Marks an id as released,
 *might return an identifier that will take the place of the released entity for compaction purposes.
 */
int release( int );

Internals:
const int bucket_size;
int next_bucket;

class flavor {
    std::list<int> reserved_buckets;
    int size;
    int last() {
        /* Finds the last slot available in the last bucket, assumes all buckets are filled. */
        return ( reserved_buckets.back() * bucket_size ) + ( size % bucket_size );
    }
    int next() {
        /* If the current bucket is full (or there's no bucket), allocate a bucket. */
        if( !( size % bucket_size ) ) {
            reserved_buckets.push_back( next_bucket++ );
        }
        return last();
    }
};

std::map<int,flavor> buckets;

int reserve( int component_mask ) {
    auto flavorref = buckets.find( component_mask );
    /* emplace new flavor in buckets list if necessary. */
    return flavorref->next();
}

/* release() swaps the id being released with the last id of it's type and shrinks the sise of that type by 1. */

The id used by this allocator is used as an index into each array-like component container. I say array-like because they need to be sparse arrays, many (all, actually) of them will be missing large chunks of indices. I believe such a sparse array has a number of implementations so I’m not worrying about it. The effect of doing this is to create many large contiguous spans of components, and when systems iterate over those components, they will be adjacent to each other.

This has some problems, the biggest of which is when releasing entities and swapping with another entity of the same type, every component that makes up that entity has to be relocated in its array, the alternative is to allow the buckets to sustain fragmentation, which complicates things and harms performance. Also if an entity has a component added or removed, it must be deleted and recreated, if this happens a lot it’ll get quite expensive.

[kevin.granade]

First off I’ll just enumerate some existing systems and the components (and data) they need, and output.
Drawing: coordinates, Sprite, doesn’t write game state
AI(might have multiple flavors): goal, coordinates, scent, vision, sounds, outputs a goal
movement: goal, action pool, updates action pool, coordinates, other entities
trap effects: coordinates, ballistics or melee target, target entity updated
Cruise control? vehicle physics, vehicle throttle, writes to vehicle throttle
Engine tick: engine stats, vehicle throttle, fuel tanks, writes to vehicle physics and fuel tanks
vehicle movement: vehicle physics, vehicle coordinates, writes to vehicle coordinates, triggers collisions (that have to happen synchronously unfortunately)

Note on application of damage, it might be better to spawn damage-causing effects as a side effect of other actions, and apply them in a later phase instead of applying it immediately, in which case:
damage application: damage details, resistances, writes to health object

Systems it probably doesn’t make sense to turn into ECS:
Scent diffusion
FoV calculation

[keyspace]

I was thinking about a data structure for insuring cache locality between components

Do I understand correctly that in the proposed scheme, changing an existing entity’s component_mask would effectively require changing its ID? And therefore require copy-moving it to a different bucket?

This might not be as bad as it sounds - chances are, entities would rarely do that. A lot of examples I can think of can be shoehorned from being a component with a related processor (system) into being a data-field in an component.

For example, there could be a separate Thrust component (for vehicles) that’s used as a key for lookups by a dedicated VehiclePropulsion processor. Or it could be a field in a Vehicle component, and get if-clause treatment from the same VehiclePropulsion sub-processor (the “sub-” coming from it now being de-facto coupled to other processors accessing Vehicle).

The above seems like a tradeoff decision between performance penalties - either due to copy-moving or having branching.

JIC, this is about the particular data structure for caching, not which components should be there in the first place.

[kevin.granade]

Do I understand correctly that in the proposed scheme, changing an existing entity’s component_mask would effectively require changing its ID? And therefore require copy-moving it to a different bucket?

Yes, adding or removing a component from an entity would require allocating a new id and copying all components to a new location.

This might not be as bad as it sounds - chances are, entities would rarely do that. A lot of examples I can think of can be shoehorned from being a component with a related processor (system) into being a data-field in an component.

For example, there could be a separate Thrust component (for vehicles) that’s used as a key for lookups by a dedicated VehiclePropulsion processor. Or it could be a field in a Vehicle component, and get if-clause treatment from the same VehiclePropulsion sub-processor (the “sub-” coming from it now being de-facto coupled to other processors accessing Vehicle).

The above seems like a tradeoff decision between performance penalties - either due to copy-moving or having branching.

I’m not sure you want to do that, if it starts making you violate ECS principles it’s just not a good allocation scheme.

JIC, this is about the particular data structure for caching, not which components should be there in the first place.

You can’t really treat those as different things, the data model and caching behavior is the component model and data engine. You CAN have fat components, but the extent to which you do that limits the benefits of using ECS in the first place, for example if you don’t factor out “thrust” or at least “engine”, you’re going to have to fall back to inheritance or something when you want different types of engines.

tl;dr, yes it’s THE major problem with this allocation model, it might make it totally unusable, or it might be fine, hard to tell until you have a running system.