Grid based system - Nested grids and lists

Discussion in 'Advanced Programming Discussion' started by Anthony@DiversionKit, Nov 17, 2018.

Tags:
  1. Anthony@DiversionKit

    Anthony@DiversionKit Member

    Joined:
    Nov 17, 2018
    Posts:
    12
    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: Nov 17, 2018
  2. sylvain_l

    sylvain_l Member

    Joined:
    Sep 18, 2016
    Posts:
    705
    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.?
     
    Yal and Anthony@DiversionKit like this.
  3. Anthony@DiversionKit

    Anthony@DiversionKit Member

    Joined:
    Nov 17, 2018
    Posts:
    12
    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: Nov 18, 2018
  4. Simon Gust

    Simon Gust Member

    Joined:
    Nov 15, 2016
    Posts:
    3,086
    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.
     
    Anthony@DiversionKit likes this.
  5. Anthony@DiversionKit

    Anthony@DiversionKit Member

    Joined:
    Nov 17, 2018
    Posts:
    12
    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)
     
  6. Yal

    Yal Member GMC Elder

    Joined:
    Jun 20, 2016
    Posts:
    3,389
    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.
     
  7. Anthony@DiversionKit

    Anthony@DiversionKit Member

    Joined:
    Nov 17, 2018
    Posts:
    12
    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.
     
    Yal likes this.
  8. Yal

    Yal Member GMC Elder

    Joined:
    Jun 20, 2016
    Posts:
    3,389
    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.
     
    nesrocks likes this.
  9. Anthony@DiversionKit

    Anthony@DiversionKit Member

    Joined:
    Nov 17, 2018
    Posts:
    12
    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.
     
  10. Simon Gust

    Simon Gust Member

    Joined:
    Nov 15, 2016
    Posts:
    3,086
    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.
     
    Ido-f and Gzebra like this.
  11. Anthony@DiversionKit

    Anthony@DiversionKit Member

    Joined:
    Nov 17, 2018
    Posts:
    12
    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.
     

Share This Page

  1. This site uses cookies to help personalise content, tailor your experience and to keep you logged in if you register.
    By continuing to use this site, you are consenting to our use of cookies.
    Dismiss Notice