Fastest Descent

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

Try interactive simulation →

Implementation

Some implmentation details of above simulation.

Bezier Curve

To allow users to create their own slope, I chose the interesting bezier curves, which are quite flexible and intuitive to understand.

To understand Bezier curves, it is easy to start with 2 nodes (linear) case, given a start $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 three nodes (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 "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$ nodes 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 system of equations, etc.

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

1. No friction.
2. 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 the segment and velocity over 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 one below, where $t_i$ is the time when ball reaches point $i$.

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