Efficient way of detecting a touched object in a game?

So 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 visi开发者_如何学运维ble 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?

Thx a lot.

The first possibility to consider is whether an acceleration method will actually help in your case. E.g., if you only have one query per frame, your current method needs to check each object once. But, if all your objects are moving, almost all acceleration structures need to update each object once -- so, in that case, why bother?

If you determine that an acceleration structure is actually needed, both your solutions seem reasonable:

• For a touch interface, you know the size of your query. So, if all your objects are the size of a touch or smaller, spatial hashing should be a good solution.
• if your objects can be large, note that spatial hashing might need to add a large object to many hash buckets. In that case, a quadtree might be a better idea.

Another solution is to maintain a tree of bounding boxes. There are a variety of algorithms that use this; one in particular is the R-tree.

I would recommend an engine such as Java Box2D

Which has many features including collision detection.

If you only have single-touch capability (that is, only one object can be touched at a time), you could have a global reference that gets updated by the touched object with an OnTouch event.

If there are many, I suppose you could have a list that you add/remove objects from as the touches enter/leave the object.