Most CPU Efficient/Fastest Method for Recording 1000s of Instances to "Grid"

I'm planning on making a spawning/despawning system. Because the initial data grab is likely increase lag/load time to start the level I need to know the fastest way of grabbing whether a desired object (or it's child) is at grid intervals and 4-5 of it's user made variables. The lists must be ordered so I can increment through it later to check what's at the correct spot to be spawned or despawned.

My current idea is to use collision_point to check for the desired object then record what's at the position and some variables if the correct object's there. Then loop through x recording as I go until the x range of the gird is full then increment the y loop and reset the x loop. When the y range of the grid in complete everything would be recorded. I think I might need multiple lists for the 4-5 user variables of the instances too.

What's the fastest method? Should I use: ds_grids, or 2-d arrays, or buffers, or something else to do this? Will the choice make a substantial speed difference here?

Where is the bottleneck most like in the above described method?


P.S: I'm not sure I understand how to step through buffers so tell me if that would be fastest to collect, but also best alternative.
 

TheouAegis

Member
Grid intervals is
x div grid_width * grid_width
y div grid_height * grid_height
Or if width and height are powers of 2, it's
x & ~(grid_width - 1)
y & ~(grid_height - 1)

Are you talking about saving stuff like in a level designer? Or are you saving stuff like in a city simulator? In either case, I mean, you could use the same method. Just use a WITH loop to ad all the data to a buffer or array to save the data, then a FOR loop when you load the data back in. This would need to be modified if you are going to implement instantaneous auto-saving, but still the same.

I personally wouldn't use a ds_grid, but to each their own. I prefer one-dimensional data structures like buffers. If I knew my data sizes and needed to write the data to a file, I'd use a buffer, otherwise an array would suffice

If you use a buffer, make it buffer_grow and set its size to 1 before filling it.

So just use
with(parent of objects you need saved){ and then save the object_index, x div grid_width, y div grid_height, and whatever variables you need saved from that object. Those variables should all have the same name between objects, even if they function differently. Some people like to just have an array of all stats and then you can use enumerators in each object to help you remember what each stat is used for.

When you need to load the data back up, just loop through the buffer and create new instances. The first chunk of data will be the object_index, the next will be the x coordinate which you multiply by grid_width, then y coordinate which you multiply by grid_height, then each of the variables in order. Just set the buffer position to 0 once and use a series of buffer_read() inside the loop to load the buffer data.

As for bottlenecks in your considerations, collision checking is your biggest bottleneck. Kiss thousands off your fps right there. Using ds_grids is slow, but not really bottlenecking slow. If you are comfortable with accessors, grids are probably easier to work with than buffers, because in general, reading and writing ds_grids is similar to arrays. Buffers are tedious to code - like, copy & paste for your sanity's sake tedious - but when handled correctly run nearly as fast as 2D arrays with easy saving & loading.

The nice thing about the buffer method and using buffer_grow, you can just append new data to the buffer without having to rewrite the entire thing. This method doesn't work so well of the user can destroy things, which would require rewriting the entire buffer, but that's just a small hiccup.

If instances can be moved around the grid and you have auto-saving, you should save the buffer addresses that point to an instance's coordinates inside each instance and have the instance update those coordinates when moved. That way you don't have to rewrite the entire buffer if just one or two instances moved.

If you can only have one instance per grid cell, then you can shrink the data pool a little by using buffer_fixed and setting the buffer size to how many cells there are in the grid multiplied by the number of stats you need to save plus one. So if your grid was 8x8 like a chessboard and each instance had 5 stats, you'd set the buffer size to 8*8*6. Since everything would now have its own grid cell, you don't need to save x and y coordinates. Instead, you'd use x and y coordinates to find the address in the buffer to write to. ...Personally, I'd probably still stick with growing buffer, since poking or seeking a buffer address is slow.
 
Last edited:
Grid intervals is
x div grid_width * grid_width
y div grid_height * grid_height
Or if width and height are powers of 2, it's
x & ~(grid_width - 1)
y & ~(grid_height - 1)

Are you talking about saving stuff like in a level designer? Or are you saving stuff like in a city simulator? In either case, I mean, you could use the same method. Just use a WITH loop to ad all the data to a buffer or array to save the data, then a FOR loop when you load the data back in. This would need to be modified if you are going to implement instantaneous auto-saving, but still the same.

I personally wouldn't use a ds_grid, but to each their own. I prefer one-dimensional data structures like buffers. If I knew my data sizes and needed to write the data to a file, I'd use a buffer, otherwise an array would suffice

If you use a buffer, make it buffer_grow and set its size to 1 before filling it.

So just use
with(parent of objects you need saved){ and then save the object_index, x div grid_width, y div grid_height, and whatever variables you need saved from that object. Those variables should all have the same name between objects, even if they function differently. Some people like to just have an array of all stats and then you can use enumerators in each object to help you remember what each stat is used for.

When you need to load the data back up, just loop through the buffer and create new instances. The first chunk of data will be the object_index, the next will be the x coordinate which you multiply by grid_width, then y coordinate which you multiply by grid_height, then each of the variables in order. Just set the buffer position to 0 once and use a series of buffer_read() inside the loop to load the buffer data.

As for bottlenecks in your considerations, collision checking is your biggest bottleneck. Kiss thousands off your fps right there. Using ds_grids is slow, but not really bottlenecking slow. If you are comfortable with accessors, grids are probably easier to work with than buffers, because in general, reading and writing ds_grids is similar to arrays. Buffers are tedious to code - like, copy & paste for your sanity's sake tedious - but when handled correctly run nearly as fast as 2D arrays with easy saving & loading.

The nice thing about the buffer method and using buffer_grow, you can just append new data to the buffer without having to rewrite the entire thing. This method doesn't work so well of the user can destroy things, which would require rewriting the entire buffer, but that's just a small hiccup.

If instances can be moved around the grid and you have auto-saving, you should save the buffer addresses that point to an instance's coordinates inside each instance and have the instance update those coordinates when moved. That way you don't have to rewrite the entire buffer if just one or two instances moved.

If you can only have one instance per grid cell, then you can shrink the data pool a little by using buffer_fixed and setting the buffer size to how many cells there are in the grid multiplied by the number of stats you need to save plus one. So if your grid was 8x8 like a chessboard and each instance had 5 stats, you'd set the buffer size to 8*8*6. Since everything would now have its own grid cell, you don't need to save x and y coordinates. Instead, you'd use x and y coordinates to find the address in the buffer to write to. ...Personally, I'd probably still stick with growing buffer, since poking or seeking a buffer address is slow.
If I use with() how do I keep it ordered so I can look up and spawn what's in the region of the grid that corresponds to being on screen? I know how that works with while{} to form an ordered ds_grid or array, but how do you do that using with()?

Is there anything I can do about the collision checking bottleneck? If the time spent here is 100 to 1 over the data organizing method (buffer, array, ds_grid, ect) then should I just choose the one easiest for me to work with, or could this choice cut the time down by at least a fifth (or ideally half)?
 

TheouAegis

Member
Once an instance moves outside the on-screen region, what do you do with it? If you are destroying them, okay we've got some changes to make. If you're just deactivating them or leaving them to their own devices, then it doesn't matter what order they are loaded from the grid.

So is there one instance per cell or are the instances going to be overlapping each other and sometimes occupying more than one cell? If it's one instance per cell, then write the object_index and stats to the data structure (buffer, array, ds_grid, whatever) at the appropriate address based on whatever coordinates each instance is at -- still using with() to loop through all the instances. Then when it comes time to load the data, you should know what cells are visible on screen, so jump to the address in the data structure that corresponds to he top-left cell on-screen and start looping through the data structure. If you are going to be loading instance data from the data structure over and over rather than just at the start of the room, then you should use an array since array reading is significantly faster than any other data structure. If you used a buffer to save and load the data, then copy the buffer contents into the array so that you can use the array thenceforth.

On the other hand, if you're going to be loading instances at the start of the room (which makes it pointless to worry about who's on-screen anyway), then you can just check if the coordinates of the instance being loaded are within the screen's area. If not, go to the next instance in the data structure.

Another idea is you could loop through everyone and dump their id into a priority queue with y+x*room_height being their priority rating, then pop each id off the priority queue to fill the save data in order.

Some considerations don't need to be, um, considered depending on what you're actually doing. Is this for saving a currently played game, like a city builder or those survival games where you have to build a base of operations? If so, save everything in any order and load it all in any order. Is this for a player-generated level editor? If so, again there's not much harm in just saving everything and then loading everything at once. If on the other hand this is for a separate level editor or something for you or your developers to use, then saving and laoding structure could definitely be an important consideration. If the data is meant to be used as an included file and loaded incrementally based on the player's actions/experience, then saving speed is not a consideration -- it comes out of your own time, not the player's -- and the saved data needs to be organized based on coordinates.

The main reason I'm not pushing ds_grids at all is because you are trying to save 5 or more variables per cell. A ds_grid used with each cell in the ds_grid corresponding to each cell in the room grid would only allow you to save one variable per cell. If you used the ds_grid to store object_index, x, y, and the other variables on an instance-per-row basis, then you're just using the slowest data structure to do what could just as easily be done with a much-faster array or slightly-faster buffer. NOW, I will grant that you could utilize a ds_grid in the same way I brought up utilizing priority queues. Since ds_grids have a sort, you can combine the x and y coordinates for each instance and save that value in the ds_grid along with the other variables you need to save, then sort whichever column you put the combined coordinates in. If you think that might be easier for you, then go ahead and use it that method.

But stay away from collision functions. That's one bottleneck you can and should easily avoid.
 
Once an instance moves outside the on-screen region, what do you do with it? If you are destroying them, okay we've got some changes to make. If you're just deactivating them or leaving them to their own devices, then it doesn't matter what order they are loaded from the grid.

So is there one instance per cell or are the instances going to be overlapping each other and sometimes occupying more than one cell? If it's one instance per cell, then write the object_index and stats to the data structure (buffer, array, ds_grid, whatever) at the appropriate address based on whatever coordinates each instance is at -- still using with() to loop through all the instances. Then when it comes time to load the data, you should know what cells are visible on screen, so jump to the address in the data structure that corresponds to he top-left cell on-screen and start looping through the data structure. If you are going to be loading instance data from the data structure over and over rather than just at the start of the room, then you should use an array since array reading is significantly faster than any other data structure. If you used a buffer to save and load the data, then copy the buffer contents into the array so that you can use the array thenceforth.

On the other hand, if you're going to be loading instances at the start of the room (which makes it pointless to worry about who's on-screen anyway), then you can just check if the coordinates of the instance being loaded are within the screen's area. If not, go to the next instance in the data structure.

Another idea is you could loop through everyone and dump their id into a priority queue with y+x*room_height being their priority rating, then pop each id off the priority queue to fill the save data in order.

Some considerations don't need to be, um, considered depending on what you're actually doing. Is this for saving a currently played game, like a city builder or those survival games where you have to build a base of operations? If so, save everything in any order and load it all in any order. Is this for a player-generated level editor? If so, again there's not much harm in just saving everything and then loading everything at once. If on the other hand this is for a separate level editor or something for you or your developers to use, then saving and laoding structure could definitely be an important consideration. If the data is meant to be used as an included file and loaded incrementally based on the player's actions/experience, then saving speed is not a consideration -- it comes out of your own time, not the player's -- and the saved data needs to be organized based on coordinates.

The main reason I'm not pushing ds_grids at all is because you are trying to save 5 or more variables per cell. A ds_grid used with each cell in the ds_grid corresponding to each cell in the room grid would only allow you to save one variable per cell. If you used the ds_grid to store object_index, x, y, and the other variables on an instance-per-row basis, then you're just using the slowest data structure to do what could just as easily be done with a much-faster array or slightly-faster buffer. NOW, I will grant that you could utilize a ds_grid in the same way I brought up utilizing priority queues. Since ds_grids have a sort, you can combine the x and y coordinates for each instance and save that value in the ds_grid along with the other variables you need to save, then sort whichever column you put the combined coordinates in. If you think that might be easier for you, then go ahead and use it that method.

But stay away from collision functions. That's one bottleneck you can and should easily avoid.
By using with() I'd avoid collision checking then? If I do this how do I put them in order then so that they occupy the correct place in a grid or array and don't go outside it's range. A grid can start at other places than x=0 or y=0, and can end before room_height or room_width, or be the whole thing divided by the cell size. The grid would always start at grid space intervals though. I also need to destroy the object instances entered in the grid once grabbed then spawn only the ones on screen. How much time would destroying them eat up, and is there another faster way?

My plan was this. Instance data would be grabbed at room begin, then destroyed, then spawned if in a region that would be on screen. If their region becomes off-screen again they would be destroyed while being marked in the grid as despawned by one of the variables kept in the grid. Then if the their region comes onscreen again they'd be created again and marked as being spawned in it. This is why order is important so I only spawn things in the screen region. Creating it if it's not marked as spawned at the moment by the grid. I think the objects could destroy themselves if outside the region and update the grid to say they're despawned. This would dramatically reduce the number of objects in a room, I'd use it on the most plentiful objects, though it wouldn't work on objects that move around independently, or enter many different states that 4 or 5 variables couldn't keep track of.
 

TheouAegis

Member
Priority queue them before filling a data structure.
Another idea is you could loop through everyone and dump their id into a priority queue with y+x*room_height being their priority rating, then pop each id off the priority queue to fill the save data in order.
You don't need to destroy instances or load and unload. You can just deactivate them when they leave the view.
 
Priority queue them before filling a data structure.


You don't need to destroy instances or load and unload. You can just deactivate them when they leave the view.
I tried deactivation a while ago, but it didn't seem efficient enough to deal with 1000s of instances without a bunch of lag. I figured this would be a lot faster, at least after the initial gather of the grid.
 

TheouAegis

Member
Did you deactivate all and activate in region? Or did you activate all and deactivate outside region? Or did you deactivate outside region and activate in region? I don't remember which, but one is faster than the others.

Destroying instances and creating new ones may be smoother, but not without its own weight to bear. On top of looping through whatever data structure you use (for reading), you will also have instance_destroy() and destroy event handling, as well as instance_create_layer(), instance creation handling (by GM), and create event handling. You'd have to fully implement it in order to properly speed test it, as its effectiveness is as situational as deactivation.

What do you mean a grid can start and end at any coordinates and be any size? Does the grid itself move? What EXACTLY are you working on? A grid of limited size is normal; that's what a chess board is, and a grid not at (0,0) is normal; that's how a lot of board games are handled, since being at (0,0) is kinda ugly, but a moving grid is a new concept for me. The closest thing I can think of to what you are describing is a game like Populous or , but even that would still be just normal view handling with a twist.


For grids not at (0,0) you subtract the grid's starting point from the instance's coordinates before converting them to cells. So if your grid starts at (8,8), then an instance at (18,25) would effectively be at (10,17 ) in the grid; if the grid is 16x16, the instance would be in cell [0,1] then.

For grids not going the full size of the room, that's only a consideration when working with 1D data structures and figuring out when not saving coordinates.

I don't understand how something that was in the grid at one point could at another point be outside the grid, since you wouldn't add instances that can exist outside the grid to the data structure.

What stats are going to need to be saved? You should only be saving stats that can change independent of the other stats or any external variables (e.g., Pokemon doesn't save 1/3 of the stats because they are not independent). If some will have 6 stats and others will have 4 stats, give them all 6 stats - 2 wasted stats is reasonable.

And if inventories are a consideration, that's a whole new post.
 
Did you deactivate all and activate in region? Or did you activate all and deactivate outside region? Or did you deactivate outside region and activate in region? I don't remember which, but one is faster than the others.

Destroying instances and creating new ones may be smoother, but not without its own weight to bear. On top of looping through whatever data structure you use (for reading), you will also have instance_destroy() and destroy event handling, as well as instance_create_layer(), instance creation handling (by GM), and create event handling. You'd have to fully implement it in order to properly speed test it, as its effectiveness is as situational as deactivation.

What do you mean a grid can start and end at any coordinates and be any size? Does the grid itself move? What EXACTLY are you working on? A grid of limited size is normal; that's what a chess board is, and a grid not at (0,0) is normal; that's how a lot of board games are handled, since being at (0,0) is kinda ugly, but a moving grid is a new concept for me. The closest thing I can think of to what you are describing is a game like Populous or , but even that would still be just normal view handling with a twist.


For grids not at (0,0) you subtract the grid's starting point from the instance's coordinates before converting them to cells. So if your grid starts at (8,8), then an instance at (18,25) would effectively be at (10,17 ) in the grid; if the grid is 16x16, the instance would be in cell [0,1] then.

For grids not going the full size of the room, that's only a consideration when working with 1D data structures and figuring out when not saving coordinates.

I don't understand how something that was in the grid at one point could at another point be outside the grid, since you wouldn't add instances that can exist outside the grid to the data structure.

What stats are going to need to be saved? You should only be saving stats that can change independent of the other stats or any external variables (e.g., Pokemon doesn't save 1/3 of the stats because they are not independent). If some will have 6 stats and others will have 4 stats, give them all 6 stats - 2 wasted stats is reasonable.

And if inventories are a consideration, that's a whole new post.
Using the included deactivation in the past I deactivated all then activated by region, and activate a few needed objects that must exist to deal with player stats. I repeat the process per frame.

I just meant the grid won't always start it's capture at the x = 0, y = 0 position in the room. It might be worth adding the ability to offset grid region lookup after grabbing the data if I decide I want the instances in the grid to sometimes move like a parallaxing background though.

Thanks for pointing me to with(). I'll definitely look into using with() instead of collision point checking when I have time to actually do this. I thought checking a single point per instance wouldn't take too much time, but I guess with a lot of instances it can still be slow.

What's fastest way to check for a specific object in an x,y range using with()?
Would this be fastest?

with(spawned_obj)
{
if x>=grid_x_begin and x<=grid_x_end
and y>=grid_y_begin and y<=grid_y_end
{
//would add to grid here if all is true
}
}
 
Last edited:
Top