Rendering order in an Entity System

Question

Say I use a basic ES approach, and also inside Systems I hold lists of all entities that Systems are required to process.

How do I maintain this list of entities in desired rendering order, i.e. for a dumb 2D RenderingSystem?

I saw this discussion, and what they suggest is to do something like Z ordering - what I would probably do is just to store a "layer" int in DrawableComponent and then, inside RenderingSystem, just sort entities by mentioned "layer" whenever the entity list for RenderingSystem changes.

They also say we could just delete and recreate the entity whenever we want it on the top, but it seems too inflexible to me.

How is this problem usually solved?

Answer 1

Sort at rendering time if you sort at all. You don't need to keep the list sorted during every operation; in fact, this may be harmful. What happens if you spawn 20 enemies at once? Sort 20 times? They sorted quality doesn't matter until rendering, so why ever do it more than once per frame?

Furthermore, with an entity-component system, it can be handy to keep component databases sorted similarly. Despite all the theoretical cruft on the Internet about ECS, you will at times need to update two object lists in parallel or otherwise break out of the single-system ideal. Keeping the entities' components in these lists consistently ordered will make such updates faster; instead of iterating over one list sequentially and the other in essentially random order, you iterate over both sequentially. Your component databases should intrinsically have this property.

There's also a strong argument to make for separate object collections. The ComponentSprite component can just be a data record noting what the object wants rendered while a completely separate scene graph manages SceneSprite objects that deal with efficient rendering. Complex game objects might be made out of multiple sprites or so on in ways that are inefficient to handle with game object hierarchies. Your renderer and object systems don't need to be interdependent. Or they can be. Whichever is easier for your game.

When the renderable list changes, just mark a flag that it's dirty. Before rendering, check the flag and resort if it's set (and then unset the flag, of course).

In 3D systems this is more important as the entire sort order is likely to shift and change almost every frame.

Remember that it's not just layer you might want to sort by. With enough objects on screen - even in 2D - you might need to sort by screen tile, sprite, effect, etc., in addition to or instead of layer/depth.

For many games you can split your renderable object list into a set of layer "buckets." When an object is create/removed/re-layered, just perform a simple add/remove as necessary to the corresponding bucket(s). No need for explicit sorting steps at all. Many 2D games work with only a few pre-defined layers so they're simply no need for arbitrary depth/layer values to sort by.

Answer 2

i had something like this once.

i sorted the entity array by property z.

i used a sorting algorithm for it.

and the game loop ran from lowest z to highest z

somthing like: (every game loop so youll need a good sorting algorithm,and that did the trick,showd the right entities in front, everything was on its defind layer)

    this.y_world_mc=y_sort_by_depth(this.y_world_mc);//sorts everything by z

for(var i = 0, len =this.y_world_mc.length;len > i; i++ )
{
    if(this.y_world_mc[i] != null )
    {

        this.y_world_mc[i].update();

    }   

} 

Answer 3

@rolen123 answer is correct. I wish to introduce a data structure, QuadTree, to the formula.

As you said, sorting a vector of thousands of entities every time you are about to render is slow. But if QuadTree is introduced things change.

Implement QuadTree is not so difficult. Implement a QuadTree to only update entities that are moving is a bit more challenging but can be done, mine does. Most implementations in internet simple destroy the whole QuadTree and recreate it when something moved, that won't work for a fast paced game.

I have a QuadTree.selectRect(x, y, with, height) method that let me obtain all entities inside the specified rectangle, entities have a z property but they are returned in any order. Then I run Quick Sort in the returned array. Then I render the entities starting at the one with the less z value.

Hint: if an entity rectangle does not fit entirely in a node do not make multiple adjacent nodes reference the same entity, move the entity up to a bigger node is better.

Sorting before rendering may sound like overkill but even 3D engines do some kind of sorting and games perform OK.