Fastest Descent

Also known as the Brachistochrone problem: we release a ball from the top of a slope, how do we shape the slope to minimize the time of descent?

Try interactive simulation →

Implementation

Some implementation details of the above simulation.

Bezier Curve

To allow users to create their own slope, I used bezier curves, which are flexible and intuitive.

To understand Bezier curves, it is easy to start with the 2-node (linear) case. Given a start point $P_0$ and end point $P_1$, we can define the curve as: $$S(t) = P_0 + t(P_1 - P_0), \quad 0 \leq t \leq 1$$

With the three-node (quadratic) case, we can construct the curve iteratively. First, we find the "linear" Bezier points by sliding along the line connecting $P_0$ and $P_1$, and $P_1$ and $P_2$. $$S_0(t) = P_0 + t(P_1 - P_0)$$ $$S_1(t) = P_1 + t(P_2 - P_1)$$

Then we slide along the line connecting $S_0(t)$ and $S_1(t)$, and find the "quadratic" Bezier points to create the Bezier curve. $$S(t) = S_0(t) + t(S_1(t) - S_0(t)), \quad 0 \leq t \leq 1$$

For the $N$-node case, we can follow the same process iteratively, and the algorithm is known as De Casteljau's Algorithm. Below is a JavaScript implementation used in the demo.

function calculateBezierPoint(t, points) {
  let currentPoints = [...points];

  for (let i = points.length - 1; i > 0; i--) {
    const newPoints = [];
    for (let j = 0; j < i; j++) {
      newPoints.push({
        x: (1 - t) * currentPoints[j].x + t * currentPoints[j + 1].x,
        y: (1 - t) * currentPoints[j].y + t * currentPoints[j + 1].y,
      });
    }
    currentPoints = newPoints;
  }
  return currentPoints[0];
}

Simulation

Normally we would have to construct an accurate physics simulation—i.e., calculate acceleration of the ball, detect collisions against the slope, solve for a system of equations, etc.

However, we can cheat a bit by making some simplifying assumptions:

1. No friction.
2. The ball stays on the surface.

Given these assumptions, and knowing conservation of energy, we can derive the speed of the ball at any given point along the slope, which is uniquely determined by the height $h$ of the point. $$E = \frac{1}{2}mv^2 + mgh \Rightarrow v(h) = \sqrt{2g(h_0 - h)}$$

Then we can discretize the slope into $M-1$ segments with $M$ points. Given that we know the distance of each segment and the velocity at which the ball travels over each segment, we can approximate the time it takes to travel over the segment and arrive at a table like the one below, where $t_i$ is the time when the ball reaches point $i$.

Finally, we can effectively replay the ball's motion. Given the current time $t$, find the closest point $i$ on the slope using binary search and move the ball to that point.