Efficient removal and adding of Components in ECS

Question

i'm working with the Ashley Entity-Component-System (related to libGDX) to program a server-side simulation for an online game and i stumbled upon a serious performance drawback, that is probably caused by how it manages Entity-Sets:

"Family", these are basically descriptors for Entities with a specific set of components. Removing a component is an costly operation because the Family-instance needs to search through an Array of entities that it manages and remove the Entity from that Array. This is O(n) for every single removal at worst.

And here's my problem: I have a Family that describes all Entities that do have a position and a velocity component. If i want to remove the velocity-component, for example, to turn it into an static entity and re-add it later to make it move again, this completely eats up my budget of frame time (50ms->20fps) with only ~7000 Entities changing Family back and forth within a frame. At the same time, moving 100000 entities takes only about 15ms at max (without multithreading ~30ms).

I have thought of these options yet:

-Change the data-structure that the Entities are sorted into, this creates new problems, but may still be the most viable Solution, i thought of mapping the Entity IDs to Objects or keeping them in a sorted data-structure.

-Sort everything once after a System has finished execution, requires redesigning a lot of code but probably reduces the time-consumption greatly

-Changing the Entity System, i know of Artemis, but it would be great if you could point me at something else for Java if you know a library that does it better.

-This whole thing may not even become a bottleneck when running the final game-simulation, it might or might not, so just going on and thinking about this later may be acceptable, since I'm probably over-engineering again.

What do you think is the way to go?

Answer 1

Disclaimer: artemis-odb dev here.

-Changing the Entity System, i know of Artemis, but it would be great if you could point me at something else for Java if you know a library that does it better.

I'm not sure whether you're referring to vanilla artemis or artemis-odb, but the latter improves on performance considerably with regards to mutating entities. You can find some benchmarks over at junkdog/entity-system-benchmarks

-Change the data-structure that the Entities are sorted into, this creates new problems, but may still be the most viable Solution, i thought of mapping the Entity IDs to Objects or keeping them in a sorted data-structure.

-Sort everything once after a System has finished execution, requires redesigning a lot of code but probably reduces the time-consumption greatly

This approach can potentially reduce overhead by quite a bit. BitSets are basically your friend here - or should be. Unfortunately, Ashley doesn't recycle ids, making a lot of indexed look-ups difficult/impossible. If you don't mind modifying ashley a bit:

• Entity ids should be recycled: enables representing a lot of internals with bitsets
• An Entity System's primary entity data source is a bitset representing the active entities' ids. Upon inserting/removing entities, the bitset[entity.id] is toggled, and the system sets a dirty flag.
• For each system; prior to processing, check if system is dirty. If so, populate the system's array-of-entities from the bits in the bitset. A side effect of this is approach is that entities are always processed in ascending id order (generally, this improves performance somewhat, at least on the JVM).

A poor man's bitset would be a LongMap - this would probably be the least invasive approach, but wouldn't give the same level of performance boost.

Answer 2

So, i figured out how to do it quick and dirty, i subclassed Array (libGDX.util) to allow for faster removal of Entities and then i swapped it with the normal Array inside the Engine class of Ashley:

package de.vatterger.threadedSim.tools;

import com.badlogic.ashley.core.Entity;
import com.badlogic.gdx.utils.Array;
import com.badlogic.gdx.utils.ObjectMap;

public class EntityArray extends Array<Entity> {
    private ObjectMap<Long, Integer> map = new ObjectMap<Long, Integer>();

    public EntityArray() {
        super(false, 16);
    }

    @Override
    public void add(Entity value) {
        map.put(value.getId(), size);
        super.add(value);
    }

    @Override
    public boolean removeValue(Entity value, boolean identity) {
        Integer i = map.remove(value.getId());
        if(i!=null && identity)
            return removeIndex(i) != null;
        else
            return super.removeValue(value, identity);
    }

    @Override
    public Entity removeIndex (int index) {
        if (index >= size) throw new IndexOutOfBoundsException("index can't be >= size: " + index + " >= " + size);
        Object[] items = this.items;
        Entity value = (Entity)items[index];
        size--;
        if (ordered) {
            System.arraycopy(items, index + 1, items, index, size - index);
        } else {
            items[index] = items[size];
            map.put(((Entity)items[index]).getId(), index);
        }
        items[size] = null;
        return value;
    }
    @Override
    public void clear() {
        map.clear();
        super.clear();
    }
}

This doesn't support all features of its superclass Array, only enough to be used with Ashleys Family-Assignment-Code, so it's probably very buggy without further editing it!