next »

[zarovv]

Hi. I have an issue with collision involving rotating cubes.

What i have is basically a cube trying to slide a tile map of other cubes stuck together.
I do collision check and response with SAT algorithm and works pretty well but the issue starts when i try to slide pass a corner of another cube.

It just gets stuck because it thinks that it collides with the corner of the other cube in the tilemap but that corner doesn't suppose to exists because the cubes in the tile should be stuck together.

Are there any solutions for this issue maybe?
There was a solution that i tried involving checking the surface area for the colliding cubes in the tilemap and handling the collision that have the largest surface area first. However this didn't work with my rotating cube because the surface areas can be equal or the surface area with the cube in the tilemap that has the corner is larger.

Here is an image for the problem:


So, has someone encountered it and may have a solution? Can't find anything that helps..

[ThemsAllTook]

This is always a tricky one. I've used the surface area solution in the past, but as you said, it doesn't work in your situation. I think the last time I implemented collision detection, what I did was basically resolve the closest collisions first and allow them to affect the velocity of the object before resolving later ones. In this situation, the cube sliding to the right would first collide with the left red cube, get pushed upward so it's not intersecting, have its y velocity set to 0, and then skate right over the crack between cubes since it's no longer trying to move downward by the time it reaches the surface of the red cube on the right.

Another thing that comes to mind would be to treat any surfaces that are stuck together as if they don't exist. The left cube effectively wouldn't have a collidable right face, the right right one wouldn't have a collidable left face. This might be a pain to calculate depending on your data structures, though.

[raigan]

I've used a bunch of different approaches, sadly nothing is perfect and there are always tradeoffs. My current go-to is to perform some basic CSG when loading the level so that there are no internal "seams" between tiles, only the external surface geometry gets collided against.

This works great, but it makes dynamic/destructible stuff a bit more difficult, and also it's a bit complicated.

In the past I've used "collide+resolve vs the closest one first" as ThemsAllTook mentioned, that seems to work well as long as your shapes are roughly circular (ie not long+thin).

[qMopey]

The best solution is to not use a cube but instead use something with a curved surface. For example, a cube with a feathered radius (numerically floating), a circle, or a capsule.

Here's an example where the edge catching problem is non-existent: https://github.com/RandyGaul/player2d

The only other option is something much more complicated. For example in 3D games a good solution is to store topology of the ground with a graph data structure. In 2D this is what Box2D does with the chain shape. Each point on the surface of a chain shape knows who its neighbors are. Collision detection is able to form a voronoi region between a point and two shared edges, effectively welding the seem together where your cube corner catches. raigan's CSG suggestion is another strategy for removing the extra Voronoi regions so the SAT algorithm cannot see the internal regions at all.

[zarovv]

thank you all for the suggestions.
i thought on maybe another approach.. for some reason it came to mind.
what if i prioritize to push the cube by the push vector of the tilemap dimension over the box dimension.

i mean, the tilemap dimension gives me a vector to push up, and the box dimension gives me a vector to push back the cube in the cube dimension so the cube is pushed backwards from the direction it was moving, so it gets stuck.

if i prioritize to push first up, meaning always prioritize to push in the tilemap dimension first, maybe it will work? its like the "surface area" solution but with a different prioritize.

this way, i wont break the sat algorithm because i dont touch it, i just prioritize to push the cube in a different order. i push with the first MTV(the push vector for the box with one of the tilemap boxes), check collisions with the other boxes in the tilemap which i saw that there was a collision, and if there is i push again.

may work?

[raigan]

The best solution is to not use a cube but instead use something with a curved surface. For example, a cube with a feathered radius (numerically floating), a circle, or a capsule.

Here's an example where the edge catching problem is non-existent: https://github.com/RandyGaul/player2d

AFAICT in that demo (which is really cool, thanks for sharing it!) the reason it doesn't get stuck on internal edges is because it's using swept collision -- which is another good solution to the problem of avoiding internal edges. (but which comes with its own set of tradeoffs/etc)

In my experience even if you're using circles you can get collisions with internal edges (or in that case, corners of tiles) where the order in which you collide vs the tiles matters.

(For circles this can be solved by resolving collision in order of distance -- essentially finding the circle center's location in the tile grid and testing the tiles above/below/left/right of that cell before handling the diagonals.)


@zarovv: I don't think it's as easy as pushing along the tile's normal, because you'll still get cases where your shape collides with the internal edge of a tile and get pushed out that way (ie horizontally in your case, instead of vertically).

[zarovv]

The best solution is to not use a cube but instead use something with a curved surface. For example, a cube with a feathered radius (numerically floating), a circle, or a capsule.

Here's an example where the edge catching problem is non-existent: https://github.com/RandyGaul/player2d

AFAICT in that demo (which is really cool, thanks for sharing it!) the reason it doesn't get stuck on internal edges is because it's using swept collision -- which is another good solution to the problem of avoiding internal edges. (but which comes with its own set of tradeoffs/etc)

In my experience even if you're using circles you can get collisions with internal edges (or in that case, corners of tiles) where the order in which you collide vs the tiles matters.

(For circles this can be solved by resolving collision in order of distance -- essentially finding the circle center's location in the tile grid and testing the tiles above/below/left/right of that cell before handling the diagonals.)


@zarovv: I don't think it's as easy as pushing along the tile's normal, because you'll still get cases where your shape collides with the internal edge of a tile and get pushed out that way (ie horizontally in your case, instead of vertically).

you're right i tried it and it worked fine until the box is at the same dimension as the tilemap(they have they same rotation or they like align to each other).
with that case i added sorting by surface area to my solution and for now it seems to work pretty well.  

what i did is first make like 2 lists. the first list is the MTVs with the tilemap dimension(for example pushing up or right in the tilemap dimension) and then a list of MTVs with the box dimension(like for example pushing back, up, right but with the box dimension. like pushing back the box based on its rotation, which will be pushing it back with the negative direction it was moving).
each list i sorted by surface area and i went through the first list and then the second list.

each time i applied a push by the MTV and then continued. each time i didn't find a collision with the next tilemap box in the list i moved to the next. each time i did find a collision i applied a push and then moved to the next in the list.

[qMopey]

if i prioritize to push first up, meaning always prioritize to push in the tilemap dimension first, maybe it will work? its like the "surface area" solution but with a different prioritize.

You're sort of on the right track. These steps will help, but you will still have lingering problems. For example, you can push on your prioritized axis to hopefully glide over the next tile on the other axis. However, once your player crosses a power of two boundary away from the origin the distance from one floating point value to another doubles (floating point error doubles on power of two alignment). This means as you run over tiles your prioritization will effectively make the player "float over the tiles" just fine, until randomly it doesn't work. What happens is as the player crosses a power of two boundary the next tile will have a numerically (but not visually) different position, and you will end up catching corners again.

Check this picture out from this webpage.



The tick marks are representing the minimum difference between two floating point numbers at different magnitudes. As you move away from the origin the floating point error doubles each time a power of two boundary is crossed.

So as you run along tiles and cross a power of two boundary, this can happen.

Even though all tiles are assigned to the same exact floating point value, due to varying magnitudes it's still going to be possible to catch edges since tiles will have slightly different x values. Not only will the tiles have slightly different x values in the example, but the behavior of the floating point x position of the player will also vary across power of two boundaries.

The implication here is that even though you might have tuned your algorithm to work well in some scenarios, it's still possible for SAT give you a MTV on the x-axis, assuming SAT finds the x-axis to be of less penetration than the y axis. Tuning will have to adjust for varying floating point errors on both the x and the y-axis as each independently varies from the origin.

One scenario may work until you walk along the x-axis far enough. Another solution might work until your player jumps to a specific tile height in the level.

It's not practical to try and hack your way around these problems. The only solution is to prevent SAT from seeing unwanted geometry at all, making it impossible to catch edges. It boils down to two options:

1. Remove internal edge geometry entirely. Something like CSG or Box2D's chain shape.
2. Use a radius of some kind. For example, rounded shapes. Somehow ensure the player is always far enough away from the internal geometry that SAT will never return internal regions as the MTV. One good way to ensure this is with swept collision detection, or careful tuning when using discrete collision detection (like low timesteps and low velocities).


The fundamental problem is that your SAT routine will still track internal edges (which means internal Voronoi regions). If you want to get rid of these without any lingering problems then you need to go back to the suggestions I made earlier, or the ones raigan (I'm assuming you're the same raigan from bullet forums?) pointed out. These solutions are eliminating internal edges and reducing the possible Voronoi regions your SAT algorithm can see.

The best solution is to not use a cube but instead use something with a curved surface. For example, a cube with a feathered radius (numerically floating), a circle, or a capsule.

Here's an example where the edge catching problem is non-existent: https://github.com/RandyGaul/player2d

AFAICT in that demo (which is really cool, thanks for sharing it!) the reason it doesn't get stuck on internal edges is because it's using swept collision -- which is another good solution to the problem of avoiding internal edges. (but which comes with its own set of tradeoffs/etc)

In my experience even if you're using circles you can get collisions with internal edges (or in that case, corners of tiles) where the order in which you collide vs the tiles matters.

You're right, the swept nature is ideal. In my experience with slower velocities, faster timesteps, and larger radii you can comfortably avoid internal edges. But, this is not an ideal solution, and does require tuning. It is an easy solution to implement though.

[zarovv]

but how can i make a rounded shape if i want a cube?
i don't want to slide a tilemap box and it will look like i am sliding a circle.

to eliminate corners i can for example make the tilemap box larger so the corner is inside another tilemap box for example. that may help in something i think..

[qMopey]

to eliminate corners i can for example make the tilemap box larger so the corner is inside another tilemap box for example. that may help in something i think..

Nope, that will not help.

to eliminate corners i can for example make the tilemap box larger so the corner is inside another tilemap box for example. that may help in something i think..

You can use a rounded cube and draw it as a cube. You can use a circle and draw it as a cube. You can use a capsule and draw it as a rectangle. You can use any rounded shape most of the time, and use rectangles/cubes depending on your character shape (like in the demo I linked earlier), which can be useful for things like standing on ledges without slipping off.