Xu & Verbrugge: 「重力の向き」や「時間」をレベル生成の座標にする — Fukai が読む

一段落要約

レベルの自動生成は、長いあいだ「地形を作る仕事」だった。壁と床と通路を並べ、そのあとで「重力を反転できる」「足場が動く」といった仕掛けを後付けで検査する。McGill 大学の Kaijie Xu と Clark Verbrugge は、この順番をひっくり返した。仕掛けそのものを座標軸に格上げして、地形と一緒に探索してしまうという提案である。

枠組みの名前は HDPCG(High-Dimensional Procedural Content Generation、高次元の手続き的コンテンツ生成)。マス目の座標 (x, y) に「今どちらの層にいるか」や「今が何秒目か」を足した、大きなグラフを作る。そのグラフの上で普通に経路探索をすると、「重力反転をちょうど3回はさむ道」のような注文が、後付けの判定ではなく生成の段階で満たせる。

論文は arXiv に置かれた版を読んだ。同じ題名の論文が FDG 2026(第21回 Foundations of Digital Games)の会議録に収録されており、査読を通った研究である。

この論文について

題名は「High Dimensional Procedural Content Generation」。著者は Kaijie Xu と Clark Verbrugge の二人で、いずれもカナダ・モントリオールの McGill 大学に所属している。

私が読んだのは arXiv の版で、ページ左端に「arXiv:2602.18943v1 [cs.AI] 21 Feb 2026」と刷られている。2026年2月21日に投稿された preprint(査読前に公開される原稿)だ。ただし同じ題名の論文が、8月10日から13日にコペンハーゲンの Royal Danish Academy で開かれた FDG 2026 の会議録に DOI 付きで載っている。つまり査読は通っている。以下の数値は arXiv 版のものであり、会議録の最終版とは細部が違う可能性がある点だけ断っておく。

今日この論文を選んだのは、パズルサイトから見て珍しく「そのまま実装できる」種類の研究だからだ。重力反転、並行世界の切り替え、時間を止めて通る足場。どれもパズルプラットフォーマーの主要な動詞であり、当サイトでも重力を裏返すという動詞として一度扱っている。それを「生成できるか」ではなく「注文どおりに生成できるか」まで押し込んだのが、この研究の位置である。『VVVVVV』(Terry Cavanagh、2010)の Steam ストアページより。ボタン一つで上下の重力が入れ替わる。論文はこのゲームを、Unity で再現した事例の手本として名指ししている。

ここまで分かっていたこと

PCG(Procedural Content Generation、コンテンツの自動生成)は、レベルや資産を機械に作らせる技術のことだ。何十年も研究されてきて、地形を作る部分はかなり上手くなっている。著者たちの言い方では、それでもレベル生成の定式化は「largely geometry-first(おおむね地形が先)」のままである。

では仕掛けはどう扱われてきたか。論文は、時間に依存する移動、離散的な相互作用のルール、地形以外の状態といったものが、生成器の中で直に表現されるのではなく、シミュレーションを使った目的関数や後処理のヒューリスティック(経験則)として注入されてきたと整理する。作ってから遊ばせて、駄目なら点を下げる、という順番である。

この順番には弱点がある。著者たちは「シミュレーションは要求を間接的にしか強制しない」ため、生成の最中に特定の仕掛けレベルの構造を狙うのが難しくなる、と書く。「重力反転が3回あるレベル」を作りたくても、乱数で作って数えて捨てる、を繰り返すことになる。

だから足りていないのは、個別のアルゴリズムではなく表現そのものだ、というのが出発点になる。仕掛けの豊かなレベルを扱うための、一般的で拡張可能な表現と問題の立て方が要る。

どうやって解いたか

発想は驚くほど素直だ。マス目に「属性」を持たせ、世界の状態を広げた状態空間の上のセルとして書く。すると経路を探すプログラムは、地形と仕掛けを一つのグラフの中でまとめて考えられる。グラフが大きくなるだけで、探索のやり方は変わらない。(図解)左は地形だけの (x, y) グリッド。右は「層」を1本足したもので、切り替え地点だけが2枚をつないでいる。同じ探索が、そのまま仕掛けの検証になる。

一つ目の軸は空間(Direction-Space)である。地形に「層」という飛び飛びの次元を足し、(x, y, z, 層)という4つの座標で到達できるかどうかを検証する。こうすると、重力の反転も、並行世界の切り替えも、「層をまたぐ辺を1本通った」という同じ出来事として扱える。バラバラだった仕掛けが一つの型に収まる。

二つ目の軸は時間(Direction-Time)だ。ここでは時間展開グラフ(time-expanded graph。同じマップを1目盛りごとに複製し、時刻の進みを辺としてつないだグラフ)を使う。プレイヤーの行動は「待つ」「歩く」「乗る」の3種類の遷移として書かれ、そのマスが今ふさがっていないかの確認や、動く足場には端点でしか乗り降りできないといった制約が付く。

どちらの軸も、共通の4段パイプラインを通る。まず大まかな骨格を作り、次にそれを制御しながら地形に落とし込み、高次元のグラフの上で成立するかを検証し、最後に複数の指標で採点する。空間の側には3つの手法が用意されている。i.i.d.(独立同分布)ノイズで作るだけの Naive Noise Baseline(NNB)、通ったところの周りに反発を置いて散らす Naive Penalty A*(NP-A*)、切り替え地点そのものを引力と斥力の場で狙い撃つ Potential Field A*(PF-A*)である。

時間の側も3つ。先に2D/3D の A* で骨格を引き、あとから周期的な足場と障害物を置いて幅優先探索で成立を確かめる Static Backbone Baseline。ビットマスクで軽い記憶を持たせた TEG-A*。層状の有向非巡回グラフの上を前向きに解く動的計画法、TEG-DP である。

分かったこと

空間の側で最も分かりやすいのは「注文どおりになるか」の数字である。切り替えの間隔について、目標との誤差(MAE、平均絶対誤差)は表3で PF-A* が小・中・大の三つの規模で 0.002 / 0.000 / 0.000。NP-A* は 0.091 / 0.093 / 0.097、無誘導の NNB は 0.288 / 0.284 / 0.326 だった。狙って置く手法は、間隔の注文をほぼ完全に守る。

切り替えの密度のほうは、そこまで綺麗ではない。同じ表3で PF-A* が 2.247 / 2.078 / 1.343、NP-A* が 2.217 / 1.366 / 2.554。二つの手法は規模によって勝ったり負けたりしている。ただし NNB は 9.410 / 8.738 / 10.978 で、桁が一つ違う。「誘導すれば効く」ことは明確だが、「どちらの誘導が強いか」は規模しだいと読める。

頑健性の指標として、論文は ARR(alternative route robustness、迂回路の残りやすさ)を測っている。単発実行の平均は PF-A* が小・中・大で 0.338 / 0.319 / 0.530、NP-A* が 0.156 / 0.215 / 0.360、NNB が 0.037 / 0.042 / 0.057。無誘導と比べると、PF-A* は 9〜10 倍ほど別ルートが残る。行き止まりだらけにならない、ということだ。

速さも実用の範囲に収まっている。表4によれば PF-A* の単発実行は、小規模で 0.138±0.060 秒、中規模で 0.663±0.278 秒、大規模でも 4.119±1.136 秒である。1本のレベルを作るのに数秒。日次のバッチなら十分すぎる。

時間の側は、実験の規模がはっきり書かれている。表2では小が 30×15 マスで時間上限 200、乱数の種は12個。中が 50×25 で上限 300、種8個。大が 80×40 で上限 500、種4個である。表6の総合スコア(単発実行)は、大規模で Static Backbone が 7.81±1.77、TEG-A* が 13.30±3.51、TEG-DP が 20.35±9.58。所要時間は 0.31±0.20 秒 / 0.25±0.18 秒 / 6.42±0.68 秒だった。

表5では、TEG-DP が TEG-A* を有意に上回るのは「2つの設定(小規模の単発、中規模の単発)を除くすべて」とされ、効果量(Cliff's δ)は「large」と報告されている。丁寧に解くほど良くなるが、その分だけ遅いという、見慣れた形の結果である。

作る側がどう使えるか

一つ目。重力反転のパズルを作っているなら、「切り替え回数」と「切り替えの間隔」を注文として渡せる。この論文が示したのは、間隔の注文なら誤差ほぼゼロで守れるということだ。難易度カーブを「序盤は間隔を広く、終盤は詰める」と言葉で決めて、そのまま生成器の引数にできる。乱数で作って数えて捨てる、をやめられる。

二つ目。動く足場のステージなら、時間展開グラフで「待ち」と「乗り」の比率を設計できる。プレイヤーが立ち止まっている時間の割合、足場に乗っている時間の割合、接触の間隔。これらが指標として並んでいるので、「待たされ感」をつまみとして持てる。テンポの調整が、感覚ではなく数字の注文になる。『Contrast』(Compulsion Games、2013)の Steam ストアページより。立体の世界と、壁に映る影の世界を行き来する。「層を切り替える」という動詞の分かりやすい実例として置く(論文で扱われたゲームではない)。

三つ目。生成しない人にも使える。手で作ったレベルを、この拡張グラフに載せるだけでよい。「重力反転を使わずにゴールできてしまう抜け道」があるかどうかは、層をまたぐ辺を禁止した状態で経路探索を回せば分かる。生成器を丸ごと導入しなくても、検証器としてだけ切り出せる。

四つ目。品質ゲートとしての摂動テスト。論文は生成後に小さな乱れを与え、作り直せるかで頑健性を測っている。同じことは運用でも使える。デイリーパズルなら、出す前に「足場を1マスずらす」「1目盛り遅らせる」を試し、解が壊れる盤面は配信しない。ARR のような指標を出荷判定に使う、という発想だ。

五つ目、これは注意として。「注文どおり」と「面白い」は別物である。この論文の指標はすべて前者を測っている。生成器を入れるときは、指標が緑でもプレイテストを省かないほうがいい。

限界

著者たちは限界を5つ挙げている。第一に、時間側の理想的な TEG-A* は「意味のある、重複しない接触」を促すために記憶と報酬で状態を膨らませる必要があり、それが状態爆発を招く。そのため実際には簡略版を使っており、扱いやすい代わりに相互作用を厳密に形作る力が落ちている。これが Static ベースラインと DP のあいだに隙間を残している、と書かれている。

第二に、扱っているのは構築的・探索ベースの手法だけで、高次元の状態空間の上で事前知識や価値関数を学べる PCGML(機械学習を使った PCG)や強化学習(試行錯誤しながら報酬が高くなる行動を学ぶ枠組み)はまだ統合していない。第三に、仕掛けの軸を一つずつ別々に評価しており、複数の仕掛けを一つの状態空間で混ぜたときの成否や規模の伸びは未評価。第四に、頑健性は作ったあとに乱してから測っているだけで、遺伝的アルゴリズムの適合度には入っていない(何度も作り直すことになり、費用が跳ね上がるため)。

そして第五が一番重い。著者たちははっきりと「we have not conducted user studies(ユーザー研究は行っていない)」と書き、遊びやすさとテンポは指標とリプレイで支えられているが、面白さの正式な証拠は今後の課題であると認めている。

Fukai がここで指摘するのは、比較の相手についてである。空間側のベースライン NNB は「i.i.d. ノイズと番号順の層切り替え」という、ほぼ無誘導の手法だ。これに 9〜10 倍で勝ったという数字は、「誘導は無誘導に勝つ」という当たり前を丁寧に確認したものと読むのが誠実だろう。既存の PCG 手法と正面から比べた表は、私が読んだ範囲では見当たらなかった。

もう一点。TEG-DP は大規模で単発 6.42 秒だが、遺伝的アルゴリズムを回すと桁が変わる。デイリーパズルのように1日1本なら問題ないが、プレイ中にその場で作るような用途には、この論文の状態のままでは届かないと私は読んだ。

Fukai の読み

私はこの研究を、「レベル生成が地図作りから制約充足に引っ越す」流れの中に置きたい。設計批評の語彙で言えば、これはレベルデザイナーが頭の中で暗黙にやっている「動詞の配置」を、探索可能な座標に翻訳した仕事である。重力反転を「絵の要素」ではなく「グラフの辺」として書き直した瞬間に、間隔も回数も注文できるようになった。面白いのは、そのために新しいアルゴリズムをほとんど発明していないことだ。A* と動的計画法という古い道具のままで、盤面の書き方だけを変えている。表現を変えると問題が易しくなる、という古典的な教訓を、パズルプラットフォーマーの語彙で見せてくれた論文だと私は読んだ。

おわりに

論文は Unity での実演も載せている。空間側では、重力反転の 2.5D レベルと、二つの時間状態を切り替えて地形と敵を抜ける 3.5D のレベル。後者は『Dishonored 2』の A Crack in the Slab や『Titanfall 2』の Effect and Cause を手本に挙げている。著者は「生成されたものがそのまま Unity のレベルであり、見えているものがそのまま遊べる」と書いている。結論部では、これらの指標を体感のテンポ・手応え・楽しさに結びつけることを今後の課題としている。

もっと深く知りたい人へ。同じ会議の系譜で PCG の評価そのものを扱った研究、たとえば PCG のベンチマークを整えようとする流れ(The Procedural Content Generation Benchmark)を合わせて読むと、「何をもって良い生成とするか」の地図が見える。当サイトでは磁力と重力、時間操作、パズルプラットフォーマーの3つの棚が、この論文が座標にした動詞にそのまま対応している。実装の前に、実際のゲームがその動詞をどう使ってきたかを眺めておくと、注文すべき数字が見えてくるはずだ。

参考文献

本記事で参照した論文と関連資料:

・High Dimensional Procedural Content Generation (Kaijie Xu, Clark Verbrugge, McGill University, 2026, arXiv:2602.18943v1 [cs.AI], 21 Feb 2026)

・同論文 / Proceedings of the 21st International Conference on the Foundations of Digital Games (FDG 2026), DOI 10.1145/3815598.3815606(査読済み版)

・FDG 2026 公式サイト(2026年8月10〜13日、Royal Danish Academy、コペンハーゲン)

・記事内の画像は Steam ストアページより:VVVVVV(Terry Cavanagh、2010)/ Contrast(Compulsion Games、2013)。いずれも論文で実験対象になったゲームではなく、動詞の実例として掲載している。

・図解は Fukai による自作(英数字のみ)。