Sign in to follow this  

a problem with collision detection...

This topic is 2821 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

i am trying to figure something about collision detection in 3D. the setting is a platform game,and i want to detect collision with a platform when the player jumps. now as far as i knew it was just shooting a ray from the player,with the direction of the player's velocity and checking if it hits any of the platform's triangles. but i can see a problem that i will present through this image which was painted with my horribly amazing MS paint skills as you can see,the happy character wants to reach the platform,so he jumps toward it,and shoots a ray from his belly toward the platform. but oh no! the ray misses and yet half of the character's body will pass through the platform. i thought of perhaps shooting 5 rays(first on the top of the character,second in the middle,third in the bottom,forth in the right side of the character and fifth in the left side of the character) but that just sounds expansive(not to mention this problem could still occur with small platforms). so,how do i handle this like a pro?

Share this post


Link to post
Share on other sites
Quote:
so,how do i handle this like a pro?
The easy answer is, 'use an existing physics engine'.

If you want to do it yourself though, your intuition that casting multiple rays is *not* the way to do it is correct. Instead, represent the objects in the game using single shapes with volume (or area, in 2-d). For example, for the player, you could use an axis-aligned box. The problem then reduces to a moving box vs. box test, which is pretty well documented online and elsewhere (terms you can search for include 'AABB SAT', 'box SAT', and 'separating axis test').

Share this post


Link to post
Share on other sites
Quote:
Original post by jyk
Quote:
so,how do i handle this like a pro?
The easy answer is, 'use an existing physics engine'.

If you want to do it yourself though, your intuition that casting multiple rays is *not* the way to do it is correct. Instead, represent the objects in the game using single shapes with volume (or area, in 2-d). For example, for the player, you could use an axis-aligned box. The problem then reduces to a moving box vs. box test, which is pretty well documented online and elsewhere (terms you can search for include 'AABB SAT', 'box SAT', and 'separating axis test').

i wonder why i didnt figure it myself... i should probably look for such documents before i ask this but,if in frame 1 the player does not collide with the platform,while in frame 2 part of the player will be inside the platform,how can i know from which side of the platform the player came?

Share this post


Link to post
Share on other sites
Quote:
if in frame 1 the player does not collide with the platform,while in frame 2 part of the player will be inside the platform,how can i know from which side of the platform the player came?
There are basically two different kinds of tests you can perform: discrete, and continuous.

A discrete test just looks at the current configuration of the two objects, with no regard for their motion over time. With this method, you can 'guess' as to where the collision occurred by computing the minimum translational vector that will resolve the intersection. This will work fine for many cases, but if the ratio of an object's speed to its size is high, you might get incorrect results, or miss collisions altogether.

A continuous test, on the other hand, takes the motion of the objects into account (usually, only constant linear velocity is considered). A continuous test can return the exact time of intersection, and in many cases can also return additional information such as the point(s) of intersection and the collision normal.

Which method to use is basically up to you.

Share this post


Link to post
Share on other sites
Quote:
Original post by jyk
Quote:
if in frame 1 the player does not collide with the platform,while in frame 2 part of the player will be inside the platform,how can i know from which side of the platform the player came?
There are basically two different kinds of tests you can perform: discrete, and continuous.

A discrete test just looks at the current configuration of the two objects, with no regard for their motion over time. With this method, you can 'guess' as to where the collision occurred by computing the minimum translational vector that will resolve the intersection. This will work fine for many cases, but if the ratio of an object's speed to its size is high, you might get incorrect results, or miss collisions altogether.

A continuous test, on the other hand, takes the motion of the objects into account (usually, only constant linear velocity is considered). A continuous test can return the exact time of intersection, and in many cases can also return additional information such as the point(s) of intersection and the collision normal.

Which method to use is basically up to you.


the second one sounds like i'll need to use math that is not simple,so i guess i'll have to try the first one.
eh... only way i can think of finding which side is the one i collide with is by using rays,which returns me to the problem that i mentioned when i created this thread...

Share this post


Link to post
Share on other sites
Quote:
eh... only way i can think of finding which side is the one i collide with is by using rays,which returns me to the problem that i mentioned when i created this thread...
Doing some research will clear that up. Try searching both the forum archives and the internet in general using some of the terms I mentioned previously; also, check out the GDNet articles section, as there is some relevant info contained therein. If after that you still have questions, post back and someone should be able to help.

Share this post


Link to post
Share on other sites
Quote:
Original post by jyk
Quote:
eh... only way i can think of finding which side is the one i collide with is by using rays,which returns me to the problem that i mentioned when i created this thread...
Doing some research will clear that up. Try searching both the forum archives and the internet in general using some of the terms I mentioned previously; also, check out the GDNet articles section, as there is some relevant info contained therein. If after that you still have questions, post back and someone should be able to help.


ok then,thanks :)

Share this post


Link to post
Share on other sites
Actually, what you are trying to do is called "pixel perfect" collision, you are just checking a simple "point" against your world; that is only helpfull when doing bullets collisions.

If you are doing an old fashioned 2d games, so your character and world are built using sprites, then you have to use "tiles collision"; if you are doing a 3d game then instead using point versus triangles, use Boxes agains boxes, or sphere again boxes or spheres, that mean enclose your character and your plataform gometry into bound primitives like boxes or spheres.

for example take a look at this article: http://www.gamedev.net/reference/articles/article1026.asp

Share this post


Link to post
Share on other sites
Quote:
Actually, what you are trying to do is called "pixel perfect" collision
I believe that is incorrect; there's nothing in the OP's post that suggests he's looking for pixel-perfect collision detection (for one thing, he specified that the game is in 3-d).

Also, the article you linked to is, I believe, somewhat outdated, and may even have some errors in it. If you want to learn about the 'swept ellipsoid' approach, try this paper instead.

Share this post


Link to post
Share on other sites
well, i managed to find out how to check which side is the side i collide with,yet not get the intersection point.
pretty much i am suppoused to take the dot product of each side's normal and the velocity,and check which one is closest to -1. the one that is closest to it is the side where the collision happens. but that still leaves me without an intersection point,and i cant use a ray since it could miss...

Share this post


Link to post
Share on other sites
Quote:
Original post by Bru
well, i managed to find out how to check which side is the side i collide with,yet not get the intersection point.
pretty much i am suppoused to take the dot product of each side's normal and the velocity,and check which one is closest to -1. the one that is closest to it is the side where the collision happens.
It sounds like you might be doing something different than the typical swept AABB test. I suppose the method you described would work (I've never tried it), but the 'real' swept AABB test will tell you *exactly* when and where the collision occurred, so no guessing is required.
Quote:
but that still leaves me without an intersection point,and i cant use a ray since it could miss...
Keep in mind that in the general case, two axis-aligned boxes will not touch at a single point, but will instead share a contact manifold consisting of a line segment. Depending on what you need the collision info for though, you can reduce this to a single contact point (e.g. by using the segment midpoint).

Once you've computed the time of impact using the continuous SAT test, you can clip the colliding features together to yield the contact manifold. All this stuff is fairly straightforward, and has been discussed a lot in the math and physics forum here on GDNet in the past. Straightforward or not though, it can be kind of a pain to implement. I certainly don't want to discourage you from doing it yourself if that's what you prefer, but I'll go ahead and mention again the option of using an existing physics library (which can save a great deal of time and effort).

Share this post


Link to post
Share on other sites

This topic is 2821 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this