Efficient way of detecting a touched object in a game?

Question

Imagine a Sims-like 2D game for a touch based mobile phone where one can interact with virtually any object in the scene.

How can I efficiently detect which object is being touched by the player?

In my short experience, looping through all the visible objects in the scene and checking if they're touched has so far done the job, but when there may be many many moving objects in the screen that sounds kind of inefficient isn't it? Keeping the visible moving objects list can consume time in itself as one may have to loop through all of them each frame.

Other solutions I've thought are:

Spatial hashing. Divide the screen as a grid and place the visible objects in the corresponding bucket. Detection of the clicked object is fast but there's additional overhead for placing the objects in the correct bucket each frame.

Maintaining a quad-tree. Moving objects have to be rearranged all the time, the previous solution looks better.

What is usually done in this case?

Answer 1

I'd recommend profiling first and check if the touching check really is a bottleneck.

Test with the maximal amount of objects that your game will use as a final product and see if you get frame drops.

If it is in fact a bottleneck, I'd say go with the spatial hasing option and see if it gets better this way.

But this is just my personal opinion. I'd say test and see if you really need to optimize, and if you do, check for alternatives.

Answer 2

To me, this suggests an off-screen buffer with a specialized render of the view on the screen. Each object is entirely one colour (no lighting calculations etc) which uniquely identifies the object. Z buffering used as for a normal render. Maybe lower resolution than the main screen render - at the very least antialiassing would be bad, so no need to render higher resolution than the screen.

This may be a way to offload most of the work to the graphics hardware.

Warning - I'm not an experienced game developer - this is just an idea, it may not be possible.

Answer 3

You can create a grid of many squares, attend to each one what static objects are visible trough an Array before the game start, then at each frame see to which square the player belong and draw the objects. Every object has an ID so the drawing is ID based:

int x = getSquare().X;
int y = getSquare().Y;
int n = Square[x][y].Number_of_objects;
for(int i = 0; i < n; i += 1){
    Draw(StaticObjet[Square[x][y].Object[i].Id]);
};