game design - How to implement n-body in an Entity Component System

Recently I've been throwing problems at Entity Component Systems to see how far I can push the paradigm. One problem in particular I struggle with, which is writing an elegant implementation of the n-body algorithm.

First, let me clarify the terminology of ECS:

• Component: a structure that holds data


• Entity: a unique identifier used to associate and retrieve component data


• System: logic executed on entities that have a specific set of components

In ECS, for every frame, each system linearly walks over the matching entities. A typical ECS implementation lays out data consecutively in memory per component, which has as advantage that it is very CPU-cache friendly.

To implement n-body, we could have three components (Location, Mass, Speed). We could then have a system called Gravity, which will update the speed of all entities that have Location, Mass and Speed. Then there could be a Move system that walks over entities with Location and Speed, and updates the locations.

For every matching entity, Gravity will have to walk over all the entities (minus one) to compute the attraction force. The first problem is, how do I efficiently get the relevant entities? A query seems wasteful since the entity set it needs is the set that Gravity is already walking over.

The second problem is when entity A computed the attraction force from entity B I'd like to reuse the computed distance when calculating the attraction force from A on B. Ideally these two computations take place in the same iteration. That, however, impacts how I iterate over the entities. If I computed A <-> B when I processed A, I don't need to iterate over A anymore when processing B.

I am not actually interested in the most practical way to implement n-body, but am curious if/how this kind of problem can be elegantly implemented with ECS.

Answer

One nice thing about systems in an ECS architecture is that they don't all necessarily need to follow the same structure of for(int i = 0; i < entities.length; i++) process(entities[i]); and then implement process(entity) as if there would be no other entities in the universe. If there is a smarter way to process entities than sequentially in natural order, you can do that.

Your gravity system can use two nested for-loops instead:

for(int a = 0; a < entities.length; a++) {
    for(int b = 0; b < a; b++) {

        calculateAttractionBetween(entities[a], entities[b]);
    }
}

This loop iterates the entities and then calcualtes the attraction between the current entity and every entity which came before. That way you never handle a combination of the same two entities. So the function calculateAttractionBetween only needs to calculate the distance between the two entities once, and then use that distance to calculate both the effect of a on b as well as the effect of b on a.

This algorithm still has a computational complexity of O(n²) and becomes cache-unfriendly as soon as your entity-array doesn't fit into the CPU cache. But if you want an accurate n-body simulation where everything is affected by gravity, then you won't get around this. The n-body problem simply is computationally expensive. There are a few optimizations you can do if you are willing to sacrifice accuracy. Like if you have some objects where the differences in mass are so large that the effect of one on the other can be ignored or when you can create localized sub-simulations which treat other sub-simulations far away as if they were a single gravity source. But all these optimizations sacrifice accuracy, so we are no longer talking about an n-body simulation like asked in the question.