Interesting ways you've used integrals

Stray_Train · 5:20pm 20 Oct 2012

I've been studying for a math exam right and the main thing I've learned is that integrals suck ass. They'd probably suck less ass if I knew more ways to apply them.

So the question is: have you some found cool applications for integrals?

Elyaradine · 6:19pm 20 Oct 2012

Great question! :) I'll ask the guys at work.

I seem to remember it being used quite a lot in lighting calculations... but that might be offline-rendering as opposed to games.

Elyaradine · 8:35pm 1 Jan 2013

Okay, so I forgot to ask the guys at work, but while I was working, and playing various videos in the background, I came across this. Not linking you to the time, because you should watch the whole thing. ;)

Check out the others while you're there, especially considering this seems to be one of your interests. They're not _all_ amazing (there are a couple of folks there that I think talked rubbish), but you can draw your own conclusions by comparing their answers to one another. ;)

http://www.youtube.com/user/opcode6?feature=watch

hermantulleken · 10:32pm 1 Jan 2013

In general game programming, formal integration does not arise so often. One reason is that you always need a numerical value, and these can be calculated without knowing that you are integrating (for instance, you can calculate the area under a sine curve without knowing the antiderrivative is -cos.)

Understanding integrals (and calculus in general) and how they are computed are extremely useful for understanding many algorithms presented in irritatingly terse mathematical form that algorithm designers sometimes use. To give one example, the following is a blurring "algorithm":

F(x, y) = \int_{A(x, y)} a * f(x, y)

Here, f, is an image function, A(x, y) is a point set around (x, y),say a square, for example, and a is a normalising constant, equal to (1/ the area of the square), say.

In an actual application, you will of course not calculate the integral, but merely sum the pixel values in the square for each point.

So if you understand integrals, you have access to much more algorithms that other programmers won't understand.

----

Another useful application of integration comes up in control, which can be used for AI, for instance. (A "control system" is roughly a system that responds "sensibly" to noisy input). PID-control uses a combination of the input (P), the derivative of the input (D), and "integral" of the input (I) to work out its response. A simple example is a steering agent that calculates a steering angle (a) based on the angle turned away from the path (f) with this:

a(t) = A * f(t) + B * f'(t) + C* \int_{x=t - t0..t} f(x) dx //You may need another constant multiplied with everything to scale it and invert it)

where you tweak A, and B, and C based on the desired behaviour and characteristics of the input f. Roughly, the integration term serves as a windowed average, which tends to filter out noise (small bumps in the road). This leads to a delay in the response, which can be reduced by the derrivative term (it serves as a kind of prediction term - remember, it calculates the rate of change).

Mini#37 (Luma Arcade's first game

) used this kind of control for the AI vehicles. This is also useful to implement fast-moving hovercrafts physics, that I have done for another unreleased game at I-Imagine see http://code-spot.co.za/2010/07/27/a-simple-trick-for-moving-objects-in-a-physics-simulation/. Of course, you won't even know that integration is involved here if you don't understand the relationship between displacement, velocity, acceleration and force.

----

Integrarion is also common in AI and advanced statistics (often the same thing). For example, neural nets (PDF), and generating numbers for arbitrary distributions. (This article does not use the concept of integration explicitly, but again, if you know "accumulative probability" is the integral of the distribution function, it is a lot easier to understand).

----

Stray_Train · 12:27am 2 Jan 2013

@hermantulleken thanks for the post :)

Questions:

a(t) = A * f(t) + B * f'(t) + C* \int_{x=t - t0..t} f(x) dx

What would f(t) look like?

What I can understand from that is:

The next angle to turn by = path offset function + the rate of path offset + smoothing value

Wouldn't you divide both f(t) and f'(t) with F(t)? Also, is t time or position along path?

hermantulleken · 1:34am 2 Jan 2013

The thing with control systems is that the very thing you try to control changes as you control it. In this case, over time, the angle offset f(t) depends on how you compensate for it.

To see how these values relate to each together, you need to look at an actual implementation. Let's say we limit the window to 10 frames, and for simplicity I will assume a fixed frame rate. To calculate the integration term, we need to "remember" 10 frames of the offset, which I will store in an array. To limit needless copying, the array is used circularly, so each frame we advance the windowIndex, so that the last offset is always at that position in the array, and earlier values before that (wrapped around the array, so position "-1" is actually position 9).

//called every frame
f[windowIndex] = CalcOffsetBetweenAgentAndPath(agent.forward, path)
f_delta = f[windowIndex] - f[(windowIndex - 1) % 10] //assuming -1 % 10 == 9, otherwise use (windowIndex + 9) % 10 
f_sum += f[windowIndex] - f[(windowIndex + 1) % 10] //we add the new value that falls in the window, and subtracts the old value that now falls outside the window.

a = (A * f[windowIndex] + B * f_delta + C * f_sum) * MAGIC_CONSTANT_FOR_SCALING_AND_INVERTING
windowIndex = (windowIndex + 1) % 10

agent.forward = CalcNewForward(agent.forward, a) //this is some physics steering function that calculates the new forward vector, based on the angle a

So you see, it is a circular calculation: f(t) depends on (among other things), the forward vector of the agent, and that in turn depends on f(t).

When tweaking, a good way to start off is punching in the formulas in excel, with some test data, and plotting f. (Test data can include smooth curves, extreme curves, etc.).

----
For this application, you would not divide by F(t).

You do that though for "local normalisation" (in effect, scaling values so that different windows can be compared more accurately in certain applications. The only example that I can quickly think of is in image algorithms, where you compute things, and then divide them by the average intensity of the window to cancel out "broad scale" intensity variations, for example to detect edges. You can test this in Gimp: take an image, duplicate it in a new layer. On the bottom layer, run "Filter | Generic | Convolution Matrix" with the central 9 squares set to 1, and divisor 9 [this is a box blur, which adds all the pixels in a 3x3 window (integration) scaled by 1/9 to keep it in visible range]. Then set the top layer mode to "Divide"; the resulting image is the image divided by the (windowed-)integral of the image.

----
t is time, but the two values are obviously related. I may be wrong, but there is possibly an adaption of the algorithm to work on position along path instead, that may be useful...

Denzil · 2:31am 2 Jan 2013

As another example where you can use PID control, say you have an AI that has to shoot at a moving target, you can use PID control to compensate for the movement (if you don't, and instead shoot directly at the target, you will always shoot behind it). Well, you could also just use some applied maths to solve this problem. But the PID implementation might be more robust to error.

Stray_Train · 8:18pm 3 Jan 2013

Dat math. I'll try work that in to a prototype this year

Interesting ways you've used integrals

Comments