How would you go about placing objects between chunks in a 2D game?

Question

I have a 2D infinitely generated world which is split up into 9 chunks at a time. Three chunks are loaded and three are unloaded whenever a player moves into a new chunk (if the player moves up a chunk the top three chunks are loaded and the bottom three are unloaded so there's always 8 chunks surrounding the player, pretty standard). My chunks are stored as 16x16 2D arrays so I loop through the array of chunks and then through each dimension of the array to access tiles.

In my game the player can place buildings and other various things which are technically groups of tiles that take up a few spaces on the grid. The issue I'm having is knowing how to refer to adjacent chunks as to whether or not the object should be allowed to be placed.

If the player is trying to place an object within the boundaries of a single chunk this is fine and works great because I can check the tiles within that chunk easily. However when checking across chunk boundaries (worst case 4 different chunk arrays) things because incredibly complicated and bug prone.

How I'm managing it right now:

The player is trying to place a 4x4 tiled building on the boundary of ChunkArray[1,1] (always the chunk under the player, as ChunkArray[2,2] makes up 9 chunks) and ChunkArray[2,1] (the chunk directly to the right of the player.

If the 4x4 building overlaps directly down the center of the boundary, lets say ChunkArray[1,1][15,5] and ChunkArray[1,1][15,6] (two adjacent tiles, one above the other on the right side of main chunk) and therefore ChunkArray[2,1][0,5] and ChunkArray[2,1][0,6] (same thing but on left side of adjacent chunk) then I'm checking to see if those tiles in the chunk to the right are clear and the tiles in the chunk under the player are clear.

You can see how this would become hellish when dealing with objects which are even larger than 4x4 or even worse if they overlap 4 different chunks at the same time.

I also thought about treating all 9 chunks relative the player as a super-chunk and combining all the chunks into one large array which would make placing objects much easier, although I haven't really processed how realistic this would be as loading/unloading and rearranging the super chunk every time a player moved between chunks could be insane.

Is there some obvious solution I'm missing?

Answer 1

Abstract chunks!

You probably have a class handling these chunks, have it be the source of truth for your world, mine is called WorldHandler, I tell it to read from position x,y and it transparently gets the chunk I need and uses it.

class ChunkHandler { // this is our "WorldHandler"
    private int[,] _chunks = new Chunk[ 16, 16 ];
    // Use a dynamically allocated array instead for memory flexibility / performance

    // Uses a global tile position to set data into the correct chunk
    public void set( int x, int y, int data ) {
        // Can be simplified if you don't have negative positions
        int cx = Math.Floor( (float) x / 16.0f );
        int cy = Math.Floor( (float) y / 16.0f );

        const chunk = this.getChunk( cx, cy );

        // Gives the chunk the relative position
        this.chunk.set( x - cx * 16, y - cy * 16, data );
    }

    // Gets the chunk 
    public void getChunk( int cx, int cy ) {
        // Check if the chunk exists and is functional before returning it
        if ( ! _chunks[ cx ][ cy ].exists ) {
            // Initialize the chunk into memory because we might need it
            _chunks[ cx ][ cy ].init();
        }
        return _chunks[ cx ][ cy ];
    }
}

Then you don't need to think about Chunks anymore, they are abstracted and isolated from your game world:

class Chunk {

    int[,] _blocks = new int[ 16, 16 ];
    // Again, dynamically allocated structures are better

    // Sets a relative position tile data in this chunk
    public void set( int x, int y, int data ) {
        // You probably have something more complicated here
        _blocks[ x ][ y ] = data;
    }
}

If chunk lookup is hard (it generally isn't), you could add a cache of 'last-accessed-chunk' at your World Handler class.

Here's an example with a 4-tile-aligned chunk:

  +4  +5  +6  +7   +8  +9  +10  +11
|----------------|-----------------|
|              X | X               |
|              X | X               |
|      C+0       |        C+1      |
|                |                 |
|----------------|-----------------|

I can transparently access position like so:

world.get(7, 0) == "X" // top left, accesses first chunk
world.get(8, 0) == "X" // top right, accesses second chunk
world.get(7, 1) == "X"
world.get(8, 1) == "X"

The idea behind this abstraction is that a placement of a multi-tile object doesn't need to be aware of how the world is layed out, that problem should be solved by a specific class.

And if you happen to store these multi-blocks objects as an object with x and y instead of in-world tiles, you could store a list of chunks that it is present to load conditionally only when all these chunks are loaded into the screen (or load it partially if any of these chunks are loaded). You could even create a class just to handle this saving of multi-block structures in your world, something like WorldMultiTileMemory.

By the way the names I provide are suggestions, I might not be the best at naming things.

If you're interested you can read more about decoupling patterns here.

Answer 2

I'm not sure what does a chunk actually contain in your implementation. I assume that these chunks are memory intensive, if you want to lazily load them. It seems to me that if you decoupled your logic from game engine content, you could easily load to memory and check a lot of grid spaces at the same time. This will require you to keep some kind of sparse container that will remember what each grid space logically contain, but that shouldn't be too complex. looping though 4 16x16 containers is at most 1024 operations, which is very little, assuming the repeated operation is quick.

For example, just for the sake of the current issue, you could cache which chunks contain things with a container of bools, and check the container in order to check whether the relevant chunks are filled, without loading the actual chunks to memory.