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

Question

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.

Answer 1

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

Answer 2

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.

Answer 3

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

Answer 4

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.