More efficient in range checking

Question

I am going to use a specific example in my question, but overall it is pretty general. I use java and libgdx.

I have a ship that moves through space. In space there is debris that the ship can tractor beam in and and harvest. Debris is stored in a list, and the object contains it own x and y values. So currently there is no way to to find the debris's location without first looking at the debris object. Now at any given time there can be a huge (1000+) amount of debris in space, and I figure that calculating the distance between the ship and every single piece of debris and comparing it to maximum tractor beam length is rather inefficient.

I have thought of dividing space into sectors, and have each sector contain a list of every object in it. This way I could only check nearby sectors. However this essentially doubles memory for the list. (I would reference the same object so it wouldn't double overall. I am not CS major, but I doubt this would be hugely significant.) This also means anytime an object moves it has to calculate which sector it is in, again not a huge problem.

I also don't know if I can use some sort of 2D MAP that uses x and y values as keys. But since I am using float locations this sounds more trouble than its worth.

I am kind of new to programming games, and I imagined there would be some eloquent solution to this issue.

Answer 1

Your idea of dividing the space into sectors is the right way to go. There are a lot of data structures that push this idea very far, and you probably need one of the following:

• an octree (or its 2D version, the quadtree).
• a BSP tree

The idea of these structures is to divide the space recursively. There are many more possibilities, including k-d trees.

Once all your debris are stored in the structure, you need to iterate over all children of the structure; if the whole child is farther than the tractor beam length, skip it; if it isn't, check each of its own children.

Answer 2

Your line of thought about dividing the space into sectors is exactly what you need. There are several different data structures and algorithms that can be used, but for this particular scenario I recommend the one described on the following link - Spatial Hashing (which is basically just a grid):

• http://conkerjo.wordpress.com/2009/06/13/spatial-hashing-implementation-for-fast-2d-collisions/

Just to clarify, spatial hashing works better for worlds where objects are small and have roughly the same size (so that you can pick a bucket size) and sparsely distributed (so that the objects are distributed between a lot of different buckets). From your description that seemed to be the case (debris in space), hence my suggestion.

On the other hand, a quadtree (or octree) while more complex, works better than spatial hashing for when objects can have large size differences (so that fitting them into the buckets is harder) and are mostly clustered together (which means they'd mostly occupy the same buckets). If that happens to be the case, you can find more information on the subject at the end of this answer.

Now, transcribing the essential portions of the article, you divide your world into sectors, or buckets:

And keep a list of objects for each bucket. The article is using a dictionary / hash table to store the buckets, but I don't really see the advantage in his example, since all the buckets are allocated when the game starts, and are referenced by an integer index. I'd say a regular array would do.

Next you need a way to translate one position in the world, into the appropriate bucket index in the array. In the article he uses:

int hashid = (int)((Math.Floor(position.X / CellSize)) +
                   (Math.Floor(position.Y / CellSize)) * width);

To find which buckets an entity should be placed in, and granted that objects won't be larger than a bucket, do the above for each of the four corners and add the object to the resulting buckets.

Finally, to get close objects, find the bucket you're currently in, and iterate over that and other adjacent buckets if needed.

I've written a few answers related to the broader topic of space partitioning, which like I said, encompasses a lot of different techniques (e.g. quadtree/octree, bsp tree, r-tree, bounding volume hierarchies):

• How to continuously find all entities within a radius efficiently?
• Documentation on 2D space partitioning

Answer 3

At lower level optimization you can compare distance squared instead of distance. if (range^2 < distance^2) saves expensive sqrt. If you don't need to compare O(N^2) range checks this might be enough optimization for you. Reading linear data is fast. Doing simple range check (its just sum, dot and compare) is fast as hell you probaly just want simple and efficient code. If N is really large then spatial stuff is once again good choise but then you need to use time coherency too to gain something.

Putting debris to buckets is O(N) too so you dont lose nothing but you gain memory efficiency and simpler code which mean faster devepment and easier debuggin.

You can do this kind of math with linear data (even with mobile devices) around 100k without even noticing the time used, computers are fast with these kind of things.

Answer 4

Assuming this is 2D, you can have a box2d sphere trigger around the ship and corresponding bodies on the debris and check when the bodies collide? If it's 3D, I think the bullet support is now available as well?