There is no "right" way, unless you use the analytic solution... of course, you normally won't have that available, unlike in testing. The Euler step is probably the most common approach. You could even use some kind of RK step if you wanted better accuracy. However, Euler is generally sufficient for a lot of simulations (even molecular dynamics). One of the best things about Verlet is that it is pretty stable and fast. For game programming that is often enough. In molecular dynamics the long simulations times usually mean that global accuracy is out the window anyway, so the long term stability is the main attraction there as well.
The need for accuracy is low in game programs, so it is not something to fret about. If you want accruacy, my first choice for most problems is Runge-Kutta-Fehlberg 4th order (Dormand-Prince coeffs) with adaptive stepping.
Help with acceleration
I see... Well, verlet made an impression on me because I was expecting it to be far more accurate. I didn't expect the initial conditions to affect the result at that extent...
I'm not planning on solving any ODEs (apart from the usual scheme in simple games), I just wanted a "first hand" experience, so I can have an opinion about these... It seems I was a little mislead with verlet...
For the most simple purposes, I prefer to use a custom euler implementation, which is far more accurate (more than 60-70%) than the regular one. Instead of approximating the area under the curve of acceleration by adding rectangles of area==dt*a(ti), I add trapezoids with area==.5*dt*(a(ti)+a(ti-1)).
The velocity is known for the previous timestep only (like verlet), but considering the speed and improved accuracy (with respect to simple forward euler), it has become my favourite for quite some time now...
I'm not planning on solving any ODEs (apart from the usual scheme in simple games), I just wanted a "first hand" experience, so I can have an opinion about these... It seems I was a little mislead with verlet...
For the most simple purposes, I prefer to use a custom euler implementation, which is far more accurate (more than 60-70%) than the regular one. Instead of approximating the area under the curve of acceleration by adding rectangles of area==dt*a(ti), I add trapezoids with area==.5*dt*(a(ti)+a(ti-1)).
The velocity is known for the previous timestep only (like verlet), but considering the speed and improved accuracy (with respect to simple forward euler), it has become my favourite for quite some time now...
Quote:Original post by someusername
I see... Well, verlet made an impression on me because I was expecting it to be far more accurate. I didn't expect the initial conditions to affect the result at that extent...
I'm not planning on solving any ODEs (apart from the usual scheme in simple games), I just wanted a "first hand" experience, so I can have an opinion about these... It seems I was a little mislead with verlet...
I still think Verlet should be performing on par with RK4 since your forcing function is smooth, however, I'm not 100% sure so I want to check it out when I get home tonight.
One last note, Verlet will be superior to RK4 if the system is Hamiltonian. Verlet will always stay close to the solution of a Hamiltonian system, unlike most other integrators. That is probably not too important for most of our applications, but you never know when these little facts will become useful [smile]
Quote:Original post by jjd
One last note, Verlet will be superior to RK4 if the system is Hamiltonian. Verlet will always stay close to the solution of a Hamiltonian system, unlike most other integrators.
I'm gonna have to look up the definition for that one... :) Thanks though.
Keep me posted if you get to try this afterall.
Quote:Original post by jjd
Verlet will always stay close to the solution of a Hamiltonian system, unlike most other integrators. That is probably not too important for most of our applications, but you never know when these little facts will become useful [smile]
From the little I've managed to read so far, what you say makes sense, because verlet calculates position only from position and acceleration (no velocity). Since velocities (which introduce error O(dt^2) in verlet) cannot affect accelerations in such a system, it seems that the solution of verlet will generally be more stable.
But then again I may be totally wrong!
Author
I appreciate all the help! :D
I have acceleration implemented now, and all tests of my space ship moving are good for now, but I have ran into another problem now.
My collision detection routine is now broke...Do I have to incorporate acceleration into my collision routine to make it work again? And if so, how would I start going about that?
Right now my collision detection is based on two circles, their given velocities and position at a given time frame.
If they collide, the result will be less than one, you just divide the distance traveled at current velocity by the result to get where point of contact would be at...Heh....
I have acceleration implemented now, and all tests of my space ship moving are good for now, but I have ran into another problem now.
My collision detection routine is now broke...Do I have to incorporate acceleration into my collision routine to make it work again? And if so, how would I start going about that?
Right now my collision detection is based on two circles, their given velocities and position at a given time frame.
If they collide, the result will be less than one, you just divide the distance traveled at current velocity by the result to get where point of contact would be at...Heh....
Acceleration wouldn't normally play any direct role in collision detection. So, you use circles as bounding regions of your objects, but how are you using the velcities? Are you creating capsules out of the bounding regions, or predicting time-of-impact?
I don't understand your current detection algorithm. Given that you divide distance by this "result" and still get distance, it should be some dimensionless factor, a ratio... but ratio of what? Since you would get a collision for "result" < 1, it makes me think that it's the ratio of the distance of the circles' centers, by the sum of their radii, but this doesn't make sense with finding the contact point as you describe, nor should it be affected by acceleration...
Anyway... To determine whether two circles collide, you can do this:
1. Consider the 1st circle stationary and find the relative position and velocity of the 2nd one with respect to the 1st.
relPos2 = Pos2 - Pos1, relVel2 = Vel2 - Vel1, all vectors.
2. If |relPos2| is less than (radius1 + radius2) you have a collision.
Calculate deltaX = (radius1 + radius2) - |relPos2|
Calculate deltaT = deltaX/|relVel2|
3. The collision point is "Pos1 + (Radius1/|relPos2|)*relPos2" and the collision occured "deltaT" time ago.
edit:
(3) should be:
Pos1' = Pos1 - Pos1Vel*deltaT
Pos2' = Pos2 - Pos2Vel*deltaT
collision point = Pos1' + (Radius1/(Radius1+Radius2))*(Pos2' - Pos1')
[Edited by - someusername on March 14, 2006 6:12:48 PM]
Anyway... To determine whether two circles collide, you can do this:
1. Consider the 1st circle stationary and find the relative position and velocity of the 2nd one with respect to the 1st.
relPos2 = Pos2 - Pos1, relVel2 = Vel2 - Vel1, all vectors.
2. If |relPos2| is less than (radius1 + radius2) you have a collision.
Calculate deltaX = (radius1 + radius2) - |relPos2|
Calculate deltaT = deltaX/|relVel2|
3. The collision point is "Pos1 + (Radius1/|relPos2|)*relPos2" and the collision occured "deltaT" time ago.
edit:
(3) should be:
Pos1' = Pos1 - Pos1Vel*deltaT
Pos2' = Pos2 - Pos2Vel*deltaT
collision point = Pos1' + (Radius1/(Radius1+Radius2))*(Pos2' - Pos1')
[Edited by - someusername on March 14, 2006 6:12:48 PM]
Author
I'm predicting time of impact (I believe)
Here is the function i am currently using:
Here is the function i am currently using:
function Circle(){ //23 for most characters is a good default this.radius;// = 23; this.center = new Vector();}//A is Circle//B is circle//movevec is the offsetted movement vectorfunction TestCollision(A, B, movevec){// Early Escape //test: if the length of the movevec is less than distance between the centers of these circles minus their radii, there's no way they can hit. var moveMag = movevec.Magnitude() var dist = B.center.Distance(A.center); var sumRadii = (B.radius + A.radius); dist -= sumRadii; if(movevec.Magnitude() < dist){return 1;} // Normalize the movevec var N = movevec.copyvec(); N.normalize(); // Find C, the vector from the center of the moving // circle A to the center of B var C = B.center.Minus(A.center); // D = N . C = ||C|| * cos(angle between N and C) var D = N.Dot(C); // Another early escape: Make sure that A is moving towards B! If the dot product between the movevec and B.center - A.center is less that or equal to 0, A isn't moving towards B if(D <= 0){return 1;} // Find the length of the vector C var lengthC = C.Magnitude(); var F = (lengthC * lengthC) - (D * D); // Escape test: if the closest that A will get to B is more than the sum of their radii, there's no way they are going collide var sumRadiiSquared = sumRadii * sumRadii; if(F >= sumRadiiSquared){return 1;} // We now have F and sumRadii, two sides of a right triangle. // Use these to find the third side, sqrt(T) var T = sumRadiiSquared - F; // If there is no such right triangle with sides length of // sumRadii and sqrt(f), T will probably be less than 0. // Better to check now than perform a square root of a // negative number. if(T < 0){return 1;} // Therefore the distance the circle has to travel along // movevec is D - sqrt(T) var distance = D - Math.sqrt(T);// Get the magnitude of the movement vector var mag = movevec.Magnitude(); // Finally, make sure that the distance A has to move // to touch B is not greater than the magnitude of the // movement vector. if(mag < distance){return 1;} // Set the length of the movevec so that the circles will just touch return distance / moveMag;}
OK. Here are a few things to consider. Is this function meant to tell you the distance between the circles or the whether two circles overlap? Decide what the purpose of this function is because you seem to be returning logical values in some places, and a real value at the end. The 'T' variables and it's associated test does nothing useful. The test immediately above it does the same thing.
I don't understand what the movevec variable is. I'm not trying to be difficult, but I just don't know what you mean by movement vector.
I'm having a blonde moment, but I suspect you don't need the test on the relative velocity. Can anyone else comment on that?
I'm not sure what is happening at the beginning of the function (one to many beers...) but I would just test whether the dot product of the relative displacement with itself is less than the square of the sum of the radii. Symbolically,
x = a - b;
x2 = dot(x,x);
r = r.a + r.b;
if (x2 < r*r) we have a collision
where a and b are the positions of the centers of the circles.
I don't understand what the movevec variable is. I'm not trying to be difficult, but I just don't know what you mean by movement vector.
I'm having a blonde moment, but I suspect you don't need the test on the relative velocity. Can anyone else comment on that?
I'm not sure what is happening at the beginning of the function (one to many beers...) but I would just test whether the dot product of the relative displacement with itself is less than the square of the sum of the radii. Symbolically,
x = a - b;
x2 = dot(x,x);
r = r.a + r.b;
if (x2 < r*r) we have a collision
where a and b are the positions of the centers of the circles.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
