2
\$\begingroup\$

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?

\$\endgroup\$
  • 1
    \$\begingroup\$ A priority queue would work pretty well. \$\endgroup\$ – MichaelHouse Jun 25 '13 at 13:20
  • \$\begingroup\$ @Byte56 Good idea, although, wouldn't it be more cache-frendly to hold them in a continous memory chunk? \$\endgroup\$ – Patryk Czachurski Jun 25 '13 at 13:30
  • \$\begingroup\$ Sure, if you're using a language where you can utilize that. The priority queue can just hold references. \$\endgroup\$ – MichaelHouse Jun 25 '13 at 13:33
  • \$\begingroup\$ @Byte56 oh, by "them" I just meant "references to entities". Anyway, I'm probably doing a premature optimization bothering about actual containers. \$\endgroup\$ – Patryk Czachurski Jun 25 '13 at 13:37
  • \$\begingroup\$ Ideally, you want to work with the fewest renderable entities each frame. The first step should be to perform visibility determination using whatever the active context is. After you have reduced it to that number, additional sorting is often done based on material (group like materials, and render transparencies last). Finally, sorting by depth can be done (though this isnt necessary for non transparent geometry). \$\endgroup\$ – Evan Jun 25 '13 at 13:58
4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ It would be nice if you could mention a suitable sorting algorithm perhaps for 2D and 3D games. \$\endgroup\$ – Nikos Aug 31 '18 at 18:39
  • 1
    \$\begingroup\$ @Nik-Lz: that's a pretty separate topic, but really any fast sort algorithm works. The complexity of sorting for rendering is more about what to sort than it is how to sort; e.g. sorting front-to-back for opaques/cutouts and back-to-front for translucents, and only sorting objects in the view frustrum at all. (That said, there are some neat sorting techniques involving render ids and radix sort, but again... kinda big, and I don't know offhand of an article to reference.) \$\endgroup\$ – Sean Middleditch Sep 3 '18 at 16:34
2
\$\begingroup\$

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();

    }   

} 
\$\endgroup\$
  • 1
    \$\begingroup\$ Ok, now that I've seen another answers, I pretty much agree with your sort-every-frame approach. \$\endgroup\$ – Patryk Czachurski Jun 26 '13 at 11:16
  • \$\begingroup\$ sometimes the most simple solution works. mine can go slow if you use bubble sort and have thousands of entities. but if you use a good sorting algorithm it should go fast. thats the point of using complex sorting algs. \$\endgroup\$ – rolen123 Jun 30 '13 at 9:51
1
\$\begingroup\$

@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.

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