## RK4 integrator

Kyle
Party member
Posts: 146
Joined: Sat Mar 16, 2013 9:46 pm

### RK4 integrator

Code: Select all

--Runge-Kutta 4 Lua implementation
--2014 Kyle Emmerich
--
--Reference: http://gafferongames.com/game-physics/integration-basics/
--Special thanks to Glenn Fiedler

local RK4 = {}
--Simple structures for ease of use
RK4.Derivative2D = function(dx, dy, dvx, dvy)
return {dx = dx, dy = dy, dvx = dvx, dvy = dvy}
end
RK4.Derivative1D = function(dx, dv)
return {dx = dx, dv = dv}
end
RK4.State2D = function(x, y, vx, vy)
return {x = x, y = y, vx = vx, vy = vy}
end
RK4.State1D = function(x, v)
return {x = x, v = v}
end

--Evaluators
RK4.Evaluate2D = function(initial, t, dt, deriv, ax, ay)
initial.x = initial.x + deriv.dx * dt
initial.y = initial.y + deriv.dy * dt

initial.vx = initial.vx + deriv.dvx * dt
initial.vy = initial.vy + deriv.dvy * dt

return RK4.Derivative2D(initial.vx, initial.vy, ax, ay)
end
RK4.Evaluate1D = function(initial, t, dt, deriv, a)
initial.x = initial.x + deriv.dx * dt
return RK4.Derivative1D(initial.v, a)
end

--Integrators
RK4.Integrate2D = function(initial, t, dt, ax, ay)
local a = RK4.Evaluate2D(initial, t, 0, RK4.Derivative2D(0, 0, 0, 0), ax, ay)
local b = RK4.Evaluate2D(initial, t, dt * 0.5, a, ax, ay)
local c = RK4.Evaluate2D(initial, t, dt * 0.5, b, ax, ay)
local d = RK4.Evaluate2D(initial, t, dt, c, ax, ay)

local dxdt = 	1.0 / 6.0 * (a.dx 	+ 2.0 * (b.dx 	+ c.dx) 	+ d.dx)
local dydt = 	1.0 / 6.0 * (a.dy 	+ 2.0 * (b.dy 	+ c.dy) 	+ d.dy)
local dvxdt = 	1.0 / 6.0 * (a.dvx 	+ 2.0 * (b.dvx 	+ c.dvx) 	+ d.dvx)
local dvydt = 	1.0 / 6.0 * (a.dvy 	+ 2.0 * (b.dvy 	+ c.dvy) 	+ d.dvy)

return RK4.State2D(
initial.x + dxdt * dt,
initial.y + dydt * dt,
initial.vx + dvxdt * dt,
initial.vy + dvydt * dt
)
end
RK4.Integrate1D = function(initial, t, dt, acc)
local a = RK4.Evaluate1D(initial, t, 0, RK4.Derivative1D(0, 0), acc)
local b = RK4.Evaluate1D(initial, t, dt * 0.5, a, acc)
local c = RK4.Evaluate1D(initial, t, dt * 0.5, b, acc)
local d = RK4.Evaluate1D(initial, t, dt, c, acc)

local dxdt = 1.0 / 6.0 * (a.dx + 2.0 * (b.dx + c.dx) + d.dx)
local dvdt = 1.0 / 6.0 * (a.dv + 2.0 * (b.dv + c.dv) + d.dv)

return RK4.State1D(
initial.x + dxdt * dt,
initial.v + dvdt * dt
)
end

return RK4
Free to whoever wants it!

Ranguna259
Party member
Posts: 911
Joined: Tue Jun 18, 2013 10:58 pm
Location: I'm right next to you

### Re: RK4 integrator

what is this ?
LoveDebug- A library that will help you debug your game with an on-screen fully interactive lua console, you can even do code hotswapping

Roland_Yonaba
Inner party member
Posts: 1563
Joined: Tue Jun 21, 2011 6:08 pm
Contact:

### Re: RK4 integrator

@Kyle: Nice work!

@Ranguna259:
RK4 is an alias for Runge Kutta 4th-order integration method.
Simply said, it is a method used to solve differential equations using a numerical approach and time discretization.
There are lots of methods for solving ODEs (Ordinary Differential Equations). The well-known and most simple one is Euler method (also Newton tangent method). There is also Heun (which is equivalent to RK2), and then RK1, RK2, RK4 (respectively for Runge-Kutta 1rst order, 2nd order and 4th order).

As for efficiency, Euler method is the fastest, but less precise (also said less stable). RK4 is costful, but very stable.
I use them a lot in my daily work (lots of fluid mechanics laws of motion, kinematics and dynamics are based on differential equations). In games though, they are used mostly for solving time-integration problems (in physics engine).

There are also this one and this one.There is also a very interesting discussion we had on this on this forum, and also a technical demo I wrote back in days to illustrate this. You can get the source on Github, it requires Löve 0.8.0.

EDIT: Side note, there is an already existing module, by Peter J. Billam, for RK methods on LuaRocks.

Kyle
Party member
Posts: 146
Joined: Sat Mar 16, 2013 9:46 pm

### Re: RK4 integrator

Roland_Yonaba wrote:@Kyle: Nice work!
Thanks! I mostly just implemented it straight from gafferongames's article on it so I can't really take much credit other than the fact that I typed it.

Roland_Yonaba
Inner party member
Posts: 1563
Joined: Tue Jun 21, 2011 6:08 pm
Contact:

### Re: RK4 integrator

Just an addendum, I also have an implementation of RK4, though it was designed for solving time-integration for an agent moving at a constant acceleration.
The other integrators (Euler, Verlet, Heun, etc) can be found here.

Ranguna259
Party member
Posts: 911
Joined: Tue Jun 18, 2013 10:58 pm
Location: I'm right next to you

### Re: RK4 integrator

I was actually looking for this a few days ago, this might come in handy as it looks like the only way do to smooth zoom and smooth movement (in my peticular method) is to use an equation, awesome
LoveDebug- A library that will help you debug your game with an on-screen fully interactive lua console, you can even do code hotswapping

Kyle
Party member
Posts: 146
Joined: Sat Mar 16, 2013 9:46 pm

### Re: RK4 integrator

Ranguna259 wrote:I was actually looking for this a few days ago, this might come in handy as it looks like the only way do to smooth zoom and smooth movement (in my peticular method) is to use an equation, awesome
If you're just looking to get from point A to point B smoothly, I recommend kikito's tween.lua! This is actually more suitable for implementing Newtonian physics.

Roland_Yonaba
Inner party member
Posts: 1563
Joined: Tue Jun 21, 2011 6:08 pm
Contact:

### Re: RK4 integrator

Kyle wrote:If you're just looking to get from point A to point B smoothly, I recommend kikito's tween.lua! This is actually more suitable for implementing Newtonian physics.
Or rsxi's recent flux.lua.
This guy is doing really great stuff

Side note, a nice set of ressources about easing (and tweening) can be found on Robert Penner's website. In my opinion, tweening is not physics, but just a visual a nice trick to provide timed controlled motion. In case you want to move agents and you don't really care about physics, you can go for tweening. It is light, cheap, fast and produces nice animatrions easily.

Ranguna259
Party member
Posts: 911
Joined: Tue Jun 18, 2013 10:58 pm
Location: I'm right next to you

### Re: RK4 integrator

Thanks, I'll look into those
LoveDebug- A library that will help you debug your game with an on-screen fully interactive lua console, you can even do code hotswapping