Grid based system - Nested grids and lists

A

Anthony@DiversionKit

Guest
Hi everyone,

I'm new here on the forums, but I have been reading a lot. Thank you for being such an helpful community. Please be patient, I'm not that much familiar with Gamemaker.


I have been trying for a few days to figure out a grid system for an exploration/city building game prototype.

world.png

The exploration part means that the player is represented on the map and freely moves around a generated world made of regions, chunks, and tiles.

The city building part means that each tile needs to have a properties ( type, resource generation, sprite, etc) that can be modified and accessed. Building is done by getting the coordinates of the tile the mouse is in, and modifying the corresponding tile.

multitile_building.png

For a building that is bigger than a tile, there is an origin tile. The origin tile and the surrounding tiles are modified to assemble the building.


But let's talk about the grid system


In my previous version I created chunks with a DSgrid and each chunk was its own object. But it did not work well for buildings that are in multiple chunks.

So I tried to design a more reliable grid system that does no need objects for everything, and this is what I came with, but I don't know if this is feasible:

grid system.png

In this system, properties are nested and use a system of coordinates:

coordinates.png


multi_chunk_building.png

and so for example, to build this building, I would need to edit (removing the intermediate lists for clarity):
  • (bottom-left) tile[3,2] ; chunk[25,12] ; area[1,1]
  • (bottom-right) tile[0,2] ; chunk[26,12] ; area[1,1]
  • (top-left) tile[3,1] ; chunk[25,12] ; area[1,1]
  • (top-right) tile[0,1] ; chunk[26,12] ; area[1,1]
And I would calculate these coordinates from the origin point : If the origin point is at an extremity of a line or column, use the next chunk, and first tile of line or column.


As for the generation itself, I would create all the grids at the generation of the world, then fill them when needed (radius around the player).

I am worried though, because that is a grid per tile + a grid per chunk + a grid per region.
For a world that is 16 regions, with regions that are 16 chunk large, with chunks that are 16 tiles large, with tiles that are 64px large:
  • REGIONS - 16x16 grid (256 positions)
  • in each position a list
  • CHUNKS - in each list a 16x16 grid (256 positions)
  • in each position a list
  • TILES - in each list a 16x16 grid (256 positions)
  • in each position a list
Totaling :
  • REGIONS - 1 16x16 grid
  • 256 lists
  • CHUNKS - 256 16x16 grids
  • 65 536 lists
  • TILES - 65 536 16x16 grids
  • 16 777 216 lists
  • and 262144x262144 room size
I do not plan to use them all at once, I plan to only fill areas around the player and I want to save unused and inactive tiles/chunks/regions to get them back only when needed. But 17 millions empty grids and lists that still seems like a LOT. But at the same time, there will never be more than a dozen objects on the map.

An easy way would be a small map like old Zeus and Cleopatra game. But I'll be loosing the exploration aspect of the idea.

I wonder if some of the final steps need to be buffers instead of grids and lists. (Probably both chunk and tile level) But I also like the operations possible with grids as it can be really helpful for generating the terrain.

I also thought of bigger grids with two of the size level inside, It is probably a good way to avoid having too many grids.

But wonder if I can get the same unified coordinates system with those.
Which is my bigger concern.


I think this could work, but I do not have enough experience in Gamemaker to know if this is the right way to do it.

So I'm asking the community:
  • What do you think of this way to generate the world (concept)
  • Do you think it would work in Gamemaker (1.4) (feasibility)
  • In terms of optimization, (given that I plan to save in a file and delete inactive tiles/chunks/regions) is this too many grids ?) (optimization)
  • Would you be interested in the progress of the project (follow-up)
 
Last edited by a moderator:

sylvain_l

Member
  • 16 777 216 lists
that's not much or thats a lots; depends what you store there.
if its 1 basic int64; it's just 64Mb of data you could still store all of that in RAM without the hassle of dealing with all your file writing reading chuncking . Chance that your tileset for drawing that is going to use much more ram/vram than that.
if instead its 1k of int64 (or anything of same size in memory); that's 64Gb that's start to be big; even on a SDD :p

as long as you don't define clearly your data requirement/constraint that's a lot of brain power used in vain. Because for me that's kind the opposite, you get your data&memory constraint/pb (if you have one!) and from there you build your solution (chunking system) not the opposite.

honestly what kind of data are you going to store at the 16x16 tiles level or at the higher level in your sytem hierarchy.?
 
A

Anthony@DiversionKit

Guest
that's not much or thats a lots; depends what you store there.
if its 1 basic int64; it's just 64Mb of data you could still store all of that in RAM without the hassle of dealing with all your file writing reading chuncking . Chance that your tileset for drawing that is going to use much more ram/vram than that.
if instead its 1k of int64 (or anything of same size in memory); that's 64Gb that's start to be big; even on a SDD :p

as long as you don't define clearly your data requirement/constraint that's a lot of brain power used in vain. Because for me that's kind the opposite, you get your data&memory constraint/pb (if you have one!) and from there you build your solution (chunking system) not the opposite.

honestly what kind of data are you going to store at the 16x16 tiles level or at the higher level in your sytem hierarchy.?
Thank you for your reply.
I am not familiar with the scale of memory things so this is very helpful. I'm probably thinking too much ahead.

From what I understand of nested grids/lists, it just stores the index(random number) of the nested list as a value ?

So apart from the first value that would be the index of the nested grid, I was planning to have only numbers, like 0-255. Because I have no parameter that would need more than 255 different options. I guess the system will take that into account. And have those number correspond to something elsewhere to prevent having to store the same strings of text for nothing.

I think that tiles lists will never have more that 50-60 parameters. Most of them 0s because they will be unused. And higher lists even less : the grid index + 10-20 parameters.
Grids themselves will only contain the lists index.


So in the end 17 000 000 x 60 x whatever size a 0-255 number is (3bytes?) + all the indexes?

If it's not that much I can maybe even push to pseudo infinite map.


EDIT:
This is the first draft of the world code that generates the full map at once without any concerns for loading radius.

(debug says 28500.0k of memory used)

Bigger map will slow down startup of the game or even run out of memory.

The system will definitely need generation and deletion of chunks on demand because of the size I aim for.

Code:
//basic units
world_width=4;  //in regions
world_height=4;
region_load_radius=1;

region_width=4; //in chunks
region_height=4;
chunk_load_radius=2;

chunk_width=16;  //in tiles
chunk_height=16;

tile_width=64;   //in pixels
tile_height=64;


//calculate room size
room_width=world_width*region_width*chunk_width*tile_width;
room_height=world_height*region_height*chunk_height*tile_height;


/* world structure */

//create the world grid
global.world_grid= ds_grid_create(world_width,world_height);
ds_grid_set_region(global.world_grid,0,0,world_width,world_height,noone);

//region level
var i;
var j;
for (i=0; i<world_width ; i++)
for (j=0; j<world_height ; j++)
        {
        //create list
        region_parameters = ds_list_create();

   
        //create grid
        chunk_grid = ds_grid_create(region_width,region_height);      
        //chunk level
        var ii;
        var jj;
        for (ii=0; ii<region_width ; ii++)
        for (jj=0; jj<region_height ; jj++)
                {
                //create list
                chunk_parameters = ds_list_create();

                //create grid
                tile_grid = ds_grid_create(chunk_width,chunk_height);
                //tile level
                var iii;
                var jjj;
                for (iii=0; iii<chunk_width ; iii++)
                for (jjj=0; jjj<chunk_height ; jjj++)
                        {
                        //create list
                        tile_parameters = ds_list_create();

                        //fill parameters inside grid
                        ds_list_set(tile_parameters,0,noone);
                   
                        //fill list inside grid
                        ds_grid_set(tile_grid,iii,jjj,tile_parameters);
                        }
       
                //fill parameters inside grid
                ds_list_set(chunk_parameters,0,tile_grid)
           
                //fill list inside grid
                ds_grid_set(chunk_grid,ii,jj,chunk_parameters);  
                }
   
        //fill parameters inside grid
        ds_list_set(region_parameters,0,chunk_grid)
   
        //fill list inside grid
        ds_grid_set(global.world_grid,i,j,region_parameters);
        }
 
Last edited by a moderator:

Simon Gust

Member
But 17 millions empty grids and lists that still seems like a LOT
It is a lot actually.
A grid or a list (or any data structure for that matter) takes way more memory than a single int64.
I ran a test and 17 million empty lists (only lists) take up 1.5 GB.
A buffer instead will also take a good 1.5 GB.
Also an array in array takes 1.5 GB memory.
->
I end up getting an out of memory error, so it might be even more than 1.5 GB.

As you see, just to maintain a data structure you need a ton of memory.

So, either you offload to the hard drive or you use a method called bitmasking instead of lists.
A single bitmask will only ever take 4 or 8 bytes no matter what.
You can only effectively store ints though.
 
A

Anthony@DiversionKit

Guest
It is a lot actually.
A grid or a list (or any data structure for that matter) takes way more memory than a single int64.
I ran a test and 17 million empty lists (only lists) take up 1.5 GB.
A buffer instead will also take a good 1.5 GB.
Also an array in array takes 1.5 GB memory.
->
I end up getting an out of memory error, so it might be even more than 1.5 GB.

As you see, just to maintain a data structure you need a ton of memory.

So, either you offload to the hard drive or you use a method called bitmasking instead of lists.
A single bitmask will only ever take 4 or 8 bytes no matter what.
You can only effectively store ints though.
Thank you for your reply Simon,

I can confirm that it's a real problem, the maximum I'm able to do right now is around 67000 (256x256 tiles map), So yeah, 17 millions of lists may be too much :)

I wasn't aware of bitmasking, this could really be helpful in this case. I can see you wrote a tutorial on the matter, maybe I can figure out how that works.

I think I'm going to do a bit of both: storing unloaded regions and chunks on the disk, and bitmasking at the last level (the one that basically creates most of the lists)
 

Yal

🐧 *penguin noises*
GMC Elder
I'm thinking the natural approach would be having a single grid based on a single tile, and use arrays instead of ds_grids (they've got less overhead and are garbage-collected) but of course it stops being feasible if you want really big worlds.... I think arrays can be 320k elements max, and max 100k wide/tall, but those limits may have increased now (read about them in the GM8.1 manual).

What's cool about arrays is that they're garbage-collected and can be instance-local, so you could have instances that represent a region and keep track of the contents in their data... you could let them process changes in their region using an alarm to spread out processing (instances could set their alarm to different times based on how far away they are, processing every step if they're on-screen and every second if they're off-screen, etc, and when you destroy an instance its memory is freed.

If you wanna use data structures you create and destroy a lot, keep in mind that their IDs may be reused. Each structure has an unique ID, but the ID of a destroyed structure can get reused at any time... just checking if an ID exists doesn't mean you got the right one, so remember to do bookkeeping to keep track of whether any given structure is valid or not.
 
A

Anthony@DiversionKit

Guest
I'm thinking the natural approach would be having a single grid based on a single tile, and use arrays instead of ds_grids (they've got less overhead and are garbage-collected) but of course it stops being feasible if you want really big worlds.... I think arrays can be 320k elements max, and max 100k wide/tall, but those limits may have increased now (read about them in the GM8.1 manual).

What's cool about arrays is that they're garbage-collected and can be instance-local, so you could have instances that represent a region and keep track of the contents in their data... you could let them process changes in their region using an alarm to spread out processing (instances could set their alarm to different times based on how far away they are, processing every step if they're on-screen and every second if they're off-screen, etc, and when you destroy an instance its memory is freed.

If you wanna use data structures you create and destroy a lot, keep in mind that their IDs may be reused. Each structure has an unique ID, but the ID of a destroyed structure can get reused at any time... just checking if an ID exists doesn't mean you got the right one, so remember to do bookkeeping to keep track of whether any given structure is valid or not.
Thank you for your comment Yal,

I didn't know about all of that. Using instances this way opens a lot of possibilities, indeed. I will definitely think about it.

That's going to take some experimentation to find the best way to do it, and to create the right mix of elements at the right level.

Thank you.
 
  • Like
Reactions: Yal

Yal

🐧 *penguin noises*
GMC Elder
I still wish GM had data objects and named user-defined events (like, say, C++), then things like this would always be easier with object methods :p

BTW, have you considering using GM tiles for your tiles? They're optimized for being on a grid and being fast to draw.
 
A

Anthony@DiversionKit

Guest
I still wish GM had data objects and named user-defined events (like, say, C++), then things like this would always be easier with object methods :p

BTW, have you considering using GM tiles for your tiles? They're optimized for being on a grid and being fast to draw.
Maybe we can start a lobbying campaign for inclusion in version 3 :p

At the moment I haven't thought too much about the drawing part. I just loop through every tile and draw according to the random tile assigned at generation and use draw_sprite. The tile type, sprite, and subimage being some of the parameters that I store in the list that I fill at world/chunk creation.

The advantage of my current system is that, since I define the basic units (tile size, chunk size) and everything is relative to them, I have no problem problem with the drawing to find the real coordinates from the position in the grid, and also changing the size of each unit if needed.

I guess this is not the fastest method and that a tile background might be better ?

I can see some advantage because I will need to draw some tiles on top of others for variety, and I can probably just add a condition in the loop for that.
 

Simon Gust

Member
Maybe we can start a lobbying campaign for inclusion in version 3 :p

At the moment I haven't thought too much about the drawing part. I just loop through every tile and draw according to the random tile assigned at generation and use draw_sprite. The tile type, sprite, and subimage being some of the parameters that I store in the list that I fill at world/chunk creation.

The advantage of my current system is that, since I define the basic units (tile size, chunk size) and everything is relative to them, I have no problem problem with the drawing to find the real coordinates from the position in the grid, and also changing the size of each unit if needed.

I guess this is not the fastest method and that a tile background might be better ?

I can see some advantage because I will need to draw some tiles on top of others for variety, and I can probably just add a condition in the loop for that.
Be warned that Game Maker cannot handle a whole screen full of draw sprite commands. Sure, buildings don't have to be 1x1 cell size but you have to assume the worst case scenario.

The built-in tiles can do that much more efficiently. It's going to chunk your fps but it's bearable in GM:S 1.4.
in GM:S 2, it would be no question that tiles could do that.

Since you're already using chunks in your project I advise you to use vertex buffers. 1 vertex buffer per chunk that is.

Vertex buffers are filled with draw-data and are incredibly fast to draw, especially when their frozen.
Once a vertex buffer is filled, it only has to be submitted.
The difficulty is that they have to be filled, which isn't exactly a fast process. Each time you want to change something you have to redo the whole vertex buffer. So keep your chunks small but not too small to minimize the total amount of vertex buffers drawn at the same time.
 
A

Anthony@DiversionKit

Guest
Be warned that Game Maker cannot handle a whole screen full of draw sprite commands. Sure, buildings don't have to be 1x1 cell size but you have to assume the worst case scenario.

The built-in tiles can do that much more efficiently. It's going to chunk your fps but it's bearable in GM:S 1.4.
in GM:S 2, it would be no question that tiles could do that.

Since you're already using chunks in your project I advise you to use vertex buffers. 1 vertex buffer per chunk that is.

Vertex buffers are filled with draw-data and are incredibly fast to draw, especially when their frozen.
Once a vertex buffer is filled, it only has to be submitted.
The difficulty is that they have to be filled, which isn't exactly a fast process. Each time you want to change something you have to redo the whole vertex buffer. So keep your chunks small but not too small to minimize the total amount of vertex buffers drawn at the same time.
Thank you for your advice.

I really like the idea of having it set once and change it only when needed. That was the kind of thing I was looking for.
 
Top