5
\$\begingroup\$

How can we combine inheritance-based polymorphism with spatial cache friendly data structures? In a simple game engine we usually have some base Entity class which is inherited from to implement the various distinct game entities. These entities are then stored by pointer in a large array of some kind, which is iterated over for updating, rendering and so on.

However this leads to bad performance because entities will be randomly scattered throughout memory. One way I thought of to fix this problem is to have a separate array for each entity type, for example:

Goblin goblins[100];
Human humans[100];
Demon demons[100]; 
Entity* entities[300]; 

My question is: Is there a more elegant solution than that? The separate arrays approach requires rewriting the core functions of the engine itself every time I want to add or remove an entity type in the game implementation. I'm looking for a general solution which doesn't care about what the subclassed entity types are as long as they inherit from a common ancestor.

\$\endgroup\$
2
\$\begingroup\$

I wouldn't do that, as you'd complicate things unnecessarily. Keep a single generic list of entities and compact toward the beginning of the array every so often. That way you will get far fewer cache misses (unlikely you'll eliminate them altogether unless you make your dataset sufficiently small). It's also bad form to type various species as you have there; you should just be using Entity, composed of components describing differences between the species. Favour composition over inheritance.

Compaction means updating entity indices everywhere in memory; otherwise you face broken links.

Look into cache-oblivious algorithms to understand how to achieve best cache performance, but note that not every problem is suited to eliminating cache misses entirely. Key is to minimise them.

P.S. If you haven't wrapped your head around implementing Entity-Component Systems yet, you'd do well not to worry about optimising cache any time too soon. Work on the basics first - long road.

\$\endgroup\$
  • \$\begingroup\$ You're right, I haven't wrapped my head around ECS yet, but not for lack of trying. I actually started out with that but decided it was too complex. All the bookkeeping required to decide which systems handle which components, and the difficulty of understanding the full behavior of an entity with more than a few components, etc. I then decided to search for something simpler, and started looking at other engines, for example the id tech engines used to create Doom, which seem to be inheritance based, and I decided that if its good enough for John Carmack it's good enough for me. \$\endgroup\$ – Anonymous Entity Mar 19 '17 at 7:15
  • \$\begingroup\$ @AnonymousEntity Indeed. I think what's important is that you do whatever's going to get you rolling, even if it's not lightning quick, learn from that, and adapt later. Implement / use the simplest ECS possible - but do try to avoid inheritance for entities. Worrying about cache performance is a bad idea that will prevent you from getting to the fun stuff. \$\endgroup\$ – Engineer Mar 19 '17 at 7:19
  • \$\begingroup\$ @AnonymousEntity ECS is much simpler than inheritance-based models. Every entity is just an integer, a number. If you want to find the position of entity i, you write positions[i]. If you want to iterate over every entity, you write for (int i = 0; i < highest_assigned_entity_id_so_far; i++), etc. \$\endgroup\$ – Miles Rout Mar 21 '17 at 20:39
  • \$\begingroup\$ I would love to discuss this with you in some other forum. \$\endgroup\$ – Anonymous Entity Mar 22 '17 at 6:48
1
\$\begingroup\$

If the costs of dynamic dispatch/indirect function calls and optimization barriers are genuinely too great and exhibit a tendency to degrade spatial locality, then the straightforward solution is model your design at a less granular level.

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