0
\$\begingroup\$

My project has upwards of 3000 2D objects but not all of them collide with each other. Between each object that can collide, a CollisionPair is created and stored inside a flattened array.

Currently, a MaxObjects is defined for accessing the flattened array. Unfortunately, when iterating over this array for collision checks, I get a lot of overhead from the for loop and null checks.

Is there a more efficient way, both in memory and performance, to store and access CollisionPairs?

Note: Many of these objects are axis-aligned boxes - how does Minecraft handle these collisions?

Improve this question
\$\endgroup\$
1
\$\begingroup\$

The solution was a lot simpler than the other things I was thinking of. I store all CollisionPairs in a separate collection and iterate over that collection.

This allows me to do what I was doing before with partitioning, setting a boolean for the CollisionPair to true to represent that the involved bodies are in the same partition.

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

A common way to solve this is to have the concept of "islands" which are just groups of objects that might collide with each other. Objects from different islands are guaranteed to be far enough away that they can never collide. Objects can change islands as they move around and islands can join and separate.

Even though this is a common technique, its just one of many ways to solve the problem. Basically you need to find a way to break your large group of objects into smaller groups of objects so you have fewer objects to test each object against.

A quad tree is another common technique which recursively breaks the world up into 4 rectangles.

The nice thing about a quad tree versus islands is that you don't need objects to be in fae apart groups to get a benefit.

Quad trees are great when objects are clustered together with no clear way to separate them.

There are plenty of other techniques though (:

Improve this answer
\$\endgroup\$
  • \$\begingroup\$ With my quad tree, after all objects are partitioned, how would I iterate through their checks? How would I cull out the redundant checks? \$\endgroup\$ – JPtheK9 Jun 28 '15 at 1:19
  • 1
    \$\begingroup\$ One way would be when you want to move an object, you find the smallest node it fits in if it was at the new position. You would then collision detect only against the objects in that node, it's parent nodes, and child nodes that overlap the object. If there's a collision at the new position you disallow the movement. If your movement deltas were large enough that it looks bad if it disallows a full movement, when doing your collision tests you could keep track of the closest "time t" collision found along the movement path and allow the object to move only that far (allow partial movement) \$\endgroup\$ – Alan Wolfe Jun 28 '15 at 1:34
  • \$\begingroup\$ BTW part of what will define a good answer for your usage case is how many objects move and how often they move. If every object moves all the time you might need a more sophisticated algorithm. \$\endgroup\$ – Alan Wolfe Jun 28 '15 at 1:35
  • \$\begingroup\$ I just saw the YouTube video of your project. It looks like all objects can move all the time! If I were in your shoes I'd give quad tree or something else relatively simple to implement a shot and see how it performs, but of course up to you if you think that's worth the effort :p \$\endgroup\$ – Alan Wolfe Jun 28 '15 at 1:45
  • \$\begingroup\$ Most of the objects are procedurally generated and unmoving. I'm going to divide the map into a fixed number of grid nodes and scan for which nodes an object belongs to if the object's position changed. \$\endgroup\$ – JPtheK9 Jun 28 '15 at 1:51

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.