Depth sorter, news ?

DaveInDev

Member
Hi there,

I know that in GMS2, now that instances layers are tied to the depth, the depth = -y method is not very good anymore because GMS2 creates a temporary layer for each new value of depth appearing in the game, which can be not efficient if your objects are changing their depth at every step...

So I saw @FriendlyCosmonaut basic method here : https://forum.yoyogames.com/index.php?threads/depth-sorting-for-gms2-alternative-to-depth-y.26079/

And I just wonder if there is any new method for depth sorting or is it the one commonly used (this one or any variant based on making a list of instances at every step, and sorting them by depth, then printing them in order).

As a first improvement, I was thinking that when you have a lot of instances, re-creating and fully sorting this list at every step is cost consuming. I Thought about creating this list as a global, and just updating it if instances are created or deleted, so that when sorting it, most of the time, if not too many instances are moving relatively to each other, it would be easier to sort, because it would be already almost sorted.

Do you know about any other method or improvement ?
 

Nidoking

Member
Most of the generally efficient sorting algorithms don't get a performance increase when the incoming data is already sorted - in fact, I think most of the sorting routines I would recommend get some of their worst performance with nearly-sorted data. The thing you have to understand is that the algorithm generally has to do the same number of comparisons to determine that the data is in order, because the computer can't "eyeball" the list to see the ordering up front. This would improve algorithms like Bubblesort, but those are inefficient in general. What you might do is choose whether to use Bubblesort or a general sort based on whether instances have been added or deleted, or whether the list needed to be rebuilt (say, because you moved to a new room). That way, you could use a quick Bubblesort for most cases, but the more efficient sort when the list is known to be largely out of order.
 

Yal

šŸ§ *penguin noises*
GMC Elder
One thing you could do is to clamp the depthsort values to a smaller range, which caps the number of managed layers GM has to manage. Also works really well if you need to have layers with set depths and don't want things to bleed into their depth ranges. And it's almost as easy as depth=-y, too!

GML:
function depthsort_get_delta(argument0) {
    return clamp((argument0 - camera_get_view_y(view_camera[0]) - VIEW_H*0.5)*0.5,-50,50)
}
(I'm using +/- 50 here since layers are 100 depth units apart by default)
 

DaveInDev

Member
Most of the generally efficient sorting algorithms don't get a performance increase when the incoming data is already sorted
You're right, in my head I was thinking bubblesort, that will improve things in most case, because most of the time, instances are just swapped into this list (unless an object is teleported anywhere, but then I can move it into the list with a special routine). I thought using the default ds_map_sort when creating the list the first time, and then using my own bubblesort, and also my own insertion routine to insert a newly created instance right at the good place.

Anyway, creating the list once at the beginning is better than recreating it at every step, no ? (admitting that instances are not created or deleted at every step).

One thing you could do is to clamp the depthsort values to a smaller range, which caps the number of managed layers GM has to manage. Also works really well if you need to have layers with set depths and don't want things to bleed into their depth ranges. And it's almost as easy as depth=-y, too!
If I understand, you are not using a list, but you are setting all objects that are outscreen to the same depth/layer because we don't care of their order.
That's a good idea.
The fact is, that, if I do not use a list but classic depths, I already use a test to set the visible parameter of objects to false when they are outside the viewport to avoid calling their draw event ; so in the step event, I can directly add " if(!visible) depth = 9999 " , so that it only creates 1 temporary layer, even if nothing of this layer will be drawn...
 

Padouk

Member
ds_grid_sort is fast, don't underestimate it ;)
We are talking what... 4 instance so sort? 10? 100? Look at your profiler I doupt you will take that much hit from it.


If you are talking about 100,000 instances that's a whole other story tough.
 

DaveInDev

Member
My problem here is around 1000 instances moving all around, but not teleporting, that's why I try to optimize from the beginning. Maybe I am wrong. I will test many solutions and profile. Thanks for your advises anyway.
 
Top