Let's say you have an array of blocks (AABB), where each block is touching or intersecting any number of other blocks. Together they make up a larger object, and because they're all touching, you can consider them to all be on the same "grid". Each block can have any size or position, but is always axis-aligned.

Now let's say you delete one of the blocks, somewhere in the middle, such that there is now a gap where blocks are no longer touching.

How would you go about detecting that you now have two clusters of blocks, two "grids", instead of one?

My first thought is to loop through all blocks, perform AABB collision checks against all other blocks, mark the ones that touch, then recursively cycle through the touched blocks looking for others that touch, until you reach the end and can look for blocks that were not marked. But that sounds extremely inefficient.

This is in plain C, so I'm trying to keep memory use limited to the existing array of block structs.

  • \$\begingroup\$ Your first thought sounds reasonable, I'd advice you to try that, and once you are done see if it's causing any performance issues. If it does, then you can look into making it more efficient. It's easier to improve something that works, rather than creating something already improved. \$\endgroup\$ – TomTsagk Feb 12 at 9:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.