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\$ – Steven Stadnicki Jun 24 '12 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\$ – User not found Jun 28 '12 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\$ – Steven Stadnicki Jun 28 '12 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\$ – Steven Stadnicki Jun 28 '12 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\$ – User not found Jul 3 '12 at 6:54

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\$ – User not found Jun 28 '12 at 8:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.