3
\$\begingroup\$

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?

\$\endgroup\$
  • 1
    \$\begingroup\$ Looking at the source, are you sure its O(N) to the number of entities? To me it seems its O(N) to the number of existing families to update some properties of the entity. The only expensive thing seems to be fetching an immutable array of all entities belonging to a family, which will be free if no changes were made, and otherwise cost O(N) to number of entities (regardless of how many changes were made) \$\endgroup\$ – Waterlimon Jun 19 '15 at 20:15
  • \$\begingroup\$ In the "Engine.java" method "updateFamilyMembership" [L.341] is a call to "familyEntities.removeValue(entity, true)";[L363] which goes through an Array (libGDX implementation) that holds the Familys Entities to find the one that needs to be deleted, because no Index is given to delete it efficiently. My guess is that this call takes very long to execute if a Family contains many Entities \$\endgroup\$ – VaTTeRGeR Jun 19 '15 at 20:26
  • 2
    \$\begingroup\$ You are correct. A better approach might be to rebuild the family entity list at end of frame instead of removing individual entities throughout the frame. Can you try buffering the component removals/additions, then at end of frame remove the family, execute the buffered changes, then recreate the family? \$\endgroup\$ – Waterlimon Jun 19 '15 at 20:42
  • \$\begingroup\$ That is what i thought about initially. I'm right now trying to subclass Array with added Entity to Index mapping, it may already provide the needed performance boost. If that doesn't work i'll try to implement what you suggested! Thanks for your help! \$\endgroup\$ – VaTTeRGeR Jun 19 '15 at 20:49
  • \$\begingroup\$ Thankfully, changing the Array to use an ObjectMap(Entity ID to Array-Index) for indexing allowed it to do ~35000 Component removes+adds+movement in 50ms, that should be more than fast enough! \$\endgroup\$ – VaTTeRGeR Jun 19 '15 at 21:30
4
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ Thanks a lot for your elaborate answer, I didn't knew about your project until now, but that's probably what I'm searching for :) I'll port my project to artemis-odb before it's too late... \$\endgroup\$ – VaTTeRGeR Jun 20 '15 at 12:57
1
\$\begingroup\$

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!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.