• Hey Guest! Ever feel like entering a Game Jam, but the time limit is always too much pressure? We get it... You lead a hectic life and dedicating 3 whole days to make a game just doesn't work for you! So, why not enter the GMC SLOW JAM? Take your time! Kick back and make your game over 4 months! Interested? Then just click here!

Depth sorting issue with objects on the same y position

IanFrank

Member
Hi!

I am using FriendlyCosmonauts depth sorting system, which is descibed here:


and here : https://github.com/GameMakerDiscord/depth-system

Basically you add all objects included in the system to a list, then sort the list by the objects Y positions, and finally draw them in the list order.

The problem is, when the objects are positioned at the same y position and overlapping, they start trading places on the list as the player moves around the room, which result in flickering behind and in front of each other. Not sure why, i guess it's a gamemaker instance handling thing.

I've made a fix that seems to work, by adding a third column where i add the ID and the object y to a binary, like this:

GML:
    dgrid[# 0, yy] = id;
    dgrid[# 1, yy] = y+z;
    dgrid[# 2, yy] = (id | id.y << 32);
..and then sort by the 3rd column.

Honestly, i don't really understand my fix 😅 and i am sure it is not stable.. So my question is - does anyone have a proper solution for this issue?

I know there are other depth sorting systems, but this one seems fine for my small rpg. :)

Thanks in advance.
 

ribbyte

Member
There is probably a proper/good solution for this, but the way you solved it would've pretty much been my first attempt as well (i.e., don't use just "y" to sort by, but "y" appended with the "id" of the object). In this case you just have to assume that "id" is always 32 bit, which I'm not sure is specified anywhere, but if it works, it works. To avoid future issues, try this:

GML:
dgrid[# 2, yy] = ((id & 0xffffffff) | id.y << 32);
This "flickering" probably happens because every time you sort, there are multiple correct ways to sort the grid if more than one entry has the same "y", so it ends up being kinda unpredictable and random. So another solution would be to try to get rid of this unpredictability or randomness. I would try to first sort the grid by the id and then to sort by "y" just as you did before. So, in the github code you linked above, try this:

GML:
//first sort by id
ds_grid_sort(dgrid, 0, true);
//Sort the grid in ascending order
ds_grid_sort(dgrid, 1, true);
Depending on how the sorting is implemented, this should give the same result every time and it should stop flickering. But this solution is probably hacky as well.
 

CMAllen

Member
Another option is to sort by x and y. Left to right, top to bottom. You'd do this by multiplying your Y value by some function of width (maximum sprite width, tile width, room width, etc -- in this example, I'll use a 32-pix tile width). Then you add the object's x value. So an object at 32x and 32y would be sorted at 1056, while the object one pixel to the left would be sorted at 1055 and the object one pixel to the right would be sorted at 1057. Problem solved.
 

IanFrank

Member
@ribbyte @CMAllen thank you both very much for your replies. I am glad to know i wasn't way off. :)

I've tried all 3 things, and

Code:
dgrid[# 2, yy] = ((id & 0xffffffff) | id.y << 32);
..also works, though i am still not sure what it does. And if it might be unstable for some reason, i think i will avoid it.

Sorting the list first after ID, then after Y does not work. I think the second sorting just overrules the first one, ignoring the order.

CMAllens suggestion also works - though i am unsure why i would use a width function, and not just multiply by ie. 32? (My tiles are 32 btw).

Right now i just added this :

GML:
dgrid[# 1, yy] = (y*32 + x) + z;
Which works. But if you could elaborate on your solution it would be great, thanks. (My z value is used for offset when the character jumps to avoid him jumping 'behind' stuff).
 

TheouAegis

Member
He says to use the width function for readability and flexibility. When you say 32, down the road you are probably going to forget why you said 32 in the first place. Or if you decide to change the size of your tiles or sprites, then suddenly that 32 might stop working.

You have your y+z value to sort by, right? Sorting is going to go off the highest value. So if y+z is 16 for one object and 17 for another, the 17 would be sorted first. Even if you multiply the values by 10, 170 is still higher than 160. Basic math.

If you simply add x to y+z, you change the sorting. If x is 0 for the one that has y+z of 17, and x is 2 for the one with y+z of 16, then 17 stays 17 and 16 becomes 18, getting sorted higher. That's a no-no, you want y+z to be the determinant. So if you multiply y+z by some number, you keep y+z as the determinant while giving room for x to be added. If the number you multiply y+z by is smaller than the largest possible value of x, then you will get the same problem as if you simply added x.

However, x can get really big, so multiplying y+z by that limit could result in a number that is too big for GM to handle, causing either a crash or some bugs at higher y coordinates. One way to simplify this is to reduce the factor applied to y+z and adjust x to exist within those new imposed limits.

In the code posted, it's suggested you only sort each sprite based on its x position relative to every 32 pixels. That way you only need to multiply y+z by 32, which GM should have no problems with in most cases. Then instead of adding x, you would add (x mod 32) or (x & 31) to (y + z)*32. (Don't add x directly.)

Personally I'd go with 64 instead of 32. And all depends on the size of your sprites, though. whatever the biggest Sprite is that would need to be sorted, use its width.
 

CMAllen

Member
Which works. But if you could elaborate on your solution it would be great, thanks. (My z value is used for offset when the character jumps to avoid him jumping 'behind' stuff).
Think about words on a page, being read from left to right, top to bottom. Each row of words and letters is a multiple of the width of the page. If your page is 128 letters wide, then the 129th letter is the first letter on the second row (1*128+1). The 5 letter on the 6th line is the 773rd letter on the page.

It's the same idea with sorting object drawing order -- each row of Y pixels is a multiple of X width of the room. But this presents us with a computational problem -- bigger numbers are more processor demanding to handle. You don't want to multiply your Y value by the width of a very large room. That will slow down your sorting, which needs to be done quickly for every frame (or nearly every frame). The solution to this is to keep the multiples of Y large enough that *when* the sorting value of two different objects are the same, they're *NOT* in the same drawing space, hence, the suggested maximum width of your sorted sprites -- when two sprites sort at the same 'depth' they won't occupy the same space on the screen, so the order which they are drawn in doesn't matter with respect to each other.
 

IanFrank

Member
@TheouAegis @CMAllen Thank you both very much for explaining this, it is greatly appreciated.

My largest sprite width is currently 256, so i ended up using this code:

GML:
dgrid[# 1, yy] = ((y+z)*256) + (x mod 256);
I expect my largest room size would be around 1920 x 1344, perhaps a bit larger, which means the sorting number for objects in the bottom right corner end up around 340.000.

So my final question.. Is that too high a number, or should i consider another approach? I've tested with 500+ objects in the sorting list, and it seems okay so far..
 

Padouk

Member
One question come to mind...
Can 2 or more objects be at the exact same X and Y?
If yes, that would be your last edge case to test... putting a few objects at the exact same X and Y and see if you still have that flickering issue.

GML:
dgrid[# 1, yy] = ((y+z)*256) + (x mod 256);
So my final question.. Is that too high a number, or should i consider another approach?
grid Cells contains double or string... without going into 52 vs 32 bits details... how about you play safe and stay bellow 32bit mark (2,147,483,647)?


If you go @CMAllen way, i'd plan for new sprites which may be wider once you start adding new assets...
how about assuming wider sprites... like *512?
how about *1024?
Heck... why not just assume 65536 wide sprites? *65536?... 1300*65536=85,196,800. Even there you still have plenty of room... for your (y+z).
(see where i'm going yet?)
--

I'm resurrecting @ribbyte's idea. (and yours in the first place) just in case you can have more than 1 actor at the same X and Y

you want to sort by Y then by <some deternimistic value>
Any value really... as long as it help you make a distinction between two actors in a consistant way over time... Your first guess at id sounds right! That's deterministic.

sort by Y then by id


Without going into the optimization bit of things, you could use Decimal part for the y and the Fractional part for id

GML:
dgrid[# 0, yy] = id;
dgrid[# 1, yy] = y+z;
dgrid[# 2, yy] = (y+z) + 1/id;
If you want to go into the optimization...
You already know y+z can't be over 65535. (we have established that through CMAllen's conversation) so 16 bits is enough.
You can expect id to be increased on every instance_create based on a seed... (100001, 100002, 100003, 100004) ...so you can expect the lower digits to be different from one to another, while the upper one to be useless for sorting.
How about we get ride of them... sorting by id mod 10 gives the same result... right? 1, 2, 3, 4.
What if you have more thatn 10 instance? .. how about 65536 instances? You think that's a fair assumption? id mod 65536..
(see where i'm going yet?)

Now it's just a matter of knowing the bitwise operator, do you agree those two lines are mathematically equivalent on integers?
GML:
dgrid[# 2, yy] =(y+z) * 65536 + (id mod 65536);
dgrid[# 2, yy] =((y+z) << 16) + (id & 0xFFFF);
This is how you get a 32bit version of what @ribbyte was talking about.... As long as your y say in range [-32768, 32767] and you have less than 65535 instances you should be fine and deterministic on most devices.
GML:
dgrid[# 0, yy] = id;
dgrid[# 1, yy] = y+z;
dgrid[# 2, yy] =((y+z) << 16) + (id & 0xFFFF);
Code:
dgrid[# 2, yy] = ((id & 0xffffffff) | id.y << 32);
..also works, though i am still not sure what it does. And if it might be unstable for some reason, i think i will avoid it.
I hope you understand it now and you are not afraid of it anymore.
 
Last edited:

IanFrank

Member
I am absolutely blown away by the math knowledge AND the will to help of you guys! Thank you very much for your input as well @Padouk !

I know logic, and i am a decent programmer, but i have a hard time wrapping my head around math like that. Been away from GM a few years, so relearning alot. So this is really helpful.

I do understand it much better after your explanation, thanks. And it also seems a bit lighter on the fps ;) I don't think there will be multiple objects at the same x,y pos, so it should be fine. :)

Thanks again. 😊
 
Top