Edited at

スーパーマリオのジャンプのアルゴリズム

先日、気持ちのいいジャンプを目指してというQiitaの記事を見かけました。記事中では、マリオのジャンプについても触れられています。マリオというと、マリオブラザースやスーパーマリオブラザース等々、色々あるのですが、これはおそらくスーパーマリオブラザースの事だと思われます。ジャンプアクションゲームといったらスーマリですね。

そのマリオのジャンプの仕組みは「マリオの速度ベクトルを保存しておいて座標を計算するんじゃなくて~」と書かれていて、別サイトのブログへのリンクが張られています。

マリオのジャンプ実装法とVerlet積分

ただ、この記述については不正確であるという別のブログもあったりします。

マリオの完コピvol.28 ジャンプの解析と修正

ホントのところはどうなんでしょうか?世界で最も有名なゲームのジャンプがどのように処理されているのか気になったので調べてみることにしました。


原典にあたる

さて、その調べ方ですが、オリジナルのプログラムを見ればいいのですから話はカンタンです。え?肝心のプログラムがどこにあるかって?それはカセットの中に決まってるじゃないですか。

DSC05587_320.jpg

皆さんのご家庭にもある、ファミコンとスーマリのカセットです。

このカセットの端子には、アドレスバスとデータバスと制御用信号線があり、スーマリの場合は、それらが素直にカートリッジ内部のROMに接続されています。

DSC05593_320.jpg

ファミコンカートリッジ自作計画

これがどういうことかというと、アドレスバスのPRG-A0~A14が15ビットのメモリアドレスを指していることになります。また、データバスはD0~D7の8本なので8ビットです。つまり、1つのアドレスごとに8ビット(一般的に1バイト)のデータを持つ32KByteのROMになります。

高級言語の配列で表現すると、

readonly byte ROM[32768] = {バイトデータ...}}

という感じです。特にROMへのアクセスを困難にするような仕組みは施されていません。

実際に電気信号として読むには、制御信号を上手くハンドリングする必要がありますが、アドレスバスとデータバスの端子の電圧は+5Vか0Vなので、ArduinoやRaspberryPiとかを上手く使えば読込み出来ます。そうして読み込んだ内容はこれがそのままプログラムということになります。

dump.jpg

ファミコンのCPUはMOS 6502互換品で、アーキテクチャやコードの命令セットもほぼ同じです。

あとは、命令のコードと機能を理解して、プログラムをひたすら読み進めていくと、何をしているのか解るわけです。理屈だけは簡単です。(実際にやってみたら簡単じゃなかった・・・)

前置きが長くなりましたが、この記事の本来の目的であるジャンプ処理の仕組みは、日本語で動作内容を書くよりも高級言語で表した方が解り易いでしょうし、動作検証もしておきたかったので、流行りのC#&Unityに置き換えてみました。

GitHub - moriyan6001/FcMario

実際のスーマリのプログラムでは、ジャンプ処理中に様々な挙動の判定や演算をしてたり、ジャンプルーチンはマリオだけでなく他のキャラの動作にも使われているようですが、その辺は省いています。

(注) 以下、プログラムの理解不足や変換ミス、カセットのバージョン違いがあるかもしれませんので、その辺は緩く見てもらえればと思います。


ジャンプ部分のコード

記事が長くなるので折りたたんでいます。↓

ジャンプ処理コード

class FcSmb

{
private int VerticalPositionOrigin; // ジャンプ開始時の位置
private int VerticalPosition; // 現在位置
private int VerticalSpeed; // 速度
private int VerticalForce; // 現在の加速度
private int VerticalForceFall; // 降下時の加速度
private int VerticalForceDecimalPart; // 加速度の増加値
private int MysteryAdjustment; // 謎補正

private int HorizontalSpeed = 00; // 横方向速度

// ジャンプ開始時の初期パラメータ
private static readonly byte[] VerticalForceDecimalPartData = { 0x20, 0x20, 0x1e, 0x28, 0x28 }; // 加速度の増加値
private static readonly byte[] VerticalFallForceData = { 0x70, 0x70, 0x60, 0x90, 0x90 }; // 降下時の加速度
private static readonly sbyte[] InitialVerticalSpeedData = { -4, -4, -4, -5, -5 }; // 初速度
private static readonly byte[] InitialVerticalForceData = { 0x00, 0x00, 0x00, 0x00, 0x00 }; // 初期加速度

// 落下時の最大速度
private static readonly sbyte DOWN_SPEED_LIMIT = 0x04;

// 1フレ前のジャンプボタンの押下状態
private bool JumpBtnPrevPress = false;

// 地面にいるかジャンプ中か
public enum MovementState
{
OnGround,
Jumping
}
private MovementState CurrentState = MovementState.OnGround;

public void ResetParam(int initVerticalPos )
{
VerticalSpeed = 0;
VerticalForce = 0;
VerticalForceFall = 0;
VerticalForceDecimalPart = 0;
CurrentState = MovementState.OnGround;
MysteryAdjustment = 0;

VerticalPosition = initVerticalPos;
}

public int PosY
{
//set { VerticalPosition = value; }
get { return VerticalPosition; }
}

public MovementState GetPlayerState
{
get
{
return CurrentState;
}
}

public void Movement(bool jumpBtnPress)
{
JumpCheck(jumpBtnPress);
MoveProcess(jumpBtnPress);

JumpBtnPrevPress = jumpBtnPress;
}

private void JumpCheck(bool jumpBtnPress)
{
// 初めてジャンプボタンが押された?
if (jumpBtnPress == false) return;
if (JumpBtnPrevPress == true) return;

// 地面上にいる状態?
if (CurrentState == 0)
{
// ジャンプ開始準備
PreparingJump();
}
}

private void PreparingJump()
{
VerticalForceDecimalPart = 0;
VerticalPositionOrigin = VerticalPosition;

CurrentState = MovementState.Jumping;

int idx = 0;
if (HorizontalSpeed >= 0x1c) idx++;
if (HorizontalSpeed >= 0x19) idx++;
if (HorizontalSpeed >= 0x10) idx++;
if (HorizontalSpeed >= 0x09) idx++;

VerticalForce = VerticalForceDecimalPartData[idx];
VerticalForceFall = VerticalFallForceData[idx];
VerticalForceDecimalPart = InitialVerticalForceData[idx];
VerticalSpeed = InitialVerticalSpeedData[idx];
}

private void MoveProcess( bool jumpBtnPress)
{
// 速度が0かプラスなら画面下へ進んでいるものとして落下状態の加速度に切り替える
if (VerticalSpeed >= 0)
{
VerticalForce = VerticalForceFall;
}
else
{
// Aボタンが離された&上昇中?
if (jumpBtnPress == false && JumpBtnPrevPress == true)
{
if (VerticalPositionOrigin - VerticalPosition >= 1)
{
// 落下状態の加速度値に切り替える
VerticalForce = VerticalForceFall;
}
}
}

Physics();
}

private void Physics()
{
// 謎の計算
int cy = 0;
MysteryAdjustment += VerticalForceDecimalPart;
if (MysteryAdjustment >= 256)
{
MysteryAdjustment -= 256;
cy = 1;
}

// 現在位置に速度を加算 (謎パラメータも加算)
VerticalPosition += VerticalSpeed + cy;

// 加速度の固定少数点部への加算
// 1バイトをオーバーフローしたら、速度が加算される。その時、加速度の整数部は0に戻される
VerticalForceDecimalPart += VerticalForce;
if ( VerticalForceDecimalPart >= 256)
{
VerticalForceDecimalPart -= 256;
VerticalSpeed++;
}

// 速度の上限チェック
if ( VerticalSpeed >= DOWN_SPEED_LIMIT)
{
// 謎の判定
if ( VerticalForceDecimalPart >= 0x80)
{
VerticalSpeed = DOWN_SPEED_LIMIT;
VerticalForceDecimalPart = 0x00;
}
}
}
}



位置と速度と加速度

ジャンプ処理はコードのまま読んでもらえれば「なるほどそうなのね」で終わるのですが、せっかくなのでもう少し説明しようと思います。

そのための予備知識として、ゲーム作りの物理本に出てきそうな、位置と速度と加速度の関係を簡潔に説明します。

スーマリジャンプの処理は基本的に、位置と速度と加速度の式です。位置は速度の時間による累積、速度は加速度の時間による累積という、ニュートンのアレです。

速度の定義は一定時間あたりの移動量なので、位置に速度を足したら次の位置になります。これが等速度運動ですね。ファミコンのゲーム画面であれば、速度は1フレーム当たりに移動するピクセル量なので、ピクセル/フレームが単位になります。1フレームで1ピクセル動く場合、1ピクセル/フレームです。スーマリは実時間に関係しないので、Δtを乗算するみたいなことはしません。1フレームあたりの処理が間に合わないと実時間あたりの速度にも影響が出ます。

速度が時間によって変化する場合は、速度の変化分が加速度として加わっていきます。いわゆる等加速度運動です。1フレームあたりに速度が1フレーム/ピクセルだけ増えるのであれば、その加速度は1ピクセル/フレーム^2になります。重力のある空間では、重力という力が加速度と関係してきますから、重力が加速度として速度に加わり、それが物体の位置を変化させるという考え方ですね。

まとめると、y:位置、v:速度、a:加速度の時は

y = y + v\\

v = v + a

という式になります。

高校くらいで学ぶ物理では、時間tにおける位置yを求める式なんかが出てきますが、

$$y = 1/2 * a * t^2$$

この計算式には掛け算が含まれています。ファミコンのCPUは動作速度が1.79MHzで掛け算命令なんてありません。また、変数(レジスタ)も8ビットの整数型だけです。このCPUに掛け算をさせるのは重い処理になります。また、スーマリはジャンプ中でもプレイヤーの操作によってジャンプの挙動が変化するので、マリオの位置を方程式を用いて事前に計算することは意味がありませんし、現在位置から1フレーム後の位置を算出するには不便な式です。

位置と速度と加速度の考え方であれば、掛け算を使わずに足し算を数回するだけで、位置の変化を計算することが出来ますから、何かと都合がいいのです。

この計算をしているのが、先のプログラムのPhysics()というメソッドです。ここで、位置と速度をフレームごとに計算しています。

ところで、プログラムを改めて見ると、素直に速度に加速度を加えてはいません。


// 加速度の固定少数点部への加算
// 1バイトをオーバーフローしたら、速度が加算される
VerticalForceDecimalPart += VerticalForce;
if ( VerticalForceDecimalPart >= 256)
{
VerticalForceDecimalPart -= 256;
VerticalSpeed++;
}

毎フレームごとに加速度の変数に一定の値を加算していき、それが256を超えたら速度を+1しています。要するに、1ビットの整数部 + 8ビットの小数部の変数があり、整数部分が1になったら速度を+1するということです。(ただし、速度を+1した時に整数部を0に戻しています)

ファミコンにしてもUnityにしても、画面の更新頻度(一定間隔毎の処理頻度)は基本的に1秒当たり約60回です。“整数”を使って位置や速度を計算すると、1フレーム当たり1ピクセルというのが最低速度になります。これは加速度も同様です。

ただ、ゲームでは、それよりも遅い速度や加速度を使いたい時もあるわけです。1秒かけて1ピクセル移動したいような、要するに、速度が0.1ピクセル/フレームみたいなことです。

そこで、整数だけで疑似的に少数表現をするために、スーマリでは加速度を1ビット、加速度の増加分を1バイトとして計算して、加速度が256を超えたら速度を+1するという方式をとっています。

上記のプログラムでは解り易さ優先でif命令を使っていますが、6502には8ビット演算をするとオーバーフローしたかどうかを表す1ビットのフラグ変数があり、そのフラグ変数の値も加える加算命令もあるので、2回の足し算命令で済んでしまいます。(C#でも計算式だけで記述できます)

最初、ここの処理を見た時には、加速度は固定少数点表記か、加速度の増加値である加加速度(躍度)なのかなと思ったのですが、ちょっと違いますね。

その他、ここまでまるっと無視してきましたが、Physics()メソッドの最初に

// 謎の計算

int cy = 0;
MysteryAdjustment += VerticalForceDecimalPart;
if (MysteryAdjustment >= 256)
{
MysteryAdjustment -= 256;
cy = 1;
}

加速度の小数部分の累積分を位置に加えるという処理が入っています。

(2019/11/08 追記:この辺は別の解釈もあるようですので、コメントも参照して頂ければと思います)


ビヨーンからのシュッ

ファミコンの座標系は左上が原点で右がプラス、下にプラスです。速度がマイナスの時には位置がマイナスされていくので上へと移動します。

マリオの初期速度はマイナスで上昇しますが、加速度が加わり続けることで速度が+1されていきます。そのうちに速度が0になり、そしてプラスになりますが、そこに判定処理が入っています。

// 速度が0かプラスなら画面下へ進んでいるものとして落下状態の加速度に切り替える

if (VerticalSpeed >= 0)
{
VerticalForce = VerticalForceFall;
}

ここの処理はコメントの通り、速度が0以上に転じたら落下用の加速度を書き換えるという意味です。この判定処理と設定値によって、上昇時と下降時は加速度の値が異なっています。具体的には、上昇時に比べると下降時は素早く落ちる挙動になっています。

擬音で表すと「ビヨ~ンからピタッとしてシュッと落ちてスタッと着地」って感じでしょうか。

ゲームの企画をする人(プランナー)がプログラマに「ジャンプはビヨーンって感じでゆっくり減速しながら上がっていくけど、着地は素早くシュッって感じでヨロシク」と説明した時に、それをプログラマが理解&納得&実装できるかどうかというのは重要なチームコミュニケーションだと思います。(ですが、もっと伝わるように伝えて欲しいと思うこともあります)

ゆっくり落下した方が着地点を狙い定めやすくなると思うのですが、スーマリでは、素早く着地させてプレイヤーに次のアクションを起こさせやすくしたのかもしれませんね。ただ、そのようにした理由は作った人にしかわかりません。教えて宮本さん!

また、この挙動は、後で説明するジャンプキャンセルとも関係してきます。

それから、落下速度には限界値があり、4に設定されています。

// 速度の上限チェック

if ( VerticalSpeed >= DOWN_SPEED_LIMIT)
{
// 謎の判定(これが無いと少しだけ計算に差が出る)
if ( VerticalForceDecimalPart >= 0x80)
{
VerticalSpeed = DOWN_SPEED_LIMIT;
VerticalForceDecimalPart = 0x00;
}
}

自然界での落下は速度に比例した空気抵抗を受けるため落下速度は次第に一定になりますから、スーマリの世界でも何かしらの抵抗力が働くようです。

ではなぜ4なのかというと、これは推測ですが、ゲームのバランス調整によって出てきた数字というだけでなく、マリオと接触判定を持つ背景や敵は8×8ピクセルのブロックサイズ単位なので、めり込みやすり抜けの誤判定を無くしているのではないかなと思われます。雑な説明ですが。たぶん(ちゃんと調べてません)。


押し続けると高く飛ぶ?

スーマリでは、ジャンプの上昇中にジャンプボタンを離すと降下動作になるというコードになっています。

// Aボタンが離された&上昇中?

if (jumpBtnPress == false && JumpBtnPrevPress == true)
{
if (VerticalPositionOrigin - VerticalPosition >= 1)
{
// 落下状態の加速度値に切り替える
VerticalForce = VerticalForceFall;
}
}

ゲームを遊んでいる時の感覚は「ボタンを長く押し続けるほど高く飛べる」ような気がしますし、取り扱い説明書でも「長い間押すと、高くジャンプします」と書かれています。

プログラムでは、飛べる高さはジャンプ開始時点で確定していて、ジャンプボタンを離すと、そこから下に強く引っ張られる(落下用の加速度に切り替わる)という処理になっているのですね。

DSC05594_320.jpg


ダッシュジャンプ

// ジャンプ開始時の初期パラメータ

static readonly byte[] VerticalForceDecimalPartData = { 0x20, 0x20, 0x1e, 0x28, 0x28 }; // 加速度の増加値
static readonly byte[] VerticalFallForceData = { 0x70, 0x70, 0x60, 0x90, 0x90 }; // 降下時の加速度
static readonly sbyte[] InitialVerticalSpeedData = { -4, -4, -4, -5, -5 }; // 初速度
static readonly byte[] InitialVerticalForceData = { 0x00, 0x00, 0x00, 0x00, 0x00 }; // 初期加速度

これらはジャンプ開始時の初期値です。

初速度、初期加速度、・・・といったパラメータが並んでいます。初速度がマイナスなのは、先ほど説明した通りで座標系の都合です。

パラメータの種類それぞれに5段階あり、それを決定しているのが以下の処理です。

int idx = 0;

if (HorizontalSpeed >= 0x1c) idx++;
if (HorizontalSpeed >= 0x19) idx++;
if (HorizontalSpeed >= 0x10) idx++;
if (HorizontalSpeed >= 0x09) idx++;

HorizontalSpeedはマリオの横方向速度です。つまり、ジャンプ開始時のX方向の移動速度でジャンプの初期値が変わるということを意味しています。

スーマリの世界では、早く走ると高くジャンプすることが出来ます。

一般的には、ベクトルは軸の成分に分解することが出来ます。ベクトルのY方向の大きさは、X方向の大きさとは関係ありません。どんなに速く走っている車でも縦方向の速度は0です。止まってる車と、走っている車の屋根から真上へジャンプした時、ジャンプできる高さは変わらないのです。

助走をしない垂直跳びと、走り高跳びではどちらが高く飛べるかというと・・・それは判定方法も判定箇所も違うので比べることは出来ません。計算対象が質点か剛体か連続体なのか時間で形状が変化するかで考え方も計算方法も大きく違いますが、スーマリのマリオは単純に点の座標だけを使って計算されています。それでも、

「助走をつけた方が高く飛べそうな気がするじゃん?」

ということになっています。正しさよりも、感覚的な動きに合わせるというのは、ゲーム作りで大切な事なのではないかなと個人的には思います。

ところで、ジャンプの初期パラメータですが、よくみると同じ数字が並んでいる列があり、実施的には3段階であることがわかります。判定は5段階ですが、挙動は3種類ということですね。なぜこうしたのかは、教えて宮本さん!案件です。

ちなみに3段階というのは、停止時・一定速度での歩行時、Bダッシュの最大速度時みたいです。停止時よりも歩行時の方が落下の加速が緩やかなんですね。このような数値にした理由はわかりませんが、マリオの歩行時は1ブロック幅の穴に落ちないようになっているので、その調整なのかもしれません。(ちゃんと調べてません)


Verlet積分?

今回の調査の元になったブログに気になる記述があります。

マリオのジャンプ実装法とVerlet積分


「昔、何かの雑誌*1でマリオのジャンプの実装法を見た覚えが~」(bit誌1997年"アーケードゲームのテクノロジ"だったかな。情報求む)


このBit誌の記事とは、アーケードゲームのドンキーコングを開発した池上通信機のメインプログラマさんによる当時の回顧録で、ドンキーコングの開発史が垣間見える貴重な資料です。

DSC05595_320.jpg

この記事中に、ジャンプの計算について触れている箇所がありましたので引用させて頂きます。


まず、放物線の方程式を思い出してもらいたい。x方向は一定速度となり問題ないため、y方向のみを考えると次の式によって求められる。

S(t)=v_0t-\frac{1}{2}gt^2

($S$:物体の位置、$v_0$:初速度、$g$:重力加速度)

この方程式の一階差分(離散値であるから差分)をとる。

\begin{align}

S(t+1)-S(t)&=v_0(t+1)-\frac{1}{2}g(t+1)^2-(v_0t-\frac{1}{2}gt^2)\\
&=v_0-gt-\frac{1}{2}g
\end{align}

さらに、二階差分をとると

S(t+2)-2S(t+1)+S(t)=-g

となる。以上より、ある画面$t$(ゲームは1/60秒ごとに画面が更新している)における物体のy座標値$S(t)$は、

S(0)=0 (基準位置)\\

S(1)=v_0-\frac{1}{2}g (初速度)\\
S(t+2)=2S(t+1)-S(t)-g

として求められる。したがって、一つ前の画面の値を2回加算し、前々の画面の値を引き、定数$g$を引けば得られることになる。$S(t)$を毎画面、正直に計算すれば3回の乗算が必要となるが、二階差分をとることにより、1回のシフトと2回の足し算で演算することができる。


高校物理などで習う、落下位置の式には掛け算が出てきます。

$$y=v_0t+\frac{1}{2}gt^2$$

この式から、掛け算を無くす考え方ですね。これはドンキーコングの基板で採用されている低速なCPU(Z80 / CPUクロックは約3MHz)を使って計算を減らそうとして導き出された式です。

一般的に、verlet積分は複数の物体の運動を近似的に計算するための手法の一つなのですが、この考え方でも同じ式になります。

verlet積分の説明と実装例は以下のページが分かりやすいです。

ジャンプしたときの座標をVerlet法で求める

先のブログの誤解は、ドンキーコングの主人公はマリオではないということと、Bit誌の記事内容がスーマリではないことです。実はBit誌の記事でもマリオと書かれているのですが、アーケードゲームのドンキーコングは発表された時点では、プレイヤーキャラはジャンプマンと表記されるか、名前のない大工で、後にマリオと呼ばれることになるので、そこはマリオ違いなのでした。

ところで、ブログに出てくる式と、bit誌の記事の式では計算方法が違うように見えるのですが、実際のドンキーコングのジャンププログラムはどうなんでしょうか?気になりますね。気になったら調べてみるというものです。


ジャンプマンのジャンプ

どのご家庭にもあると思われるドンキーコングの基板です。

DSC05590_320.jpg

基板上にROMが載っているので、ファミコンのカセット同様にメモリからプログラムを読むことが出来ます。オリジナルのコードを元にジャンプ周りの処理だけをC#&Unity化してみました。

記事が長くなるので折りたたんでいます。↓

ジャンプ

public class AcDkJump

{
private int StartYpos;

private int Counter;
private int PosYi;
private int PosYd;

static readonly int DY_I = 1;
static readonly int DY_D = 0x48;

public int PosY
{
get { return PosYi; }
}

// 地面にいるかジャンプ中か
public enum MovementState
{
OnGround,
Jumping
}
private MovementState CurrentState = MovementState.OnGround;
public MovementState PlayerState
{
get
{
return CurrentState;
}
}

// 1フレ前のジャンプボタンの押下状態
private bool JumpBtnPrevPress = false;

// constructor
public AcDkJump(int y)
{
StartYpos = y;
ResetParam();
}

public void ResetParam()
{
CurrentState = MovementState.OnGround;
PosYi = StartYpos;
PosYd = 0;
Counter = 0;
}

public void Movement(bool jumpBtnPress)
{
if (jumpBtnPress == true && JumpBtnPrevPress == false && CurrentState == MovementState.OnGround)
{
ResetParam();
CurrentState = MovementState.Jumping;
}

int prevYpos = PosYi;

JumpUpdate();

// 着地判定
if (PosYi >= StartYpos)
{
PosYi = StartYpos;
CurrentState = MovementState.OnGround;
}

JumpBtnPrevPress = jumpBtnPress;
}

private void JumpUpdate()
{
if (CurrentState == MovementState.OnGround) return;

// 定数での上昇
PosYi = PosYi - DY_I;
PosYd = PosYd - DY_D;
if (PosYd < 0)
{
PosYi--;
PosYd = 256 + PosYd;
}

// フレームカウンタ値から整数・少数を算出する
int Breg = (Counter >> 4) & 0x0f;
int Creg = 8 * (Counter * 2 + 1) & 0xff;

// フレームカウンタ値による位置更新
PosYi = PosYi + Breg;
PosYd = PosYd + Creg;
if ( PosYd >= 256)
{
PosYi++;
PosYd = PosYd - 256;
}

Counter++;
}

}


流し読みすると、処理の最初に以前の位置を保持しているのでBit誌の記事の通りなのかなと思えるのですが、

int prevYpos = PosYi;

なんと、この保持された値が使われている形跡がありません。では、どのようにしてジャンプの動きを作り出しているのかというと、フレームごとに更新されるカウンター値を元に値を算出して、移動位置を変化させています。これは一体・・・?

なぜ、Bit誌の記事と違うジャンプの実装がされているのかという謎だけが残りましたが、長くなりましたので、この辺で記事を書き終えたいと思います。


追記(2019/11/10)

記事の公開後に様々なご意見をいただいたので、記事公開にあたって考えたことをポエムとしてnoteの方に“マリオジャンプの公開で考えたこと”として書きました。