I'm creating a game with lots of instances. On each iteration of the game loop, I only want to deal with the ones that are near the player. Currently, I do this by constructing a list of all the existing instances within a rectangle surrounding the player every few iterations. However, this takes far too long. How could I speed it up?

  • \$\begingroup\$ You should look at quadtrees or octrees. I think it fits what you are looking for. \$\endgroup\$ – Heckel Sep 23 '14 at 18:41
  • \$\begingroup\$ @Heckel I agree. \$\endgroup\$ – ClassicThunder Sep 23 '14 at 18:53

Space Partitioning

In mathematics, space partitioning is the process of dividing a space (usually a Euclidean space) into two or more disjoint subsets (see also partition of a set). In other words, space partitioning divides a space into non-overlapping regions. Any point in the space can then be identified to lie in exactly one of the regions.

In summary Space Partitioning is the process of breaking a large number of items into non overlapping sets. This will benefit you because you can calculate what set your player is in and only deal with the items in that set.

I would recommend either a Quadtree (2D) or an Octree (3D). One advantage of Quadtrees/Octrees is that because they are evenly divided it easier make the updating more inclusive by simply moving a few nodes up the tree and iterating over everything below that point.

For implementing a Quadtree I would recommend looking at this article.

enter image description here

For implementing a OctreeI would recommend looking at this article.

enter image description here

|improve this answer|||||

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.