Hello,

In the video at 32:05 we can see the map drawn and the red area correctly showing where the memory is not used.

I can not understand how the drawing code knows how the rooms should be placed relative to each other (right/left or top/bottom). When we were storing the whole 128x128 block of memory for the chunks, I understand how we can figure out the relative position of each room, because this memory block is kind of rectangular and based on the offset of a value, whether it's an empty spot or a wall block, we can figure out visually where that block should be positioned.

But when the tiles are stored sparsely, the used memory block does not represent a rectangle anymore, so how do we know when the room should be drawn above another one or to the left of another one ?

The concept of tiles and tile chunks are separated things.

The game still allocates 128 * 128 tile chunks (handmade.cpp ~line 127), but those chunks don't allocate memory for tiles, unless you try to access the chunk.

Since you access chunk based on their chunk coordinates (x,y,z) you know where a chunk is relative to another, and by consequence you know which tile is where.

Conceptually the sparseness of the tile map didn't change anything in the memory layout.

struct tile_chunk
{
    /* Only a pointer to tiles (8 bytes). In the sparse version
       the tiles will only be allocated when accessed. */
    uint32 *Tiles;
};

struct tile_map {
    uint32 TileChunkCountX;
    uint32 TileChunkCountY;
    uint32 TileChunkCountZ;
    /* This still allocates 128 * 128 chunk, but a chunk is only
       a pointer to tiles (8 bytes on 64bit), not the actual tile
       memory. */
    tile_chunk *TileChunks;
}

/* Rendering */

uint32 ChunkCountY = TileMap.TileChunkCountY;
uint32 ChunkCountX = TileMap.TileChunkCountX;

for ( uint32 ChunkY = 0; ChunkY < ChunkCountY; ChunkY++ ) {
    for ( uint32 ChunkX = 0; ChunkX < ChunkCountX; ChunkX++ ) {

        uint32 ChunkOffset = ( ChunkY * ChunkCountX + ChunkX );
        tile_chunk* Chunk = TileMap.TileChunks + ChunkOffset;

        if ( chunk.Tiles ) {
            /* This chunk contains tiles */

            /* Assuming a chunk is 16 * 16 tiles */
            for ( uint32 TileY = 0; TileY < 16; TileY++ ) {
                for ( uint32 TileX = 0; TileY < 16; TileX++ ) {

                    uint32 AbsoluteTileX = ChunkX * 16 + TileX;
                    uint32 AbsoluteTileY = ChunkY * 16 + TileY;
                    uint32 TileValue = Chunk.Tiles + ( TileY * 16 + TileX );
                    ...
                }
            }
        }
    }
}

Thank you.

So We still allocate same 128x128, we just don't touch the parts of this 128x128 block until we actually need to put a value in a specific part of it. So the untouched parts are still 'taken' by us, but the memory is just zeroed, right ?

But aren't those 'zeroed' parts of this 128x128 block still kind of unavailable for us to store some other info, unrelated to tile map because if we wanted to use that zeroed memory for something, we would need to search for those zeroed regions and pack data in those, and that sounds kind of inconvenient.

So what is the actual gain of this kind of sparseness, if we still reserve the whole 128x128 region ?

A tile chunk is the concept of a group of tiles, in our case, a block of 16 * 16 tiles. But in practice, the tile_chunk structure is a single pointer to some memory where we store the tiles. So the size (in terms of bytes) of a tile chunk is the size of a pointer, which is 8 bytes on a 64 bit CPU.

We only allocated 128 * 128 tile_chunk, which means we allocate 128 * 128 * 8 bytes. After this allocation, no tiles are currently allocated.

When we will try to access the actual tiles of the chunk, than we will allocate memory for the tiles of that chunk, which is 16 * 16 * 4 (as a tile value is a uint32 which is 4 bytes).

So at startup we allocate 128 * 128 * 8 bytes (131 072 bytes). When we access a tile chunk for the first time we allocate it: 16 * 16 * 4 bytes (1024 bytes).

In the sparse version:

• Any chunk that isn't used only cost 8 bytes;
• Any used chunk cost 8 + (16 * 16 * 4) bytes (tile_chunk size + the size for the tiles) or 1032 bytes.

In the non sparse version any chunk (used or not) cost 8 + (16 * 16 * 4) bytes.

Schema of the memory:
c = tile_chunk structure
t = tile data (one t is 16 * 16 * 4)
o = any data unrelated to the tiles
0 = unused memory

At startup:
|000000000000000000000|
We push the tile chunk array
|cccc00000000000000000|
Any other part of the application pushes data
|ccccooo00000000000000|
We access a chunk, triggering the allocation for the tiles
|ccccooot0000000000000|
Any other part of the application pushes data
|ccccoootoooo000000000|
We access another chunk
|ccccoootoooot00000000|
...

In the non sparse version it was:
|cccctttttttttttttttttoooooooooo000000|

Thanks very mucho.

I understand it now.