Efficiently culling off-screen objects on a top-down 2D map

I know efficiency is key in game programming and I've had some experiences with rendering a "map" earlier but probably not in the best of ways.

For a 2D TopDown game: (simply render the textures/tiles of the world, nothing else)

Say, you have a map of 1000x1000 (tiles or whatever). If the tile isn't in the view of the camera, it shouldn't be rendered - it's that simple. No need to render a tile that won't be seen. But since you have 1000x1000 objects in your map, or perhaps less you probably don't want to loop through all 1000*1000 tiles just to see if they're suppose to be rendered or not.

Question: What is the best way to implement this efficiency? So that it "quickly/quicker" can determine what tiles are suppose to be rendered?

Also, I'm not building my game around tiles rendered with a SpriteBatch so there's no rectangles, the shapes can be different sizes and have multiple points, say a curved object of 10 points and a texture inside that shape;

Question: How do you determine if this kind of objects is "inside" the View of the camera?

It's easy with a 48x48 rectangle, just see if it X+Width or Y+Height is in the view of the camera. Different with multiple points.

Simply put, how to manage the code and the data efficiently to not having to run through/loop through a million of objects at the same time.

As for complex objects I think the best way is just to reduce them to surrounding rectangles, and check if that rectangle is inside the viewport. Even if you will render a texture which is not actually visible (because of it's shape) it's still will be probably faster than doing a more complex detection algorithm.

As for handling large maps efficiently you should subdivide your map on larger scale, say 10x10. Then you check your viewport intersection. In worst case it hits 4 this 'regions' which will result in (100x100)*4 = 40K objects. This is a simplified example. For a real usage you should consider Quadtree structure which is especially efficient for such subdivisions and collision detection (viewport visibility check is basically collision check between viewport and sprite).

• Using a Quadtree for map tiles is a bit of an overkill... since you can just calculate the proper indexes of tiles which need to be rendered. And besides, regions are simpler, and I would recommend using them for the first round of optimizations. It will help understand and use quadtrees later on :) +1. Commented Nov 20, 2012 at 9:18
• @Liosan it's not clear from question if this 'tiles' are of a same size, otherwise solution would be quite trivial, of course. Commented Nov 20, 2012 at 9:41
• you're right, Deukalion even wrote a comment to a different answer saying 'And a tile isn't always the exact same size'. Commented Nov 20, 2012 at 9:49
• Does QuadTree even work with anything but exact region sizes? Every region shouldn't be a rectangle sized because the object inside the rectangle aren't so it doesn't make a rectangle. So it will NOT be a say 1024x1024 pixel grid that's rendered, it's shape might be very orthodox. Commented Nov 22, 2012 at 22:54
• Well, I guess no (I haven't really used quadtrees myself), but that doesn't really matter if you can put everything into surrounding rectangle region. Anyway, if quadtree is not appropriate for your task for some reason, you, most probably, need to use similar approach. Commented Nov 23, 2012 at 2:57

When you have many mobile objects, you should store them by their coordinates in a multi-dimensional tree structure. That way you can efficiently get a list of all objects which are inside a given rectangle. You can even get them ordered by their x- or y-coordinates, which is important for drawing order when object sprites overlap.

This will also come in very handy for collision detection.

See the wikipedia article about k-d trees for details.

When 2d trees are too complicated for you, there is also an easier but not much less effective alternative: Store the objects as children of the tiles. When you move an object, you remove it from the object list of its old tile, and put it into the object list of the new one. When you draw the objects, you again iterate over the tiles in the viewport and retrieve their objects. Then you sort them all by y-coordinates and draw them.

Don't know if it is the best way, but this is how I learn to do it:

you have an two-dimensional array of "tiles"

public Tile tilemap[][];


and you decide the position of the "camera" with a Vector2, you will only render what is inside the scene, the big rectangle is what you can see on the screen, is useless to draw the rest of the scene.

Now you need to get the offsets, assuming you want your camera to be at the center of the scene:

offsetX = (graphics().width() / 2 - Math.round(cam.Position().X));
offsetX = Math.min(offsetX, 0);
offsetX = Math.max(offsetX, graphics().width() / 2 - mapWidth);
offsetY = (graphics().height()) / 2 - Math.round(cam.getPosition().Y);
offsetY = Math.min(offsetY, 0);
offsetY = Math.max((graphics().height() / 2 - mapHeight), offsetY);


now, in which part of the array the visible tiles start and finish?

firstTileX = pixelsToTiles(-offsetX);

lastTileX = firstTileX + pixelsToTiles(graphics().width());

firstTileY = pixelsToTiles(-offsetY);

lastTileY = firstTileY + pixelsToTiles(graphics().height());

int pixelsToTiles(int pixels) {
return (int) Math.floor((float) pixels / Tile.getHeight());
}


and in your draw method, you just loop through the visible part of the array:

   for (int x = firstTileX; x < lastTileX; x++) {
for (int y = firstTileY; y < lastTileY; y++) {
Vector2 position = new Vector2(tilesToPixelsX(x) + offsetX,
tilesToPixelsY(y) + offsetY);
tilemap[x][y].Draw(surf, position);
}
}

• Yes, but tile was an example to simplify things. I already wrote that I understand the process of determining if an object is already in "view" with rectangle / title shaped, not with more advanced shapes that have multiple points. Also, I was looking for something that makes me "not" go through all the tiles during each Update() method in XNA. If I have a "LARGE" map, with about 10000 objects (shapes of 3 points and more) this isn't the way to do it. Each Update I have to run a loop of 10000 updates and just as many calculations. I don't use tiles and this is not efficient; I've been there. Commented Nov 20, 2012 at 5:07
• And a tile isn't always the exact same size, so I can't do it with that either. I don't use rectangles. Commented Nov 20, 2012 at 5:08
• Simply put: I only want to loop through objects that SHOULD be rendered, not loop through objects that shouldn't at all. Commented Nov 20, 2012 at 5:10
• @Deukalion Riktothepast's code DOES only loop through tiles that should appear within the bounding box of the screen (although this isn't very clear). The same basic technique can be used to loop through any rectangle of tiles within a given set of coordinates. Commented Nov 20, 2012 at 13:15

You can have one Bitmap that is the whole scene but not displayed. And then a displayed screen sized camera layer Bitmap that just draws from the whole scene but only the part that needs to be shown.