Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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);

            }
        }
    }
...
share|improve this question
2  
Are you absolutely positive you are only rendering what's in the camera's view, meaning is the code for determining what to render correct? –  Neeko Aug 5 '11 at 17:40
4  
The framerrate drops from 60 to 20 fps, just because of the allocated memory? That's very unlikely, there must be something wrong. What platform is it? Is the system swapping virtual memory to disc? –  Maik Semder Aug 5 '11 at 17:41
4  
@Drackir In this case I'd say it's wrong if there even is a tile class, an array of suitable length integers should do, and when there is a half a million objects, OO overhead is no joke. I suppose that it is possible to do with objects, but what would the point be? An integer array is dead simple to handle. –  eBusiness Aug 5 '11 at 18:14
3  
Ouch! Iterating all the tiles and calling Draw four times on each one that's in view. There's definitely some improvements possible here.... –  thedaian Aug 5 '11 at 21:05
9  
You don't need all the fancy partitioning talked about below to render only what's in view. It's a tilemap. It's already partitioned into a regular grid. Just calculate the tile at the top-left of the screen and the bottom-right, and draw everything in that rectangle. –  Blecki Aug 5 '11 at 23:39

8 Answers 8

up vote 46 down vote accepted

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.)

share|improve this answer
3  
The region part seems interesting, if I recall correct, that's how minecraft does it, however, it doesn't work with how the terrain in Terraria evolves even if you're nowhere near it, like grass spreading, cacti growing and the like. Edit: Unless of course, they apply elapsed time since last time the region was active, and then perform all changes that would've happened in that period. That might actually work. –  William 'MindWorX' Mariager Aug 5 '11 at 20:56
1  
Minecraft definitely uses regions (and the later Ultima games did, and I'm pretty sure many of the Bethesda games do). I'm less sure of how Terraria handles terrain, but they likely either apply elapsed time to a "new" region, or they store the entire map in memory. The latter would demand a high RAM usage, but most modern computers could handle that. There might be other options that haven't been mentioned, as well. –  thedaian Aug 5 '11 at 21:12
    
I'll have a look at the region method, as it seems the best way to handle it, since having everything in memory at once is a waste of resources. I could always visit each region slowly, to avoid too big updates when the player explores. This seems like a good answer, and I'll mark it so. Then I just need to update the method I use to autotile. –  William 'MindWorX' Mariager Aug 5 '11 at 21:20
2  
@MindWorX: Doing all the updates when it reloads wouldn't always work--suppose you have a whole bunch of barren area and then grass. You go away for ages and then walk towards the grass. When the block with the grass loads it catches up and it spreads in that block but it won't spread into the closer blocks that are already loaded. Such things progress MUCH slower than the game, though--check only a small subset of the tiles in any one update cycle and you can make distant terrain live without loading down the system. –  Loren Pechtel Aug 5 '11 at 21:40
1  
As an alternative (or supplement) to "catching up" when a region nears the player, you could instead have a separate simulation iterating over each distant region and updating them at a slower rate. You could either reserve time for this each frame or have it run on a separate thread. So for example you might update the region the player is in plus the 6 adjacent regions every frame, but also update 1 or 2 extra regions as well. –  Lewis Wakeford Jun 27 '13 at 23:02

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.

share|improve this answer
    
Yeah, later iterations of my engine evolved to use that. Mostly to reduce memory consumption and to increases speed. ByRef types are slow compared to an array filled with ByVal structs. Nonetheless it's good that you added this to the answer. –  William 'MindWorX' Mariager Jun 28 '13 at 1:06
    
Yeah stumbled upon it while looking for some random algorithms. Immediately noticed you where using your own tile class in your code. It's a very common mistake when your new. Nice to see you are still active since you posted this 2 years ago. –  Menno Gouw Jun 28 '13 at 6:47
1  
You don't need either health or damage. You can keep a small buffer of most-recently-picked tile locations and the damage on each. If a new tile is picked at and the buffer is full then roll off the oldest location from it before adding the new one. This limits how many tiles you can mine at a time but there's an intrinsic limit to this anyway (roughly #players * pick_tile_size). You can keep this list per-player if that makes it easier. Size does matter for speed; smaller size means more tiles in each CPU cacheline. –  Sean Middleditch Jan 12 at 8:55
    
@SeanMiddleditch You are right but that was not the point. The point was to stop and think what you actually need to draw the tiles on screen and do your calculations. Since the OP was using a whole class i made a simple example, simple goes a long way in a learning progress. Now unlock my topic for pixel density please, you are obviously a programmer try to look at that question with the eye of a CG artist. Since this site is also for CG for games afaik. –  Menno Gouw Jan 12 at 9:24

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.

share|improve this answer
    
I'm not really sure you're answering the question that's being asked, since you're talking about encoding (and perlin noise), and the question seems to deal with problems of performance. –  thedaian Aug 5 '11 at 19:12
    
Using the proper encoding (such as perlin noise) you can then not worry about holding all those tiles in memory at once.. instead you simply ask your encoder (noise generator) to tell you what is supposed to appear at a given coordinate. There's a balance here between CPU cycles and memory usage, and a noise generator can help with that balancing act. –  Dan-o Aug 5 '11 at 19:36
1  
The issue here is that if you're making a game that allows users to modify the terrain somehow, simply using a noise generator to "store" that information wouldn't work. Plus, noise generation is fairly expensive, as are most encoding techniques. You're better off saving CPU cycles for actual gameplay stuff (physics, collisions, lighting, etc) Perlin noise is great for terrain generation, and encoding is good for saving to disk, but there's better ways to handle memory in this case. –  thedaian Aug 5 '11 at 20:21
    
Very great idea, however, like thedaian, the terrain is interacted with by the user, which means I can't mathematically retrieve information. I'll look at the perlin noise anyways, to generate the base terrain. –  William 'MindWorX' Mariager Aug 5 '11 at 21:21

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.

share|improve this answer

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. :)

share|improve this answer
    
+1 for "premature optimization is the root of all evil" I'm guilty of this :( –  thedaian Aug 5 '11 at 21:35
15  
-1 a quadtree? Overkill a bit? When all the tiles are the same size in a 2D game like this (which they are for terraria), it is extremely easy to figure out which range of tiles are on screen - it's just the upper-leftmost (on the screen) to the lower-rightmost tiles. –  BlueRaja - Danny Pflughoeft Aug 7 '11 at 15:06

@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).
share|improve this answer

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.

share|improve this answer

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

share|improve this answer
1  
-1 This answer is too general to be useful, and the link you provide doesn't directly address this particular problem. The Flyweight pattern is one of many, many ways to manage large data sets efficiently; could you elaborate as to how you would apply this pattern in the specific context of storing tiles in a Terraria-like game? –  postgoodism Nov 2 '12 at 19:18

protected by Noctrine Jun 28 '13 at 1:17

Thank you for your interest in this question. Because it has attracted low-quality answers, posting an answer now requires 10 reputation on this site.

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.