How can I quickly determine whether objects are onscreen in 2D?

Currently, I have this in each object's renderer's update method:

        float a = transform.position.x * Main.scale;
float b = transform.position.y * Main.scale;
float c = Camera.main.transform.position.x * Main.scale;
float d = Camera.main.transform.position.y * Main.scale;
onscreen = a + width - c > 0 &&
a - c < GameView.width &&
b + height - d > 0 &&
b - d < GameView.height;


transform.position is a 2D vector containing the game engine's definition of where the object is. This is then multiplied by Main.scale to translate that coordinate into actual screen space.

Similarly, Camera.main.transform.position is the in-engine representation of where the main camera is, and this is also multiplied by Main.scale.

The problem is, as my game is tile-based, thousands of these updates get called every frame, just to determine whether or not each object should be drawn. How can I do this more efficiently, please?

• You could set-up hierarchical bounding boxes for the objects, so that you do not have to (necessarily) check each individual object. See bounding volume hierarchy on wikipedia. – Matthias Aug 22 '14 at 11:51

With just a couple of slight rearrangements, you could have:

float a = (transform.position.x - Camera.main.transform.position.x) * Main.scale;
float b = (transform.position.y - Camera.main.transform.position.y) * Main.scale;

onscreen = a > -width && a < GameView.width
&& b > -height && b < GameView.height;


It will save you a few calculations, but wont really make a big performance difference I think. Another way would be to do the reverse of the scaling. Instead of calculating the scaling for each tile each time, you can calculate the reverse for the camera and GameView positions, whenever they chance. This happens one time per frame at most, while the tiles take N_TILES per frame calculations. So reformulating the code, it could be something like this:

float a = transform.position.x - ScaleCamera.x;
float b = transform.position.y - ScaleCamera.y;

onscreen = a > -width && a < ScaledGameView.width
&& b > -height && b < ScaledGameView.height;


A perhaps more efficient way to do it is by blocks. Make a set of say 10x10 tiles be in a block. Now calculate for the block as a whole if it should appear on the screen, considering it's greater dimension. If it does, you can either draw all the tiles, or refine what you show or not from there. You can later change the size of each block to make your needs, making them larger if it's needed, so you can quickly jump big blocks of tiles.

So, given that I don't know how your code is, you could have something like this:

class TileBlock {
int x, y, w, h; // defines the area of the block
Vector<Tile> tiles;

public boolean isInsideBlock(Tile tile) {
if inside area
return true

return false
}

if isInsideBlock(tile)
return true

return false
}

public Vector<Tile> getTiles() {
return tiles;
}

... etc ...
}


Then on tile creation, you can have either try to directly add to the blocks until it returns true, or you could make it more elegantly, and have a TileManager or TileBlocksManager, to handle that for you. So then:

for(Tile tile : tiles)


And on rendering:

blocks = blocksManager.getVisibleBlocks(Camera camera, GameView gameView)
for(TileBlock block : blocks) {
Vector<Tile> tiles = block.getTiles()
for(Tile tile : tiles) {
do what you need to do
}
}


On a side note, too big blocks will mean that if a block is accepted for refining/showing, then you will have to process all the small tiles inside. So be wise when picking a number, don't make it too small or it's pointless the work and time you spend, but don't be greedy and make huge blocks as well.

I hope this gives some ideas.

• As the maps can get fairly huge, I went for a quadtree-based solution in the end - I already used quadtrees for speeding up collision detection, but it hadn't even crossed my mind to use them for determining whether or not stuff was onscreen until I read your answer, so thanks :-) – Ben Ezard Aug 22 '14 at 16:31

Keep an "on-screen tiles" collection that you update each time the camera moves and each tile has a reference to the objects in it. This was you only need to update the objects referenced by the tiles that are on screen (or just outside).