Xu et al.: ゲームの「仕掛け」を座標に格上げして解けるレベルを自動生成する — Fukai が読む

TL;DR(一段落要約)

ゲームのレベルを自動生成する技術(PCG)の多くは、まず地形の形だけを作り、ジャンプのタイミングや重力反転といった「仕掛け」は後付けで検証する。本論文はこの順序を逆転させ、仕掛けそのものを座標の一つとして地形と同時に設計する枠組み「高次元PCG(HDPCG)」を提案する。位置に「階層」や「時間」という軸を足した拡張グラフの上で経路探索を走らせることで、解けることを生成の最中に保証する。著者は重力反転や移動床のレベルを、解の通り道つきで自動生成し、Unity 上で実際に遊べる形まで再現してみせた。

はじめに

本稿で読むのは、McGill 大学(カナダ・モントリオール)の Kaijie Xu と Clark Verbrugge による『High-Dimensional Procedural Content Generation』である。2026年2月21日に arXiv に投稿された preprint(プレプリント、投稿原稿。まだ peer-review、つまり専門家による査読を正式に通したとは確認できない段階)で、論文 ID は arXiv:2602.18943。本文はゲーム研究の会議向けの体裁に整えられているが、私が確認した限りでは現時点では arXiv 上の公開にとどまる。被引用数もまだ立っておらず、広く議論される前の新しい仕事だと先に断っておく。

私がこれを今日の一本に選んだのは、「実装に近いか」という私の基準にまっすぐ刺さったからだ。PCG(Procedural Content Generation、ゲームの地形やレベルを自動で作る技術)の論文は理論に閉じがちだが、本論文は重力反転や移動床という具体的な仕掛けを題材にし、しかも生成したレベルを Unity 上で実際に遊べる形にまで落としている。「作る人がそのまま使える話」として、ホットの濃いめのコーヒー片手に、紙に印刷した PDF へ色ペンで線を引きながら読み進められた一本だ。

背景

まず背景を整理したい。レベル自動生成の研究は長らく「地形の形」を中心に進んできた。2Dのタイルマップや見栄えのする3D空間を作る手法は数多いが、時間に依存する移動、離散的なルールのある相互作用、空間以外の状態(たとえば「今どの世界にいるか」)といった仕掛けは、生成の後でシミュレーションや後処理によって帳尻を合わせる扱いが主流だった。著者はこれを「geometry-first(地形優先)」と呼ぶ。

この順序には弱点がある。地形と仕掛けが強く絡み合うレベル——たとえば「この床は3秒後にしか乗れない」「この壁は別の世界では通れる」——では、形を先に決めてから仕掛けを足すと、そもそも解けない(クリア不能な)レベルが量産されやすい。著者が問題にするのは、仕掛けを生成器の中で正面から表現する「一般的で拡張可能な表現方法」が欠けていた、という点だ。解けるかどうかを後から確かめるのではなく、作りながら保証したい——これが本論文の出発点である。

アプローチ(方法)

著者の発想を一言でいえば「仕掛けを座標に格上げする」ことだ。普通は位置(x, y, z)だけでマス目を考えるが、HDPCG ではそこに「階層」や「時間」といった追加の軸を足す。各マス目は「どこにいるか」に加えて「どの層にいるか/今が何秒目か」までを抱えた状態になる。著者はこれを「次元拡張グラフ(Dimensional-Expanded Graph、位置に追加の軸を編み込んだ経路網)」と呼ぶ。時間を軸にした特別な場合が、古くから知られる「時間展開グラフ(time-expanded graph、各時刻ごとに地図を複製してつなぐ手法)」にあたる。

この拡張グラフの上では、レベルが解けるかどうかは「スタートからゴールまで経路が引けるか」という単純な探索問題になる。著者は A*(エースター、目的地までの見積もりを使って最短経路を効率よく探す探索法)や幅優先探索、動的計画法(dynamic programming、小さな部分問題の答えを積み上げて全体の最適解を出す方法)を使って、生成の最中に解の通り道を一本見つける。経路が引けなければそのレベルは無効として捨てるか、パラメータを振り直してやり直す。つまり「解けること」が生成の前提条件(著者の言葉では first-class invariant、最初から守られる不変条件)として組み込まれている。

全体は四段の流れで統一されている。まず(1)おおまかな骨格となる経路を引き、次に(2)その骨格の周りに通路や部屋、層の切り替え地点、動く床などの属性とルールを肉付けする。続いて(3)拡張グラフ上の経路探索で「本当に通れるか」を検証し、最後に(4)できたレベルを指標で評価して、必要なら遺伝的アルゴリズム(genetic algorithm、良い個体を選んで少しずつ変異させ世代を重ねて改良する最適化手法)でパラメータを探索し直す。空間でも時間でも、この同じ四段の枠で扱えるのが本論文の骨格だ。

具体化は二方向で行われる。「空間方向」は位置に層を足し、VVVVVV のような重力反転や、Dishonored 2・Titanfall 2 のような並行世界の切り替えを扱う。手法は三つあり、ほぼ無誘導の素朴な基準線(NNB)、通った道から後の道を遠ざける「分散」を効かせた NP-A*、切り替え地点の座標を明示的に狙い撃つ PF-A* と、制御の強さが段階的に上がる。「時間方向」は位置に時間を足し、周期的に動く床や敵を扱う。こちらも素朴な静的骨格、簡略化した TEG-A*、そして本命の TEG-DP(動的計画法版)の三つだ。

発見

結果を見よう。空間方向では、切り替え地点の「最小間隔」をどれだけ狙い通りに作れるか(間隔の制御性)で PF-A* がほぼ完璧だった。目標値との平均絶対誤差(MAE、狙いと実際のズレの平均)は小規模から大規模まで約0.00で、NP-A* は約0.09、無誘導の NNB は約0.28〜0.33とずれが大きい(論文 Table 3)。密度の制御も大規模では PF-A* が誤差約1.34で、NP-A* の約2.55より正確だった。総合品質スコアでは小・中規模では NP-A* が勝ち(小規模のGAで168.9 対 137.6)、大規模では PF-A* が逆転する(GAで412.3 対 400.0)。NNB は大規模でスコアが大きく崩れる(単発でマイナス327.5)と著者は報告している。

頑健性、つまりレベルに小さな障害物のノイズを混ぜても別の経路で復帰できるかでは、PF-A*(単発)だけがいくらかの成功率を示した(大規模で0.217±0.40、他はほぼ0)。著者はこれを「PF-A* の間隔の規則正しさが、局所的な作り直しのしやすさにつながる」と読む。ただし遺伝的アルゴリズムで品質スコアを最大化すると、余裕のある回り道が刈り取られて逆に脆くなると注意している。速度は単発なら PF-A* で小規模0.138秒・大規模4.1秒だが、GAを回すと大規模で500秒近くかかる(Table 4)。

時間方向では、総合スコアの順位が TEG-DP > TEG-A* > 静的骨格、という形でおおむね一貫した。著者は多重比較の補正(Holm-Bonferroni 法)をかけても、小・中規模の単発を除く多くの条件でこの差が統計的に有意だったと述べている。そして両方向とも、生成したレベルを Unity 上で実際に動かし、重力反転・時間切り替えのレンズ・移動床のタイミングが、計算で出した解の通りに遊べることを確認している。「地形だけ一致」ではなく「仕掛けごと再現」できた、というのが著者の主張だ。

使いどころ

では、ゲームやパズルを作る人はこれをどう使えるか。具体例を挙げたい。第一に、もし自分が VVVVVV のような重力反転プラットフォーマーを作っているなら、「切り替えの頻度(密度)」と「切り替え地点の最小間隔」という二つのつまみを回すだけで、細かい連続反転で操作技術を試させる区間と、ゆったり進ませる区間を、解ける保証つきで打ち分けられる。手作業で地形を縫い合わせる必要がない、というのが効く。

第二に、もし Dishonored 2 や Titanfall 2 のような「過去と現在を切り替えて進む」時間シフト・パズルを作るなら、同じ密度・間隔のつまみが今度は「時間ジャンプの間合い」を制御する。素早い多段ジャンプの場面と、じっくり構えた仕掛け場面を作り分けられる。第三に、もし Super Mario 3D World のような移動床のタイミング・アクションなら、「床に乗っている時間の割合(ride ratio)」と「イベントの最小間隔」を目標値として与えれば、待つ・歩く・乗るのリズムを設計者側から指定できる。

より一般に、本論文の効きどころは「レベルのブロックアウト(おおまかな下書き)」だと私は読む。解ける通り道を一本確保した骨格を自動で量産し、その上に人が手で味付けする、という分業ができる。制約充足やSATソルバー(条件を満たす解があるかを機械的に判定する道具)でパズルの解の有無を確かめている人にとっては、「解の存在を後で検査する」のではなく「解を持った状態で生成する」という発想の転換が、そのまま自分のパイプラインに移せるはずだ。

限界

限界もはっきりしている。まず著者自身が認めている点から。理想的な時間方向の探索(完全版 TEG-A*)は、どの床や端点をすでに使ったかという「相互作用の記憶」を状態に持たせる必要があり、組み合わせが爆発して最小規模でもタイムアウトしたという。そのため簡略版で妥協しており、静的骨格と本命 DP の間に性能差が残る。また、PCGML(機械学習でレベルの傾向を学ぶ手法)や強化学習はまだ組み込んでおらず、仕掛けは一軸ずつ別々に評価していて、層と時間を同時に混ぜた複合的なレベルは検証していない。頑健性も生成後の検査どまりで最適化には組み込めていない。そして決定的に、被験者を使ったユーザー研究がなく「面白さ」の証拠は今後の課題だと著者自身が明言している。

Fukai がここで付け加えて指摘するのは、二点だ。一つは、本手法が保証するのは「解の通り道が一本ある」ことであって、レベル全体の体験ではない、という点。著者も「通路を広げた後に想定外の近道が生まれうる」と認めているが、裏を返せば、生成された一本道が設計者の意図したリズムを本当に持つかどうかは、指標の重み付け次第で揺れると読める。もう一つは、評価がほぼ自動指標と再生映像に閉じていることだ。間隔や密度を正確に当てられても、それが人にとって「歯ごたえ」や「理不尽さ」としてどう感じられるかは、この論文の射程の外にある——その点は著者も認めている。

Fukai の読み

ここからは私(Fukai)の読みだ。私はこの研究を、PCG の歴史における「地形から仕掛けへ」という重心移動の中に置きたい。これまでのレベル生成は「どんな形か」を問い、解けるかは後から確かめてきた。HDPCG はその問いを「どんな状態遷移の網か」へとずらし、解けることを設計の前提に組み込んだ。設計批評の語彙でいえば、これはレベルデザイナーが頭の中で暗黙にやっている「この仕掛けなら、ここでこう動けるはず」という可達性(到達できるかどうか)の読みを、グラフ探索として外在化・自動化した試みだと整理できる。形ではなく「動ける道筋」を一級市民に据えた点に、私はこの論文の射程の広さを感じる——というのが、ここだけは私の解釈である。

おわりに

最後に地図を渡しておきたい。もっと深く知りたい人は、本論文が下敷きにしている Seth Cooper らの Sturgeon シリーズ(制約充足でレベルと解の通り道を同時に生成する研究)や、Kaylah Facey と Seth Cooper の時空間 WaveFunctionCollapse(時間を軸に加えたレベル生成)を合わせて読むと、「解を持ったまま生成する」系譜の地図が見えてくる。逆に、本論文がまだ手を付けていない PCGML や強化学習との接続に興味があるなら、Julian Togelius らの PCG 教科書的研究から入ると、本論文がどこに空白を残したかが立体的に分かるはずだ。

参考文献

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

・High-Dimensional Procedural Content Generation (Kaijie Xu, Clark Verbrugge, 2026, arXiv preprint arXiv:2602.18943, 2026-02-21 投稿)

・同論文の HTML 版(本文・図・実験設定)

・関連研究: Seth Cooper & Mahsa Bazzaz, Sturgeon-MKIV: constraint-based level and playthrough generation with graph label rewrite rules (AIIDE 2024) — 制約充足でレベルと解を同時生成する系譜

・関連研究: Kaylah Facey & Seth Cooper, Toward space-time WaveFunctionCollapse for level and solution generation (AIIDE 2024) — 時間を軸に加えたレベル生成

※ 数値はすべて本論文の本文・Table 3 / Table 4 の記載に基づく。被引用数はまだ立っておらず、広く議論される前の段階である。