Jump to content

  • Log In with Google      Sign In   
  • Create Account


Collision detection behaving incorrectly


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
8 replies to this topic

#1 stu_pidd_cow   Crossbones+   -  Reputation: 1748

Like
0Likes
Like

Posted 24 July 2012 - 12:08 AM

I'm trying to implement 3D collision detection using SAT. It works really well when colliding with a single object and even most circumstances with multiple objects simultaneously. One problem I have found is that if a cube is moving along a bunch of square planes with gravity applied, it will get caught on the squares. Here's a picture to demonstrate:


Posted Image

The cube cannot move from its position. From what I understand, the reason is that SAT is pushing it to the side because the downward force is greater than the speed that the cube is moving horizontally.
So my question is, is there a way to get around this? This scenario is quite critical for my game, otherwise I wouldn't have asked.
Thanks.

Sponsor:

#2 stu_pidd_cow   Crossbones+   -  Reputation: 1748

Like
0Likes
Like

Posted 24 July 2012 - 08:48 PM

OK, I think I've found my problem more specifically, so I'll try to simplify my question:

Assume square A collides with square B and C simultaneously like in the following picture:
Posted Image
I am expecting square A to move to the following location:
Posted Image
But, the way my algorithm works is that it evaluates square B and the square C individually, meaning it is placed like this:
Posted Image
This is obviously incorrect. So what is the best way to handle collision in this scenario?

Cheers.

#3 raigan   Members   -  Reputation: 674

Like
0Likes
Like

Posted 25 July 2012 - 07:22 PM

This comes up a lot in relation to platformer movement/physics; the solutions seem to be either some sort of preprocessing (i.e identify the shared edges between the ground boxes and flag them, so that your collision model is a flat/smooth/continuous surface rather than a bunch of boxes), or some sort of logic to filter out or order the collisions.

If your dynamic object is a sphere, you can repeatedly push the sphere out of the single closest point on the world, this should correctly avoid bumping into seams; for a box, I'm not sure if there's something similar you can do. In your example, solving the deepest penetration first would work, but I don't think this works in general.

#4 Postie   Members   -  Reputation: 916

Like
0Likes
Like

Posted 27 July 2012 - 12:06 AM

You could calculate the amount of penetration of the moving object with all objects it is colliding with and then do the collision resolution on the collision between the object with the highest penetration first.

A simple metric for determining penetration amount could be the distance between the two object's centre's, although won't be 100% accurate for cubes.

Edited by Postie, 27 July 2012 - 12:08 AM.

Currently working on an open world survival RPG - For info check out my Development blog: ByteWrangler

#5 raigan   Members   -  Reputation: 674

Like
0Likes
Like

Posted 27 July 2012 - 07:36 AM

@Postie: I suggested this, but it doesn't work in general, only for that specific diagram.

As I mentioned, "deepest penetration first" does work for spheres, but for boxes it fails; depending on the speed of horizontal movement, the amount of gravity, and the particular time that the frame is sampled, the penetration with the "wall" can be deeper than that of the "floor".

One solution used in old platformers is to decompose A's movement into a series of axial movements, i.e first slide A along x,z then slide it along y.

OTOH you could solve this by trying every combination of collision ordering (i.e collect all collisions, then solve them in every order) and compare the results to see which lets you move A as far in the player-specified-direction as possible. If there are only a handful of collisions this may be feasible, otherwise the possible permutations will explode.

Or you could try caching the previous contact direction and solving collisions with that collision normal first. If this only happens with floors, you could also just solve collisions in order of decreasing y component in the contact normal, so that you solve "floor" collisions first.

All of these solutions involve first detecting ALL collisions, then selecting one, rather than the simpler approach of detecting and solving each collision one at a time.

I think most games solve this by using smooth triangle meshes as collision shapes; sadly this is a very static/pre-made solution and rules out a lot of interesting dynamic movement of the world.

#6 stu_pidd_cow   Crossbones+   -  Reputation: 1748

Like
0Likes
Like

Posted 27 July 2012 - 03:49 PM

OTOH you could solve this by trying every combination of collision ordering (i.e collect all collisions, then solve them in every order) and compare the results to see which lets you move A as far in the player-specified-direction as possible. If there are only a handful of collisions this may be feasible, otherwise the possible permutations will explode.


I tried something like this and it worked perfectly. Unfortunately, it only ran at 4 FPS, which is far from sufficient for me.

I'm thinking of applying something more specific to my game. ie There will be different states for movement, such as airborne (gravity will be applied) and grounded (no gravity but collision will be checked for ground below). I'm thinking this might be the best approach.

#7 Postie   Members   -  Reputation: 916

Like
0Likes
Like

Posted 27 July 2012 - 07:10 PM

@Postie: I suggested this, but it doesn't work in general, only for that specific diagram.


I think I interpreted your post slightly differently when I first read it, though in retrospect we are talking about very similar things.

@stu_pidd_cow: Re: 4 fps, are you performing a broadphase collision detection pass first to reduce the number of collision tests?
Currently working on an open world survival RPG - For info check out my Development blog: ByteWrangler

#8 raigan   Members   -  Reputation: 674

Like
0Likes
Like

Posted 27 July 2012 - 08:27 PM

You could try using raycasts (or, AABB-sweeps) from slightly "above" the box's position each frame, sort of how FPSs handle stepping up small steps. This is getting further away from a "physics-based" approach though, but maybe that's not really important?

#9 stu_pidd_cow   Crossbones+   -  Reputation: 1748

Like
0Likes
Like

Posted 28 July 2012 - 03:37 PM

@stu_pidd_cow: Re: 4 fps, are you performing a broadphase collision detection pass first to reduce the number of collision tests?


I just added a broadphase pass and it boosted the FPS up to about 10-40 (depending on the amount of objects colliding).
The way I'm doing it is by finding all of the possible resolutions for a collision, then checking each of these resolutions for collisions, etc. After doing this 2 or 3 times, I find all of the resolutions that didn't have any collisions, and find which of these is the shortest.




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS