Jump to content
  • Advertisement
Sign in to follow this  
adriansnetlis

How does Runge-Kutta 4 work in games

This topic is 764 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 want to find out one simple thing that I can nowhere find solution for.

So I have this workflow:

  • I know object's position vector which is x
  • I know object's velocity vector which is v
  • I know object's applied force vector which is f
  • Object's mass is m
  • dt is the timestep

The force includes spring equation with high stiffness. This results in forward Euler method being critically unstable.

dv = f / m
v += dv * dt
x += v * dt

I need to replace this with Runge-Kutta somehow. However, I don't know how. Also I think that this may affect gravity part of force which I don't want to(propably). I even don't know how to make it act for spring-part only. Propably there's no need, tho. I don't even know:D

Share this post


Link to post
Share on other sites
Advertisement
The Wikipedia page on RK methods seems pretty good: . If you have trouble understanding that page, please ask a more concrete question.

To use RK4 you need to be able to recompute f after half a step, so you need to have f specified as a function of time and x, not a single number.

However, if you are trying to integrate a system with stiff springs you probably should consider an implicit method.

Share this post


Link to post
Share on other sites
Oh, perhaps this is what you are having trouble with: In the equation y' = f(t,y), you can take y to be the vector (x,v). See if the Wikipedia page makes more sense with that in mind.

Share this post


Link to post
Share on other sites

I don't think that most physics engines use RK4 at all, most use semi-implicit euler for its balance of speed and stability. It's ok for simple stuff like mass/spring systems, but once you incorporate collision detection and response with RK4 there is not much benefit except in certain cases. For each substep you still need to test for collisions and respond so the performance is about 4x worse than 1st-order integration methods. The integration accuracy is better than just performing 4 1st order steps, but there are many headaches involved with using RK4 in a full physics simulation for games.

Edited by Aressera

Share this post


Link to post
Share on other sites

I need to replace this with Runge-Kutta somehow. 

No, you don't.

 

I don't think that most physics engines use RK4 at all, most use semi-implicit euler for its balance of speed and stability. It's ok for simple stuff like mass/spring systems, but once you incorporate collision detection and response with RK4 there is not much benefit except in certain cases. For each substep you still need to test for collisions and respond so the performance is about 4x worse than 1st-order integration methods. The integration accuracy is better than just performing 4 1st order steps, but there are many headaches involved with using RK4 in a full physics simulation for games.

Yep. RK4, in short, is garbage. I always found it bizarre that Gaffer on Games recommends it by citing its accuracy, which isn't a particularly important integration property for a game. Stability (energy conservation/symplectic) is a vastly more useful property, and RK4 doesn't have it. In most cases, you can simply use semi-implicit euler and be on your way. Hell, it's faster performance to drive semi-implicit euler at higher frequency than to run RK4.

Share this post


Link to post
Share on other sites

The Wikipedia page on RK methods seems pretty good: . If you have trouble understanding that page, please ask a more concrete question.

To use RK4 you need to be able to recompute f after half a step, so you need to have f specified as a function of time and x, not a single number.

However, if you are trying to integrate a system with stiff springs you probably should consider an implicit method.

Hm... The problem is that the wikipedia page uses 't' parameter which doesn't exist in game. That 't' parameter hardcodes it to curve. However, game's don't need it.

 

The implicit method is impossible in games, cause it has a closed loop. Current velocity calculation requires current position and current position calculation requires current velocity. You need to know one to calculate other one.

 

 

 

I need to replace this with Runge-Kutta somehow. 

No, you don't.

 

I don't think that most physics engines use RK4 at all, most use semi-implicit euler for its balance of speed and stability. It's ok for simple stuff like mass/spring systems, but once you incorporate collision detection and response with RK4 there is not much benefit except in certain cases. For each substep you still need to test for collisions and respond so the performance is about 4x worse than 1st-order integration methods. The integration accuracy is better than just performing 4 1st order steps, but there are many headaches involved with using RK4 in a full physics simulation for games.

Yep. RK4, in short, is garbage. I always found it bizarre that Gaffer on Games recommends it by citing its accuracy, which isn't a particularly important integration property for a game. Stability (energy conservation/symplectic) is a vastly more useful property, and RK4 doesn't have it. In most cases, you can simply use semi-implicit euler and be on your way. Hell, it's faster performance to drive semi-implicit euler at higher frequency than to run RK4.

 

Either I suck at implementing the semi-implicit method or either it's still not stable enaugh. I tried it, but it's UNSTABLE. You can take a look at the last video in my BATMA post. If implicit was possible, that one may be better.

Share this post


Link to post
Share on other sites

I don't think that most physics engines use RK4 at all, most use semi-implicit euler for its balance of speed and stability. It's ok for simple stuff like mass/spring systems, but once you incorporate collision detection and response with RK4 there is not much benefit except in certain cases. For each substep you still need to test for collisions and respond so the performance is about 4x worse than 1st-order integration methods. The integration accuracy is better than just performing 4 1st order steps, but there are many headaches involved with using RK4 in a full physics simulation for games.

Yep. RK4, in short, is garbage. I always found it bizarre that Gaffer on Games recommends it by citing its accuracy, which isn't a particularly important integration property for a game. Stability (energy conservation/symplectic) is a vastly more useful property, and RK4 doesn't have it. In most cases, you can simply use semi-implicit euler and be on your way. Hell, it's faster performance to drive semi-implicit euler at higher frequency than to run RK4.

 

 

I allow RK4 as option to be used for the substep calculations in vehicles. The general physics, collisions, etc. are calculated by the physics engine (PhysX in this case) normally at its own Euler rate. Within the vehicle, I can enable RK4 to perform the internal vehicle dynamics calculations (torques, internal inertias, etc) per physics step. The resulting forces are then passed to Physics for the regular physics step.

 

RK4 and Euler with 4 substeps result in the same performance. The differences are RK4 providing more stability and somewhat "smoother" values compared with 4 Euler integrations.

Edited by Edy

Share this post


Link to post
Share on other sites

Hm... The problem is that the wikipedia page uses 't' parameter which doesn't exist in game. That 't' parameter hardcodes it to curve. However, game's don't need it.


How is that a problem? The Wikipedia page is considering a more general case than the one you are working on. There is nothing wrong with a function of position and time that doesn't actually depend on time.

 

The implicit method is impossible in games, cause it has a closed loop. Current velocity calculation requires current position and current position calculation requires current velocity. You need to know one to calculate other one.


That's why these methods require you to solve a linear system of equations. This is not an impossible problem. Edited by Álvaro

Share this post


Link to post
Share on other sites

 

Hm... The problem is that the wikipedia page uses 't' parameter which doesn't exist in game. That 't' parameter hardcodes it to curve. However, game's don't need it.

How is that a problem? The Wikipedia page is considering a more general case than the one you are working on. There is nothing wrong with a function of position and time that doesn't actually depend on time.

I just don't understand how would I implement it in the integration system. It doesn't make any sense. What to put in the f(y, t)? In my case it's single input equation f(dv) which is used to update the position.

 

 

 

The implicit method is impossible in games, cause it has a closed loop. Current velocity calculation requires current position and current position calculation requires current velocity. You need to know one to calculate other one.


That's why these methods require you to solve a linear system of equations. This is not an impossible problem.

 

 

I don't understand. What type of linear system of equations(whatever it means) can lead to a value for use in equation which's solution is needed to obtain that value. It's just impossible. Unless there is alternate equation which gives the exact same result.

 

Why is integration so horribly complex thing? I start to really hate it... :(

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!