sorting grid with one column first, then second

[ZombieSquirrel]

I've been at this for hours now and can't figure this out, and not gettinng a working answer
I need to sort a grid in an ascending order.
The grid has 3 columns: an instance name, an instance y value, and an instance x value.

I'm doing this to have my own depth system.
Now, I definitely have to order the grid for the y values,
which is a quick
ds_grid_sort(grid, row, true)

but... some y values are the same! For those, I need to give priority to instances with a larger (or smaller) x value.
Let's say 2 instances are right next to each other, in this way, the left instance will always have priority over the right one, but this can only be done if I sort the x values as well, at least for those instances with the same y value.

A quick example:
row y row x
1 1
2 2
5 3
3 4
2 5

becomes (after sorting y)
row y row x
1 1
2 2
2 5
3 4
5 3
OR it becomes
row y row x
1 1
2 5
2 2
3 4
5 3

Notice the region where the y's are 2.
I need to make sure they always get ordered in just the one possibility:
2 2
2 5
(smaller x value gets priority)

So in order to do this, I'd need to define the region where the y values, after being sorted, are the same. Then I need to sort that region only while leaving the rest of the sorted grid intact.

Anyone have an idea?

I've been told to sort x first, then y, and I get the logic behind that, but this just does not work...

It might have to do with that my player is part of this grid, so the player's x and y wil cause this grid to constantly update according to the player's movement.

Somehow I think it can't be this difficult to just have a bunch of instances that, when one's y is lower than the other, the second gets drawn on top. If one's y is the same, the left one gets drawn first.


I've been told Game Maker is good for concepts, but if you want to make a real game to just go Unity. I refuse that. I have a simple concept, but this is quite essential and I'm baffled that there's no function that does something like

ds_grid_sort_multiple or something, where you sort one row first, keep that row sorted, then evaluate those numbers that are the same, then sort them according to a second row of numbers…

If there is a solution, i need exact code, like what kind of functions do i follow up on each other?

 

[Slyddar]

I'm surprised GML doesn't allow you to sort by 1 column first, and then sort by another, and it retains the order of the previous sort. That seems like a bug and something that should be fixed.

In the meantime though, I thought I'd code it up for you for fun. Here's the full code, with a sample grid created, for testing. I had the grid order a little different to you, as I am used to x always coming before y.

Hope it helps.

Spoiler

// 0 - name,  1 - x, 2 - y
dst = ds_grid_create(3, 30);
//populate grid for testing
for (var i = 0; i < ds_grid_height(dst); ++i) {
    dst[# 0, i] = "Instance" + string(i);
    dst[# 1, i] = irandom(9);    //x
    dst[# 2, i] = irandom(9);    //y
}

var w = ds_grid_width(dst), h = ds_grid_height(dst), i, j, temp;

//sort by x first
ds_grid_sort(dst, 1, true);

//sort by y
var sort_column = 2;

do {
    var swapped = false;
    for (var i = 0; i < h - 1; ++i) {
        //is this row and the next row out of order?
        if dst[# sort_column, i] > dst[# sort_column, i + 1] {
            //i and i + 1 are out of order, so swap and remember

            //resize grid
            ds_grid_resize(dst, w, h + 1)

            //copy row i to end of grid
            ds_grid_set_grid_region(dst, dst, 0, i, w, i, 0, h);

            //copy the row i + 1 to row i
            ds_grid_set_grid_region(dst, dst, 0, i + 1, w, i + 1, 0, i);

            //copy the last temp row to i + 1
            ds_grid_set_grid_region(dst, dst, 0, h, w, h, 0, i + 1);

            //remove temp grid row if grid allows
            if h > 1 ds_grid_resize(dst, w, h);

            //remember we swapped
            swapped = true;
        }
    }
} until !swapped;

 

[Dmi7ry]

I'm surprised GML doesn't allow you to sort by 1 column first, and then sort by another, and it retains the order of the previous sort. That seems like a bug and something that should be fixed.

I don't think so. GMS can't know what changes were made (i.e. which values exactly should keep positions).

// 0 - name,  1 - x, 2 - y
dst = ds_grid_create(3, 30);
//populate grid for testing
for (var i = 0; i < ds_grid_height(dst); ++i) {
    dst[# 0, i] = "Instance" + string(i);
    dst[# 1, i] = irandom(9);    //x
    dst[# 2, i] = irandom(9);    //y
}

var w = ds_grid_width(dst), h = ds_grid_height(dst), i, j, temp;

//sort by x first
ds_grid_sort(dst, 1, true);

//sort by y
var sort_column = 2;

do {
    var swapped = false;
    for (var i = 0; i < h - 1; ++i) {
        //is this row and the next row out of order?
        if dst[# sort_column, i] > dst[# sort_column, i + 1] {
            //i and i + 1 are out of order, so swap and remember

            //resize grid
            ds_grid_resize(dst, w, h + 1)

            //copy row i to end of grid
            ds_grid_set_grid_region(dst, dst, 0, i, w, i, 0, h);

            //copy the row i + 1 to row i
            ds_grid_set_grid_region(dst, dst, 0, i + 1, w, i + 1, 0, i);

            //copy the last temp row to i + 1
            ds_grid_set_grid_region(dst, dst, 0, h, w, h, 0, i + 1);

            //remove temp grid row if grid allows
            if h > 1 ds_grid_resize(dst, w, h);

            //remember we swapped
            swapped = true;
        }
    }
} until !swapped;

Simply solution, but works slower than, for example, this:

#macro DATA_NAME 0
#macro DATA_X 1
#macro DATA_Y 2

/// @function data_sort(grid)

var data = argument0;

ds_grid_sort(data, DATA_Y, true);

var width = ds_grid_width(data);
var height = ds_grid_height(data);

var plist = ds_priority_create();
var result = ds_grid_create(width, height);

var last_posy = 0;
var result_index = 0;

for (var i=0; i<height; ++i)
{
    var posy = data[# DATA_Y, i];
    if i != 0 and last_posy != posy
    {
        while !ds_priority_empty(plist)
        {
            var index = ds_priority_delete_min(plist);
            result[# DATA_NAME, result_index] = data[# DATA_NAME, index];
            result[# DATA_X, result_index] = data[# DATA_X, index];
            result[# DATA_Y, result_index++] = data[# DATA_Y, index];
        }
    }

    ds_priority_add(plist, i, data[# DATA_X, i]);
    last_posy = posy;
}

while !ds_priority_empty(plist)
{
    var index = ds_priority_delete_min(plist);
    result[# DATA_NAME, result_index] = data[# DATA_NAME, index];
    result[# DATA_X, result_index] = data[# DATA_X, index];
    result[# DATA_Y, result_index++] = data[# DATA_Y, index];
}

ds_grid_copy(data, result);
ds_grid_destroy(result);
ds_priority_destroy(plist);

(I didn't test it well, so it may contain bugs)

 

[ZombieSquirrel]

Thanks!

 

[Nocturne]

You already have a topic for this here: https://forum.yoyogames.com/index.php?threads/sorting-grid-regions.60586/#post-365544

Please do NOT post the same topic twice.