Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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?

share|improve this question
3  
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. –  Steven Stadnicki Jun 24 '12 at 17:34
    
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) –  jSepia Jun 28 '12 at 7:55
    
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. –  Steven Stadnicki Jun 28 '12 at 15:30
1  
Essentially, the linear search approach takes time roughly a*n for some medium-ish value of a, whereas the pick buffer takes time roughly b*n+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. :-) –  Steven Stadnicki Jun 28 '12 at 15:33
    
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. –  jSepia Jul 3 '12 at 6:54
add comment

1 Answer

up vote 2 down vote accepted

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.

share|improve this answer
    
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. –  jSepia Jun 28 '12 at 8:00
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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