Brachistochrone with Walls

タイム0.000 s

ベスト— s

曲線を設計する

8つの点を上下に動かして曲線を設計します。「再生」を押すと曲線に沿ってボールが滑ります。壁にぶつからないように、できるだけ速くゴールを目指しましょう。短いルートが速いとは限りません。最初に深く下ってスピードをつけた方が速い場合もあります。壁に当たる曲線は赤くなり、再生できません。

点を選ぶと、左下の矢印ボタンでも動かせます。ボタンを押し続けると連続して動きます。キーボードの上下キーも使えます。

補足）ボールは大きさのない点（質点）として扱い、重力に従って滑ります。回転・摩擦はなく、曲線から離れません。壁との接触はボールの中心で判定します。

曲線はBスプラインを用いて描かれており、制御点を動かすことで曲線の形を変えられます。制御点は必ずしも曲線上にあるとは限りません。Bスプラインについて（Wikipedia）

答えと比べる

「答え」を押すと、このステージで作れる最速のコースを計算し、自分のコースに金色の線で重ねます。この時点では再生しません。「再生」を押すと、自分の球と金色の球が同時に出発します。答えを表示したまま制御点を動かすこともできます。「答え」をもう一度押すと、答えを隠せます。

答えは、このゲームの8つの制御点を動かすBスプラインで作成できる曲線の中で、最速となるコースを数値的に求めたものです。任意の曲線の中で最適とは限らないことに注意してください。計算には、ステージや端末によって数秒かかることがあります。計算方法は「解説」を参照してください。

ステージの変更

数字を選択すると壁の数を0から2まで変えられます。「ランダム」を押すと新しいステージがランダムに生成されます。「手動」を押すと自分で壁とゴールを動かせます。「完了」を押すと配置が確定し、曲線の編集に戻ります。

最速降下曲線とは

最速降下曲線（brachistochrone curve）は、静止出発した質点が重力のもとで摩擦なく滑り、より低いゴールへ最短時間で到達する曲線です。壁などの障害物がない場合、横に離れた2点を結ぶ最速の曲線は、直線ではなくサイクロイドの一部になります。

「どの曲線を選べば時間が最も短くなるか」を考えるこの問題は、大学の数学・物理で、変分法の入門としてよく扱われます。

Wikipediaで詳しく見る

最速降下曲線や最適化、変分法を扱う和書として、寒野善博・土谷隆『最適化と変分法』があります[5]。

Below, we explain the mathematics of the brachistochrone problem with walls (obstacles).

The model and travel time

Let $x$ be horizontal and $y$ point upward. We describe the track by the graph of a function $f$ , with $y=f(x)$ for $0\le x\le L$ . The start is $(0,H)$ and the goal is $(L,h)$ , where $h<H$ . We require $f(0)=H$ , $f(L)=h$ , and $f(x)<H$ for $x>0$ . The ball is a point mass starting from rest. We neglect friction, air resistance and rotation, and assume that it stays on a fixed track.

For gravitational acceleration $g$ and mass $m$ , conservation of energy gives

\begin{aligned}\frac12 mv(x)^2+mgf(x)&=mgH,\\v(x)&=\sqrt{2g(H-f(x))}.\end{aligned}

A small length along the track is $\sqrt{1+(f^\prime(x))^2}\,\mathrm{d}x$ . Dividing by the speed and integrating gives the travel time

T[f]=\frac1{\sqrt{2g}}\int_0^L\frac{\sqrt{1+(f^\prime(x))^2}}{\sqrt{H-f(x)}}\,\mathrm{d}x.

We seek the track that minimizes this time while avoiding the walls. In the classical problem without walls, the fastest curve is a cycloid, which can be derived from the Euler–Lagrange equation[4].

A change of variables and route choices

Using the square root of the drop, $u(x)=\sqrt{H-f(x)}$ , the travel time becomes

J[u]=\frac1{\sqrt{2g}}\int_0^L\sqrt{u(x)^{-2}+4(u^\prime(x))^2}\,\mathrm{d}x.

The integrand is convex in $(u,u^\prime)$ , so $J$ is a convex functional of $u$ . This convex reformulation is known[1].

Consider a wall over a horizontal interval $I_j$ , with bottom $\ell_j$ and top $r_j$ ; for simplicity, assume $r_j<H$ . Avoiding it requires either $f\ge r_j$ throughout the interval or $f\le\ell_j$ throughout it. Allowing both route choices gives a nonconvex feasible set. Once we fix the side and use $u$ , we only need one of the linear constraints

u(x)\le\sqrt{H-r_j},\qquad x\in I_j

u(x)\ge\sqrt{H-\ell_j},\qquad x\in I_j.

With $N$ walls, we can enumerate at most $2^N$ choices of above or below, solve the convex problem for each choice, and compare their optimal values. For two walls, the four choices are above–above, above–below, below–above and below–below.

Numerical computation with B-splines

For computation, we fix a horizontal parameterization $x=x(s)$ and express $u(x(s))$ as a linear combination of B-spline basis functions[2]. The variables are finitely many coefficients. The objective remains convex and the wall constraints remain linear for each fixed route. We approximate the integral by numerical quadrature with positive weights, check the constraints over each entire wall interval, and add constraints where needed. Each finite-dimensional convex problem is solved using a logarithmic barrier and Newton's method[3]. Comparing the optimal values gives a numerical global solution within the chosen B-spline curve family.

A rigorous treatment requires further discussion of the singularity at the stationary start, existence of minimizers, and discretization error. We omit these details here. For the singularity and existence in the classical problem without walls, see[4]; for convex optimization and splines, see[3] and[2].

Previous work on obstacles

Alessi et al., in A Dynamic Programming Approach for the Brachistochrone Problem, discretize the problem on a grid and use dynamic programming to find paths around obstacles[5]. This site uses a different curve representation and solution method: it enumerates the above/below choices for the walls, represents the square root of the drop with B-splines, and solves a convex optimization problem for each choice.

References

Erik Balder. The brachistochrone problem made elementary. University of Utrecht, 2002.
Carl de Boor. A Practical Guide to Splines, revised edition. Springer, 2001.
Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, 2004.
Rodney Coleman. A Detailed Analysis of the Brachistochrone Problem. arXiv:1001.2181v2, 2012, Sections 3 and 7.
André Eduardo Alessi, Gabriel Vinicius Bacci, Hugo Gielamo Próspero, José Eduardo Saroba Bieco and Eduardo Fontoura Costa. A Dynamic Programming Approach for the Brachistochrone Problem. Anais do Computer on the Beach, 16, 414–421, 2025.

以下では、壁（障害物）がある場合の最速降下曲線の数学的な解説を行います。

問題設定と到達時間

横向きを $x$ 、上向きを $y$ とし、コースを関数 $f$ のグラフ $y=f(x)$ 、 $0\le x\le L$ で表します。始点を $(0,H)$ 、終点を $(L,h)$ 、 $h<H$ とし、 $f(0)=H$ 、 $f(L)=h$ 、 $f(x)<H$ （ $x>0$ ）を課します。球は静止出発する質点とし、摩擦・空気抵抗・回転を考えず、固定されたレールから離れないものとします。

重力加速度を $g$ 、質量を $m$ とすると、エネルギー保存則から

\begin{aligned}\frac12 mv(x)^2+mgf(x)&=mgH,\\v(x)&=\sqrt{2g(H-f(x))}\end{aligned}

です。曲線に沿う微小な長さは $\sqrt{1+(f^\prime(x))^2}\,\mathrm{d}x$ なので、これを速さで割って積分すると、到達時間は

T[f]=\frac1{\sqrt{2g}}\int_0^L\frac{\sqrt{1+(f^\prime(x))^2}}{\sqrt{H-f(x)}}\,\mathrm{d}x

となります。今回求めるのは、壁にぶつからないという条件を満たす曲線のうち、この時間を最小にするものです。なお、壁がない古典的な問題では、最速の曲線はサイクロイドです。この曲線はオイラー・ラグランジュ方程式から導けます[4]。

変数変換と壁の通過側

落差の平方根 $u(x)=\sqrt{H-f(x)}$ を変数にすると、到達時間は

J[u]=\frac1{\sqrt{2g}}\int_0^L\sqrt{u(x)^{-2}+4(u^\prime(x))^2}\,\mathrm{d}x

と変換できます。被積分関数は $(u,u^\prime)$ の凸関数なので、 $J$ は $u$ の凸汎関数となることが知られています[1]。

横区間 $I_j$ 、下端 $\ell_j$ 、上端 $r_j$ （簡単のため $r_j<H$ とします）の壁を避ける条件は、区間全体で $f\ge r_j$ または $f\le\ell_j$ であり、上側と下側のどちらも許す実行可能集合は非凸です。一方、通過側を固定し、変数を $u$ に置き換えれば

u(x)\le\sqrt{H-r_j},\qquad x\in I_j

もしくは、

u(x)\ge\sqrt{H-\ell_j},\qquad x\in I_j

のいずれか片方の線形制約のみを扱えば良いことになります。したがって、壁が $N$ 枚なら上・下の最大 $2^N$ 通りを列挙し、通過側を固定した各凸最適化問題を解いて最適値を比較すれば、全体の最適値を求められます。例えば、壁が2枚の場合は、上上、上下、下上、下下の4通りに対応する4つの凸最適化問題を解いて最適値を比較します。

Bスプラインによる数値計算

数値計算では、横方向のパラメータ表示 $x=x(s)$ を固定し、 $u(x(s))$ をBスプライン基底の線形結合で表します[2]。変数は有限個の係数となり、目的関数の凸性と、通過側を固定した壁制約の線形性が保たれます。積分を正の重みを用いた数値積分で近似し、壁区間全体での制約を確認しながら必要な制約を追加します。各組合せに対応する有限次元の凸最適化問題は、対数バリア法とニュートン法を用いて解きます[3]。最後に各問題の最適値を比較し、採用したBスプライン曲線族における数値的な大域解を求めます。

厳密には、静止出発点での積分の特異性、解の存在性、離散化誤差などの議論が必要ですが、ここでは省略します。古典的な壁なし最速降下曲線問題の特異性・存在性は[4]、凸最適化とスプラインの詳細は[3]、[2]を参照してください。

障害物を扱った先行研究

Alessiらの A Dynamic Programming Approach for the Brachistochrone Problem は、障害物を含む問題を格子上に離散化し、動的計画法で経路を求めています[6]。このサイトでは、壁の上下の通過側を列挙し、落差の平方根をBスプラインで表して各通過側の凸最適化問題を解くため、曲線の表現と解法が異なります。

参考文献

Erik Balder. The brachistochrone problem made elementary. University of Utrecht, 2002.
Carl de Boor. A Practical Guide to Splines, revised edition. Springer, 2001.
Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, 2004.
Rodney Coleman. A Detailed Analysis of the Brachistochrone Problem. arXiv:1001.2181v2, 2012, Sections 3 and 7.
寒野善博・土谷隆著、東京大学工学教程編纂委員会編．最適化と変分法（東京大学工学教程基礎系数学）．丸善出版、2014年．
André Eduardo Alessi, Gabriel Vinicius Bacci, Hugo Gielamo Próspero, José Eduardo Saroba Bieco and Eduardo Fontoura Costa. A Dynamic Programming Approach for the Brachistochrone Problem. Anais do Computer on the Beach, 16, 414–421, 2025.