RK4 integrator

Showcase your libraries, tools and other projects that help your fellow love users.
Post Reply
Kyle
Party member
Posts: 146
Joined: Sat Mar 16, 2013 9:46 pm

RK4 integrator

Post by 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!
User avatar
Ranguna259
Party member
Posts: 911
Joined: Tue Jun 18, 2013 10:58 pm
Location: I'm right next to you

Re: RK4 integrator

Post by Ranguna259 »

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 :D

Check out my twitter.
User avatar
Roland_Yonaba
Inner party member
Posts: 1563
Joined: Tue Jun 21, 2011 6:08 pm
Location: Ouagadougou (Burkina Faso)
Contact:

Re: RK4 integrator

Post by 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
Party member
Posts: 146
Joined: Sat Mar 16, 2013 9:46 pm

Re: RK4 integrator

Post by Kyle »

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.
User avatar
Roland_Yonaba
Inner party member
Posts: 1563
Joined: Tue Jun 21, 2011 6:08 pm
Location: Ouagadougou (Burkina Faso)
Contact:

Re: RK4 integrator

Post by 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.
User avatar
Ranguna259
Party member
Posts: 911
Joined: Tue Jun 18, 2013 10:58 pm
Location: I'm right next to you

Re: RK4 integrator

Post by 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 :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 :D

Check out my twitter.
Kyle
Party member
Posts: 146
Joined: Sat Mar 16, 2013 9:46 pm

Re: RK4 integrator

Post by Kyle »

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 :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.
User avatar
Roland_Yonaba
Inner party member
Posts: 1563
Joined: Tue Jun 21, 2011 6:08 pm
Location: Ouagadougou (Burkina Faso)
Contact:

Re: RK4 integrator

Post by Roland_Yonaba »

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.
User avatar
Ranguna259
Party member
Posts: 911
Joined: Tue Jun 18, 2013 10:58 pm
Location: I'm right next to you

Re: RK4 integrator

Post by Ranguna259 »

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 :D

Check out my twitter.
User avatar
darkfrei
Party member
Posts: 1168
Joined: Sat Feb 08, 2020 11:09 pm

Re: RK4 integrator

Post by darkfrei »

Kyle wrote: Mon Apr 21, 2014 7:55 pm
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
:awesome: in Lua we Löve
:awesome: Platformer Guide
:awesome: freebies
Post Reply

Who is online

Users browsing this forum: No registered users and 11 guests