GameMaker Random object's placement in grid too slow

M

Midastouch

Guest
Hello everyone,
I created a grid, each cell can have a value =0 or value = 1 (value 0 is water, value 1 is ground).
As you can see in the code bellow, i place randomly 50 obj_copper on the map, only on the cell with a value = 1

GML:
if instance_number(obj_copper) < 50 {

        var aa, bb;

        aa = irandom_range(0,ds_grid_width(grid_));

        bb = irandom_range(0,ds_grid_height(grid_));

        var value_copper = ds_grid_get(grid_, aa, bb);//check the value in the grid//check if value = 0 or 1

        if (value_copper = 1) {

            instance_create_depth(aa*32 ,bb*32,-1, obj_copper)

}}
My problem is that it's very slow, it put 3-5 seconds to put my 50 obj_copper.
And in a while i will place more ad more objects.
I want to improve my code, can you help me?
 
M

Midastouch

Guest
This is my grid creation

GML:
randomize(); //Get a different seed every launch
cellSize = 32; //The size for each terrain block
fillpercentage = 25;// More = more ground

//This will give us the size for our data grids
width = room_width / cellSize; // How many horizontal cells?
height = room_height / cellSize; // How many vertical cells?

//Create the grid with 2 values
grid_ = ds_grid_create(width,height);//This function returns an id which must be used
//in all further functions that deal with this ds_grid

for (var j = 0; j < height; j ++) {
    for (var i = 0; i < width; i ++) {
        if irandom(100) < fillpercentage  {
             ds_grid_set(grid_, i, j, 1);
        } else {
             ds_grid_set(grid_, i, j, 0);
        }
    }
}
 

Simon Gust

Member
It can take long. It can even take an infinity of time if you do not have 50 copper grid spaces.
The most exspensive functions you have there are instance_number() and instance_create_depth().
You can't reduce the number of instance_create_depth() of course, but you can cut down on the instance_number() checks.

- make a list
- Loop through the grid and collect all positions where copper is.
- shuffle the list
- loop through the list and create the copper at the positions given by the list entries.
Code:
var copper_list = ds_list_create();

var w = ds_grid_width(grid_);
var h = ds_grid_height(grid_);

for (var i = 0; i < w; i++) {
for (var j = 0; j < h; j++) {
    var value_copper = ds_grid_get(grid_, i, j);
    if (value_copper == 1) {
        var pos = i | j << 16;
        ds_list_add(copper_list, pos);
    }
}}

ds_list_shuffle(copper_list);
var size = min(ds_list_size(copper_list), 50);

for (var n = 0; n < size; n++)
{
    var pos = copper_list[| n];
    var xx = pos & 65535;
    var yy = pos >> 16;
    
    instance_create_depth(xx*32, yy*32,-1, obj_copper);
}

ds_list_destroy(copper_list);
Warning; If your grid is very large, this might even take longer than your version!
You can compare them.
 

Nidoking

Member
You could also potentially cut this down quite a bit by populating copper_list while you're creating the grid in the first place, rather than going through it a second time afterward. That should be more or less constant time aside from the actual creation of the grid.
 
M

Midastouch

Guest
It can take long. It can even take an infinity of time if you do not have 50 copper grid spaces.
The most exspensive functions you have there are instance_number() and instance_create_depth().
You can't reduce the number of instance_create_depth() of course, but you can cut down on the instance_number() checks.

- make a list
- Loop through the grid and collect all positions where copper is.
- shuffle the list
- loop through the list and create the copper at the positions given by the list entries.
Code:
var copper_list = ds_list_create();

var w = ds_grid_width(grid_);
var h = ds_grid_height(grid_);

for (var i = 0; i < w; i++) {
for (var j = 0; j < h; j++) {
    var value_copper = ds_grid_get(grid_, i, j);
    if (value_copper == 1) {
        var pos = i | j << 16;
        ds_list_add(copper_list, pos);
    }
}}

ds_list_shuffle(copper_list);
var size = min(ds_list_size(copper_list), 50);

for (var n = 0; n < size; n++)
{
    var pos = copper_list[| n];
    var xx = pos & 65535;
    var yy = pos >> 16;
   
    instance_create_depth(xx*32, yy*32,-1, obj_copper);
}

ds_list_destroy(copper_list);
Warning; If your grid is very large, this might even take longer than your version!
You can compare them.
Your code works perfectly i just added a line to limit the instance number ( if (instance_number (obj_copper) <50))

GML:
var copper_list = ds_list_create();

var w = ds_grid_width(grid_);
var h = ds_grid_height(grid_);

for (var i = 0; i < w; i++) {
for (var j = 0; j < h; j++) {
    var value_copper = ds_grid_get(grid_, i, j);
    if (value_copper == 1) {
        var pos = i | j << 16;
        ds_list_add(copper_list, pos);
    }
}}

ds_list_shuffle(copper_list);
var size = min(ds_list_size(copper_list), 50);

for (var n = 0; n < size; n++)
{
    var pos = copper_list[| n];
    var xx = pos & 65535;
    var yy = pos >> 16;
    if (instance_number (obj_copper) <50) {
    instance_create_depth(xx*32, yy*32,-1, obj_copper);
}}

ds_list_destroy(copper_list);
 

Simon Gust

Member
Your code works perfectly i just added a line to limit the instance number ( if (instance_number (obj_copper) <50))

GML:
var copper_list = ds_list_create();

var w = ds_grid_width(grid_);
var h = ds_grid_height(grid_);

for (var i = 0; i < w; i++) {
for (var j = 0; j < h; j++) {
    var value_copper = ds_grid_get(grid_, i, j);
    if (value_copper == 1) {
        var pos = i | j << 16;
        ds_list_add(copper_list, pos);
    }
}}

ds_list_shuffle(copper_list);
var size = min(ds_list_size(copper_list), 50);

for (var n = 0; n < size; n++)
{
    var pos = copper_list[| n];
    var xx = pos & 65535;
    var yy = pos >> 16;
    if (instance_number (obj_copper) <50) {
    instance_create_depth(xx*32, yy*32,-1, obj_copper);
}}

ds_list_destroy(copper_list);
You should add this line outside the loop because now, you're having 50 instance_number() checks again.
You should change this line
Code:
var size = min(ds_list_size(copper_list), 50);
to this
Code:
var size = min(ds_list_size(copper_list), 50)  - instance_number(obj_copper);
This way, there should be absolutely no way there are going to be more than 50 copper.
 
M

Midastouch

Guest
You should add this line outside the loop because now, you're having 50 instance_number() checks again.
You should change this line
Code:
var size = min(ds_list_size(copper_list), 50);
to this
Code:
var size = min(ds_list_size(copper_list), 50)  - instance_number(obj_copper);
This way, there should be absolutely no way there are going to be more than 50 copper.
Oh!, ok because with this line :
GML:
var size = min(ds_list_size(copper_list), 50);
I have an obj_copper on every cell = 1
 

Simon Gust

Member
Oh!, ok because with this line :
GML:
var size = min(ds_list_size(copper_list), 50);
I have an obj_copper on every cell = 1
Are you sure?
The loop should stop at whatever is smaller: 50 or the size of the list (if there are less than 50 cells found) then, if copper objects have existed before, the value will be deducted by the amount of copper instances beforehand.
 
M

Midastouch

Guest
Are you sure?
The loop should stop at whatever is smaller: 50 or the size of the list (if there are less than 50 cells found) then, if copper objects have existed before, the value will be deducted by the amount of copper instances beforehand.
Yes with this line
GML:
var size = min(ds_list_size(copper_list), 50);
Ihave an obj_copper on every cell = 1
 
M

Midastouch

Guest
Yes with this line
GML:
var size = min(ds_list_size(copper_list), 50);
Ihave an obj_copper on every cell = 1
i did a little debug code :
Code:
draw_text(10,100,"Width : " + string(ds_grid_width(grid_)));
draw_text(10,110,"height : " + string(ds_grid_height(grid_)));
draw_text(10,80,"Copper" + string(instance_number(obj_copper)))
width = 32
height = 18
obj_copper = the number change all the time around 1 number on the screen i can see this 147/148/147/148/147/148....

However if i put your first code in the create event i have 48 49 or 50 obj_copper
 
M

Midastouch

Guest
Make sure the code isn't in the step event, or else your room will fill up with copper very quick.
Ok can you explain me these lines please :
GML:
var pos = i | j << 16;
var pos = copper_list[| n];
var xx = pos & 65535;
var yy = pos >> 16;
 

Nidoking

Member
That's a clever way of storing two numbers in a variable that can only hold one number.

Let's suppose that you want to store the numbers 35 and 49 in a single variable. One way you could do it would be to store the number 3500049. The last five digits are the second number, and everything to the left of that is the first number. The operators here are doing the same thing with binary, storing the first number in the top 16 bits and the second number in the bottom 16 bits.
 

Simon Gust

Member
Yes, exactly. Because your grid is so small you could also work with
Code:
var pos = i | j << 8;
var pos = copper_list[| n];
var xx = pos & 255;
var yy = pos >> 8;
Or to make it look more friendly:
Code:
var pos = make_color_rgb(i, j, 0);
var pos = copper_list[| n];
var xx = color_get_red(pos);
var yy = color_get_green(pos);
As colors are just binary values consisting of a red, green and blue component.
 
Top