1
\$\begingroup\$

I've implemented Minkowski subtraction to test whether (and where) two AABBs collide, independent of framerate/time-step, in my Minecraft-like game.

But since there may be tens of thousands of voxels, I'm realizing I can't just test everyone of them. Is there an alternative to just scanning for nearby voxels? I worry that if I just do collision for voxels within a fixed range, then I've undone the framerate independence that I had sought.

\$\endgroup\$
  • \$\begingroup\$ Are your voxels stored in any kind of spatial lookup structure, like a grid or octree? \$\endgroup\$ – DMGregory Oct 19 '18 at 12:25
1
\$\begingroup\$

First of all, minkowski sum is overkill for this, since the blocks are static. Go a bit simpler and use swept AABB.

Secondly if you can, break the world into chunks, then only check blocks inside chunks the player collides with. This reduces the amount of blocks you need to check from hundreds of thousands to a couple thousand (if we assume a chunk size of 10 x 100 x 10, then it' around 90000). Chunks are basically big blocks and if the player doesn't go very fast (very fast in this context means faster, than 1 chunk per frame), then you only need to check the chunk the player is standing in and the 8 neighbouring ones.

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

This post is a bit old, but it got bumped, so I'll followup with the solution I implemented.

I used the players velocity (multiplied by the framerate) to compute a simple 3D cartesian range of voxels that the player could collide with.

When moving diagonally, it tests more voxels than is required (as crudely sketched below):

enter image description here

However, at typical FPS & velocity, only about a dozen voxels are tested per frame (regardless of the size of the world). So I'm quite happy with it.

Seems so obvious now; can't believe I asked, lol.

| improve this answer | |
\$\endgroup\$

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.