ハクソク

世界を動かす技術を、日本語で。

最適化の金字塔：『ローラーコースタータイクーン』の裏側を探る

45日前原文(larstofus.com)

概要

  • RollerCoaster Tycoon の技術的最適化についての解説記事
  • ゲームが アセンブリ言語 で書かれた理由とその影響
  • OpenRCT2 によるリバースエンジニアリング情報の活用
  • パフォーマンスを意識した ゲームデザイン の工夫
  • 代表的な最適化事例とその現代的意義

RollerCoaster Tycoonの驚異的な最適化技術

  • Stay Forever というドイツの大手ゲームポッドキャスト出演の経緯
  • RollerCoaster Tycoon（1999） とその続編が「最適化の傑作」と呼ばれる理由
  • Chris Sawyer がほぼ一人でアセンブリ言語で開発した事実
  • 1999年当時のハードウェアで、数千人のエージェントを同時にシミュレート可能な設計
  • 現代の同種ゲームでも達成困難な 安定したフレームレート

アセンブリ言語の採用とその影響

  • 開発当時でも アセンブリ言語 は既に珍しかった手法
  • 他の多くのゲームが C言語 や C++ を採用していた時代背景
  • アセンブリ言語による 手動最適化 が高いパフォーマンスを実現
  • 現代の コンパイラ最適化 と比較した場合の違い
  • RCTが 最後の大規模アセンブリ製ゲーム である可能性

OpenRCT2による最適化の解析

  • OpenRCT2 はRollerCoaster Tycoon 1&2の完全互換リイマジネーション
  • 元のソースコードは非公開だが、 リバースエンジニアリング で挙動を再現
  • 現代向けに一部最適化を 解除・変更 している例も紹介
  • すべての最適化事例は紹介しきれないが、代表例で解説

データ型の最適活用

  • 金額の保存方法についての 細かな最適化
  • 例： パーク全体の価値 は4バイト、 ショップの価格 は1バイトで管理
  • OpenRCT2では現代CPU向けに 8バイト変数 へ統一

ビットシフトによる演算最適化

  • ビットシフト演算 （<< や >>）の多用
  • 2,4,8,16など 2の累乗 を使った乗除算の高速化
  • 計算式自体も ビットシフトしやすい数値 で設計
  • 現代の開発現場では ほぼ不可能 な設計思想
  • ゲームデザイナーとプログラマーが 同一人物 だからこそ実現

パフォーマンスを意識したゲームデザイン

  • RCTは Chris Sawyer がデザインとプログラミングを一手に担当
  • 例： 経路探索（パスファインディング） の設計
    • 一般的な「目的地を決めてから経路探索」方式を避ける
    • ゲストは基本的に ランダムウォーク で移動
    • 分岐点でほぼランダムに方向選択、デッドエンド回避のみの簡易ルール
  • 本格的な経路探索は メカニックや出口を目指す時のみ限定的に実行
  • 経路探索の 深さ制限 を設け、パフォーマンス低下を防止
    • 例：通常ゲストは5分岐まで、メカニックは8分岐まで、地図購入者は7分岐まで

混雑処理と群衆制御

  • ゲスト同士の 衝突判定や回避処理を一切実装しない 方針
  • 1タイルに 数千人が重なって存在可能
  • ただし、周囲のゲスト数を 幸福度や不満足度 に反映
  • プレイヤーには 混雑回避のレイアウト設計 が求められるが、計算コストは大幅削減

現代的意義と教訓

  • コードとデザインの 密な連携 が生んだ最適化の極致
  • 現代でも 開発者間の対話 や 技術的課題への割り切り が重要
  • 技術的制約が ゲーム体験の一部 として昇華された好例

著者の活動案内

  • Mastodon、Bluesky、LinkedInでのフォロー案内
  • ゲーム開発、Unreal、プログラミングに関する記事を 毎月発信

Hackerたちの意見

面白かった、ありがとう！RCTについてもっと知りたいなら、これもおすすめだよ：「ローラーコースタータイクーンのクリエイター、クリス・ソーヤーへのインタビュー（2024年）」 https://news.ycombinator.com/item?id=46130335 「ローラーコースタータイクーン（または、マイクロプローズの最後の華）」 https://news.ycombinator.com/item?id=44758842 「ローラーコースタータイクーン25周年：『どれだけ自分に影響を与えたか、驚きだ』」 https://news.ycombinator.com/item?id=39792034 「ローラーコースタータイクーンは最後の作品だった [動画]」 https://news.ycombinator.com/item?id=42346463 「ローラーコースタータイクーンの物語」 https://www.youtube.com/watch?v=ts4BD8AqD9g

この記事はどの言語について話してるの？コンパイラが2の累乗での乗算や除算を最適化しないって。符号付き整数の除算でも、現在のコンパイラは正の値と負の値を別々に処理するインラインコードを出力して、除算命令を避けてるよ（もちろんサイズを最適化する場合を除いて）。

└

アセンブリで書かれているから、コンパイラではなくアセンブラを通るんだよ。

└

そう思ってたけど、x86ではclangとgccがLEAのバリエーションを使ってるみたいだね。もしそうやってやってるなら、かなり速いはずだよ。だって、×4を変えても https://godbolt.org/z/EKj58dx9T

「プログラマーがゲームデザイナーに、9.5の代わりに8を使うように数式を変更できるか聞いているところを想像してみて。CPUが計算しやすい数字だからね。」ゲームデザイナーは、バイナリ算術の実行時パフォーマンスを心配する必要はないっていうのは、すごく良い意見だと思う。そんなのはプログラマーの運命だから。2026年でも、数値特性はゲームデザイナーにとって絶対に考慮すべきことだし、それがゲームデザインで使う数字に影響を与える。良いデザイナーはね。もちろん、こういうことを無視する悪い開発者やデザイナーもたくさんいるけど、それは自由だからじゃなくて、単に知らないからなんだ。多くの場合、それがゲームの質の低下に繋がる静かな要因の一つになってる。

└

具体例は？

└

その通り。私は小さくて成長中のCADカーネルを書いていて、いくつかのゲームやリアルタイムビジュアライゼーションツールで使われてる（ https://github.com/timschmidt/csgrs ）けど、数値計算はまだ解決されてない問題だと言えるよ。すべての数値表現には、速度、精度、ストレージサイズ、複雑さ、さらにはどんな質問ができるかに関する固有のトレードオフがあるんだ（例えば、浮動小数点誤差を考慮しないで二つの浮動小数点数が等しいかを尋ねるのは、あまり意味がないことが多い）。「実数のためのAPIに向けて」（ https://dl.acm.org/doi/epdf/10.1145/3385412.3386037 ）は、これに対処するための段階的複雑性技術を詳しく説明している良い論文の一つで、ほとんどの計算は速くて常に返ってくる（任意精度の計算は時々永遠に続くか、メモリが尽きるまでだけど）。でも、必要ならもっと精度の高い答えを求めることもできる。もちろん、区間算術や記号代数エンジンなど、全く別の選択肢もある。トレードオフを理解しないと、痛い目を見ることになるよ。

└

「そして多くの場合、それはゲームの質の目に見える低下に寄与する静かな要因の一つだ」ゲームデザイナーはもうハードウェアの限界に縛られてないよ、限界を押し広げたいと思わない限りはね。ゲームの質は、最も効率的な実行時パフォーマンスだけじゃない。ゲームが楽しいかどうかが主な問題だし、メカニクスが機能するか、重大なバグがあるか、ストーリーが一貫しているか、キャラクターが共感できるか、没入感を壊すものがあるかどうかも重要だよ。だから、悪いプログラミングによる頻繁なカクつきは確かに低品質のサインだけど、ターゲットオーディエンスのハードウェアでスムーズに動くなら、改善は他のところで行うべきだね。

└

それは意味がないよ。だって、掛け算はここ30年（PS1から）ずっと速かったし、浮動小数点も25年（PS2から）速いしね。ゲームデザインに関係する数字は、通常フレームごとに数回しか使わないから、プログラムのサイズだけが重要なんだ。これは過去40年間（NESから）ほとんど制約されてないし。

└

数値の特性は、2026年でもゲームデザイナーにとって絶対に考慮される要素だよ。特に良いデザイナーはね。昔はこう考えてたけど、今は違う。こういったマイクロ最適化が重要じゃないと納得させられたのは、現代のプロセッサのサイクルカウントを読んだから。Zen 5では、整数の加算は1サイクル、掛け算は3、割り算は約12だ。でも、これは全体の話じゃない。CPUは同時に5つの掛け算を実行できるし、約3つの割り算も同時にできる。RCTの頃は、パイプラインがずっと少なかった。初代Pentiumでは、掛け算は11サイクル、割り算は46サイクル以上かかってた。これらは100MHzのクロックサイクルのCPUでの話。だから、終わるのにもっとサイクルがかかるだけじゃなくて、パイプライン化もできなかったし、CPUは今の一般的なCPUの1/30から1/50のサイクルレートで動いてたんだ。これ、SIMD命令にも触れてないし。整数のトリックや最適化は無意味だよ。現代のゲームでは、メモリのレイアウトの方がずっと重要なんだ。CPUが実際に時間をかけるのはそこだからね。int[]を使って操作を行えば、Monster[]に対して操作するよりもずっと速いよ。キャッシュミスが起きると、100から1000サイクルのペナルティが発生するからね。サイクルを3から1に減らすことで得られるメリットなんて吹き飛んじゃうよ。

└

それに関連して、ARM Cortex-M4シリーズのマイクロコントローラーを使った消費者向け電子機器のプロジェクトで、実際にカスタムの擬似乱数生成ルーチンを書いたんだ（市販のものを修正したけど）。マジックミキシング定数を、CrazyなThumb-2の即値命令で単一の即値として読み込めるものに変えたんだ。試したすべての乱数テストに合格したよ。定数プールから何も引き出さず、メモリのスタールを避けることで、乱数をたくさん使っても速く効率的に動かせたし、すぐに寝られるようになった。楽しいエンジニアリングだったな。どれだけ重要だったかは分からないけど、書くのは楽しかったよ。（どちらにせよ、ほとんどは勤務時間外にやったと思う。）残念ながら、最終的にはその指示がないもっと小さくて安いCortex-M0プロセッサに移行したから、結局出荷されなかったと思う。それに、そのプロジェクトの後任がほとんどを捨てて書き直したんだ。理由は良いものも悪いものもあったけど。

└

これが本当のフルスタックプログラマーってことだね。

└

昔のドライブゲームを思い出すな。進むにつれて、道が徐々に「構築」されていく感じだった。道のカーブは直線セグメントとして描かれてた。問題ではなかったけど、プログラマーがパフォーマンスを良くするために即興で工夫してたのが明らかだったね。

いい記事だね。ありがとう！本当に素晴らしい！Factorioのブログを思い出したよ。あのゲームは今でも大きな最適化の挑戦だし、デザインにも合ってると思う。面白いことに、もし10,000個の銅コイルがある長いコンベアベルトがあったら、実際には入口と出口のタイルだけがアクティブで、他は動かなくてもいいんだ。何も変わらないからね… ベルトが完全に、または均等に飽和している限りは。だから、そのメカニクスを避けることができるんだ。

└

Factorioの拡張で流体の仕組みが変わったのにはかなりがっかりした。昔のシステムには独特の面白さがあったし、新しいシステムは明らかにパフォーマンスが良いけど、リアリズムが失われちゃったのが残念だね。

同じトリックは、割り算を節約するために逆方向でも使えるよ。NewValue = OldValue >> 3; これは基本的に NewValue = OldValue / 8; と同じだね。RCTではこのトリックをいつも使ってるし、OpenRCT2版でもこの構文は変わってないよ。コンパイラがこの最適化をしてくれないからね。（強調は俺の）全く違うよ。もし型が >> と / が同じ意味になるなら、現代のコンパイラは常に2の累乗での割り算をシフトとして実装するよ。

OpenRCT2のソースを読んでいると、現代のコードではあまり見かけない一般的な構文があって、こんな感じの行があるんだよね。 > NewValue = OldValue << 2; このセクションの捉え方には賛成できないな。ビットシフトは低レベルのコードでは常に使われてるし、ただの古臭い最適化じゃなくて、バイナリデータ（つまりコンピュータ上のすべてのデータ）を扱う自然な方法なんだ。現代の低レベルコードでも、ビットシフトやビット演算子はたくさん使われてるよ。低レベルプログラミングは、パフォーマンスの高いゲームには絶対に必要だし、自分が低レベルプログラミングをしていなくても、ほぼ確実にそれを多用しているエンジンやライブラリを使ってると思う。ゲームの最適化についての記事が、低レベルコードに対して「昔はこうだった」みたいなちょっと古臭い視点を持ってるのには驚いたよ。

└

これらの低レベルのビットトリックは、TempleOSのHolyCソースコードを読んで学んだんだ。この行が何をするのかを理解したとき、天才になった気がしたのを覚えてる：dc->color=c++&15; ヒント：これは「Lines」デモプログラムからのもので、そのソースはここにあるよ： https://web.archive.org/web/20180906060723/https://templeos.... そして、これが実行されたときの見た目（Minecraftで動いてるのは無視してね）： https://youtu.be/pAN_Fza6Vy8?t=38

Warcraft 1（1994年）、Warcraft 2（1995年）、StarCraft（1998年）は、すべて2の累乗に合わせたマップサイズ（64ブロック、128ブロック、256ブロック）を使っていて、シフトファクターを事前に計算して、遅かった古い386/486コンピュータでの除算や乗算を避けてたんだ。各マップブロックは2x2セルで、各セルは8x8ピクセルだったから、背景セルやフォグオブウォーのオーバーレイを描画するのがすごく簡単なアセンブリ言語になったんだ。Warcraftなどは、オフスクリーンバッファにマップやスプライト、フォント、フォグオブウォーを描画するために、数千行のアセンブリ言語しか使ってなかったし、オフスクリーンバッファから画面にブリットするのも簡単だった。残りのコードはアセンブリで書く必要がなくて、パフォーマンスが重要でないコードには書くのに時間がかかりすぎるからね。その他はポータブルアセンブラ、つまりCで書かれてた。編集：比較のために言うと、スーパーファミコン用のBlackthorneはすべて85816アセンブリだった。Genesis版（Motorola 68000）とDOS版（Intel 80386）は、それぞれのアセンブリ言語に手動で書き写されてた。PC版のBlackthorneも、100Kのレンダリングコードを生成するためのカスタムアセンブラマクロがたくさんあったんだ。ブリザードでは、コンソールアプリのポート作業から、アセンブリコードを書くのにプログラマーの時間がかかりすぎることを学んだよ。編集2：Comanche: Maximum Overkill（1992年、ボクセルベースのヘリコプターシミュレーター）は、DOSのリアルモードで完全にアセンブリで書かれてたのを覚えてる。すごい技術的偉業だけど、保護モードに移植するのが大変すぎて、後のバージョンではポリゴンレンダリングに切り替えたと思う。

└

Maximum Overkillは素晴らしいゲームだった。何百時間もプレイしたと思う。

パスファインディングのセクションを見て、Marcel VosっていうYouTubeの配信者を思い出した。彼はパスファインディングがどう機能しているかを深く掘り下げてるんだ。https://youtu.be/twU1SsFP-bE 彼はRCTの仕組みや実装についての深い動画をたくさんアップしてるよ！

最近のゲーム最適化の話を見つける場所ってある？特にクイック逆二乗ルートの話が面白い。以前の人生でVRAYに時間をかけすぎた人間としては、リアルタイムレイトレーシングが実現したなんて信じられないよ。

元のアセンブリソースが、マクロの使用でOpenRCTのものよりもずっと簡潔だったんじゃないかって思う。Mobygamesで彼のゲーム履歴を調べたら、Chrisは1984年から書いてるみたいで、RCTが1999年に出たときには、手で全てのオペコードを書いてたとは考えにくいな。80年代にC64で遊んでたアセンブラにもマクロがあったし。