GameMaker [Solved] Growing Forest Performance Issues

Papa Doge

Member
Hello,

I'm woking on a feature where trees left unchecked grow into a massive forrest. I have two working versions right now but both have performance issues once I get to around 100 trees.

I need some advice on how to fix one of my versions or something new to try.

/* ------------------------------------------------- */

VERSION 1

Description:
Each tree object has a variable called "seeding", that when true initiates a FOR loop that checks the 4x4 space around the tree looking for an available 32x32 cell to drop a single seed. If a cell is found, it is added to a ds_stack where a separate object does the work of planting each seed using a LIFO queue.

/* ------------------------------------------------- */

VERSION 2

Description:
Each tree object has a variable called "seeding", that when true accesses a local "count" variable that starts in cell position 0 (top left) and checks to see if a seed can be placed in that location. If that space is available, the coords are added to a ds_stack where a separate object does the work of planting each seed using an LIFO queue. If there is no space, the tree waits for the next germination to begin and then checks cell 1 and so on until a space is found.

/* ------------------------------------------------- */

FULL SET OF CODE

obj_germinator:
Contains all my timers for when trees should seed and grow

CREATE EVENT
Code:
/// @description 

/* -------------------- */

// Debugging
debugging = false;

// Germination
time_germinating = 0;
time_to_germinate = 540;
growth_rate = 1;

// Sprouting
time_sprouting = 0;
time_to_sprout = 320;
sprout_rate = 1;

// Seeding
ds_stack_seeds = ds_stack_create();
STEP EVENT
Code:
/// @description 

/* -------------------- */
#region Germinating
/* -------------------- */

scr_debugging("Time germinating is " + string(time_germinating));

time_germinating = APPROACH(time_germinating, time_to_germinate, growth_rate);
if (time_germinating == time_to_germinate) {
    time_germinating = 0;
    with (obj_tree) {
        if (obj_tree.sprouting == false) {
            seeding = true;   
        }
    }
}

/* -------------------- */
#endregion
/* -------------------- */

/* -------------------- */
#region Sprouting
/* -------------------- */

time_sprouting = APPROACH(time_sprouting, time_to_sprout, sprout_rate);
if (time_sprouting == time_to_sprout) {
    with(obj_tree) {
        if (sprouting == true) {
            stage++;   
        }
    }
    time_sprouting = 0;
}

/* -------------------- */
#endregion
/* -------------------- */

/* -------------------- */
#region Seeding
/* -------------------- */

if (ds_exists(ds_stack_seeds, ds_type_stack)) {
   
    if (ds_stack_size(ds_stack_seeds) > 0) {
        var seed_coordinates = ds_stack_pop(ds_stack_seeds);
        var seed_x = seed_coordinates[0];
        var seed_y = seed_coordinates[1];
        instance_create_depth(seed_x, seed_y, -seed_y, obj_tree);   
    }

}
obj_tree:
The individual instances of trees in the room that wait until the germinator says it's time to seed and then perform their seeding check.

Code:
/* -------------------- */
#region Seeding
/* -------------------- */

if (seeding == true) {
    scr_debugging("Trying to drop seeds here...");
   
    scr_seeding_check();
   
    seeding = false;

}
/* -------------------- */
#endregion
/* -------------------- */
scr_seeding_check version 1:

Code:
// Add available space as cell coordinates in a temp table
var ds_list_spaces = ds_list_create();

var xx = x1;
var yy = y1;
var free_space;
var count = 0;

for (var i=0; i<(rows*columns); i++) {
   
    free_space = scr_tile_check_germination(xx, yy);

    if (free_space == true) {
        ds_list_spaces[| count] = [xx, yy];
        count++;
        show_debug_message("Adding to the list position " + string(i));
    } else {
        show_debug_message("Something in the way at position " + string(i));   
    }
       
    xx += cell_size;
   
    if (xx == x2) {
        xx = x1;
        yy += cell_size;
    }
       
}

// Randomly select one of the cells and place a single seed
//var num_spaces = ds_list_size(ds_list_spaces);

if (count > 0) {
   
    var lifo_queue = obj_germinator.ds_stack_seeds;
    var random_space = floor(clamp(random(count), 0, count - 1));
    show_debug_message("Number of spaces is " + string(count) + " and random space set to " + string(random_space));
    var seed_coords = ds_list_spaces[| random_space];
    ds_stack_push(lifo_queue, seed_coords);
   
}

// Destroy the list to free u memory
ds_list_destroy(ds_list_spaces);[/B]
scr_seeding_check version 2:
Code:
// Check current position for avaiable space
var free_space;
free_space = scr_tile_check_germination(xx, yy);

// If we can seed here add these coords to the germinator's stack
if (free_space == true) {
   
    var seed_coords = [xx, yy];
    var lifo_queue = obj_germinator.ds_stack_seeds;
    ds_stack_push(lifo_queue, seed_coords);
   
    show_debug_message("Added seed coords to the stack");   
   
} else {
   
    show_debug_message("Something in the way at position " + string(count));   
   
}

// Increment the seeding position and count
xx += cell_size;
count++;
   
if (xx == x2) {
    xx = x1;
    yy += cell_size;
}

if (count == count_max) {
    count = 0;
    xx = x1;
    yy = y1;
}
[/B]

scr_tile_check_germination:

This little script is checking the specific attributes of the tile our tree wants to drop a seed in. Trees need to be planted on grass/dirt and cannot grow on top of other kinds of grounded objects like the ones in the list. This simply returns true or false if a seed can go here.

Code:
/// @ desc scr_tile_check_germination(x,y)
/// @arg x
/// @arg y

// Script that takes a specific point in the game grid and
// returns true if it has avaiable space for a tree to grow
// and false if it does not.

// CREATE REFERENCES FOR TILE DATA
var layer_grass_and_dirt =    layer_get_id("Terrain_land"); 
var map_grass_and_dirt =    layer_tilemap_get_id(layer_grass_and_dirt); 
var layer_rocks =            layer_get_id("Terrain_rocks");
var map_rocks =                layer_tilemap_get_id(layer_rocks); 
var layer_water =            layer_get_id("Terrain_water"); 
var map_water =                layer_tilemap_get_id(layer_water); 
var layer_mountains =        layer_get_id("Terrain_mountains"); 
var map_mountains =            layer_tilemap_get_id(layer_mountains);

// STRUCTURES AND OBSTANCLES TO CHECK FOR
var has_structure =        position_meeting(argument0+cell_size/2,argument1+cell_size/2,obj_structures_parent); 
var has_enemy =            position_meeting(argument0+cell_size/2,argument1+cell_size/2,obj_enemy_parent); 
var has_soil =            position_meeting(argument0+cell_size/2,argument1+cell_size/2,obj_soil); 
var has_portal =        position_meeting(argument0+cell_size/2,argument1+cell_size/2,obj_portal);
var has_player =        place_meeting(argument0+cell_size/2,argument1+cell_size/2,obj_player_parent);
var has_barrier =        position_meeting(argument0+cell_size/2,argument1+cell_size/2,obj_barriers_parent); 
var has_sentry =        position_meeting(argument0+cell_size/2,argument1+cell_size/2,obj_sentry_parent); 
var has_environment =    position_meeting(argument0+cell_size/2,argument1+cell_size/2,obj_environment_parent); 

// PERFORM THE CHECKS
var origin_seedable        = tilemap_get_at_pixel(map_grass_and_dirt,argument0,argument1);
var origin_unseedable    = tilemap_get_at_pixel(map_rocks,argument0,argument1) 
                        + tilemap_get_at_pixel(map_water,argument0,argument1) 
                        + tilemap_get_at_pixel(map_mountains,argument0,argument1)
                        + has_structure
                        + has_enemy
                        + has_soil
                        + has_portal
                        + has_player
                        + has_barrier
                        + has_sentry
                        + has_environment
                        ;

// If there is anything in this cell that would prevent us from building...
var seedable_tile;

if    (origin_seedable != 0) && (origin_unseedable == 0) { 
    seedable_tile = true;
} else { 
    seedable_tile = false; 
}

// RETURN THE RESULTS
return seedable_tile;
/* ------------------------------------------------- */

Version 2's results are quite bad. I could make it better but selecting a cell at random to check instead of moving through the 4x4 space serially, but that still won't fix my performance issues. I had assumed that the FOR loop in version 1 was the culprit, but even with that loop removed in version 2 I still see significant hang when I have a lot of trees doing checks at once.

I was hoping my stack approach would fix this but it seems the issue is somewhere else and I'm having a hard time wrapping my head around the problem space and honestly my code at this point.

As always, any and all help is greatly appreciated.
 

Simon Gust

Member
I see you are working with cells for your trees and objects. Why not create a cell based structure instead of doing exspensive collision checks?
No matter how well you optimize scr_seeding_check, the next script scr_tile_check_germination will always be your downfall.

You can set up an array or a ds grid and store information there. You may as well leave the objects in and store their ids in there.
Code:
global.cell = 0;

var w = room_width / cell_size;
var h = room_height / cell_size;

for (var i = w; i >= 0; i--) {
for (var j = h; j >= 0; j--) {
    global.cell[i, j] = noone;
}}
Every instance you create will lookup it's position divided by cell_size inside global.cell and plant it's id in there.
If you've got multiple instances per cell, you can store a list or an array of ids in there as long as you keep it persistent.

Then you do not have to call collision functions per object but only per id, causing no slowdown no matter how many instances you've got.
 

Papa Doge

Member
Thanks for your reply @Simon Gust

I've read your proposal a few times now and I think I understand in general terms what you are saying but I'm still missing something.

The problem you see is that my script "scr_til_check_germination" is taking in the center point of a cell and then running 12 collision checks for a single cell times the 16 cells we need to check resulting in 192 collision checks per object per step, and that's what's causing everything to hang and eventually crash when I have 100+ objects.

That definitely makes sense.

I used to have a system that sort of looks like what you are describing as part of an obj_grid object for enemy AI:

STEP EVENT
Code:
room_w    = room_width;
room_h    = room_height;
columns    = room_w div cell_size;
rows    = room_h div cell_size;

// Create a grid...
global.grid = mp_grid_create(0,0,rows*2,columns*2,cell_size,cell_size); // So create the grid for enemies to find targets...

// Add the instances...
mp_grid_add_instances(global.grid,obj_obstacles_parent,false);
mp_grid_add_instances(global.grid,obj_enemy_frustrations,false);
I tried using this code for my enemies so they find the quickest path to the player while avoiding obstacles but their movement wasn't organic enough so I abandoned it.

Is your proposal suggesting I do something like this? What is meant by "Then you do not have to call collision functions per object but only per id"? Are you saying I should have a obj_grid object that declares a global array that stores the id of every object instance inside a cell and then my obj_tree simply needs to check if said global cell array contains any values at a specific cell location?
 

NightFrost

Member
I would say two basic problems there are how you're defining every tree as an object, and run collision checks for seed drops. I would define the terrain as 2d data structure grid, and each tree as an array or list of data stored in a master array or list. The biggest reason why you'd want trees as objects is movement collision checks, but if everything is grid-aligned then you only need to check the 2d terrain grid for passable terrain (creature vs creature collisions would still be object collisions as creatures are not grid aligned).
 

Papa Doge

Member
Hmmm. I'm still not understanding exactly but I took some of the advice above and tried to modify my system accordingly.

I think ya'll are right 100% when you say that the expensive object collision checks are my issue so I tried to think of a creative solution around that problem with some of the stuff you said above.

I ended up designing an "elder tree" that I place in the level that uses a timer to know when it should create spores. Right now I have it create two spore objects every time the timer is up. Those spores travel away from the elder tree at a variable direction and speed. I might actually want to animate this but for now it's just an invisible spore object.

The spore object has a variable called "air_time" which determines how long it stays in the air before landing. When it's time to land, I use my expensive scr_tile_check_germination script once based on the grid position of the spore. I get the grid position with the setup suggested by @Simon Gust

Here's what the step event for the spore object looks like:

Code:
/// @description 

/* -------------------- */

// Increase flight time
air_time = APPROACH(air_time, air_time_max, 1);
scr_debugging("Spore " + string(id) + " here with an elder id of " + string(elder_id) + " moving at an angle of " + string(direction) + " at a speed of " + string(speed));

// Plant a seed if there's space for it
if (air_time == air_time_max) {
    var grid_column        = x div cell_size;
    var grid_row              = y div cell_size
    var plant_x                = grid_column * cell_size;
    var plant_y                = grid_row * cell_size;
   
    var free_space = scr_tile_check_germination(plant_x, plant_y);
   
    if (free_space = true) {
        with(instance_create_depth(plant_x, plant_y, -plant_y, obj_tree)) {
            elder_id = other.elder_id;   
        }
    } else {
        scr_debugging("Spore couldn't land because there's something here...");   
    }
   
    instance_destroy();
   
}
So the spore plants a seed if there's space and the right kind of terrain and then promptly destroys itself.

I kind of like this system and I just let it run with profiler to see how much of a hit it has on performance and am pretty satisfied with the results. I have all kinds of interesting gameplay ideas about this elder tree too, like maybe if the player kills it all the children die. I haven't really decided yet but that's why I'm passing the "elder_id" from elder tree to spore to regular tree so I know where all these trees originated.

Anyways, thanks for the help.
 

TheouAegis

Member
Thanks for your reply @Simon Gust

I've read your proposal a few times now and I think I understand in general terms what you are saying but I'm still missing something.

The problem you see is that my script "scr_til_check_germination" is taking in the center point of a cell and then running 12 collision checks for a single cell times the 16 cells we need to check resulting in 192 collision checks per object per step, and that's what's causing everything to hang and eventually crash when I have 100+ objects.
Each tree object has a variable called "seeding", that when true initiates a FOR loop that checks the 4x4 space around the tree looking for an available 32x32 cell to drop a single seed. If a cell is found, it is added to a ds_stack where a separate object does the work of planting each seed using a LIFO queue.
I'm trying to picture this here. A 4x4 space around something?

0 1 2 3
4 5 6 7
8 9 A B
C D E F

Where does the tree's cell go? For something to be around the tree, shouldn't it be an odd number?

0 1 2
3 T 5
6 7 8

Then the "12 collision checks" suggests it's set up like

0 1 2 3
4 T T 7
8 T T B
C D E F

But whatever the case, working with cells instead of collisions is still viable. If the trees don't need to be individualized, then you just check if a neighboring cell isn't occupied by a T (tree). If it's a 2x2 tree, then you check if the cells neighboring that new cell are available.

If the trees need to be individualized, you could maybe get by with storing their timers in the cells. Then every step just loop through the entire data structure counting down cells and when the value in the cell reaches 0, reset it and attempt to seed a neighboring cell.


Regardless, if your elder tree setup is working satisfactorily, congrats and just run with that for now. :banana:
 
Top