Let's say a game use a component-based hierarchy to store all of its entities. So it can have objects, characters, lights organized in some kind of tree.

When rendering the game, it needs to first render objects, then lights. So it needs to first traverse the hierarchy and render all the objects it finds, then traverse a second time to render all the lights it finds. What is a better way to do this? If the hierarchy has thousands of entities, it could be slow to traverse twice the tree.

I thought about having two lists, one containing objects to render, the second one being lights. Each time the user adds an entity to the hierarchy, it adds it to the corresponding list. This way, the game only have to traverse the object list then the light list, without traversing useless entities.

What is the best option?


You shouldn't have a hierarchy. One reason component-based approaches are popular right now is because it's easy use them to separate the association of a component with an entity (the "hierarchy") with the actual concrete storage of the components such that the storage can be contiguous and cache-friendly for processing.

Ideally, you'd have a renderable component and a processor/system that holds all those components. Because that system knows that the rendering must be done in two phases, it can keep the components in two otherwise-contiguous arrays. Then it can simply blast through the first array, and then the second array, issuing the appropriate calls to the real, underlying renderer to first draw the objects and then lights, or whatever else you need.

In an entity system, what hierarchy exists is usually only one level deep: entities have components, but components don't have other components. In any case, you don't want to be traversing components for processing by looking at each entity and then looking at each of its children (components) in that hierarchy. As you said, it's not very efficient.

Divorce the conceptual association of your entities and their child component references from the physical storage of their components and you solve the problem.

  • \$\begingroup\$ Sorry if I wasn't clear, but I was referring to entity hierachy, not component hierarchy. For instance, a character can be defined by these entities in a hierarchy: - A head, which has as a children a torso, which has as brother arms, which has a hand as a children, etc. Each of them have a contiguous array of components (Transform, rendering data etc.) \$\endgroup\$ Jun 14 '16 at 17:43
  • \$\begingroup\$ Yeah, I thought that's what you were referring to; I'm saying that feels pretty wrong. What you're talking about sounds more like a localized scene graph, something that might be the domain of a specific system of components (rendering or "aspect") but not all entities across the board. And it sounds like it still leads you into the problem of not having all renderable components in an array, instead you have all components for an entity in an array, which leads you to the design issue you're presenting. I'm suggesting you keep all components in an array by system, not by entity. \$\endgroup\$
    – user1430
    Jun 14 '16 at 17:47
  • \$\begingroup\$ I'm not sure I understand. My components are things like transform information, texture, light color etc. How can I store them all in a contiguous array? I still need them linked to an entity. Do you suggest that instead of entities in a localized scene graph having components, I should have entities in a graph and somewhere else an array of components linked to a entity? That way, when rendering entities I iterate over the components array and not by entities? \$\endgroup\$ Jun 14 '16 at 18:03
  • \$\begingroup\$ @AdrienNeveu Do you mind joining the Game Development Chat so we can clarify what we're discussing? \$\endgroup\$
    – user1430
    Jun 14 '16 at 18:35

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.