Legacy GM Random terrain generator very slow

P

paulog

Guest
Hello! I'm thinking about adding a random terrain generator to my game, so I created an empty project to test some codes.

I managed to do something I like, but the problem is that it's somehow really slow.

I'll atach the code I used in the end of this post, but basically:

-There is a loop that fills the room with 10x10 tiles
-Each tile has a 50% chance of becoming grass or water
-If I press E, every grass tile that is surrounded by 4 water tiles or more, becomes a water tile
-If I press W, every water tile that is surrounded by 4 grass tiles or more, becomes a grass tile

If the room is 200x200 pixels or less the process is very fast, but as I increase the size, the process keeps getting slower. If the room is 1280x720 pixels, for example, it takes more than three seconds.

Is there a way to make this faster? Or that is just normal? Am I doing this the wrong way? If someone could help me I'd be very grateful. Thanks in advance!

Here is the code:

GML:
randomize()
for(xx = 10; xx <room_width - 5; xx += 10)
{
for(yy = 10; yy <room_height - 5; yy += 10)
{
instance_create(xx,yy,obj_tile)
}
}

GML:
space = choose(1,2,3,4)
if space >= 1 and space <= 2
{
instance_create(x,y,obj_grass)
}
if space >= 3 and space <= 4
{
instance_create(x,y,obj_sea)
}
instance_destroy()

GML:
if position_meeting(x,y-6,obj_sea)
{
csea+= 1
}
if position_meeting(x,y+6,obj_sea)
{
csea+= 1
}
if position_meeting(x-6,y,obj_sea)
{
csea+= 1
}
if position_meeting(x+6,y,obj_sea)
{
csea+= 1
}
if csea>= 4
{
instance_create(x,y,obj_sea)
instance_destroy()
}

GML:
if position_meeting(x,y-6,obj_grass)
{
cgrass+= 1
}
if position_meeting(x,y+6,obj_grass)
{
cgrass+= 1
}
if position_meeting(x-6,y,obj_grass)
{
cgrass+= 1
}
if position_meeting(x+6,y,obj_grass)
{
cgrass+= 1
}
if cgrass>= 4
{
instance_create(x,y,obj_grass)
instance_destroy()
}

All the sprites have the origin point in the center.
 
D

Deleted member 13992

Guest
Couple things. Place tiles, not instances, for terrain. Otherwise you're asking for trouble the larger the world gets. Other thing is to try and use seeds so that development runs are at least repeatable.
 

CloseRange

Member
well you used 10x10 tiles and that makes math much easier.
With a 1080 x 720 room you are iterating over 128 x 72 tiles, or 9216.
Each iteration performs 4 positions_meeting's and position_meeting is fairly slow.

To speed this up, store tiles in a 2d array and do a check on that instead. Getting position data from an array is very fast.
 
P

paulog

Guest
Couple things. Place tiles, not instances, for terrain. Otherwise you're asking for trouble the larger the world gets. Other thing is to try and use seeds so that development runs are at least repeatable.
But is there a way to check if a position is meeting with tiles just like with instances of objects?

well you used 10x10 tiles and that makes math much easier.
With a 1080 x 720 room you are iterating over 128 x 72 tiles, or 9216.
Each iteration performs 4 positions_meeting's and position_meeting is fairly slow.

To speed this up, store tiles in a 2d array and do a check on that instead. Getting position data from an array is very fast.
When you say tiles, you mean gamemaker tiles, or the objects that I'm creating that I'm calling tiles?
I never used arrays or ds grids before, so I did some research. I think I get how to store a tile location in a ds grid, but how can I check if it's coliding with another differente tile? Sorry for my ignorance.
 

CloseRange

Member
when I say tile i mean the concept of a tile in room generation. If you use game maker's tiles, objects, variables, arrays, or ds_maps to represent them, doesn't matter. They are all tiles in this case (or cells might be a better name)
GML:
/// Create Inital structure
size = 10; // size of cell
// get how many 'tiles' will fit in the room
wid = room_width div size;
hei = room_height div size;
for(var xx=0; xx < wid; xx++) {
    for(var yy=0; yy < hei; yy++) {
        data[xx][yy] = instance_create(xx*size, yy*size, obj_tile);
        data[xx][yy].pos_x = xx;
        data[xx][yy].pos_y = yy;
    }
}
GML:
/// [/SPOILER]tile create event
// instead of having a water object and grass object, use one object with a variable that determines the type of tyle
typeWater = 0;
typeGrass = 1;
type = choose(typeWater, typeGrass); // choose a random type
create a script for checking a tiles surrounding bits
GML:
/// scr_checkSurrounding(type);
var t = argument[0];
var o = obj_generator; // name of the object that ran the above code
// we do pos_x != 0 to ensure this tile isn't left boud, otherwise we will get an error
var l = pos_x != 0 && (o.data[pos_x-1][pos_y].type == t);
var r = pos_x != o.wid-1 && (o.data[pos_x+1][pos_y].type == t);
var u = pos_y != 0 && (o.data[pos_x][pos_y-1].type == t);
var d = pos_y != o.hei-1 && (o.data[pos_x][pos_y+1].type == t);
return l + r + u + d;
GML:
/// Check the surrounding tiles.
if(keyboard_check_pressed(ord("E")) && type == typeGrass) {
    if(check(typeWater) >= 4) type = typeWater;
}
if(keyboard_check_pressed(ord("W")) && type == typeWater) {
    if(check(typeGrass) >= 4) type = typeGrass;
}
as for drawing these tiles, you can either set the sprite_index based on what 'type' is set to, or you can do it in the draw event.
Persanolly I would remove the tile object all together and represent it all with variables in the obj_generate, but that's just a preference
 
Last edited:

Roldy

Member
If the room is 200x200 pixels or less the process is very fast, but as I increase the size, the process keeps getting slower.
Is there a way to make this faster? Or that is just normal?
Hi you seem to be asking a question about Asymptotic computational complexity.

Unless your algorithm runs in constant time, then yes it is normal for your algorithm to take more time as the input size grows. i.e. The more items you have to process then the more time the total process consumes. How much more depends on the algorithm.

If your algorithm runs in polynomial time then it is considered "good," if it does not run in polynomial time it is considered "bad." For some problems there are no good algorithms. And other problems have many good algorithms, which exact good algorithm to use can depend on alot of things.

Your creation algorithm runs in linear time. That is pretty good. Your 20x20 tile example processes 400 items. Your 128x72 tile example processes 9216 items. You should expect the 9216 item run to take ~23 times longer than the 400 item run.

Notice I didn't mention any exact times. Just a relative time. The actual amount of time will depend on what hardware it is run on, and what operation are being performed on each input item. Your computer takes 3 seconds for a long run. My computer might take 10 seconds, and John's computer might take 1 nanosecond. On a ten year old smart phone it might take an hour.

If your 400 items took 0.1 seconds the you can expect your 9216 items to take about 2.3 seconds.

Unless you can find an algorithm that is faster than linear (logarithmic) that solves the same problem, then your best option is to reduce the time the operations take for processing 1 item. If you can reduce the amount of time it takes to do 1 item you will be able to reduce the amount of time it takes to to 9216 items. But, if you use an algorithm with a linear runtime, 9216 items will always take at least 9216 times longer than the time it took to do 1 item.

When optimizing, first look for faster algorithms. If none are suitable then try to use faster or fewer operations. Good Luck.
 
Last edited:

rytan451

Member
@Roldy The algorithm in use is not linear. This being legacy GM, and there being collision checks per object, this is in fact quadratic time.

In order to speed up this process, you should probably store the terrain type in an array. So:

GML:
// Create event
// Constants: CHUNK_WIDTH = 128, CHUNK_HEIGHT = 128, WATER = 0, GRASS = 1

// Initialize terrain array
terrain_array = 0;
terrain_array[CHUNK_WIDTH - 1, CHUNK_HEIGHT - 1] = WATER;

terrain_sprites = 0;
terrain_sprites[1] = 0;

// You may wish to change these sprites as needed.
terrain_sprites[WATER] = spr_water;
terrain_sprites[GRASS] = spr_grass;

tile_width = sprite_get_width(spr_water);
tile_height = sprite_get_height(spr_water);


// Fill terrain array with 50% water, 50% grass
for (var _x = 0; _x < CHUNK_WIDTH; _x++) {
    for (var _y = 0; _y < CHUNK_HEIGHT; _y++) {
        terrain_array[_x, _y] = choose(WATER, GRASS);
    }
}

// Press w event
var row_above = 0;
row_above[CHUNK_WIDTH - 1] = WATER;

var grass_adjacent = 0;

for (var _y = 0; _y < CHUNK_HEIGHT; _y++) {
    for (var _x = 0; _x < CHUNK_WIDTH; _x++) {
        if (_x != 0) {
            if (row_above[_x - 1] == GRASS) {
                grass_adjacent += 1;
            }
        }
        if (_x != CHUNK_WIDTH - 1) {
            if (terrain_array[_x + 1, _y] == GRASS) {
                grass_adjacent += 1;
            }
        }
        if (_y != 0) {
            if (row_above[_x] == GRASS) {
                grass_adjacent += 1;
            }
        }
        if (_y != CHUNK_HEIGHT - 1) {
            if (terrain_array[_x, _y + 1] == GRASS) {
                grass_adjacent += 1;
            }
        }
        row_above[_x] = terrain_array[_x, _y];
        if (grass_adjacent >= 4) {
            terrain_array[_x, _y] = GRASS;
        }
    }
}

// Do something similar for the press e event

// Draw event

for (var _x = 0; _x < CHUNK_WIDTH; _x++) {
    for (var _y = 0; _y < CHUNK_HEIGHT; _y++) {
        // You may wish to add animations; in which case, add a looping counter for the image index.
        draw_sprite(terrain_sprites[terrain_array[_x, _y]], 0, x + _x * tile_width, y + _y * tile_height);
    }
}
This is a linear time algorithm. Furthermore, it is an algorithm with better than linear space usage (O(sqrt(N)) < O(N)) beyond the input data.

(Since this was written on the fly, within the forum text editor, this code may not work as-is. However, it should be possible to glean some useful insights from this code)
 

Roldy

Member
@Roldy The algorithm in use is not linear. This being legacy GM, and there being collision checks per object, this is in fact quadratic time.
I stated that his creation algorithm is linear, which it is.

GML:
randomize()
for(xx = 10; xx <room_width - 5; xx += 10)
{
for(yy = 10; yy <room_height - 5; yy += 10)
{
instance_create(xx,yy,obj_tile)
}
}
If legacy GM does not use some sort of spacial partitioning then yes his 'press e' 'press w' actions may be quadratic. But I left that unsaid, as the idea was for him to answer his own question. But I believe 1.4 GMS actively uses spatial partitioning for collision checks.
 
Last edited:
P

paulog

Guest
when I say tile i mean the concept of a tile in room generation. If you use game maker's tiles, objects, variables, arrays, or ds_maps to represent them, doesn't matter. They are all tiles in this case (or cells might be a better name)
GML:
/// Create Inital structure
size = 10; // size of cell
// get how many 'tiles' will fit in the room
wid = room_width div size;
hei = room_height div size;
for(var xx=0; xx < wid; xx++) {
    for(var yy=0; yy < hei; yy++) {
        data[xx][yy] = instance_create(xx*size, yy*size, obj_tile);
        data[xx][yy].pos_x = xx;
        data[xx][yy].pos_y = yy;
    }
}
GML:
/// [/SPOILER]tile create event
// instead of having a water object and grass object, use one object with a variable that determines the type of tyle
typeWater = 0;
typeGrass = 1;
type = choose(typeWater, typeGrass); // choose a random type
create a script for checking a tiles surrounding bits
GML:
/// scr_checkSurrounding(type);
var t = argument[0];
var o = obj_generator; // name of the object that ran the above code
// we do pos_x != 0 to ensure this tile isn't left boud, otherwise we will get an error
var l = pos_x != 0 && (o.data[pos_x-1][pos_y].type == t);
var r = pos_x != o.wid-1 && (o.data[pos_x+1][pos_y].type == t);
var u = pos_y != 0 && (o.data[pos_x][pos_y-1].type == t);
var d = pos_y != o.hei-1 && (o.data[pos_x][pos_y+1].type == t);
return l + r + u + d;
GML:
/// Check the surrounding tiles.
if(keyboard_check_pressed(ord("E")) && type == typeGrass) {
    if(check(typeWater) >= 4) type = typeWater;
}
if(keyboard_check_pressed(ord("W")) && type == typeWater) {
    if(check(typeGrass) >= 4) type = typeGrass;
}
as for drawing these tiles, you can either set the sprite_index based on what 'type' is set to, or you can do it in the draw event.
Persanolly I would remove the tile object all together and represent it all with variables in the obj_generate, but that's just a preference
Your insights were very useful! The speed of the terrain generation is now much much faster. Thank you! You were right also about the tile object being unnecessary, I removed it and it also made things a bit faster.

Hi you seem to be asking a question about Asymptotic computational complexity.

Unless your algorithm runs in constant time, then yes it is normal for your algorithm to take more time as the input size grows. i.e. The more items you have to process then the more time the total process consumes. How much more depends on the algorithm.

If your algorithm runs in polynomial time then it is considered "good," if it does not run in polynomial time it is considered "bad." For some problems there are no good algorithms. And other problems have many good algorithms, which exact good algorithm to use can depend on alot of things.

Your creation algorithm runs in linear time. That is pretty good. Your 20x20 tile example processes 400 items. Your 128x72 tile example processes 9216 items. You should expect the 9216 item run to take ~23 times longer than the 400 item run.

Notice I didn't mention any exact times. Just a relative time. The actual amount of time will depend on what hardware it is run on, and what operation are being performed on each input item. Your computer takes 3 seconds for a long run. My computer might take 10 seconds, and John's computer might take 1 nanosecond. On a ten year old smart phone it might take an hour.

If your 400 items took 0.1 seconds the you can expect your 9216 items to take about 2.3 seconds.

Unless you can find an algorithm that is faster than linear (logarithmic) that solves the same problem, then your best option is to reduce the time the operations take for processing 1 item. If you can reduce the amount of time it takes to do 1 item you will be able to reduce the amount of time it takes to to 9216 items. But, if you use an algorithm with a linear runtime, 9216 items will always take at least 9216 times longer than the time it took to do 1 item.

When optimizing, first look for faster algorithms. If none are suitable then try to use faster or fewer operations. Good Luck.
That is very interesting, thank you for the information. I'll surely be aggregating this thinking on my next codes.
You may be right. It might be an option in 1.4 that has to be turned on. And in GMS2 it is on by default.
That's right. I turned it on and it also helped me with speed a little.
 
Top