I need help sorting a ds_grid

Calvix

Member
Hi there guys, iv'e been strugling with a problem for a week now and i could really use some help, for some context im trying to implement field of view using the ray casting method (iv'e adapted a method from roguebasin to gml), everything is working fine except one thing, so i keep a ds_grid filled with positions, asi in x and y corrdinates of the map, so at some point the grid might look something like

GML:
``````grid[# 0, 0] = 1
grid[# 0, 1] = 4
grid[# 1, 0] = 1
grid[# 1, 1] = 3
grid[# 2, 0] = 1
grid[# 2, 1] = 5
grid[# 3, 0] = 1
grid[# 3, 1] = 3
grid[# 4, 0] = 2
grid[# 4, 1] = 3
grid[# 5, 0] = 2
grid[# 5, 1] = 5
grid[# 6, 0] = 2
grid[# 6, 1] = 6``````
what i need to do is to remove duplicate entries from the grid, so every position in the map is only holded once by the grid. To do this i thought of just sorting the grid by column and then compare the values with the previous value and delete when duplicates apear. The thing is that i can only sort by one column at a time, wich means that repeated values aren't always adjacent to one another, if i paste them as an array youll see what i mean:

GML:
``````[ 1,4 ]
[ 1,3 ]
[ 1,5 ]
[ 1,3 ]
[ 2,3 ]
[ 2,5 ]
[ 2,6 ]
[ 2,2 ]``````
as you can see the first column is sorted properly but the second isn't. I don't know how to even aproach this problem anymore, any help would be great! Also if there is a solution that dosen't involve sorting the grid im all ears, i just thought this would be the "propper" way to solve it but right now i don know how to achieve such a sort. Thanx a lot!

Nidoking

Member
If you're iterating through the grid, why not just store each value as you see it (in an array, for example), and if you already have that value stored, then you delete it.

Calvix

Member
If you're iterating through the grid, why not just store each value as you see it (in an array, for example), and if you already have that value stored, then you delete it.
how would i check if its already stored? do i loop trought the entire array comparing?

Nidoking

Member
how would i check if its already stored? do i loop trought the entire array comparing?
That would be the simplest way. There are better options, like using them as keys in a map and just checking to see whether the key exists, or initializing an array to as many zeroes as you'll need and seeing whether the entry at that index is one. ds_list_find_index is another example of a way to do it, slowly but simply. It's all up to you.

Calvix

Member
I came up with this method, sorting the initial grid by it's first column, then after that looping through the grid and spliting that grid based on the first column index, then sorting that sub grid by it's second column, so i get the first part of the original grid sorted, then copy this sub grid in a new "sortedGrid", repeat for all indexes, return sorted grid, destroy all grids. The thing is that im having an error i can't find why, im debbuging my ass off haha i could use some help.

For debbug purposes i made a debbug object that has this code in the KEY PRESS S event:

GML:
``````grid = ds_grid_create(2, 9);

grid[# 0, 0] = 1
grid[# 0, 1] = 1

grid[# 1, 0] = 1
grid[# 1, 1] = 3

grid[# 2, 0] = 1
grid[# 2, 1] = 2

grid[# 3, 0] = 2
grid[# 3, 1] = 3

grid[# 4, 0] = 2
grid[# 4, 1] = 1

grid[# 5, 0] = 2
grid[# 5, 1] = 4

grid[# 6, 0] = 3
grid[# 6, 1] = 3

grid[# 7, 0] = 3
grid[# 7, 1] = 4

grid[# 8, 0] = 3
grid[# 8, 1] = 1

ds_grid_sort(grid, 0, true);
GridSortBySecondColumn(grid);

for (var i = 0; i < ds_grid_height(grid); i++){

show_debug_message(string(grid[# 0, i]) + " " + string(grid[# 1, i]));
}``````
the GridSortBySecondColumn function looks like this:

GML:
``````function GridSortBySecondColumn(_grid){

var grid = _grid,
auxGrid = ds_grid_create(2, 0),
sortedGrid = ds_grid_create(2, 0),
auxIndex = 0,
auxIndex2 = 0,

//ammount of times to loop trough the original grid
_max = ds_grid_get_max(grid, 0, 0, ds_grid_height(grid) -1, 0);

for(var i = 0; i <= _max; i++){
for (var j = 0; j < ds_grid_height(grid); j++){

//check for all entries that have the same first number to split into a new grid
if grid[# j, 0] == i{

auxGrid[# 0, auxIndex] = grid[# 0, j];
auxGrid[# 1, auxIndex] = grid[# 1, j];
auxIndex ++;
}
}

//sort the new grid
ds_grid_sort(auxGrid, 1, true);

//copy the content of the new grid into the sorted one
for (var k = 0; k < ds_grid_height(auxGrid); k++){

sortedGrid[# 0, auxIndex2] = auxGrid[# 0, k];
sortedGrid[# 1, auxIndex2] = auxGrid[# 1, k];
auxIndex2 ++;
}

//restart the auxiliar grid for the next loop
auxIndex = 0;
ds_grid_resize(auxGrid, 2, 0);
}

//return grid and clean grids
return grid;
ds_grid_destroy(grid);
ds_grid_destroy(auxGrid);
ds_grid_destroy(sortedGrid);
}``````
and the error log i get is this one:

GML:
``````Grid 0, index out of bounds writing [2,0] - size is [2,9]
Grid 0, index out of bounds writing [2,1] - size is [2,9]
Grid 0, index out of bounds writing [3,0] - size is [2,9]
Grid 0, index out of bounds writing [3,1] - size is [2,9]
Grid 0, index out of bounds writing [4,0] - size is [2,9]
Grid 0, index out of bounds writing [4,1] - size is [2,9]
Grid 0, index out of bounds writing [5,0] - size is [2,9]
Grid 0, index out of bounds writing [5,1] - size is [2,9]
Grid 0, index out of bounds writing [6,0] - size is [2,9]
Grid 0, index out of bounds writing [6,1] - size is [2,9]
Grid 0, index out of bounds writing [7,0] - size is [2,9]
Grid 0, index out of bounds writing [7,1] - size is [2,9]
Grid 0, index out of bounds writing [8,0] - size is [2,9]
Grid 0, index out of bounds writing [8,1] - size is [2,9]
Grid 0, index out of bounds writing [2,0] - size is [2,9]
Grid 0, index out of bounds writing [3,0] - size is [2,9]
Grid 0, index out of bounds writing [4,0] - size is [2,9]
Grid 0, index out of bounds writing [5,0] - size is [2,9]
Grid 0, index out of bounds writing [6,0] - size is [2,9]
Grid 0, index out of bounds writing [7,0] - size is [2,9]
Grid 0, index out of bounds writing [8,0] - size is [2,9]
0 0
0 0
0 0
0 0
0 0
0 0
0 0
1 1
1 3``````

i have no clue what went wrong, i hope someone can help me as im going mad with this problem hahaha thnx a lot if anyone can spot the error!!

EDIT: maybe i messed up the accessors?

Nidoking

Member
Oh, found it. You've got a [# j,0]. I don't think you mean that.

Calvix

Member
but the iteration only needs the height because i manually access the width with accessors, i don't see where the the problem would be, if you could explain a little more please the width is always fixed at 2

Calvix

Member
let me check
ok you are a genius, im not in my pc to make sure but it seems to be that, thnx a lot!!!

Calvix

Member
hmmm i still get this error after that correction, i don't understand what the problem might be, i thought the logic was on point so i still i might have missed something with accessors

GML:
``````Grid 3, index out of bounds writing [2,0] - size is [2,9]
Grid 3, index out of bounds writing [2,1] - size is [2,9]
Grid 3, index out of bounds writing [3,0] - size is [2,9]
Grid 3, index out of bounds writing [3,1] - size is [2,9]
Grid 3, index out of bounds writing [4,0] - size is [2,9]
Grid 3, index out of bounds writing [4,1] - size is [2,9]
Grid 3, index out of bounds writing [5,0] - size is [2,9]
Grid 3, index out of bounds writing [5,1] - size is [2,9]
Grid 3, index out of bounds writing [6,0] - size is [2,9]
Grid 3, index out of bounds writing [6,1] - size is [2,9]
Grid 3, index out of bounds writing [7,0] - size is [2,9]
Grid 3, index out of bounds writing [7,1] - size is [2,9]
Grid 3, index out of bounds writing [8,0] - size is [2,9]
Grid 3, index out of bounds writing [8,1] - size is [2,9]
0 0
0 0
0 0
0 0
0 0
0 0
0 0
1 1
1 3``````
the same error :/

Nidoking

Member
return grid;
ds_grid_destroy(grid);
ds_grid_destroy(auxGrid);
ds_grid_destroy(sortedGrid);
I don't know what you're still doing wrong, but this last part is wrong. The destroy calls can't happen because they're after the return, and you can't destroy grid because you're returning it.

David Richard

Member
Grids are simple arrays and can be sorted. That's neat. Now, I just would like to clarify something because I am a bit confused on what needs to be done. Do you mean that you would transform this:

GML:
``````[0, 1]
[0, 3]
[4, 0]
[2, 1]
[2, 5]
[2, 2]
[1, 5]
[0, 6]
[3, 3]``````
to:
GML:
``````[0, 1]
[1, 5]
[2, 1]
[3, 3]
[4, 0]``````
or to:
GML:
``````[0, 1]
[0, 3]
[0, 6]
[1, 5]
[2, 2]
[3, 3]``````
or:
GML:
``````[0, 0]
[1, 2]
[2, 3]
[3, 5]
[4, 6]``````
Because, in all cases, different things need to be done and you will not have the same solution. Up to now, what I have read so far, there seams to be unexisting indexes because some numbers don't exist or some arrays are maybe undefined. But since there is no reference into the expected results, it's hard, at least for me, to try and figure out how to help.

One thing that COULD help is to create a DS gris with both numbers together so grid [3,1] becomes grid [0, 31] and [0, 4] becomes grid [0, 04]. From there, you could sort the DS Grid by the second column, loop that grid and redo the new grid as per the new sorted grid's second column number. So your new gris would take 4 => New grid [0, 4] and 31 to [3,1]. But thats if you want it sorted that way because you did mention something about wanting to exclude doubles. But the doubles that need to be excluded, are they from column 0, column 1, both? Which column needs to be cleaned?

Calvix

Member
Ill make it clearer, say i have a grid that looks like this

GML:
``````[1, 1]
[1, 3]
[1, 2]
[2, 1]
[2, 1]
[2, 3]
[2, 2]
[3, 1]
[3, 1]``````
what i need as an output once sorted is

GML:
``````[1, 1]
[1, 2]
[1, 3]
[2, 1]
[2, 1]
[2, 2]
[2, 3]
[3, 1]
[3, 1]``````
so then i can clean it up to be

GML:
``````[1, 1]
[1, 2]
[1, 3]
[2, 1]
[2, 2]
[2, 3]
[3, 1]``````
as you can see both columns are sorted, first the index 0 one then the one with index 1 (i mean by "priority" as all pairs are kept as they where initialy), once that is done i already have a script to get rid of duplicates transforming the grid into a ds list and removing duplicate entries.

Calvix

Member
hmmm iv'e tried a couple of debug stiff, so when i do this

Code:
``````function GridSortBySecondColumn(_grid){

var grid = _grid,
auxGrid = ds_grid_create(2, 0),
sortedGrid = ds_grid_create(2, 0),
auxIndex = 0,
auxIndex2 = 0,
_max = ds_grid_get_max(grid, 0, 0, ds_grid_height(grid) -1, 0);
show_debug_message(_max)

for (var i = 0; i < ds_grid_height(grid); i++){ ----------------------------------------------------------------------------

show_debug_message("a: " + string(grid[# 0, i]) + " " + string(grid[# 1, i]));                                            THIS IS THE DEBUG STUFF!!!!!!
}---------------------------------------------------------------------------------------------------------------------------

for(var i = 0; i <= _max; i++){
for (var j = 0; j < ds_grid_height(grid); j++){

if grid[# 0, j] == i{

auxGrid[# 0, auxIndex] = grid[# 0, j];
auxGrid[# 1, auxIndex] = grid[# 1, j];
auxIndex ++;
}
}

ds_grid_sort(auxGrid, 1, true);

for (var k = 0; k < ds_grid_height(auxGrid); k++){

sortedGrid[# 0, auxIndex2] = auxGrid[# 0, k];
sortedGrid[# 1, auxIndex2] = auxGrid[# 1, k];
auxIndex2 ++;
}

auxIndex = 0;
ds_grid_resize(auxGrid, 2, 0);
}

return sortedGrid;
}``````
i get this:

Code:
``````0 -------------THIS IS THE RETURN OF THE _max VALUE
a: 0 0
a: 0 0
a: 0 0
a: 0 0
a: 0 0
a: 0 0
a: 0 0
a: 1 1
a: 1 3``````
so the grid content is getting deformed for some reazon somewhere, so weird and also the _max that should return 3 is returning 0, im completly lost now

Calvix

Member
i now moved this

GML:
``````grid = ds_grid_create(2, 9);

grid[# 0, 0] = 1
grid[# 0, 1] = 1

grid[# 1, 0] = 1
grid[# 1, 1] = 3

grid[# 2, 0] = 1
grid[# 2, 1] = 2

grid[# 3, 0] = 2
grid[# 3, 1] = 3

grid[# 4, 0] = 2
grid[# 4, 1] = 1

grid[# 5, 0] = 2
grid[# 5, 1] = 4

grid[# 6, 0] = 3
grid[# 6, 1] = 3

grid[# 7, 0] = 3
grid[# 7, 1] = 4

grid[# 8, 0] = 3
grid[# 8, 1] = 1``````
to the create event, then just left the printing loop in the key press (avoiding calling my function alltoghether and guess what, there is something wrong outside of the function aparently, can't for the love of god figure out what!!!
the loop in the press S event looks like this

GML:
``````for (var i = 0; i < ds_grid_height(grid); i++){

show_debug_message(string(grid[# 0, i]) + " " + string(grid[# 1, i]));
}``````
im not even sorting it
and the output is this

GML:
``````1 1
1 3
0 0
0 0
0 0
0 0
0 0
0 0
0 0``````
so the first two entries are fine but then it messes up, this means that this weird grid is the input we got to the function, but still the _max value SHOULD be 1, because it's the biguest number in the column im checking for, and still it returns 0.
i really need a sanity check, im pretty sure it's something really dumb what is causing all the problems but can't figure out what it might be

Calvix

Member
OMG ok the first problem was that i accesed the indexes in the worng oreder inthe create event
i did
GML:
``````grid[# 0, 0] = 1
grid[# 0, 1] = 1

grid[# 1, 0] = 1
grid[# 1, 1] = 3

grid[# 2, 0] = 1
grid[# 2, 1] = 2

grid[# 3, 0] = 2
grid[# 3, 1] = 3

grid[# 4, 0] = 2
grid[# 4, 1] = 1

grid[# 5, 0] = 2
grid[# 5, 1] = 4

grid[# 6, 0] = 3
grid[# 6, 1] = 3

grid[# 7, 0] = 3
grid[# 7, 1] = 4

grid[# 8, 0] = 3
grid[# 8, 1] = 1``````
when i should've done

GML:
``````grid[# 0, 0] = 1
grid[# 1, 0] = 1

grid[# 0, 1] = 1
grid[# 1, 1] = 3

grid[# 0, 2] = 1
grid[# 1, 2] = 2

grid[# 0, 3] = 2
grid[# 1, 3] = 3

grid[# 0, 4] = 2
grid[# 1, 4] = 1

grid[# 0, 5] = 2
grid[# 1, 5] = 4

grid[# 0, 6] = 3
grid[# 1, 6] = 3

grid[# 0, 7] = 3
grid[# 1, 7] = 4

grid[# 0, 8] = 3
grid[# 1, 8] = 1``````
the thing is that now runing the function i get this output
GML:
``````1 3
1 2
1 1
2 3
2 1
2 4
3 4
3 1
3 3``````
GML:
``````1 1
1 2
2 1
2 3
2 4
3 1
3 3
3 4``````
wich sadly means that there is something wrong with the logic, what i was afraid from the beggining, i want to cry hahaha
i know the post got extremly long so im extremly thankfull to everyone taking the time to read trough it, you guys are awesome!

Calvix

Member
Ok GREAT NEWS! iv'e corrected a bunch of stuff and almost everything is working properly! so the logic wasn't bad at all
the only problem now is with the "_max" variable, for some reason it only goes to 3 even if i change the array, so if the array looks like this

GML:
``````grid[# 0, 0] = 1
grid[# 1, 0] = 1

grid[# 0, 1] = 1
grid[# 1, 1] = 3

grid[# 0, 2] = 1
grid[# 1, 2] = 2

grid[# 0, 3] = 2
grid[# 1, 3] = 3

grid[# 0, 4] = 2
grid[# 1, 4] = 1

grid[# 0, 5] = 2
grid[# 1, 5] = 4

grid[# 0, 6] = 3
grid[# 1, 6] = 3

grid[# 0, 7] = 3
grid[# 1, 7] = 0

grid[# 0, 8] = 4
grid[# 1, 8] = 4``````
the _max returns 3 instead of 4, i have no clue why, but i feel like im almost there
rememeber that _max = ds_grid_get_max(grid, 0, 0, gridHeight, 0);

so it SHOULD return 4, but instead it returns 3, so once i run the function it returns a properly sorted grid but without the last entry because in the for loop that uses the "i" variable, "i" never gets to 4, ill keep invetigating

Calvix

Member
I DID IT!!!! IT WORKS PERFECTLY!!! THANKS A LOT YOU GUYS IM SOOOO HAPPY!!!!!
ill post the solution in case anyone else might find it usefull

instead of using this weird native function ds_grid_get_max(grid, 0, 0, gridHeight, 0), wich, for some odd reason, dosen't work properly i decided to code the logic for it myself so it looks like this

GML:
``````var _max = 0

for (var q = 0; q < ds_grid_height(grid); q++){

if grid[# 0, q] > _max _max = grid[# 0, q];
}``````
now for the complete function, in case anyone finds it usefull of at least intresting haha here it is

GML:
``````function GridSortBySecondColumn(_grid){

var grid = _grid,
auxGrid = ds_grid_create(2, 0),
sortedGrid = ds_grid_create(2, 0),
auxIndex = 0,
auxIndex2 = 0,
_max = 0;

for (var q = 0; q < ds_grid_height(grid); q++){

if grid[# 0, q] > _max _max = grid[# 0, q];
}

for(var i = 0; i <= _max; i++){

for (var j = 0; j < ds_grid_height(grid); j++){

if grid[# 0, j] == i{

auxGrid[# 0, auxIndex] = grid[# 0, j];
auxGrid[# 1, auxIndex] = grid[# 1, j];
auxIndex ++;
}
}

ds_grid_sort(auxGrid, 1, true);

for (var k = 0; k < ds_grid_height(auxGrid); k++){

sortedGrid[# 0, auxIndex2] = auxGrid[# 0, k];
sortedGrid[# 1, auxIndex2] = auxGrid[# 1, k];
auxIndex2 ++;
}

auxIndex = 0;
ds_grid_resize(auxGrid, 2, 0);
}

return sortedGrid;
}``````
this will take a 2 rows sorted grid (sorted using the native sort function for grids and sorting by the first column) as an argument and then sort it again by the second column

so with this input:
1 1
1 3
1 2
2 2
2 3
2 1
3 1
3 3
4 1

it will give this output:
1 1
1 2
1 3
2 1
2 2
2 3
3 3
4 1

THANK YOU GUYS SO MUCH!! im FINALLY DONE WITH THE RAY CASTING METHOD FOR FIELD OF VIEWWWWWWW