はじプロで迷路自動生成

はじめに

方式の紹介

　迷路の自動生成アルゴリズムを解説したサイトは沢山ありますが、こちらのサイトがお勧めです。迷路生成以外にも基本的なアルゴリズムが紹介されているので一読の価値ありです。

　方式については沢山情報があるのでそちらを参照していただく事にして、この記事でははじプロで棒倒し法と穴掘り法による迷路の自動生成を行う実装戦略について解説します。

目標

• 150ノードン程度で実装可能である事
  　迷路生成はゲームの本質ではなくあくまで機能の一部です。そもそも少ないリソースでボリューム効果を得る為に使うのであって、迷路生成だけでノードンを食いつぶすようなら採用すべきではありません。

• 10秒で生成完了する事
  　メリットのある方式であっても、迷路生成に時間がかかりすぎるようではゲームへの採用を見送ります。よく言われるWEBサイトの応答時間6秒、最悪でも10秒程度を目標に迷路生成を完了させます。

棒倒し法

棒倒し法を使ったゲーム(ドルアーガの塔)はこんな感じです。

迷路の素材

　棒倒し法では何もない所に動的にオブジェクトを生成する事で迷路を形成します。オブジェクトの動的生成にはモノを発射ノードンを使います。

　モノ発射は1ゲーム中に使用可能な数に上限があります。

• モノ発射（1コ）は1ゲームあたり64個配置可能
• モノ発射（10コ）は1ゲームあたり16個配置可能
• モノ発射（100コ）は1ゲームあたり2個配置可能
  　()内の数は対象のモノ発射がゲーム内に生成可能なオブジェクトの上限を表します。この数を超えて更に生成を続けると、最初に生成したオブジェクトから順次消滅していきます。

迷路サイズ

　ドルアーガの塔の最上階は「全ての壁が左方向を向く」という演出を採用しています。最初からこれをオマージュしたいと思ってたのでモノ発射(100)以下の壁枚数にする、というのが(私の勝手な)要件の一つでした。縦横の壁を7*14=98にすると100以下になるので要件を満たします。

壁生成方向の決定

　棒倒し法で壁を作るルールは以下の通りです。

• 1段目は上下左右4方向の何れか
• 2段目以降は上(1段目の方向)を除く3方向の何れか
• 既に壁がある方向に壁は作れない

　1段目は乱数(4)で方向を決定し、2段目以降は乱数(3)で方向を決定します。乱数の目と壁の方向を(1=左, 2=下, 3=右, 4=上)と対応付け、全ての段の出目と方向を統一します。
「既に壁がある方向に壁は作れない」は何度も乱数を振り直したくない¹ので、被った時に備えもう一つ乱数(2)を並行して準備しておきます。
　右から左、上から下へ移動しながら壁を生成した時、「既に壁がある方向に壁は作れない」状況は「左に壁を生成、一歩左に移動、右に生成」のケースしかありません。直前の壁生成方向をカウンターに記録しておき、前回が(1=左)で今回が(3=右)となる場合に、予備で求めておいた乱数(2)の値を採用します。

生成方向とモノ発射の種類

• 左(=1)は最初の要件により最大96枚、モノ発射(100)確定
• 下(=2)は96/4≒25枚、壁が被った時の補正分も含めて70枚あれば足りそう
• 右(=3)は96/4≒25枚、同様に補正で減るので40枚あれば足りるでしょう
• 上(=4)方向は１段目だけ生成される可能性があるので最大14ですが現実的には14/4≒4枚

上記を根拠にモノ発射を割り当てます。

• 左(=1) モノ発射(100)
• 下(=2) モノ発射(100)
• 右(=3) モノ発射(10)を4個
• 上(=4) モノ発射(10)

物理的振る舞いの検討

モノ発射の発射待ち

　モノ発射の最小待ち時間は0.1秒(=6フレーム)です。最新モデルでは4方向にそれぞれ専用のモノ発射を割り当てていますが、同じ方向に発射する場合いくらシグナルを送っても待ち時間が経過するまで壁は生成されません。
　壁を生成する為にシグナルを送り続けますが、同様に壁の生成が完了したら即座に次の座標に移動する必要があります。よって壁の生成完了を検知する為の触っているセンサーが必要です。

揺れる物体の安定待ち

　フリースライドによる物体の移動に伴いオブジェクトはグラグラ揺れています。揺れたまま壁を生成すると壁がグダグダな方向に射出されてしまいます。発射可能位置に到着した後、揺れがおさまるまで安定待ちする必要があります。
　計画した発射座標と壁生成器の中心座標を比較し、縦横の値の差が一定量以下であれば安定とみなせる為、位置センサーを生成器の中心に取り付けます。

安定待ち時間の短縮

　ワープアウト時の移動量リセットを組み込む事で安定待ち時間を短縮することが出来ます。フリースライドで目的地に移動させる対象は小さな(=軽い)オブジェクト一つとワープ出口のみとして軽量化を図り、揺れを軽減します。
　壁生成器はワープ入口を常にONにしたワープ接続を利用します。

モノ発射(100)を回転させて使ったらどうか

　最初のモデルはモノ発射(100)一つを用いて4方向に角度を変えながら壁生成していましたが、回転も加わると安定までの時間が膨大になりトータルで80秒位かかってました。これでは使い物にならないので4方向独立したモノ発射を取り付け、壁生成器を回転させない事でおよそ1/8位の時間短縮に成功しています。

壁生成器を複数パラレル実行したらどうか

　モノ発射ノードンの使用制限個数を考慮すると2つまで壁生成器を作れますが、ノードンが倍必要になります。ドルアーガの塔は各ステージの謎を解くフラグ管理と多数の敵キャラを用意することを考えると無駄使いは出来ません。実行性能が倍になるのは魅力的ですが、総合的に判断して不採用にしました。

壁生成器

壁生成器のイメージ図

　そこそこ時間のかかる処理をそれなりの回数繰り返し実行する時、タイマーによる待ち時間を挟むとそこがボトルネックになります²。はじプロのタイマーは最小単位が0.1秒(=6フレーム)なので、かなり大雑把で深刻な待ち時間を発生させます。
　この手の回路で高速化を実現するには、シグナルが並列に処理されるステートマシンとして実装する必要があります。ステートマシンと言うと大げさですが、はじプロでは回路の開始地点以外に1フレーム使用するノードン(カウンターやフラグ)を使わなければ自ずとステートマシンになります。

下図左側の四角形(これらは状態を持つのでステート)は全て1フレーム消費するノードンですが、それ以外のモノ発射に至るまでの経路上のノードン処理時間合計が1フレーム未満となる為、全体として1フレーム毎に動作する回路になります。

壁の生成方向

　乱数(3,4)、前回乱数値、予備乱数(2)の3つの状態から今回の生成方向を決定します。壁生成が完了したら一斉に状態を変更します。

安定待ち

　壁を生成する計画座標(カウンターに格納したX,Y)と実座標(壁生成器に取り付けた位置センサー)の座標の差の絶対値が一定量以下になった時点で安定したと見なします。この実装では計画座標を1m単位[^1m単位]のグリッド上の交点としていますが、ぱっと見で崩れていない壁を生成出来る誤差は0.05(=5cm)以下でした。誤差は小さいほど良いのですが0.01(=1cm)にすると更に待ち時間が延びるので5cmを採用します。

壁生成待ち及び次サイクルへの移行トリガー

　壁生成方向が確定し、計画座標で安定すると壁の生成を担当するモノ発射にシグナルが届きます。グリッド間の距離は1mありますが³、生成する壁の長さは85cmと短めにしておきます。触ってるセンサーの最小幅が10cmなので少し予備を取ってこのサイズにしています。

　判り易く図示すると以下のようなサイズ感になっています。ぱっと見分からない程度に隙間が空いてます。

　結果としてグリッドの交点に隙間がある迷路になりますが、キャラクターが通過できない幅なのでゲーム上は問題にならないでしょう。

　このセンサーのシグナルは壁生成のトリガーであると共に全ての状態の更新のトリガーになっています。

棒倒し法の成果

　ノードン数123個, 壁枚数98, 生成時間10.3秒。
　棒倒し法は私の初期作品(4階建てのドルアーガの塔)で採用していますが、まだノードン削減テクニックを使う前の実装なので110ノードン位には圧縮可能でしょう。

　結局10秒切れてないんですけどステージ開始時に対象ステージのヒント絵を表示したり、BGMを流したり、迷路生成途中でも見切りでユーザー入力を受け付けて(カメラに映らない所で迷路生成を続けていて)と、苦肉の演出で誤魔化してリリースしました。

　ボトルネックは安定待ち時間だと目星がついています。今回の実装はフリースライドによる移動を行っていますが、この後紹介する高速なカーソル移動法を採用したらもう少し違う結果が得られるかもしれません。

穴堀り法

穴掘り法を使ったゲーム(ペンゴ)はこんな感じです。

迷路の素材

　穴掘り法では予め配置したブロックを消去しながら迷路を形成します。また迷路サイズは縦横共に奇数である必要があります。
　「予めブロックを配置」とありますが、ブロックを予め配置するという事はその数分のノードンを消費するという事です。9×9=81個ではちょっと狭い、11×11=121個だと見栄えは保つが回路を作る余裕がない、13×13=169個では150ノードンを超える。
　予めブロックを配置するのは無理があります。150を大幅に超えて実現出来たとしてもそれは私にとって作る価値が無い物なので、ここでもモノ発射を使う事にします。

迷路サイズ

　見栄えが良く実装上合理的な数として11×11のブロックにしました。
　モノ発射(10)を横に11個並べ、縦方向に連続して10個射出させます。同時に最下段にもモノ発射(10)を１つ配置し、こちらは横方向に射出します。
　穴掘り法は奇数座標の任意の点から掘り始めて良いのですが左下(0,0)を開始地点にすると、あら不思議⁴、最初からそこにはブロックが存在しません。

　これより大きい13×13を使うと、モノ発射(10)は16個までの制限に引っ掛かりモノ発射(100)も使う必要が出てきます。
　PENGOのフィーチャーでもある「ブロックを押してぶつかった地点でブロックが止まる」の実装を「押したブロックを消去し同じ座標に動かせるモノをワープで召喚、動かせるモノが壁に接したらモノ発射(100)でブロックを生成した後、召喚解除」と予定しています。迷路生成完了後に残るブロック数は120-70=50個です。モノ発射(100)なら50個のリサイクルに十分耐える長さなので、面倒な回路を別途組まなくて済みます。
　あとは生成座標をシンプルに(1～10)の数列だけで決定出来るので座標算出用のノードン消費が少なく済みます。
　実装上合理的な数はこうして決まりました。モノ発射の特性として0.1秒に1回しか射出出来ないのでブロックの初期配置だけで1秒消費しますが、ノードン数をかなり減らせるので選択しない理由はありません。

掘削方向の決定

　掘削機は現在位置から上下左右に2マスの場所を検査し、そこがブロックであれば掘削可能とみなし現在位置から目的地までの２ブロックを消去します。外壁もブロックと同じ幅で用意し外壁の外側を空白にしておけば外壁に飛び出す事もなくなります。
　掘削方向は乱数で決定しますが、ここで何回も振りなおすのは避けたいので工夫手抜きします。
　　掘削方向を(1=右, 2=下, 3=左, 4=上, 5=右, 6=下, 7=左, 8=無し(掘れない))とします。乱数で1～4の方向を得た後、その方向が掘削不能であったら順次+1した数を評価し掘削可能な位置が得られるまで加算します。加算した方向が掘削可能であればその方向に堀り進め、掘れなければ移動できず現在位置に止まり続けます。

掘削機とマーカー

掘削機のイメージ図

　掘削機で掘り進めて行き止まりに達した場合、掘削可能な任意の場所から再開してよいのですが、ここでも乱数を何度も振りなおして掘削可能かの検査とダメならやり直し…を繰り返してしまうと迷路生成時間がどんどん伸びてしまいます。
　このような終わりが見えない処理(オーダー記法でビシッと計算量を決められない処理)は好きじゃないので、一定時間で必ず終わるようマーカーを導入しました。

　掘削機とマーカーは独立して動作します。掘削機の役割は穴掘り法そのものなので割愛します。マーカーは「掘削可能な場所であれば留まり、掘削不能なら探索を続ける」という役割を持ちます。
　非同期に動作する掘削機とマーカーは難易度が高いかもしれませんが、状態遷移をしっかり設計すれば期待通りに動きます。

マーカーの役割

　マーカーは原点からブロック上をサーチし、周囲に掘削可能なブロックがあればそこに留まります。掘削機が4方の何処も掘れずマーカーが静止状態の場合、掘削機の掘削機能をOFFにしてマーカー座標に移動します。
　本来の実装では掘削可能な場所を記憶しておき、行き止まりになったらスタックから任意に選んだ点を開始地点にしますが、はじプロはメモリ相当の回路を作るのにもそこそこ大量のノードンを必要とします。ノードン節約の為メモリの代わりにマーカーを選択しました。

またマーカーの座標が画面外に到達したらサーチ完了となるので迷路生成完了の判定にも使えます。

物理的振る舞いの検討

　棒倒し法で得られた教訓に「フリースライドで移動した物体は揺れが収まるまで時間を要する」がありました。これが解決しない事には更なる高速化は望めません。ブロックの消去は破壊または出口のないワープ(/dev/nullみたいなもの)を使えば良いのですがこれもまた課題を孕んでいます。

高速なカーソル

　海外のグル⁵の一人Scrubzが教えてくれた高速なカーソルを使うことで、揺れの安定待ち問題が解決します。厳密には「移動開始時はとても速いが目的地に近づくにつれて加速度を落とす」なので高速且つ速やかに止まる移動法です。実装は結構簡単で目的地との距離の差を加速度として与えるだけです。このカーソルの移動方法を掘削機の動力に利用します。
(最後に引用したツイートが英語なのは彼へのThanksを伝える為です）

掘削方法

　はじプロの物理エンジンは対象との相対速度が速いと効果範囲が広がる⁶という悩ましい仕様が実装されています。衝突判定が見た目以上に拡がったり、モノを壊すやワープ入口の効果範囲も広がります。高速移動中は対象の中心点から球体状に効果範囲が広がります。
　素早く動き安定も早い動力を得たので嬉々として実装してみると、周囲のブロックも巻き込んで消えていきます。こちらはおめくり氏の助力を得て消去対象の中心で効果発動させずに、消去対象から離れた場所で効果発動させると上手くいくというアイデアです。別の表現で例えると「ブロックの上空で爆発を起こし、その衝撃波で対象を消す」という方法です。
　掘削機の速度と爆発点の高さを試行錯誤してようやく安定して消去する設定が見つかりました。

　余談ですがこの効果範囲は毎フレーム爆発点の座標を中心に球体状に発動します。球体が移動するイメージではなく串ダンゴのような形状になります。これが理由なのかは解明仕切れてませんが、ブロックサイズをデフォルトの80cmから1mに拡大すると消し残しが生じたり周囲を巻き込んだりするので正確な球ではなく、結構雑な球形をしていると予想されます。
　今の所デフォルトサイズのブロックなら実現可能、という不安定な方式です。

穴掘り法の成果

　ノードン数158個, ブロック数11×11 = 121, 生成時間平均4.5秒。

　ノードン数は150を少しオーバーましたが、6秒を切れたので迷路自動生成としては大満足です。この後PENGOを完成させるべく機能追加をしてたのですが特徴的なBGMを入れたい欲と、入れたら確実に512に収まらない葛藤が続いていてゲームとしては未完成です。

1. 重なった方法と同じ方向が出続ける可能性がありますし、乱数生成の1フレーム時間が積み重なると性能劣化の原因になります ↩

2. 私がタイマー嫌いな理由はこれ。事あるごとに言ってるけどwait()系の処理を使うとゲームがモッサリするので使う気にならない。 ↩

3. 真偽値が整数の1または0になるので、整数のゲーム座標系を設計すると、スケール調整の為のノードンが不要になるのでお勧めです。 ↩

4. プログラムを書いてるとよくありますが「自分のやりたいことに対して都合よく数が嵌る」時、数の美しさを感じます。 ↩

5. 日本のおめくり氏、海外のZertolurian, Scrubzが突出したセンスの持ち主です。 ↩

6. 最高60fpsの粒度でしか動作しないのですり抜け防止の苦肉の策なんでしょうね。分からなくもないんですがギチギチにチューンナップしようとすると結構無理な仕様だったりします。 ↩