Looking for a better design for drawing sprites in order.

[alwayslearning]

The problem is, code execution order does not guarantee sprites will be drawn in order without some sort of method to track their levels, sort the sprites, and then drawing them.

What are your ways of doing this?

My method:
If the drawables need to be rendered they are added to a draw vector (only happens when set view == true, not every frame)
At the end of each frame, drawables on vector are sorted (std::sort), then merged with an in-order drawables list.
Then the list is iterated through executing windows::draw()

By the end, the draw list contains all the drawables rendered last frame in order, removing the need to continually adding, sorting sprites every frame.


If a drawable is no longer visible, it is removed from the list.
I use a map to do this rather than iterate through the list looking for the drawable.

[Ashenwraith]

You should not be changing your list if nothing is changed.

Ideally you should be trying to recycle as many sprites as you can or draw them off screen if they are reappearing fast.

[alwayslearning]

I agree.  Objects are only added and removed if their visibility or levels have changed.  Which is not a common occurrence in the middle of a non-game state.

I am wondering if there are any implementation designs that are an improvement over mine as it is costly to remove drawables from the list.   All drawables on the list are used as the key and the list iterators used as the value within an std::map to facilitate searching drawables for removal.

This requires 2 calls to map (find, and erase) and 3rd call to list (erase).

[Ashenwraith]

Did you try sprite recycling like I suggested?

For example, you have a fixed average for drawables and you edit the drawables themselves.

Instead of taking them out of an array you could replace their image with a sf:Color(0,0,0,0)

If they reappear soon you could move them offscreen

You have to look at the workload and see if it's the gpu or the cpu that could use the most benefit.

[Laurent]

Removing a sprite from a collection will always be much faster than sending all the OpenGL commands required to draw it.

[Ashenwraith]

Removing a sprite from a collection will always be much faster than sending all the OpenGL commands required to draw it.

That's what I thought, but what if you are doing snow or constant enemies. Wouldn't it be better to just move it off screen?

Also say you have an enemy die, you could make it 0,0,0,0 then change it to treasure in the same sprite set?

I'm trying to think of what would keep the cache as consistent as possible with tricks.

[Laurent]

"The fastest geometry is the one that you don't draw".

Reusing sprite instances is not really an optimization, a sprite is a lightweight object and its creation/destruction doesn't involve expensive operations.

[Cyrano]

"The fastest geometry is the one that you don't draw".

Reusing sprite instances is not really an optimization, a sprite is a lightweight object and its creation/destruction doesn't involve expensive operations.

So then, what is an optimization?

I can see how not drawing geometry over and over is a good idea. It wastes time and CPU power, but aside from reducing redundancy and useless system calls, what other optimizations can you make?

[Laurent]

Optimizations that you can make depend on what the application, what it draws and how it uses the graphics module.

But basically, SFML is designed so that people can concentrate on high-level stuff and not on finding the most optimized way of doing things -- there's only one in SFML.

[Cyrano]

Optimizations that you can make depend on what the application, what it draws and how it uses the graphics module.

But basically, SFML is designed so that people can concentrate on high-level stuff and not on finding the most optimized way of doing things -- there's only one in SFML.

I like that line of reasoning.

The reason I asked was simply to find out whether or not there was a more efficient way of getting the job done.

Thanks!

-Cyrano

[alwayslearning]

For anyone still reading.

I wrote up another method of storing drawables by using std::multiset and compared it with my original.

It's approximately 2x faster.
Using the list, vector, and map = ~37 seconds
Using multiset = ~20 seconds

I'm going to stick with multiset.

[Ashenwraith]

That's interesting, I was researching multiset.

Can you post your code?

[panithadrum]

For anyone still reading.

I wrote up another method of storing drawables by using std::multiset and compared it with my original.

It's approximately 2x faster.
Using the list, vector, and map = ~37 seconds
Using multiset = ~20 seconds

I'm going to stick with multiset.

You should test it with different amount of drawables (10, 100, 1000 and 10000 for example). I'm sure the results will be different from a certain number of it.

What about std::multimap?

[gsaurus]

I didn't noticed there were 2 threads about the same thing. I posted an example using multiset here

[alwayslearning]

Running with differing amount of drawables.  

This is my test scenario (worst case)
Adding sprites 1 by 1.
Drawing through.
Removing 1 by 1 using the find/lookup methods.

Here are the results so far (in ticks):
10,000 loops
a) map + vector + list
b) multiset

10 sprites
a) 343
b) 188

100 sprites
a) 3797
b) 2047

1000
a) 326,219
b) 26,812

(retested 1000 sprites)
a) 392,266
b) 26,406

10000
a) -
b) -

I'll write one up using multimap in a second.