I'm currently using an R-Tree for both picking and collision testing. Each entity on screen has a bounding box for collisions and a separate one for picking. Since entities may change position very frequently, both trees must be updated/reordered once per frame.

While this is very efficient for collisions, because the tree is used in hundreds of collision queries every frame, I'm finding it too costly for picking, because it only gets queried when the user clicks, thus leading to a lot of wasted tree updates.

What would be a more efficient way to implement picking without as much overhead?

  • 3
    \$\begingroup\$ How many pickable objects do you have on screen? For collisions, hierarchical approaches make more sense because you're trying to improve on an O(n^2) naive algorithm, but since picking is inherently O(n), unless you can make substantial gains by preprocessing data (i.e., if you're not looking at a full O(n log n) update for rebuilding your tree every frame) then it seems like there's little point in using a hierarchy in the first place. \$\endgroup\$ Jun 24, 2012 at 17:34
  • \$\begingroup\$ Thanks for the suggestion. I'm making a library, so I can't give you an estimation of how many objects I'll have on screen, it.depends on the game. Out of curiosity, would your response be any different if I was dealing with, say, a million pickable objects on screen? (obviously not a desirable case) \$\endgroup\$ Jun 28, 2012 at 7:55
  • \$\begingroup\$ As a matter of fact, yes - at that point I think I would start recommending a 'pick buffer', where you render all your objects (or at least their object IDs) to an additional offscreen buffer and perform your picking just by looking up the appropriate pixel in that buffer. Note that this approach is still a linear one - but can be much more efficient on a per-object basis than querying each object individually. \$\endgroup\$ Jun 28, 2012 at 15:30
  • 1
    \$\begingroup\$ Essentially, the linear search approach takes time roughly an for some medium-ish value of a, whereas the pick buffer takes time roughly bn+p, but with a much smaller value of b. So if n is small then the '+p' term overwhelms the difference between a and b, but if n is large then the pick buffer approach (esp. if hardware-accelerated) may win out. (Also, insert the obligatory 'make games, not engines' link here. :-) \$\endgroup\$ Jun 28, 2012 at 15:33
  • \$\begingroup\$ Understood. Hardware acceleration cannot be counted on in HTML5 and a game with millions of entities would probably be too slow to run anyway, but thanks for satisfying my curiosity. And I'm aware of the "make games not engines" saying, but my company is both selling the engine and making games with it ;) It's still good advice though. \$\endgroup\$ Jul 3, 2012 at 6:54

1 Answer 1


As Steven Stadnicki suggested in his comment, and what is also suggested in a related question over at stackoverflow, just do a linear search without any hierarchy.

  • \$\begingroup\$ Thank you, I guess a linear search should do. I was in doubt as to whether there was a better option, but sometimes I forget that simpler is usually better. \$\endgroup\$ Jun 28, 2012 at 8:00

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .