Jump to content
  • Advertisement
Sign in to follow this  
Mythics

Multi-Layered 2D Tile-Based map, how to render efficiently (culling)?

This topic is 2154 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Simple enough concept, but it's really confusing for me. Feel free to look at this demo to get an idea of the perspective I'm referring to, but the real map is HUGE and many many layers thick.

It's all 2D, using SpriteBatch in C#. I'm currently checking every potentially visible tile on every potential layer, from back to front, to see if it 'exists' (not just if it's visible) and then drawing it. I am indeed able to compare where the player is with the zoom factor to cut out anything outside of the screen area vertically/horizontally per layer, but as I draw each layer, I'm unaware of a fast method to skip entire layers completely hidden by layers above them or to only attempt to draw single cubes when only a few on a given layer are actually visible.

Any suggested methods of how to ONLY render truly visible tiles, without iterating through all tiles to check for their visibility?

Thanks,
Mythics

Share this post


Link to post
Share on other sites
Advertisement
Just a couple quick ideas off the top of my head (I don't have much time right now):

This seems like it could be an ideal use for using a tree data structure, such as BSP or quadtree or something.

This also seems like it could possibly be done quicker and maybe easier using 3D, limiting the camera to the perspective you want, and let the GPU do the culling for you.

Share this post


Link to post
Share on other sites
I can't see the video because I am on a cellphone, but I am assuming you have uniformly sized tiles (as in, all the tiles are of the same size).

A very easy optimization is to just handle visible tiles. Do this by storing a 2D tile map, and get your camera's position and your view size in your tiles space.
Suppose every tile is 50x50 units (pixels?), your camera position is then divided by (50, 50) to get into your tile space. Same goes for the view size, for example (800, 600) / (50, 50).

Using the four numbers you got, you can iterate over the actual visible tiles in the 2D map.

As to rendering itself - I do not know how C# batches work, but while making my sprite map rendering code I found out that GPUs /really/ like to draw things together and not have many tiny calls (it's a known fact, but I never imagined the speed difference).

So, use a texture atlas if you are not, to remove swaps and thus make more rendering calls (there are also texture arrays).

A second less obvious thing, is that while testing speed, rendering from the first tile seen to the last - which includes a lot of unseen tiles if your view is small compared to the map size (since the "GPU representation" of the map is a linear array) - is a lot faster than rendering only the visible tiles line by line. Even when the difference in the amount of tiles rendered was huge, and there were only a few lines to render.

So even if something looks very inefficient and stupid, your hardware might like it better anyway.

With these two simple things I can render millions of sprites in one call at high FPS, and there are more things you can improve, such as the actul vertex data (triangle strips, for example, since the whole map is just a big grid).

I am not sure how much control you have over those things with C#'s sprite batches though, like I wrote above.

Share this post


Link to post
Share on other sites
I forgot to mention two things and I can't seem to be able to edit my post.

First of all, render empty tiles with a fully alpha'd texture (in the texture atlas) - otherwise you get a lot of render calls and your performance will be a lot worse.

The second thing is that I didn't explicitly say anything about the map representation - you should have two "views" of the data. One is a 2D array of things representing your tiles (for data used for game logic and such, e.g. Is this tile collidable?), and another one is your typical sprite list used for rendering.
Splitting these will make everything a lot easier and faster.

Share this post


Link to post
Share on other sites
I forgot to mention two things and I can't seem to be able to edit my post.

First of all, render empty tiles with a fully alpha'd texture (in the texture atlas) - otherwise you get a lot of render calls and your performance will be a lot worse.

The second thing is that I didn't explicitly say anything about the map representation - you should have two "views" of the data. One is a 2D array of things representing your tiles (for data used for game logic and such, e.g. Is this tile collidable?), and another one is your typical sprite list used for rendering.
Splitting these will make everything easier and faster.

Sorry if these things are obvious, but I had to figure them for myself at the time, so I hope I helped. :)

/edit
Now can edit again and it sent a double posot in the middle...? All this silliness is why I almost never do anything on a cellphone...

Share this post


Link to post
Share on other sites
This might have been what wolfscaptain was saying but just wanted to throw in my two cents:

For example you have a ridiculous sized map of 10000 tiles x 10000 tiles.
Your "camera" offset (just some RECT) you use for viewable play area: 800 x 600.
Your tile sizes are 32x32 pixels wide/high.
So your camera only displays 25 tiles widthwise and 18 tiles heightwise.

Using the tile size multiplied by how many tiles you have your actual pixel area is: 320,000 x 320,000

If your camera's top left (origin) is located at 5000 x 3000 pix

Divide the camera's X location by tile width. 5000 / 32 = 156
Divide the camera's Y location by tile width 3000 / 32 = 93

So assuming you have some sort of 2D array of tiles you can just start at X index of 156 and Y index of 93
and iterate 25 index wide on the X index and 18 index high on the Y index and you'll render your viewable area.
Maybe add + 1 or +2 on each just to make sure there's no weird clipping going on the sides and you'll be good.

Even if you iterate through all layers this way, and don't take into account whether things are visible or not, it shouldn't slow down performance enough to be noticeable.

Share this post


Link to post
Share on other sites

This might have been what wolfscaptain was saying but just wanted to throw in my two cents


Yes that's what I meant, but you wrote it in a clearer manner.

From my WebGL experiments, there are indeed performance issues, mainly having to do with a lot of rendering calls.
Rendering a mere few thousands of tiles, each having a separate call, reduced the frame rate to below 5, while having one call can render about two million with zero optimizations at 60+ frame rate - on my pretty old GPU - for example.

Though, like I've mentioned before, I am not really sure how much control you get over these things in C# sprite batches.

Here's a real-time example of these two simple improvements. Might take time to load, the map is 470KB.
You can play with it by moving around and zooming with the right mouse button and the scroll respectively.
It's only 480000 tiles, but I've tested numbers above million. Seems to have some issues with browsers though, I guess they don't quite agree to allocate huge buffers for security reasons?

You can see that the tiles being rendered aren't necessarily only the tiles being seen (in fact there are always more). This is the second improvement I mentioned. Even if it causes a huge increase in the rendered tiles, it's just faster than rendering only the visible tiles line by line.

By the way, this is unrelated to clipping or performance, but after trying a few ways, I've figured that the easiest way to "zoom" in/out on a tile map is to have all your tiles as 1x1 units, and scale everything in shaders. The scaling factor is then simply your zoom factor, and it's just easy to change it real time without having to actually change the sprites.
So in case you need zooming, you might want to try that.

Share this post


Link to post
Share on other sites
Here's an idea I didn't see posted by anyone else. You could render each layer to a separate texture, so that you can then render the whole map with just a few draw calls. Anytime a tile changes, you'd have to redraw that layer's texture. This way you don't need to loop through all the tiles nearly as often.

Share this post


Link to post
Share on other sites

Here's an idea I didn't see posted by anyone else. You could render each layer to a separate texture, so that you can then render the whole map with just a few draw calls. Anytime a tile changes, you'd have to redraw that layer's texture. This way you don't need to loop through all the tiles nearly as often.


Great idea!

You can render the map in a few calls also with buffers, but I can see using N textures for N layers as being a whole lot faster if they are indeed generated in a smart way (such as including one tile to each direction which is not visible, and then only re-generation the texture if you move more than one tile to whatever side).

Share this post


Link to post
Share on other sites
[font=georgia, serif]Another approach would be to construct a "meta layer" that goes on top of the entire tile map.[/font]

[font=georgia, serif]This meta layer would describe on which layer the topmost tile can be found.[/font]
[font=georgia, serif]Since your sprite rendering looks to be isometric, you would likely want to include a secondary value that tells you how many layers deep to render starting at the referenced layer, so that we could handle the "edge" rendering properly.[/font]

[font=georgia, serif]Essentially, you would precalculate which tiles are visible at the start and store the data on the Meta Layer.[/font]
[font=georgia, serif]Every time there is a change to the tilemap, you would only have to recalculate the visibility of the grid position for the removed tile.[/font]

[font=courier new, courier, monospace]ie:[/font]


[font=courier new, courier, monospace]Sprite Layer 0 (3x3):[/font]
[font=courier new, courier, monospace]X X X[/font]
[font=courier new, courier, monospace]X X X[/font]
[font=courier new, courier, monospace]X X X[/font]

[font=courier new, courier, monospace]Sprite Layer 1 (3x3):[/font]
[font=courier new, courier, monospace]X X X[/font]
[font=courier new, courier, monospace]O O X[/font]
[font=courier new, courier, monospace]O O X[/font]

[font=courier new, courier, monospace]Sprite Layer 2 (3x3):[/font]
[font=courier new, courier, monospace]X O O[/font]
[font=courier new, courier, monospace]X O O[/font]
[font=courier new, courier, monospace]X X O[/font]


[font=georgia, serif]Where:[/font]
[font=georgia, serif]X - Indicates a tile that has a sprite that must be rendered.[/font]
[font=georgia, serif]O - Indicates a tile that has no sprite (transparent)[/font]

[font=georgia, serif]Your Meta Layer would look something like this :[/font]
[font=courier new, courier, monospace] [/font]
[font=courier new, courier, monospace][font=courier new, courier, monospace]2 1 1[/font] [/font]
[font=courier new, courier, monospace][font=courier new, courier, monospace]2 0 1[/font][/font]
[font=courier new, courier, monospace][font=courier new, courier, monospace]2 2 1[/font][/font]
[font=courier new, courier, monospace] [/font]
[font=courier new, courier, monospace][font=courier new, courier, monospace]Where: (assuming that layer 0 is on the bottom / background) Each number refers to to the sprite layer that holds the topmost visible tile.[/font][/font]
[font=courier new, courier, monospace][font=courier new, courier, monospace]This would drastically reduce (but not eliminate) your overdraw and rendering would simply be a matter of iterating through the meta layer.[/font][/font] Edited by Frakkus

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!