この記事の対象と、書いている範囲
自動生成のステージが「解けない」ことを防ぎたい人に向けた、設計と実測の記録です。考え方・失敗・測った数字を残しています。 下に合法な引き操作と生成の疑似コードを載せています。完成した生成器一式ではなく、設計を理解するための説明です。 作る手順全体はAIでUnityゲームを作る流れを見てください。
箱を押して目印に載せるパズルを作りました。面は自動生成です。この手のパズルで怖いのは、解けない面を配ってしまうこと。押した箱が角にはまれば、そこで詰みます。
答えは単純でした。クリアした状態から巻き戻して作る。
1000種
毎回検査する種の数
全部解ける
2.2ms
1面を作る時間
解かせながら作って
38→90
狙いの手数に入った数
100面あたり
4つ
ソルバーを速くした工夫
最初は1面5秒超
巻き戻して作れば、解けるかどうかは考えなくていい
作り方はこうです。
手順 01
クリアした状態を作る
箱は全部、目印の上
手順 02
箱を引いて散らす
押すのではなく引く
手順 03
その配置が問題になる
引いた手を逆にたどれば解ける
押す操作は「プレイヤーが箱の反対側に立って、箱を前に動かす」。その逆は「プレイヤーが下がって、箱が自分のいた場所に来る」です。散らす手はこれしか使いません。
解ける面を選ぶのではなく、解ける面しか作らない。
箱を引く操作と生成の手順
箱だけを好きな場所へ移すと、押して戻せる保証がなくなります。実装ではプレイヤーの位置も持ち、プレイヤーが1マス下がり、箱を元の足元へ移す操作に限定しました。
引く前: [箱][人][空き]
引いた後:[空き][箱][人]
戻すときは、人が左へ箱を押せば元に戻る。
下がる先は盤内で、壁も別の箱もないことが条件です。箱へ近づく歩行も合法な空きマスに限ります。コードでは壁と目印を Board、プレイヤーと箱の位置を LevelState に分けています。
次は LevelGenerator の現在の処理を整理した疑似コードです。関数名は説明用で、そのまま実行するC#ではありません。
最大10回、盤を作り直す:
全ての箱を目印に載せたクリア状態を作る
上限回数まで、歩行と合法な引き操作を行う
まだクリア状態なら候補にしない
序盤は探索を省き、その後は2回引くごとに測る
ソルバーで最短の押し回数を求める（探索上限20,000）
狙いの範囲内なら、その面を返す
範囲外でも、いちばん近い解ける候補を覚える
狙いの押し回数の上限を超えたら、引くループを止める
ソルバーの探索上限に達したときも、その盤での探索を打ち切る
引くのが止まった最後の状態も測る
範囲内がなければ、覚えておいた候補を返す
候補もなければ、内側の壁を減らした盤で再試行する
それでも生成できなければ、失敗を返す
ソルバーの探索上限到達を「解なし」と同じ意味で扱うと、解ける盤を誤って捨てます。逆再生で到達した盤には戻る手があるので、ここでは計算を打ち切ったと区別します。解けることと、狙った難しさに入ることは別の条件です。
それでも「難しさ」は揃わなかった
これで解ける面はできます。ところが遊んでみると、3手で終わる面と、10手以上かかる面が混ざる。狙いは面の番号ごとに決めていたのに、そこへ入ったのは100面中38面でした。
理由は単純で、引いた回数と、本当に必要な押し回数が一致しないからです。引いて散らしても、押して戻すときには近道が見つかります。
引き終わってから測る（38/100）
- 決めた回数だけ引いて、最後に1回だけ解かせる
- 近道があると、狙いより簡単な面になる
- 外れたら作り直し。何度やっても当たらない
引く途中で測る（90/100）
- 引く途中で解かせて、最短の押し回数を見る
- 狙いの範囲に入った瞬間に止める
- 超えてしまったら、その盤は捨てて次へ
狙いの数字は、実測してから決める
当たらない原因はもう1つありました。そもそも作れない難しさを狙っていたのです。
最初は「10〜24押し」を狙っていました。測ってみると、7×7の盤・箱2個で作れるのは中央値7押し前後。届くはずのない目標を置いて、外れ続けていただけでした。
難しさは押し回数だけで作らない
押し回数を伸ばすより、盤を広げる・箱を増やす・壁を足すほうが素直に難しくなります。いまは面の番号で「6×6・箱1個 → 8×8・箱3個・壁4枚」と上げていき、押し回数の狙いはそれぞれの構成で実際に作れる範囲に合わせています。
ソルバーが重すぎた（1面5秒超 → 2.2ms）
引く途中で解かせる方式では、ソルバーの速さが面の生成時間に効きます。最初の素直な実装では、100面の検査が400秒でも終わりませんでした。現在は序盤を省き、その後も2回引くごとに1回の探索にしています。
プレイヤーの歩数で探索していた
- 症状
- 枝が4方向×深さぶんに増えて、まったく終わらない
- 原因
- 歩数を数えると、同じ箱の配置でも「プレイヤーがどこを歩いたか」で別の状態になる
- 対処
- 押した回数で測る。プレイヤーが歩いて行ける範囲が同じなら、同じ状態としてまとめる
全部の状態を平らに探していた
- 症状
- 解ける面なのに、探索の上限（20,000状態）に当たって「解けない」と返る
- 原因
- 幅優先だと、答えに近い枝も遠い枝も同じ優先度で広げてしまう
- 対処
- A* にする。残りを「箱から近い目印までの距離の合計」で見積もる。これ以上小さくならない見積もりなので、最短であることは保ったまま探索が減る
詰んだ配置の先まで調べていた
- 症状
- 無駄な枝で状態が膨らむ
- 原因
- 角（隣り合う2辺が壁）に入った箱は、もう二度と動かせない。そこから先に解はない
- 対処
- 目印の上でなければ、その枝を切る
探索の中で毎回配列を作り直していた
ここだけで体感が変わった- 症状
- 状態を1つ広げるたびに、盤の大きさぶんの配列を確保していた
- 原因
- 「歩いて行ける範囲」を塗るための作業用配列を、その場で `new` していた
- 対処
- 作業用の配列を使い回す。作り直すと数十倍遅い
結果はこうなりました。
# 1面を作る（盤を作る → 引く → 解く をくり返す） 100面 220ms / 範囲内 90/100 / 平均押し 5.7 # 1000種類の種で作った面が、すべて解けることの検査 run_tests true 33/33 件成功 (EditMode, 7.48s)
作業用の配列を共用して、解ける面を「解けない」と誤判定した
これは自分のバグです。探索の途中で、「いま広げている状態の塗り分け」と「状態をまとめるときの塗り分け」に同じ配列を使っていました。
結果、正しい押し手を取りこぼして、解けるはずの面に「解けない」と返る。生成器はそれを捨てるので、面が1つも作れないという形で表に出ました。
⚠️ 共用しているものが壊れると、遠いところで症状が出る
出たエラーは「面を作れなかった」。原因は探索の中の配列です。症状が出た場所と原因の場所が離れているときは、途中の値をそのまま信じないで、小さい盤で1回だけ解かせて確かめるのが早いです。
できあがったもの
画面に出している PUSHES 3 は、作るときにソルバーが出した最短の押し回数です。作った瞬間に「この面は3押しで解ける」と分かっているので、そのまま目安として見せています。
まとめ
- クリアした状態から巻き戻して作ると、解けるかどうかの判定が要らなくなる
- ただし難しさは揃わない。引く途中で解かせて、狙いの手数に入った候補を採用する。現実装は探索を間引き、範囲外の候補へ戻る場合もある
- 狙いの数字は実測してから決める。作れない難しさを狙っても外れ続ける
- ソルバーは工夫しないと重い。押し回数で測る／見積もりつき探索／詰みの枝を切る／配列を使い回すの4つで 1面 2.2ms
- 共用した作業用の配列は、遠いところで症状が出るバグになる