Tell me more ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.
up vote 2 down vote favorite
2

This question already has an answer here:

Currently I'm sorting and looping every entity on my level but I really don't need to. Only a small subset would be on screen.

If I could extract a list of entities from my main list that are on screen (or near the screen), that would be great, but I believe maintaining a different kind of list like a quad-tree or something might be in order, but I have no experience with such things.

How can I do this?

share|improve this question
When you say this, are you drawing every object or are you looping through all of the objects, checking if they need to be drawn, and then drawing them? – Polar Mar 16 at 11:56
I'm looping them all and checking their position, yes. – Caustic Mar 16 at 11:58
1  
Try googling keywords like: camera culling, camera clipping. If you would use quadtree(for 2d) or octree (for 3d), then you would iterate only those entities, which are near camera. Google "binary space partitioning (BSP)" too. – Denis Narushevich Mar 16 at 12:21
@Byte56 It's only a duplicate if he's dealing with 2D - 3D approaches are subtly different (enough to warrant different answers). – Polar Mar 16 at 16:07
@Polar 2D is in the title, I'll update it to be in the tags. I take it then, that you agree it's a duplicate. – Byte56 Mar 16 at 16:13
show 3 more comments

marked as duplicate by Byte56, Sean Middleditch, bummzack, Trevor Powell, Josh Petrie Mar 22 at 15:15

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

1 Answer

up vote 2 down vote accepted

There are a few methods I can think of, and all of them involve partitioning - Binary Space Partitioning, Quadtrees (and by extension, Octrees) and k-d trees.

Binary Space Partitioning: Binary Space Partitioning, or BSP, works by dividing the list of polygons (or in your case entities) into 2, then subdivides those into 2 recursively, until it reaches a predetermined condition (e.g. 10 entities in a partition). The main benefit of BSP is that it allows you to determine groups of objects which must be drawn quickly. The disadvantage is that it can end up taking a lot more memory than the original list (because some objects are split in two - to make this work with entities, you would have to alter the algorithm slightly).

Quadtrees/Octrees: First of all, to make things clear - quadtrees and octrees work on exactly the same principle of each other, but quadtrees are used in 2-dimensional space, and octrees in 3-dimensional space. This is as a quadtree divides areas into 4 (top-left, top-right, bottom-left, bottom-right), whereas an octree divides areas into 8 (top-front-left, top-front-right, top-back-left, top-back-right, etc.). Octrees basically work by sorting the entities into the different areas, and then further subdividing the relevant/visible ones.

K-d trees: Finally, there are k-d trees. These are similar to BSP and Octrees in the sense that they divide up the area, but they operate on dimensions, and are always binary. I'll be honest, I'm not 100% clear on k-d trees - it would be best to do your own research.

At this point, I would advise reading about these (and googling the terms Denis suggested), and then making a decision. I'd go with octrees myself, but I don't know exactly what conditions you're under and what you're trying to do with these entities.

share|improve this answer

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