How'd they do it: Millions of tiles in Terraria

Question

I've been working up a game engine similar to Terraria, mostly as a challenge, and while I've figured out most of it, I can't really seem to wrap my head around how they handle the millions of interactable/harvestable tiles the game has at one time. Creating around 500.000 tiles, that is 1/20th of what's possible in Terraria, in my engine causes the frame-rate to drop from 60 to around 20, even tho I'm still only rendering the tiles in view. Mind you, I'm not doing anything with the tiles, only keeping them in memory.

Update: Code added to show how I do things.

This is part of a class, which handles the tiles and draws them. I'm guessing the culprit is the "foreach" part, which iterates everything, even empty indexes.

...
    public void Draw(SpriteBatch spriteBatch, GameTime gameTime)
    {
        foreach (Tile tile in this.Tiles)
        {
            if (tile != null)
            {
                if (tile.Position.X < -this.Offset.X + 32)
                    continue;
                if (tile.Position.X > -this.Offset.X + 1024 - 48)
                    continue;
                if (tile.Position.Y < -this.Offset.Y + 32)
                    continue;
                if (tile.Position.Y > -this.Offset.Y + 768 - 48)
                    continue;
                tile.Draw(spriteBatch, gameTime);
            }
        }
    }
...

Also here is the Tile.Draw method, which could also do with an update, as each Tile uses four calls to the SpriteBatch.Draw method. This is part of my autotiling system, which means drawing each corner depending on neighboring tiles. texture_* are Rectangles, are set once at level creation, not each update.

...
    public virtual void Draw(SpriteBatch spriteBatch, GameTime gameTime)
    {
        if (this.type == TileType.TileSet)
        {
            spriteBatch.Draw(this.texture, this.realm.Offset + this.Position, texture_tl, this.BlendColor);
            spriteBatch.Draw(this.texture, this.realm.Offset + this.Position + new Vector2(8, 0), texture_tr, this.BlendColor);
            spriteBatch.Draw(this.texture, this.realm.Offset + this.Position + new Vector2(0, 8), texture_bl, this.BlendColor);
            spriteBatch.Draw(this.texture, this.realm.Offset + this.Position + new Vector2(8, 8), texture_br, this.BlendColor);
        }
    }
...

Any critique or suggestions to my code is welcome.

Update: Solution added.

Here's the final Level.Draw method. The Level.TileAt method simply checks the inputted values, to avoid OutOfRange exceptions.

...
    public void Draw(SpriteBatch spriteBatch, GameTime gameTime)
    {
        Int32 startx = (Int32)Math.Floor((-this.Offset.X - 32) / 16);
        Int32 endx = (Int32)Math.Ceiling((-this.Offset.X + 1024 + 32) / 16);
        Int32 starty = (Int32)Math.Floor((-this.Offset.Y - 32) / 16);
        Int32 endy = (Int32)Math.Ceiling((-this.Offset.Y + 768 + 32) / 16);

        for (Int32 x = startx; x < endx; x += 1)
        {
            for (Int32 y = starty; y < endy; y += 1)
            {
                Tile tile = this.TileAt(x, y);
                if (tile != null)
                    tile.Draw(spriteBatch, gameTime);

            }
        }
    }
...

Answer 1

Are you looping through all 500,000 tiles when you're rendering? If so, that's likely going to cause part of your problems. If you loop through half a million tiles when rendering, and half a million tiles when performing the 'update' ticks on them, then you're looping though a million tiles each frame.

Obviously, there's ways around this. You could perform your update ticks while also rendering, thus saving you half the time spent looping through all those tiles. But that ties your rendering code and your update code together into one function, and is generally a BAD IDEA.

You could keep track of the tiles that are on the screen, and only loop through (and render) those. Depending on things like the size of your tiles, and screen size, this could easily cut down the amount of tiles you need to loop through, and that would save quite a bit of processing time.

Finally, and perhaps the best option (most large world games do this), is to split your terrain into regions. Split the world into chunks of, say, 512x512 tiles, and load/unload the regions as the player gets close to, or further away from, a region. This also saves you from having to loop through far away tiles to perform any sort of 'update' tick.

(Obviously, if your engine doesn't perform any sort of update tick on tiles, you can ignore the part of this answers that mentions those.)

Answer 2

I see one huge mistake here not handled by any of the answers. Of course you should never draw and iterate over more tiles then you need too. What's less obviously is how you actually define the tiles. As i can see you made a tile class, i always used to do that too but it's a huge mistake. You probably have all sorts of functions in that class and that creates a lot of unnecessary processing.

You should only iterate over whats really necessary to process. So think about what you actually need for the tiles. To draw 'm you only need a texture, but you do not want to iterate over an actual image since those are large to process. You could just make a int[,] or even a unsigned byte[,] (if you do not expect more then 255 tile textures). All you need to do is iterate over these small arrays and use a switch or if statement to draw the texture.

So what do you need to update? The type, the health and the damage seems sufficient. All of these can be stored in bytes. So why not make a struct like this for the update loop:

struct TileUpdate
{
public byte health;
public byte type;
public byte damage;
}

You could actually use the type to draw the tile. So you could detach that one (make a array of it's own) from the struct so you do not iterate over the unnecessary health and damage fields in the draw loop. For updating purpose you should consider a wider area then just your screen so the game world feels more alive (entities change position off screen) but for the drawing of things you just need the tile that are visible.

If you keep the above struct it only takes 3 bytes per tile. So for saving and memory purpose this is ideal. For processing speed it does not really matter if you use int or byte, or even long int if you have a 64 bit system.

Answer 3

There's different encoding techniques you could use.

RLE: So you start with a coordinate (x,y) and then count how many of the same tile exist side-by-side (length) along one of the axies. Example: (1,1,10,5) would mean that starting at coordinate 1,1 there are 10 tiles side-by-side of tile type 5.

The massive array (bitmap): each element of the array holds onto the tile type that resides in that area.

EDIT: I just came across this excellent question here: Random seed function for map generation?

The Perlin noise generator looks to be like a good answer.

Answer 4

You should probably partition the tilemap as already suggested. For example with Quadtree structure to get rid of any potential processing(e.g. even simply looping through) of the unnecessary(not visile) tiles. This way you only process what might need processing and increasing the size of the dataset(tile map) does not cause any practical performance penalty. Of course, assuming that the tree is well balanced.

I don't want to sound dull or anything by repeating the "old", but when optimizing, always remember to use the optimizations supported by your toolchain/compiler, you should experiment with them a bit. And yes, premature optimization is the root of all evil. Trust your compiler, it knows better than you in most cases, but always, always measure twice and never ever rely on guesstimates. It's not about having the fast implementation of the fastest algorithm as long as you don't know where the actual bottleneck is. That's why you should use a profiler to find the slowest(hot) paths of the code and focus on eliminating(or optimizing) them. Low-level knowledge of the target architecture is often essential for squeezing out everything the hardware has to offer, so study those CPU caches and learn what a branch predictor is. See what your profiler tells you about cache/branch hits/misses. And as using some form of a tree data structure shows, it's better to have intelligent data structures and dumb algorithms, than the other way around. Data comes first, when it comes to performance. :)

Answer 5

Isn't it all about too many draw calls? If you put all your maps tile textures int a single image - tile atlas, there will be no texture switching while rendering. And if you batch all your tiles into a single Mesh it should be drawn in one draw call.

About the dynamic aditing... Maybe quad tree isn't such a bad idea. Assuming that tiles are being put into leaf and non-leaf nodes are just batched meshes from its childrens, root should contain all tiles batched into one mesh. Removing one tile requires nodes updates (mesh rebatching) up to the root. But at every tree level there is only 1/4th of the mesh rebatched wchich shouldnt be that much, 4*tree_height mesh joins?

Oh and if you use this tree in clipping algorithm you will render not always root node but some of its children, so you dont even have to update/rebatch all nodes up to root, but up to the (non-leaf) node you are rendering at the moment.

Just my thoughts, no code, maybe its nonsense.

Answer 6

@arrival is right. The problem is the draw code. You're buildIng an array of 4*3000+ draw quad commands (24000+ draw polygon commands) per frame. Then these commands are processed and piped to the GPU. This is rather bad.

There are some solutions.

• Render big blocks (for example, screen size) of tiles into a static texture and draw it in a single call.
• Use shaders to draw the tiles without sending the geometry to the GPU every frame (i.e. store the tile map on the GPU).

Answer 7

What you need to do, is split the world into regions. Perlin noise terrain generation can use a common seed, so that even if the world isnt pregenerated, the seed will form part of the noise algo, which nicely seams the newer terrain into the existing parts. This way, you dont need to calculate more than a small buffer ahead of the players view at a time (a few screens around the current one).

In terms of handling things such as plants growing in areas far away from the players current screen, you can have timers for example. These timers would iterate through say files storing information about the plants, their position etc. You simply need to read/update/save the files in the timers. When the player reaches those parts of the world again, the engine would read in the files as normal, and present the newer plant data on screen.

I used this technique in a similar game I made last year, for harvesting and farming. The player could walk far away from the fields, and on returning, the items had been updated.

Answer 8

I've been thinking about how to handle that much zillions of blocks and the only thing that comes to my head is the Flyweight Design Pattern. If you don't know, I deeply suggest reading about it: might help a lot when it comes to saving memory and processing: http://en.wikipedia.org/wiki/Flyweight_pattern