I’m creating a Tilemap class for my game that uses a 2D array of instances of a Tile class I created.
It works exactly as one would expect; I run a for loop inside a for loop to get the indices and pass it into a Draw method. I want to have thousands of tiles in the game at once like Terraria or similar games - not necessarily updating them, just having them in memory. Memory isn’t really a problem, the problem I’m running into is that drawing them all at once is too slow. Since I obviously don’t want to draw tiles offscreen, I check if they’re offscreen before drawing them by creating a rectangle with for the tile, and just check if that intersects with a rectangle I have representing my camera’s viewport. The problem is, checking whether or not to draw them and then only drawing the tiles onscreen is far SLOWER than just drawing them all.
I tried grouping the tiles into regions, using a 3D array, so that I didn’t have to go through every tile, just every 100 or so, but I couldn’t figure out how to implement that. Basically I am asking: What would be the fastest way to have thousands of tiles, but only draw the ones on the screen, whithout using all my cpu?
You could use quad trees for that. This let’s you very quickly filter out large numbers of tiles because it checks against the bounding volumes of the current level of the tree. At the first level after the root node you have four leaves. So in the best case you can filter out 3/4 of all tiles with 4 checks! Quad trees are just a data structure where you keep the information which tile belongs to which tree leaves. Hope that info is somewhat correct and makes sense. Just read about it I guess there are very good resources about this topic available.
I did some research, but it seems a little advanced for my current skill level. Do you have any websites/article’s you’d recommend on quadtrees or something else related?
It has been a very long time since I looked into it. So I have no specific resource I could point you to. It is not that complicated but it may look a bit at first. Basically how it works is that you build the tree on startup, since in your case the objects tiles are not moving you don’t have to rebuild it after that point. So you just get the benefits of performance I’mprovement out of it if you apply the tree. It is just holding the information of what tiles are inside a part of a tree. And you keep a bounding volume in this case a rectangle for each node. So you make your tests against the tree and you traverse it further if the volume is inside your view. If a part is outside your view, just ignore it. This is where you get your improvement out of. You don’t have to check each tile which belongs to the nodes which you already sorted out. Also the first checks are happening at a larger scale. Your whole map is devided into four equally sized parts. That’s where the name comes from.
I see what your saying. Thanks, that might be the solution I need, because it sounds so much faster. One more question: If I’m storing thousands of tiles, and referencing each one’s type which is a byte, am I better off just creating a 2d array of bytes? I don’t know a ton about how c# uses memory and stuff so pardon me if it sounds stupid.
If you use a tile-span memory tracking method, you don’t need to use any kind of culling or testing. I tried the same concept in 3D - worked quite well) - you could have a world with millions of things in it and it wouldn’t matter. It’ll only ever draw/process exactly what’s visible (or partly off-screen).
Here’s some rough psuedocode:
map[x,y] (or map[x,y,layer])
// tile coordinate of center of screen:
mapLoc = new Point(camPos.X/64, camPos.Y/64);
// how much to offset the map by when drawing it (for smooth scrolling)
Vector2 draw_offset = camPos.X-mapLoc.X*64, camPos.Y-mapLoc.Y*64;
v = screen_center.Y - 64*17;
for(b=mapLoc.Y-17 to mapLoc.Y+17) {
h = screen_center.X - 64*20;
for(a =mapLoc.X-20 to mapLoc.X+20) {
// (Draw is some method that handles the Map[a,b].offset, scale, rotation, sourceRect, etc)
Draw(Point(h,v)+drawoffset, Map[a,b]);
h+=64;
}
v+=64;
}
You’ll notice the screen offset moves up to 64 in any direction and resets to scroll seamlessly if you consider how the math works. This way there’s no need for any tests and what you see is what is processed… I think I said that already… ;p
You can do tricks with tagging these fake-tile coords with anything you like including moving characters too (and build ai guidance systems into them) - it’s really handy.
(I should mention, you should probably also safe-guard against a or b going off the map)
If your using a 2d array of indexes the way i understand it the fastest and best way is to find the top left visible tile on the screen and the bottom right visible tile on the screen
Tile[,] tileGrid = new Tile[1000, 1000];
//Populate the tileGrid
//Drawing Method
Point topLeft = new Point(123, 40);
Point bottomRight = new Point(245, 90);
for(int x = topLeft.X; x < bottomRight.X; x++)
{
for (int y = topLeft.Y; y< bottomRight.Y; y++)
{
tileGrid[x, y].Draw();
}
}
You can also add some overdraw to your topleft and bottomright point if needs be. This way your only ever itterating over tiles that are on your screen.
I think boot is right on it. You don’t need to check every single tile, instead take advantage of the fact they are arranged on a grid and calculate the minimum and maximum tile x and y index. You will need to know the windows size and offset of the grid to figure it out but it should be relatively easy.
Also as an aside I’m under the impression your approach to “Early Out” tiles before calling the draw function is actually good practice in general (though maybe not in this specific situation), imagine all the work your computer saves by not having to consider all that stuff. BUT under the hood the monogame and opengl or whatever is very super optimized so you have to optimize your code like crazy but you should be able to make it faster.
Post for the overboard type
So you’ve got some pretty good low cpu options here, but I want to share one more option that is O(1) CPU for the hardcore types out there who love their CPU and hate their GPU(actually I think GPU performance might be lower too, shh).
You can generate a VertexBuffer with a the element type being just the index of a texture in some premade texturemap
You can then use an hlsl geometry shader to generate polys for each tile, then a vertex shader to fit them to the camera, and a 2dsampler to grab the right part of the texture map for each tile. Since those are the hard part, I’m not gonna write them, but it could be done if you really wanted.
Really though, take the solution boot offered. It’s the right one for your skill level.