ありがたくないおきょう

プログラム構成

配信中、WikipediaのForthの記事のURLだけ書かれたコメントをいただいたことがあるため関連を要調査。
細かな差はありそうですが、確かに命令体型が似ています。

スタックマシン

他言語にて作成されたのか、16bit幅のソフトウェアスタック操作による処理が数多く見受けられます。 $0600-$06FFがソフトウェアスタックとして使用されています。($0600-$067F:下位, $0680-$06FF:上位)

ソフトウェアスタック操作サブルーチンを呼ぶことで、スタックに積まれた16bit値を1, 2個POPし、演算結果を1個PUSHします。
スタックポインタとしてXレジスタを使用しており、随所にXレジスタの退避・復帰処理が存在します。

JSR地獄

ソフトウェアスタック操作やそれを用いた細切れのサブルーチン処理が多いため、JSR命令が大量に並ぶことも珍しくありません。 時々ネイティブ命令を吐いたり、最後のJSR命令をJMP命令に置き換える程度の最適化はあるようです。

; Check the destination tile and invalidate the controller input
; if it is a wall attribute.
; Wall : 0, 1, 6, 7, 8, 9, 10, 11, 12, 16
; Argument:
;   Stack[0] = Y offset (base:6)
;   Stack[1] = X offset (base:8)
VmProc_CheckFieldDestinationTile:
B8E5 :	20 EA 96		JSR	VmHelper_SaveMemTemp_06				;prologue
B8E8 :	20 E1 C0		JSR	VmProc_GetMemoryOffsetY_ChipY
B8EB :	20 4E 97		JSR	VmOp_Add_AB					;(Y + (6 + yArg)) % 15
B8EE :	20 C1 B8		JSR	VmProc_ModScreenTileYOffset
B8F1 :	20 17 98		JSR	VmOp_Asl_04
B8F4 :	20 AE 95		JSR	VmOp_Swap					;save Y, calculate X
B8F7 :	20 A6 BC		JSR	VmHelper_PushFieldChipX
B8FA :	20 4E 97		JSR	VmOp_Add_AB					;(X + (8 + xArg)) % 16
B8FD :	20 D3 B8		JSR	VmProc_ModScreenTileXOffset
B900 :	20 4E 97		JSR	VmOp_Add_AB					;(Y << 4) + X
B903 :	20 8D BC		JSR	VmHelper_PushConst_0500				;$0500 = Map data (reg Y = 0)
B906 :	20 8D 95		JSR	VmOp_ReadOffsetByte				;read map tile
B909 :	20 FE 96		JSR	VmHelper_WriteTempAddressWord_02
B90C :	20 27 97		JSR	VmHelper_ReadTempAddressWord_02
B90F :	20 49 98		JSR	VmHelper_PushConst_0000
B912 :	20 C5 94		JSR	VmOp_Compare_Equal				;if(  (tile ==  0) // sea
B915 :	20 27 97		JSR	VmHelper_ReadTempAddressWord_02
B918 :	20 4D 98		JSR	VmHelper_PushConst_0001
B91B :	20 C5 94		JSR	VmOp_Compare_Equal				;  || (tile ==  1) // bushes
B91E :	20 2D 95		JSR	VmOp_Or
B921 :	20 27 97		JSR	VmHelper_ReadTempAddressWord_02
B924 :	20 89 98		JSR	VmHelper_PushConst_0010				;  || (tile == 16) // door of time
B927 :	20 C5 94		JSR	VmOp_Compare_Equal
B92A :	20 2D 95		JSR	VmOp_Or
B92D :	20 27 97		JSR	VmHelper_ReadTempAddressWord_02
B930 :	20 61 98		JSR	VmHelper_PushConst_0006
B933 :	20 12 95		JSR	VmOp_Compare_BGeatherThanOrEqual		;  || ((6 <= tile) && (tile <= 12))
B936 :	20 27 97		JSR	VmHelper_ReadTempAddressWord_02
B939 :	20 79 98		JSR	VmHelper_PushConst_000C
B93C :	20 0B 95		JSR	VmOp_Compare_AGeatherThanOrEqual
B93F :	20 19 95		JSR	VmOp_And
B942 :	20 2D 95		JSR	VmOp_Or
B945 :	20 C9 95		JSR	VmOp_CheckNotZero				;){
B948 :	90 03			BCC	.Accept						;  ClearJoypad();
B94A :	20 BB BA		JSR	ClearJoypad					;}
B94D :	4C B3 96	.Accept	JMP	VmOp_ReadTempMemAddr				;epilogue

JSR, RTS命令はそれぞれ6サイクルかかるため、サブルーチン呼び出し1セットにつき12サイクルを消費します。上記ルーチンは34個のJSR命令があるため408サイクル。
1フレームにかけられるサイクル数は29780.5サイクルなので、これだけで1.4%の時間を消費してしまいます。

手続型メインループ

当然処理時間はネイティブ実装よりも圧倒的に劣るため、1フレームに処理できる内容はわずかになります。
フィールド画面では32フレーム、戦闘画面では10フレームを1ループとして動作しており、その中で1フレームだけコントローラーを読んでいます。
つまり、32フレームに一回しかコントローラー入力を受け付けないということになります。

エミュレータのラグフレームカウンタはコントローラ読み取りを元にしていることが多く、このゲームの場合ほぼ毎フレームカウンタが増えることになります。

32フレーム周期では、このフレームは移動先決定処理、次フレーム待機、目的座標へ1px移動、次フレーム待機、…といった流れになっています。
フレームの待機時には、VBlankフラグ監視ルーチンに入るタイプで、サブルーチンをすべて抜けて無限ループに戻ることはありません。

ラグフレーム

フィールド上では定期的にラグフレームが発生していることが知られています。
こんなゲームの解析を始めたきっかけ。

ラグフレーム可視化

PPU VBlank flag

スキャンライン=241, サイクル=1のタイミングでVBlankフラグ($2002 bit7)や、NMI信号のアサートがおこなわれます。
VBlankフラグは$2002を読み取ると0クリアされるのですが、フラグが立つ瞬間に読み取りをしてしまうと、CPUがNMI信号を認識して割り込みをかける前にネゲートされてしまいます。

; Bug : 1/7 chance that NMI will not be executed
; BIT abs(4), BVS rel(3) => 7 cycles
; If the NMI is turned on in the 4th cycle of the BIT instruction,
; it will be skipped.
	.org	$BBE0
.WaitVBlankExit	BIT	PPUSTATUS			; 4
		BVS	.WaitVBlankExit			; 3/2 Wait *Sprite 0hit*, loop during VBlank
		JMP	SetDisplayScreenPosition

このゲームではなぜかVBlank終了時のスプライト0ヒットフラグが消えるのを待っているのですが、実質的には一緒です。

実際にリードアクセスが発生するのは、Absoluteアドレッシングの場合は4サイクル目となります。
また、CPUはPPUの1/3の速度で動作しているためPPU 3サイクル分、 そのうちM2クロックのhighがリードのため、PPU 1.875サイクル分のリードが発生することになります。

1タイルの歩行におけるラグフレーム発生の期待値は、 32 [frame] * (2 / 21) [PPU cycle] = 3.048 [frame] 程度になります。

エミュレータ上でのラグフレーム再現

FCEUXではOld PPU/New PPU共に、このVBlankフラグの再現ができていないようです。(2.3.0現在)
よって、speedrun.com上では実機とエミュでカテゴリが分かれています。 今後のFCEUX再現性向上や、他再現性の高いエミュが主流になるとカテゴリ統合されるかもしれません。
競技として面白いかは別として。

なお、FCEUX New PPUはステータス領域でノイズがちらつくのでOld PPU推奨です。

テストROMを作って調べた結果のリスト
多分TASVideosのNES Accuracy Testsを見るのが一番手っ取り早いと思います。

  • [OK] Mesen
  • [OK] BizHawk (NesHawk)
  • [NG] BizHawk (QuickNes)
  • [OK] puNES
  • [OK] Nestopia UE
  • [NG] FCEUX (Old PPU)
  • [NG] FCEUX (New PPU)
  • [NG] VirtuaNES

なお、このゲームに限定してであればラグフレームが発生した場合 $BA1B が実行されるため、 ブレークポイント等を利用すれば時間計測をせずともラグフレームの発生有無を判別可能です。

結局

「人力で調整可能ですか?」 → 「1フレーム内で実行される命令サイクルを正確に計算できる人間なら可能です(無理)」

TASの場合、コントローラ入力でサイクルを頑張って調整することになりますが、 32フレームに1回しか介入できないため全てのラグフレームを回避することは難しく、ある程度の妥協が必要そうです。
(セレクトポーズ中はかなり低減されますが…)

コンティニュー

仕組み

Aボタンを押下した瞬間のBボタン入力状態直近4回分によってコンティニュー先が決定されます。
そのため「AB AB AB」のようなメッセージにおける「AB」とは同時押しを意味しています。 同時押しが難しい場合、Bボタンを押してからAボタンを押しても同等の効果を持つため、入力が安定しやすいです。

なお、コンティニューコマンドについては拡張ポートに刺したコントローラーは反応しないので、標準コントローラーから入力してください。

入力された直近4回分のコマンドを4bitの数値として以下のテーブルのインデックスとして参照し、Xページを表の値、Yページを入力値として再開します。
そのため、同じYページに複数の再開エントリは登録できず、また0x10ページ目以降のYページからの再開はできません。
登録値が0x00の場合、標準スタート(台湾)になります。

コンティニュー先一覧

入力値登録値入力コマンド再開ページ再開ポイント
$00$00---($0E, $10)標準スタート
$01$14AB($14, $01)ゴビ砂漠
$02$00------標準スタート
$03$1AAB AB($1A, $03)洛陽の都
$04$06AB A A ($06, $04)タクラマカン砂漠
$05$00------標準スタート
$06$00------標準スタート
$07$11AB AB AB($11, $07)長州の都
$08$00------標準スタート
$09$0EAB A A AB($0E, $09)小屋
$0A$1AAB A AB A ($1A, $0A)建物なし
$0B$05AB A AB AB($05, $0B)小屋
$0C$00------標準スタート
$0D$18AB AB A AB($18, $0D)河南地方
$0E$10AB AB AB A ($10, $0E)成都の都
$0F$00------標準スタート

注釈 : ゲーム内の表記を尊重し、可読性のために漢字へ直すのみに留めています。政治的主張・意図はありません。

サウンドドライバ

あとで書く。

その他細かいこと

全域ツッコミどころ満載。

インタビュー記事

【リレーブログ(クリエーター編)第2回】”スーパーモンキー大冒険”tks様

プログラマー O氏

集まってきたのはまずプログラマーのOさん。
彼はコモドールマニアで...(後略)

コモドール64の6502開発環境や文化をファミコンに流用したのでしょうか。

デザイナー N氏

件のメッセージについては手垢が付くほどあちこちで触れられているのでもう興味ないです。

容量制限

なんせウリである数百画面にも及ぶ巨大マップ。あれだけでメモリ容量のほぼ総てを使い切ってしまって、考えていた他の仕様がほとんど入らなくなってしまったという。
当時のファミコンのメモリは キャラクター 256Kbit、プログラム&データ 256Kbit と非常にタイニーな環境で、 通常であれば圧縮であるとか、様々なテクニックを使って、容量を稼がなければいけないわけなのですが、当時の我々にはそういうスキルが足りてなかったのです。

6502ネイティブで書くともっと入りますよ^^

…という冗談はさておき。
ゲームロジック以外のシステム的な処理や静的な画面データの簡単なRLE圧縮等、一部はネイティブ実装されていたりするので、6502が全く書けない方ではなかったと推察されます。(コードの効率はさておき)
開発ツール選定の時点で間違っていたわけです。
データの持ち方をちょっと変えるだけでそれなりのプログラム容量が捻出できるので、アルゴリズム選択も間違っていますが。
時間も足りなかったのではないでしょうか。

CHRも(あの内容に対して)マッパー使ってCHR 32KB(4バンク)は多い方だと思いますよ。メッセージ分差し引いてもかなり余ってるので。