3
\$\begingroup\$

---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?

\$\endgroup\$
  • 1
    \$\begingroup\$ You're probably overestimating how much one of those look thoughs costs in terms of clock cycles. \$\endgroup\$ – Bálint Dec 12 '17 at 14:55
  • \$\begingroup\$ @snb am I even doing component based entities right? I am having a feeling that I am missing something, since this performance problem is not a thing anywhere else. What I could do would be to use shared pointers instead of normal ones and simply have the logic functions look for all components of interest and simply set its own shared pointers to those components. But then I gotta account for changes in the component structure and that is gonna be an even worse mess. There is obviously something I am doing wrong here \$\endgroup\$ – MoustacheSpy Dec 12 '17 at 15:24
  • 1
    \$\begingroup\$ @snb Before judging that, one should profile. In an actual situation. Yes, runtime complexity is a thing, but that code could be a drop in the ocean when taking a look at the big picture. \$\endgroup\$ – Alexandre Vaillancourt Dec 12 '17 at 15:43
  • 1
    \$\begingroup\$ @snb First of all, if you want to get the most out of the computer, then you don't use an ECS to begin with, since it adds an overhead; secondly, it doesn't really matter in a real world scenario, since you usually don't have thousands of components \$\endgroup\$ – Bálint Dec 12 '17 at 16:04
  • \$\begingroup\$ To me the problem here is logicComponent. You don't necessarily want a component to reach around and look at its entity and then figure out what components it has attached and grab data. That's a system's responsibility to have functionality, and systems don't process things in this scalar one-entity-at-a-time mindset. It is at least better to err on the side of components just being raw data, not logic. Your logicComponent probably wants to be a system of some sort. \$\endgroup\$ – user77245 Dec 12 '17 at 19:27
5
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Don't you have to check if something is purged first before you do anything? \$\endgroup\$ – opa Dec 12 '17 at 20:59
  • \$\begingroup\$ You can, but you don't necessarily have to if you order your various systems in the update loop. if you group all your "potentially purging entities" functions toward the top of the loop, then purge, then do the others that don't change purge state of anything, you could potentially save cycles on the systems that never purge anything. You cant always do this though. Moving an player to a pickup should purge the pickup entity. depending on the order, the pickup may sit there for a frame too long. In all though, it's an optimization you have to evaluate on a case by case basis. \$\endgroup\$ – Stephan Dec 12 '17 at 21:04
  • \$\begingroup\$ One approach I saw with this had each system check for the existence of the GUID before processing its behavior. It would purge any entries that didn't have a matching GUID in the entities collection. This made purging less explicit, as you just delete the GUID, and let the systems clean it up for you on their next pass. \$\endgroup\$ – Stephan Dec 12 '17 at 21:09
  • 1
    \$\begingroup\$ So systems would instead just check before hand, for each component, if the GUID for the component matches a real entity, and if not, deletes that component from the components list? \$\endgroup\$ – opa Dec 12 '17 at 21:20
  • \$\begingroup\$ Yes, exactly so. \$\endgroup\$ – Stephan Dec 12 '17 at 21:36
3
\$\begingroup\$

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.

\$\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.