How do components in a component based entity system

Question

---Most of the stuff I am talking about I read here---

I am currently tring to wrap my head around component based systems to make a simple game engine of sorts.

I am having a hard time understanding how its supposed to work. I get that there are components which all inherit from the same base, which provides basic functions (init, update, end) and lets all of the different kind of components be stored in the same array of pointers. I get that. However I dont get how any efficient interactions of the components in a game object are supposed to happen.

Lets say I made a component that stores the amount of gold in a treasure chest (lets call it dataComponent). Lets also assume I made a component that does something when its update function is called (lets call it logicComponent)

There is also a class called Entity

class entity{
private:
    vector<component*> components;
public:
    void addComponent(component* comp);
    void removeComponent(component* comp);
    void getComponent(int id);
}

Lets now say I plan to make treasureChest, without any functions. Its just a background model. Then I will make a new enitity and using addComponent I will add the dataComponent(and give it 100 gold pieces in its constructor) and a logicComponent(and give it nothing in its constructor). The player might take out, or put in as much gold as he likes. We dont know how much gold there is in the chest. There might even be multiple dataComponents storing how many jewels or weapons are in the chest.

Example:

void main(){
    Entity chest;
    chest.addComponent(new dataComponent<int>("gold",100)); //100 gold pieces
    chest.addComponent(new dataComponent<int>("guns",2)); //2 weapons
    chest.addComponent(new logicComponent()); //this is going to do the printing
    updateEnt(Entity);//simply iterates through all components of the entity and calls thier update functions.
}
EXPECTED OUTPUT:
This chest contains 100 gold and 2 guns

The logic components job is to somehow get its hands on the data and print it to the screen.

My question is: How can the logic component get access to the other components in the same object as it is in and access the approperate ones (the ones it needs to function) without looking through the entire array every single time?

Answer 1

Components are just a collection of data and logic. How you store and relate them to the logical entity is where you gain or lose performance depending on the strategy you choose.

My example and explanation is in Java, but the theory can be applied to any language.

The way I usually handle custom Component engines is with HashMap registries of components. This ends up with a game engine that looks a lot like a relational database. Lookups and data manipulation are fast, and it can easily handle millions of entities at a time in memory. It has been a while since I've built one, so I don't remember any cons to the approach, but maybe someone does and can improve this answer.

Essentially it boils down to HashMaps and GUIDs. Each Entity is nothing more than a Globally Unique Identifier (GUID) which serves as the key in each HashMap. A HashMap exists for every ComponentType in your game. There are ways to make this more general purpose, but I'm going with the naive solution for simplicity of argument.

We first need to track existing Entities. I do this with a HashMap with a GUID as the Key, and a boolean as the Value which indicates whether or not the entity should be destroyed.

public class Entity
{
  HashMap<GUID,boolean> entities =new HashMap<GUID,boolean>();

  public Entity()
  {
  }

  public GUID create()
  {
      GUID entity= new GUID();
      entities.put(entity,false);
      return entity;
  }

  public HashMap<GUID,boolean> getAll()
  {
      return entities;
  }

  public void markPurge(GUID entity)
  {
      entities.put(entity, true);
  }

  public void purgeReady()
  {
      //removes all entities that have a value of true, 
      //only called once all other purges have been called
      for(GUID entity : entities)
      {
        if(entities.get(entity))
          entities.remove(entity);
      }
  }
}

Lets say the object needs health, lets start with creating a Health component. During the initialization of your game, you'd create a HashMap to register Entities that have the HealthComponent.

public class Health
{
  private HashMap<GUID,int> healths=new HashMap<GUID,int>();

  public Health(){}

  public void set(GUID entity, int health)
  {
      healths.put(entity, health);
  }

  public int get(GUID entity)
  {
      return healths.get(entity);
  }

  public void remove(GUID entity)
  {
      healths.remove(entity);
  }

  public void add(GUID entity)
  {
      healths.put(entity, 100);
  }

  public void add(GUID entity, int health)
  {
      healths.put(entity, health);
  }

  public void purge(ArrayList<GUID> entities)
  {
    for(GUID entity : entities)
       healths.remove(entity);
  }
}

To spawn a new Entity with 100 health in our game, we first generate a new Entity GUID, then assign it a Health component.

public void setup()
{
  //spawn an entity, and add a Health component in one step
  Health.add(Entity.Create());
}

To actually use the components and assign game logic to them, I use Systems. Each System performs a piece of game logic, like destroying an entity if its health reaches zero.

public class DeathSystem
{
  Entity entities;
  Health healths;
  public DeathSystem(Entity e, Health h)
  {
     entities=e;
     healths=h;
  }

  public void update()
  {
     for(GUID entity : health.keySet())
     {
       if(healths.get(entity)==0)
           entities.markPurge(entity);
     }
  }
}

Now we simply call our systems in our main game loop, after handling user input. Altogether yielding the following

Entity entities;
Health healthComps;
DeathSystem deathSystem;
GUID player;
boolean run = true;

public void main(String args)
{
    setup();
    while(run)
    {
      update();
    }
}

public void setup()
{
    entities= new Entity();
    healthComps = new Health();
    deathSystem = new DeathSystem(entities, healthComps);
    player=entities.create();
    healthComps.add(player);
}

public void update()
{
    handleInput();
    //attackSystem.update();
    //healSystem.update();
    deathSystem.update();
    //finally, call the function that calls purge on all the component registries to remove any destroyed objects
    purgeAll();
    if(entities.getAll().size()==0)
       run=false;
}

The beauty of this kind of structure is that all of your entity lookups are O(1) operations, and each System only operates on Entities currently registered as having the relevant components. Because of this, the systems only do what is absolutely necessary. If none of your entities have health, the death system has nothing to iterate over, and returns in constant time. This also keeps the memory footprint at an absolute minimum.

There are other approaches as well, but this is the one that I've had the most success with, and I think this illustrates that a component isn't so much an object, as a fuzzy collection of data and logic.

Answer 2

Your component entity system doesn't match that which was shown in the article. The article doesn't attach logic components to entities, it uses system objects which look for data components.

Additionally IDs are typically enumerations or bit keys instead of strings. You'd have a system component that would do something like:

function update(entities):
    for each entity in entities:
        for each component reference in entity:
            ... do computation with component

Binary Search

With your method, yes the only way to find components is to linearly search through the array. If however you can sort your components by key, then this is less of an issue as long as you aren't constantly adding and removing components. With sorted lists you can perform binary search which has a runtime cost of log2(n) which if you have 128 components on an object means you need to go through only 7 comparisons per object at max. When you want to keep stuff sorted, you can use binary search to insert in the proper place as well.

Lock and Key

There is however another way. Some entity component systems invoke a lock and key mechanism. What this affords us is a method to see if our entity even has a given component in the first place before searching in constant time via bit manipulation. Each component is given a single bit value (1, 2, 4, 8 ... 2^n) which you then or with your entities current "lock" and you get a bitfield of entity keys. When a system wants to use your entity to use its components it simply has to compare its set of components it needs (a key) and your entities lock via the and operator and comparing that value against the systems key. If your system has that key, you know you won't be wasting time by searching it to find your component

This system has some draw backs in that you can't have more components types of components than the size of your lock, and you might run into issues with adding multiple of the same component to a given entity (though 99% of the time it doesn't make sense to add two health bars, and your system wont be able to distinguish non unique components anyway)

Array index equals Component ID

Another way besides that, if you don't have too many entities you could alternatively get constant time look ups with arrays of components that are simply the size of the number of components you could ever possibly have. You would get instant look up of components (where the index in the array would correspond to their ID) and you could lower the amount of memory used if you pushed common component ids towards the top (meaning that most of the time you could avoid allocating memory to the next N elements, with only checking the size of your array first to make sure you don't walk off the end when checking).

Hash table for Components for each entity

An additional way to fix this is to use a hash table per entity which hashes component IDs to components (resulting in O(1) access amortized). With small sizes of N it may end up taking more space and being slower than per index ID array solutions or using binary search.

System Observable Components.

A final method I've seen is that each system, each time a new entity is added (registered), adds pointers to the components to a personal list such that it doesn't even need to look up anything on the entity at all when calling the update function. All the system needs to do is iterate and apply its algorithm on each set of components in its internal list. When entities are destroyed we unregister them from each observer by searching through the list of components and removing them. If components are constantly removed and added, it may be beneficial to implement the binary search strategy I talked about earlier here with the component list, but if they are instead only removed sparingly, but added often it would be better to just do linear searches.

I've implemented a system that uses lock and key, binary search and the system observable method myself, though it won't necessarily be the best method for every situation.