1
$\begingroup$

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?

$\endgroup$
7
  • 1
    $\begingroup$ please say me, why my question gets downvoted after one minute. I have no idea what I could have done wrong $\endgroup$ Commented Nov 25, 2018 at 14:48
  • 1
    $\begingroup$ I didn't downvote but the criterion "least possible curvature" is meaningless as the curvature varies along the curve. In addition, least curvature and short length are contradictory goals. Finally, you have no reason to believe that Adobe Illustrator uses this criteria at all. $\endgroup$ Commented Nov 25, 2018 at 14:58
  • 3
    $\begingroup$ I think the downvotes are wrong. This is a perfectly reasonable question from a nonmathematician asking for help where mathematics may come into play. The way it's asked makes no literal sense mathematically, but that's no surprise given the source. $\endgroup$ Commented Nov 25, 2018 at 15:00
  • $\begingroup$ From other comments, I infer that what you are after is a "fastest curve". You fell deep in an XY problem I am afraid. $\endgroup$ Commented Nov 25, 2018 at 15:00
  • $\begingroup$ I'm sorry, when my explanation was bad, but i'm not a native english speaker and It's really hard for me to find the right words, especially describing a hard problem in maths $\endgroup$ Commented Nov 25, 2018 at 15:01

2 Answers 2

Reset to default
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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?

$\endgroup$
7
  • 1
    $\begingroup$ I'm programming an AI for a race game through a couple of checkpoints. If my car goes straight in direction of the checkpoint, then it has to slow down and make a huge turn there, so I wanted it to drive on such a curve, which I tried to explain (It seems, that my explanation was very bad) $\endgroup$ Commented Nov 25, 2018 at 14:57
  • $\begingroup$ @JosefZoller That clarifies a lot. You have indeed asked an x-y question: meta.stackexchange.com/questions/66377/what-is-the-xy-problem . I think the real question is finding the fastest track, given the physical characteristics of the car - how fast can it accelerate or decelerate, how fast can it take turns. That's a hard problem. Programmng a bezier curve might give you a good enough answer. You could post it here in much more detail and hope for help. $\endgroup$ Commented Nov 25, 2018 at 15:05
  • $\begingroup$ Thanks for explaining to me the downvotes. I'll try to improve my question $\endgroup$ Commented Nov 25, 2018 at 15:08
  • $\begingroup$ I think the official name for the area your problem lives in is :"calculus of variations". I doubt that there's a neat solution, but you can post it and hope. $\endgroup$ Commented Nov 25, 2018 at 15:12
  • $\begingroup$ @Rahul What lovely links - particularly the second one. I hope the OP appreciates them. $\endgroup$ Commented Nov 25, 2018 at 15:26

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.