## the best way to do collision detection

Member
Posts: 177
Joined: 2002.08
Post: #16
Quote:Originally posted by Feanor

On with collision detection. Who is recommending using a library? Mark Levin. ghettotek wants to learn some new ideas. You could at least word it differently: "You might consider ... ", but why not be encouraging? That's what iDevGames is about.

I meant the operative word there to be "consider". I don't mind if he considers it and then decides I'm totally wrong

And besides, having some source lying around that's proven to work for the same task can be an invaluable learning tool even if it's not used directly in the program in question.
Member
Posts: 78
Joined: 2002.06
Post: #17
Quote:Originally posted by Feanor
... except that said he wanted to know more about how to do it. He can't learn very much by employing someone else to do it for him.

Noted in that case if you want to learn more about it, which is very worth while even if you end up using someone elses code, as you will have an idea of how it works.

Have a look at these:

http://www.gamasutra.com/features/20000330/bobic_01.htm
http://www.flipcode.com/tutorials/tut_collision.shtml

There as some good bits here as well, although they concentrate on the physics.

http://www.d6.com/users/checker/dynamics.htm

Actual collision detection is usually tied very much to the pyhsics engine you use. If you want actual algorithms to tell if something is hit then I can give you them, but to handle physics and proper responses is harder.
Mars_999
Unregistered

Post: #18
Quote:Originally posted by inio

has nothing to do with calculus. [/b]

How is that? It's a derivative. Calculus is the instantaneous rate of change or am I wrong. Intergration and derivatives are calculus. I dont' remember intergration anymore due to way to many rules. I do know this 2x^3 derivative is 6x. Thats why I put 12x^4 = 48x^3 if you remember the power rule that is correct. Drop the exponent and multiply and subtract one from the exponent. That's a part of calculus. Unless Calculus has changed.
Feanor
Unregistered

Post: #19
Quote:Originally posted by Mars_999
How is that? It's a derivative. Calculus is the instantaneous rate of change or am I wrong. Intergration and derivatives are calculus. I dont' remember intergration anymore due to way to many rules. I do know this 2x^3 derivative is 6x. Thats why I put 12x^4 = 48x^3 if you remember the power rule that is correct. Drop the exponent and multiply and subtract one from the exponent. That's a part of calculus. Unless Calculus has changed.

You didn't include the derivate symbol, so all you wrote was an equality formula consisting of two equations in one unknown, NOT a derivate solution. While the derivate of 12x^4 may be 48x^3 (and no one is arguing that), you have to say "d/dx..." to have a technically correct expression. We all knew what you meant, but some people are afraid you will fail calculus, or maybe that you will corrupt naive readers of the board with your fast and loose short hand.

Are we far enough off topic yet? Does anyone have anything to say about collision detection, or just about how to write calculus expressions that Look Really Cool™? Am I being an fascist moderator? Is there life on other planets?
Mars_999
Unregistered

Post: #20
Quote:Originally posted by Feanor
You didn't include the derivate symbol, so all you wrote was an equality formula consisting of two equations in one unknown, NOT a derivate solution. While the derivate of 12x^4 may be 48x^3 (and no one is arguing that), you have to say "d/dx..." to have a technically correct expression. We all knew what you meant, but some people are afraid you will fail calculus, or maybe that you will corrupt naive readers of the board with your fast and loose short hand.

Are we far enough off topic yet? Does anyone have anything to say about collision detection, or just about how to write calculus expressions that Look Really Cool™? Am I being an fascist moderator? Is there life on other planets?

Ok, I see now. Yes thats my bad. Sorry I was just starting to wondering if my calculus was right? dy/dx =. My prof was anal about using = then your result when we did calculus. So now I am a rebel!! I did get an A in all my math though. Muahahha

What I was getting at with calculus is why couldn't you use the derivative to find the point your looking for? Oh, I think it just hit me that might lead to differential equations? Or am I lost? I never took D.E. just for the record!
Feanor
Unregistered

Post: #21
Why would we not use calculus? Because it is slow? :?: Actually I am not sure how to use it in collision detection, being not even a novice (although I read an article on it today). Seriously, most of the equations used are linear, so calculus cannot help. Everything should be lines and planes and points -- that is, in the discrete approach. In the predictive approach, it might indeed be helpful if your paths are quadratic.
Member
Posts: 145
Joined: 2002.06
Post: #22
Quote:Originally posted by Feanor
Why would we not use calculus? Because it is slow? :?: Actually I am not sure how to use it in collision detection, being not even a novice (although I read an article on it today). Seriously, most of the equations used are linear, so calculus cannot help. Everything should be lines and planes and points -- that is, in the discrete approach. In the predictive approach, it might indeed be helpful if your paths are quadratic.
Calculus becomes useful when you want to determine if moving objects could intersect. For example, given two spheres centers, velocities, accelerations, and radii, you can use calculus to find the time(s) when they will be nearest each other, and from that determine if they could intersect at any time between two given instants.

"He who breaks a thing to find out what it is, has left the path of wisdom."
- Gandalf the Gray-Hat

Bring Alistair Cooke's America to DVD!
Moderator
Posts: 869
Joined: 2003.01
Post: #23
Knowledge of higher maths is very useful, latest when you have to optimze code. Often, it really helps to write out the math and do simplifications/rearrangements that way, rather than doing it in the code, where you might not even see what you have to do.

Discrete math, linear algebra, differential calculus, tensor math, etc, can all be useful, but they are a work of the devil.

You actually don't need calculus to determine when two things intersect, its linear algebra, if I am not mistaken. In code, you don't use calculus, really, since calculus is mostly theory. You might use it when designing code, though.

Anyhow, I always wondered why I had to take 4 semesters of math. 90% of it I can't remember, but those rest 10% come in handy at times. It can impress people if you can prove that 1+1=2 with about 10 pages of theorems . And being fussy about math, a teacher once zeroed a math exam because I wrote an = sign instead of an arrow in a place.

- D.G
Mars_999
Unregistered

Post: #24
Quote:Originally posted by Feanor
Why would we not use calculus? Because it is slow? :?: Actually I am not sure how to use it in collision detection, being not even a novice (although I read an article on it today). Seriously, most of the equations used are linear, so calculus cannot help. Everything should be lines and planes and points -- that is, in the discrete approach. In the predictive approach, it might indeed be helpful if your paths are quadratic.

Calculus deal with any equations. Linear or ^2 or ^3 really doesnt' matter. I was thinking about the detection of two objects and their times and velocities as was stated by Inio. But in games I guess people could care less about accuracy, because calculus is going to be accurate as it gets. I just thought that using calculus would be fast because you could derive a equation that would work for your world and use that equation instead of all these spheres, planes and everything else you can think of. But to tell you the truth I haven't had Calculus in a long time now and its to rusty for me to use anymore but if your good at it you could use it to do some powerful calculations instead of using trig all the time.
Feanor
Unregistered

Post: #25
Right, that's what I meant by "predictive collision detection" -- predicting collisions by extrapolating current velocities. The only time this is used is when objects are moving very fast, and there is a possibility that they could travel through another object between frames of animation. I still am having trouble determining the particular application of calculus methods, although I can see that for accelerating objects, rates of change would be involved. inio is the math whiz around here; maybe he has some idea.

I can see linear algebra being useful for solving two equations in two unknowns in order to see if paths interesect in space. I cannot at the moment see how to put time into it, in order to avoid false positives for paths that intersect but disjointly in time. I am sure that someone has put a solution out somewhere.
Nibbie
Posts: 1
Joined: 2009.06
Post: #26
Predictive collision detection is a matter of calculating the x and y coordinates of the objects as a function of time (t), then using that to find the distance between pairs of objects as a function of time: sqrt( [x1(t) - x2(t)]^2 + [y1(t) - y2(t)]^2 ). You want to set that equal to the sum of the radii of the objects = r1+r2. It greatly simplifies things to just square both sides and get rid of the radical: [x1(t) - x2(t)]^2 + [y1(t) - y2(t)]^2 = (r1+r2)^2

Then you "just" solve for 't'. This is much easier said than done because after combining like terms and all that the equation turns out to be somewhere between a 3rd to 5th order polynominal, depending on whether the objects are accelerating or not. So you've got to find formulas for solving cubic/quartic/quintic (3,4,5th-order) equations, and implement those. I hope you like working w/complex numbers.

In the end you may get up to 5 points of intersection. The only one you really should be concerned about is the lowest 't' value past the current time. anything before that has already happened, the one right after that is after the objects "pass thru" each-other, which is exactly what you're going to prevent them from doing, and the remaining ones aren't going to happen because the collision will change the trajectories of the objects. More often than not there won't be any future intersection points because the two objects aren't going to collide.

You always want to take the first collision over all pairs, because that collision is going to change the trajectories and thus possibly affect future collisions. This also means that you'll have to recalculate after each collision. (And whenever an object makes a course adjustment.)

A nice optimization is realizing that you don't have to recalculate ALL pairs - you really only have to do about 2N recalculations, rather than NxN, but that's a whole 'nother topic that I'll leave for the ambitious to work out on their own.

Frankly, I think predictive collision detection can be much faster than other methods, depending on the application. The main difficulty is solving for t and keeping track off all the predictions and re-calculations you have to do. There are formulas out there to solve for t for up to second-order position equations (x = a+bt+ct^2), but if your position equations are any more complex than that, you'll want to consider approximating or using a different method altogether. This method certainly has it's advantages, and a second-order equation is perfect for a true-to-physics space game (neglecting gravity). I'm using it. Hence I'm able to explain it.
Moderator
Posts: 3,591
Joined: 2003.06
Post: #27
Nice input on the subject, but this thread is over six years old! I guess it's still relevant, but talk about raising the dead...