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; Human humans; Demon demons; Entity* entities;
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.