How to implement n-body in an Entity Component System

Question

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 1

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.

Answer 2

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.

Depending on how detailed you want it, everything is relevant, at least in physics. Basicly, everything attracts everything.

So, if you have a physics game with 3 to maybe 8 Objects, thats not a big deal.

But if you got a space simulation, you dont need to calculate the gravitational effect of a screwdriver to the pilot or the mascot dog.

In that case, you only need to calculate the gravitational force of objects with a certain gravitational impact. Planets excert a massiv amount of gravity, the sun does that aswell and most moons are also relevant. After that its debateble. On top of that, just asume Planets are on rails and are basicly indisruptable by your capabilites, else you got a new Universe Sandbox.

And even then it is easier to just calculate the influence of the object with the highest gravitational impact nearby. You dont need to know how much Pluto tuggs on you, when you are 500 km away from the sun. This is called the sphere of influence and is used in Kerbal Space Program to not calculate every effect, just for one body.

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.

Again, if you only have a few objects, thats not a big deal. If you have only 8 objects, you could store the position of an object and additionally the position for each other object. Calculating the distance isn't that fast, but really not a problem. To iterate other them, you will need to take the hard way. E.G. for four Entities.

1.
A <-- pair A with every other Entitiy and apply each other forces to both, 
B     like (A,B), (A,C), (A,D).
C
D

2.
A
-
B <-- Repeat the same with B, but ignore A, so (B,C), (B,D)
C
D

3.
A
B
-
C <-- Repeat with (C,D)
D

4. Only D is left and doesnt need to apply forces.

If you can simplify your calculations, like with a sphear of Influence or only certain bodys apply gravity, its much simpler and you only need one direction (Only A --> B, not B --> A aswell). Only exception then would be something like a gravity mine, that creates its own gravity, but can be influcenced by gravity.

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.

If you can make and ECS work for certain effects, just dont. Its not helpful to break ECS just to strangly develop a system that works, but is hard to manage and error prone.

If you only got a hammer, every problem looks like a nail.