GameMaker DS Grid sorting same values

[MeBoingus]

Hi all,

Spoiler: In-depth, boring explanation of 'why':

Long story short, I'm trying to make a 'light' object system for my game. My goal is to be able to handle... quite a few objects on screen at once. Really, the player can just keep spawning them as much as they like.
Seeing as GM has a bunch of overhead when it comes to objects, I decided a good approach would be to create a DS grid (originally planned on using a 2D array. More on that later.) that stores the basic info I'd need about these objects.
For each item in the grid, the following information is stored [ID, x, y, Sprite] (for this example case).

Wherein ID is a unique identifier that links to that 'specific object'.

I have a step event that iterates through the grid and performs updates to each of these 'objects'. For example, it changes their Y position.
I then have a draw event that iterates through the grid, and draws each sprite at the given x and y coordinates.

I originally planned to use a 2D array, and write (or rather 'acquire') a simple sorting algorithm (I.E. QuickSort) to sort it.
This is because 2D arrays are just inherently faster for reading and writing in this situation.

I decided to use grids because... well... ds_grid_sort exists, and why bother reinventing the wheel?
I could, in theory, write a simple function that converts the 2D array to a ds grid, sorts it with ds_grid_sort, and then converts it back into an array - but that's a problem for future me.

This (obviously) all works fine. The main issue I've run into is depth sorting.

EDIT: A link to the GMS2 project in which I'm experiencing this issue. You'll notice that if two or more 'objects' are at the same y value and any two of the objects on top of one another, they start to flicker randomly between being 'above' and 'below' the other.

I want to sort a DS Grid based on the value in the 3rd column. using ds_grid_sort works perfectly fine, except if there are multiple rows with the same value in the 2nd column.
If this is the case, it seems to randomly decide where these same values wind up in the grid.

If you read the "In-depth, boring explanation of 'why'" featured above - I'm iterating through this grid, and using information from each row to draw a (potentially) different sprite.
If I have two sprites that are on top of one another (at the same y position), the order in which they're drawn (after being sorted based on their y position) randomly changes every time I sort the grid.


Is there any way to prevent this? My idea would be to find all of the elements that are the same, and then sort them based on the data in the first column. Sadly, I am weak in the upper-story, so to speak, and have absolutely no idea how to write an efficient sorting algorithm.


Would it be more worthwhile to simply:
Use a 2D array.
Write a sorting algorithm function.
Make the above-mentioned algorithm 'fall back' on the 1st value in the array if it finds two matching values.


If so, and guidance or examples of QuickSort (or any other reasonable sorting algorithms) written in GM?


Thanks in advance!

 

[davawen]

For quicksort, there is this really good implementation by the coding train, that actually tells you how it works.
It's in JavaScript, but you almost don't need to change anything to get it working in GML.


It would probably be easier if you were using 2.3, but you can just make scripts.

 

[Nidoking]

Sorting the whole grid twice, first by the first column and then by the third column, should give you what you want, assuming that the first column values are unique. That would depend on the exact implementation of ds_grid_sort, but it may be worth a try.

 

[MeBoingus]

Sorting the whole grid twice, first by the first column and then by the third column, should give you what you want, assuming that the first column values are unique. That would depend on the exact implementation of ds_grid_sort, but it may be worth a try.

Sadly this would not work.

Let's say our grid looks like this:

[3] [X] [50]
[0] [X] [100]
[2] [X] [100]
[1] [X] [30]

The first sort (by the 3rd column) would result in this:

[1] [X] [30]
[3] [X] [50]
[0] [X] [100]
[2] [X] [100]

The second sort would then destroy what the first sort did and result in the following:

[0] [X] [100]
[1] [X] [30]
[2] [X] [100]
[3] [X] [50]

The second sort wouldn't just be taking into account the values that are the same and sorting those, it would be sorting the entire grid.

I could perhaps, in theory, store each of the 'same' values in a grid of other values that are the same, sort those, and then add them back to the grid. I'll look into that later on.

 

[Nidoking]

first by the first column and then by the third column

The first sort (by the 3rd column)

There is a vital difference between the idea I posted and the one you seem to have found. I think I may have found why you're having trouble putting things in the proper order here.

 

[FrostyCat]

You can add a slight tiebreaker factor to the weight, say the ID of the instances divided by 1000000000. Then if ds_grid_sort() picks up the difference, it will sort it one way consistently throughout the tying instances' lifetime.