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?
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.
For implementing a OctreeI would recommend looking at this article.