Advertisement

2D tilemaps "Chunk Theory".

Started by February 06, 2014 11:46 PM
8 comments, last by Jakob Krarup 10 years, 11 months ago

Hello!

I'm looking to get as much theory as possible on this subject, I have a hobby project i'm working on: a 2D orthographic game which i have used the standard tile grid array technique to render in XNA. But would like to implement dynamic loading of groups of tiles (chunks) so i can implement larger worlds then a standard grid.

The part of the theory i most understand is when the camera, or object gets close to the edge of a chunk the new one is loaded in the direction the camera is traveling and the chunk behind is unloaded. I guess the theory is to have an array that tracks chunks, then another array inside the chunk to track tiles?

Things I don't understand:

  • Loading an adjacent chunk that "lines up" with the old one.
  • Best way to "signal" a new chunk should be loaded.
  • General Implementation details

I would like to heavy research this topic as i want it to be a center point of any other 2d games i make in the future.

So i welcome any and all recommended:

  • Books
  • Tutorials
  • Videos

And of course code snippets and comments would be very valuable to me. (most proficient with XNA)

Thanks.

Edit: (Also had another question on general tile maps, should i ask here or start a new thread)?

Loading an adjacent chunk that "lines up" with the old one.


What don't you understand specifically?

Each chunk is a fixed size (e.g., every chunk is 64x64 tiles, or whatever size you decide to use) and intended to be put in a fixed place in the layout of chunks. That is, the chunk at (1,3) is directly left of the chunk at (2,3). The top row of tiles of one is horizontally adjacent to the top row of tiles on the other.

If you represent tile positions with a single (x,Y) pair then you get the chunk by dividing each component by the chunk width and the position of the tile within that chunk is the remainder of that division. Going again with 64x64 chunks, the tile at world position (127,561) is in chunk (127/64,561/64)=(1,8) and the local position of the tile within that chunk is (127%64,561%64)=(63,49).

Best way to "signal" a new chunk should be loaded.


When the camera distance to the edge of the chunk become smaller than some distance D1, load it. When the distance becomes larger than some other distance D2 (with D2>D1), unload it. Generally you pick D1 such that the load time of a chunk is less than the time it takes for the player to travel the distance D1 so that the chunk is fully loaded up by the time the player can see it. To avoid hitches related to loading, you'll probably want to do at least the I/O portion in a background thread (assuming you don't have easy asynchronous I/O in your language/framework of choice).

General Implementation details


This is an incredible broad one.

One issue to be aware of is that using a naive position for objects like a single global (X,Y) tile position is going to limit the size of your world more than you might like. Such a coordinate can only get so big. There's really no way to realistically give you a truly infinite world, but you do need to apply some thought regarding the size you want to allow. There's a lot of good text online about the size limitations of a 32-bit float, and the size limitations of a 32-bit int are pretty easy to derive.

There are two related approaches to solving this issue (they can even be combined to solve two different aspects of the problem). The first is to split your global position up into two indpendent coordinate pairs (GlobalChunkX,GlobalChunkY) and (LocalTileX,LocalTileY). If the local tile coordinate hits the edge of the chunk size, reset it and increment/decrement the global chunk. e.g.,

if (LocalTileX >= 64)
{
  LocalTileX -= 64;
  GlobalChunkX += 1;
}
Genericizing the code to handle configurable chunk sizes, both coordinates, and both directions is left as an exercise. smile.png

The second approach is to localize coordinates. This is a bit difficult as it affects many parts of your codebase and requires some coordinate between the different parts (though with cleverness you can decouple them somewhat). The idea here is to keep all your global coordinates relative to the center of the camera or some other moving point that remains close to the camera. One option is to make every global coordinate relative to the chunk overlapping the center or upper-left-corner of the camera. In this way the coordinates do not grow without bound; as the player heads left/west, the coordinates constantly reset to be near 0,0 as chunks scroll by. Any coordinates saved to disk can be saved relative to some other position.

One final issue coming to mind is how you know which chunk to load. If you have a big 2D array of all chunks, that array itself is going to be potentially quite large. A better approach is a sparse array. This can be implemented by taking the global position of a chunk (its X,Y coordinate) and using that or a hash of it as a key. The disk layout could be that every chunk saved to disk has the filename X_Y.chunk or some hexadecimal name based on the hash of the (X,Y) coordinate. If you use the hash approach, note that to deal with collisions you'd still want the X_Y part in the filename, e.g. AE6F780D_12_57.chunk. An advantage here is that if you have a lot of chunks you can deal with folder size limitations by breaking up the hash into a folder hierarchy, e.g. the previous becomes AE/6F/78/0D/12_57.chunk.

You'll also want to experiment with chunk size. Too big or too small will cause efficiency and management issues. It's very hard to give advice here without just profiling/measuring your implementation. You should avoid hard-coding a chunk size and make it a value you can change (at compile time is fine). That doesn't mean you need to support worlds with arbitrary chunk sizes at runtime, just make sure you can tweak the value during development until you find something comfortable.

Sean Middleditch – Game Systems Engineer – Join my team!

Advertisement

This is my very simple attempt at drawing a single chunk, Its probably horribly inefficient and "incorrect" lol


public class Game1 : Game
    {
        //Chunksize
        int width = 10;
        int height = 10;

        //tilesize
        int tSize = 64;

        GraphicsDeviceManager graphics;
        SpriteBatch spriteBatch;

        public static Texture2D texture;

        //Chunks
        chunk[] ChunkArray = new chunk[5];

        //Tile
        public class tile
        {
            public Texture2D texture;
        }

        //chunk
        public class chunk
        {
            public tile[,] tiles;

            public chunk()
            {
                this.tiles = new tile[5, 5];
                BuildChunk();
            }

            public void BuildChunk()
            {
                for (int x = 0; x < 5; x++)
                {
                    for (int y = 0; y < 5; y++)
                    {
                        this.tiles[x, y] = new tile();
                        this.tiles[x, y].texture = Game1.texture;
                    }
                }

            }

        }
        private void addChunkToArray()
        {
            ChunkArray[0] = new chunk();
        }

        public Game1()
            : base()
        {
            graphics = new GraphicsDeviceManager(this);
            Content.RootDirectory = "Content";
        }


        protected override void Initialize()
        {
            // TODO: Add your initialization logic here

            base.Initialize();
        }


        protected override void LoadContent()
        {
            // Create a new SpriteBatch, which can be used to draw textures.
            spriteBatch = new SpriteBatch(GraphicsDevice);
            texture = Content.Load<Texture2D>("tile.png");
            addChunkToArray();
            // TODO: use this.Content to load your game content here
        }

        protected override void UnloadContent()
        {
            // TODO: Unload any non ContentManager content here
        }

        protected override void Update(GameTime gameTime)
        {
            base.Update(gameTime);
        }

        protected override void Draw(GameTime gameTime)
        {
            GraphicsDevice.Clear(Color.CornflowerBlue);

            spriteBatch.Begin();

            //foreach (var chunk in ChunkArray)
            for (int ci = 0; ci < ChunkArray.Length; ci++)
            {
                {
                    if (ChunkArray[ci] != null)
                    {
                        foreach (var tile in ChunkArray[ci].tiles)
                        {
                            for (int y = 0; y < height; y++)
                            {
                                for (int x = 0; x < width; x++)
                                {
                                    spriteBatch.Draw(tile.texture, new Rectangle(x * 64, y * 64, tSize, tSize), Color.White);
                                }
                            }
                        }
                    }
                }
                spriteBatch.End();
                base.Draw(gameTime);
            }
        }
    }
}

My next goal was to set up another chunk to the right of that one using the array, but it seems from your post that i should pretty much reevaluate the whole theory?

Assuming the map can expand in four directions, you might have a grid of 9 chunks, much like a Tic-Tac-Toe board, loaded into memory at once (if you are only moving in one direction, vertically or horizontally, then 3 or 5 would be a better number). The chunk in which the player currently resides is always at the center. When the player crosses the boundary into another chunk, then you would unload one column or row and load a new one depending on the direction the player moved.

For example, say the player moves north into the chunk directly above the center one. Now, you unload the entire bottom row (three chunks). The center row now becomes the bottom row, the top row now becomes the center row, and you load three new chunks to fill in the top row. If diagonal movement is disallowed, you could simplify it to 5 chunks - the middle, N, S, E and W. You're still loading and unloading the same number of chunks, just in a different pattern. But I'd still go with 9 myself.

You'll want a decent chunk size for this, though. If the chunks are too small, you'll be loading more frequently unless you adapt the algorithm a bit.

Assuming the map can expand in four directions, you might have a grid of 9 chunks, much like a Tic-Tac-Toe board, loaded into memory at once (if you are only moving in one direction, vertically or horizontally, then 3 or 5 would be a better number). The chunk in which the player currently resides is always at the center. When the player crosses the boundary into another chunk, then you would unload one column or row and load a new one depending on the direction the player moved.

For example, say the player moves north into the chunk directly above the center one. Now, you unload the entire bottom row (three chunks). The center row now becomes the bottom row, the top row now becomes the center row, and you load three new chunks to fill in the top row. If diagonal movement is disallowed, you could simplify it to 5 chunks - the middle, N, S, E and W. You're still loading and unloading the same number of chunks, just in a different pattern. But I'd still go with 9 myself.

You'll want a decent chunk size for this, though. If the chunks are too small, you'll be loading more frequently unless you adapt the algorithm a bit.

Yes, I understand that in theory, and that's what i'm trying to accomplish but its the implementation theory that's my problem.

If I have a chunk that is 50x50 tiles big, The player/camera gets to local tile 30,0 and wants to load the next chunk(next set of 50x50 tiles), How do i know where to start drawing the next chunk?

If I have a chunk that is 50x50 tiles big, The player/camera gets to local tile 30,0 and wants to load the next chunk(next set of 50x50 tiles), How do i know where to start drawing the next chunk?


How is your camera set up? How big are your tiles in pixels (or what is your camera scale) ? You should be able to trivially map the camera position to a visual (pixel?) position within the chunk, which you then just subtract from the chunk's visual width to find out the dimensions of the screen bounding box of the chunk. That is then easily used to find the draw location of each adjacent chunk.

If your camera is set up sensibly than you're really going to be working in units of tiles, e.g. each tile is 1x1 in-game units, and the camera scales those units when rendering to get the actual on-screen size you want. All the math for determining bounding boxes becomes super simple then. You can find out if the chunk is within the screen or goes past the screen by putting it through the camera pipeline/matrix (taking you from world space or units of 1 tile to camera space or normalized [-1,+1] coordinates mapping to the screen bounds) and then checking if the bounds exceed [-1,+1].

Sorry, I don't feel I'm explaining this super well. Hopefully someone else with a better ability to illustrate math will step in and help.

Sean Middleditch – Game Systems Engineer – Join my team!

Advertisement

Hi Mellkor smile.png

A similar question popped up on the Microsoft XNA forums a while back, and I posted some graphics to visualize the theory and a code sample with class diagram.

(scroll down to "I found some time yesterday, and coded a framework for making infinite worlds.")

I hope it will prove useful to you smile.png

Kind regards - Jakob

www.xnafan.net - tutorials, tools and code samples for making games :)

Hi Mellkor smile.png

A similar question popped up on the Microsoft XNA forums a while back, and I posted some graphics to visualize the theory and a code sample with class diagram.

(scroll down to "I found some time yesterday, and coded a framework for making infinite worlds.")

I hope it will prove useful to you smile.png

Kind regards - Jakob

Thanks mate! ill have take a look over the drawings and code.

( I am working on a similar problem in Java )

From what I am reading - small "chunk" groups need to be saved as a separate map files, and loaded into memory off screen to reduce "lag".

However the more I think about it - wouldn't constantly opining and closing files cause system strain ?

How the hay does MineCraft do it ?

I cannot remember the books I've read any more than the meals I have eaten; even so, they have made me.

~ Ralph Waldo Emerson

Hi Shippou You could fiddle a bit with the chunk sizes, to ensure that you would only read/dump files from and to disk every so often. If your maps are pretty simple, the amount of data in memory shouldn't be a problem. To my knowledge this is the same way Minecraft does it. You could also cache a bigger amount of chunks, say two concentric circles worth around the one the player is currently in. I can't see this becoming a problem on modern computers. Try the sample that's for download on my Blog - I haven't experienced any problems, and the chunks there are very small, to illustrate the concept. If you make 255x255 chunks you would load a lot less and the files would still be fast to read and not too much of a strain on memory. Kind regards - Jakob

www.xnafan.net - tutorials, tools and code samples for making games :)

This topic is closed to new replies.

Advertisement