"fastest" curve through n points

Question

I'm programming an AI for a race game, where my car has to drive through some checkpoints. If I let it drive straight in direction of the checkpoints, it has to slow down and make a huge turn after each checkpoint.
So I thought, I could calculate a curve through this checkpoints, which should be a trade-off between having the least possible curvature and being as short as possible.

If I have for example this 4 checkpoints:

\begin{align*} &A(6,8)\\ &B(10,2)\\ &C(6,3)\\ &D(2,2) \end{align*}

Then the curve should look approximately like this.

How can I calculate this? It has something to do with splines, but I'm not a mathematician and it's quite hard for me to find some understandable sources.

I think the easiest for me, would be, if somebody could provide an example, how to calculate the curve in my example?

Answer 1

The shortest possible curve would connect the points with straight lines. But that would mean essentially infinite curvature when you suddenly change direction. To smooth out the transition you have to lengthen the curve.

That means you have to specify some kind of tradeoff between length and curvature. You are right that various kinds of splines or bezier curves will do that. It's probably what Adobe has done; they keep their calculation under the hood in the software.

Why do you need to do the calculation yourself?

Answer 2

I think what you are looking for is the so called Minimum Energy Curve (or Minimum Energy Spline), which is constructed by minimizing a certain energy functional of the curve while treating the interpolated points as constraint.

The following shows a typical energy functional

$$E(t) = (1-w)\int_0^1{||c'(t)||^2dt} + w\int_0^1{\kappa(t)^2dt} $$

where $c'(t)$ is the first derivative of the curve $c(t)$, $\kappa(t)$ is the curvature of the curve and $0.0 \le w \le 1.0$. The first integral term represents the stretch energy and the second integral the bending energy of the curve. You can choose to minimize the stretch energy or the bending energy alone by using $w=0.0$ or $1.0$ respectively or you can choose to minimize a combination of both.

Because the existence of the nonlinear term $\kappa(t)$, it is often desired to replace the curvature by the second derivative as

$$E_s(t) = (1-w)\int_0^1{||c'(t)||^2dt} + w\int_0^1{||c''(t)||^2dt} $$

so that the solution can be easily found by solving a linear equation set.