Jump to content
  • Advertisement
mujina

Generic component traversing with components that should be part of inheritance tree. Alternatives?

Recommended Posts

What could be a way of avoiding using inheritance and virtual methods when designing components for an entity-component-system?

I'll be more specific about my design issue:

I currently have different classes for different kinds of colliders (let's say, CircleCollider and LineCollider).

My system that checks for collisions and updates the positions and/or velocities of my entities should be something like:

for entity_i in alive_entities {
  collider_i = get_collider_of_entity(entity_i) // components of same kind are stored contiguously in separate arrays
  transform_i = get_transform_of_entity(entity_i)
  for entity_j in alive_entities {
    collider_j = get_collider_of_entity(entity_j)
    transform_j = get_transform_of_entity(entity_j)
    if check_collision(collider_i, collider_j) {
      update(transform_i)
      update(transform_j)
    }
  }
}

my problem is that I don't have a generic `get_collider_of_entity` function, but rather a function `get_circle_collider_of_entity` and a separate one `get_line_collider_of_entity`, and so on. (This happens because under the hood I am keeping a mapping (entity_id -> [transform_id, sprite_id, circle_collider_id, line_collider_id, ...]) that tells me whether an entity is using certain kinds of components and which are the indices of those components in the arrays containing the actual components instances. As you can see, each component class is corresponding to a unique index, namely the index position of the array of the mapping described above. For example, transforms are 0, sprites are 1, circle colliders are 2, line colliders are 3, and so on.)

I am in need to write a system as the one in the snippet above. I can write several overloaded `check_collision` functions that implement the logic for collision detection between different kinds of geometric primitives, but my problem is that I am not sure how to obtain a generic `get_collider_of_entity` function. I would need something that would get me the collider of an entity, regardless of whether the entity has a circle collider, a line collider, a square collider, etc.

One solution could be to write a function that checks whether in my internal entity_id -> [components_ids] mapping a certain entity has a collider at any of the indices that correspond to colliders. For example, say that the indices related to the collider classes are indices 10 to 20, then my function would do

get_collider_of_entity (entity_id) {
  for comp_type_id in 10..20{
    if mapping[entity_id][comp_type_id] not null {
      return components_arrays[comp_type_id][entity_id]  
    }
  }
  return null
}

This could turn out to be pretty slow, since I have to do a small search for every collider of every entity. Also, it may not be straightforward to handle returned types here. (I'm working with C++, and the first solution - that is not involving inheritance in any way - would be returning a std::variant<CircleCollider, LineCollider, ... all kinds of components>, since I would need to return something that could be of different types).

Another solution could be having some inheritance among components, e.g. all specific component classes inherit from a base Collider, and overrride some virtual `collide_with(const Collider& other)` method. Then I would redesign my mapping to probably reserve just one index for colliders, and then I would actual colliders in a polymorphic array of pointers to colliders, instead of having a separate array for CircleColliders, another for LineColliders, and so on. But this would destroy any attempt to be cache-friendly in my design, wouldn't it? That's why I am looking for alternatives.

A third alternative would be to just have a single, only, Collider class. That would internally store the "actual type" ( aka what kind of collider it is ) with dynamic information (like an enum ColliderType). Then I would have all colliders have all members needed by any kind of colliders, and specific collision detection functions which I can dispatch dynamically that only use some of that data. (Practical example: a "Collider" would have a radius, and the coordinate for 2 points, and in case its type was "circle" it would only make use of the radius and of one of the 2 points - used as the center -, while if it was a "segment" it would only make use of the 2 points). My gut feeling is that this would bloat all colliders, and, even if the bloat could be reduced - using unions in some smart way for storing members? I wouldn't know how -, then still the design would be pretty brittle.

I'm clueless and open for ideas and advice! How do you handle in general situations in which you have components that can be naturally modeled as subclasses of a more generic component class? Inheritance? Smart hacks with variants, templates, macros, custom indexing? Dynamic "internal" type?

Share this post


Link to post
Share on other sites
Advertisement

I think, your problem is you are mixing up the ECS-philosophy with the OOP-philosophy.

In ECS a Component should ideally only have data; the System does the operations on that data each frame.

You could then inside the collision-system write 2 loops for any combination of collision-volume-component-types, where inside you know which 2 types you got, avoiding the inner loop type-check and just calling a specialized function to calculate if there is a collision.

Share this post


Link to post
Share on other sites
On 10/10/2019 at 1:19 PM, mujina said:

But this would destroy any attempt to be cache-friendly in my design, wouldn't it? That's why I am looking for alternatives.

Is this part of your system going to be cache constrained?  Somehow I doubt it.

It looks like you're working on a physics system that relies on ECS. 

What you've got there is an all-to-all test that presents the worst case of collision detection. 

How is your system open to extension? You've got several types of colliders, you've mentioned a circle collider and a line collider.  There are many other natural collision objects, since those are 2D probably rectangle, triangle, general polygon, and sprite/shape based collision objects will show up as well. 

In the first code block at least you're working generically, an entity could use any arbitrary collider object. You could implement that as objects derived from a common base, or as an index to the type of collision objects in your system, that doesn't particularly matter.  You should probably verify that it actually has a collision object, and if not, automatically fail the collsion test (if it has no collider it cannot collide).  You'er also testing each comparison twice, once is an A-to-B test, then again as a B-to-A test.

Regardless of the collision objects, you're working with an all-to-all test.  That's only going to work for a relatively low number of items. Physics systems usually use a broad phase (as a very fast general-purpose filter) and then a narrow phase (testing the actual items).  I'd start out with a proximity based process that only tests things that are immediate neighbors. For most games, most items have 0 collision neighbors so they don't get tested at all. A few items have the potential to collide. That test is often run with the spatial grid, never touching the details of the objects.

My guess is that you're over-thinking it. Modern machines have about a billion instructions available every frame. First write something then works. Then make it work well.  Then, only if necessary, make it faster. 

Assuming you only have a few hundred objects you could probably have a naive solution that runs the all-to-all test you've written, although you should clean it up to not test against itself and not duplicate A-to-B and B-to-A. Adding a broad phase test to only test items that are neighbors could likely handle many thousand collision tests per update without any further optimization.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!