RK4 integrator

[Kyle]

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]

what is this ?

[Roland_Yonaba]

@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).

This article @GafferOnGames is quite an authority on the topic.
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]

@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]

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]

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

[Kyle]

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]

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]

Thanks, I'll look into those

[darkfrei]

Free to whoever wants it!

Thanks, it looks like I really need it!

Code: Select all

	-- Runge-Kutta 4 Lua implementation
	-- (c) darkfrei 2021
	--
	--Reference: http://gafferongames.com/game-physics/integration-basics/
	--Special thanks to Glenn Fiedler

local RK4 = {}

function RK4.evaluate (state, dt, d)
	state.x=state.x + d.dx*dt
	state.v=state.v + d.dv*dt
	return {dx=state.v, dv=state.a}
end

function RK4.integrate (x, v, acc, dt) -- old position and velocity; new acceleration, dt between them
	local state = {x=x,v=v, a=acc}
	local derivative = {dx = 0,	dv = 0}
	local a = RK4.evaluate (state, 0, derivative)
	local b = RK4.evaluate (state, 0.5*dt, a)
	local c = RK4.evaluate (state, 0.5*dt, b)
	local d = RK4.evaluate (state, dt, c)
	local dxdt = (a.dx+2*b.dx+2*c.dx+d.dx)/6
	local dvdt = (a.dv+2*b.dv+2*c.dv+d.dv)/6
	
	return state.x + dxdt*dt, state.v + dvdt*dt
end

return RK4