離散空間の熱拡散に基づくダンジョン形状に対する難易度指標
不思議のダンジョンやROGUE、DQM(Jとピサロ除く)などのダンジョンの自動生成は、事前に準備した部屋パーツを組み合せによって実現している。そして、生成時に選択される部屋パーツに制約をかけ、部屋内のギミックのプールを変えることで難易度を調整する。
難易度を適切に調整することで、ゲーム体験に良い効果をもたらす
ここで言う「ギミック」とは、「プレイ中に位置や状態が変化する可能性があるもの」である。不思議のダンジョンではポケモン、DQMでは敵モンスターや宝箱、アイテムなどがそれに対応する。
しかしながら、この方法では部屋単位の難易度は設定できても、スタート地点からの順序やアクセス可能性を考慮したダンジョンの地点に対する難易度が推定できない。そのため、アクセスが難しいのに渋い報酬や、早期にたどり着くのに得すぎる報酬、迷いやすいのに難しいギミック配置の実現を許容せざるを得ず、プレイヤー体験に影響を及ぼしてしまう
従来作品はそれを対処するために、全体的に均一な難易度のギミックを配置したり、部屋のアクセス可能性に制約をかけたりしている
そこで、（ギミック配置前の）ダンジョンの各地点の難易度を計算する手法を提案する。これにより、例えば、難易度を考慮した迷路の自動生成や、自動生成されたダンジョンの難易度の評価、難易度を考慮したギミック配置などが可能になる。
本研究ではダンジョンの難しさの要素のうち、移動可能性の数に着目する。具体的には、移動可能性が高いほど選択肢が多く、負荷がかかる。一方、移動可能性が低いほど、選ぶ選択肢が少なく、負荷が小さい。そのことから、各セルの基本難易度を移動の自由度とする。そして、各通路が繋がっているため、移動方向に自由度を均等に分配し、移動をシュミレートする。このようにして何度も分配を繰り返していくことで、自ずと迷路の難易度が見えてくる。
この手続きを以下のように定式化する
仕組み
1. 構造的特徴の抽出
ある通路セル $ (i, j) における自由度 $ N_{i,j} は、
$ C_{i,j}^{k,l}=F_{i,j}F_{i+k,j+l}
code:tex
$ N_{i,j} = F_{i,j}+\sum_{(k,l) \in \mathcal{N}} C_{i,j}^{k,l}
$ (i, j) ：セルの座標
$ F ：迷路の状態を表すフィールド
壁なら $ F_{i,j}=0
通路なら $ F_{i,j}=1
$ \mathcal{N} = \{(0,1), (0,-1), (1,0), (-1,0)\}：上下左右の隣接セルへの相対座標
$ N の空間的な変化（通路の自由度がどれだけ急に変化するか）によって、通路構造の局所的な複雑さを求められ、行き止まりや、通路の合流・分岐点で高い値を示す。
code:tex
D_{i,j} = \sum_{(k,l) \in \mathcal{N}} (N_{i+k,j+l}- N_{i,j}) C_{i,j}^{k,l}
2. 熱拡散モデルによる難易度評価
物理学の熱拡散現象を模倣して、迷路の難易度を評価する。
構造が複雑な場所を「熱源」とし、その熱が迷路の通路を伝わっていく様子をシミュレーションする。
難易度スコアの時間変化を $ R_{i,j}\lbrack t \rbrack とする。
シミュレーションの各時間ステップにおける更新は、以下の方程式の離散形で表される。
code:tex
$ R_{i,j}\lbrack 0\rbrack =N_{i,j}
$ R_{i,j}\lbrack 1\rbrack =R_{i,j}\lbrack 0 \rbrack +\alpha \sum_{(k,l) \in \mathcal{N}}\left( R_{i+k,j+l}\lbrack 0\rbrack - R_{i,j}\lbrack 0\rbrack \right)C_{i,j}^{k,l} = N_{i,j}+\alpha D_{i,j}
code:tex
R_{i,j}\lbrack t+1\rbrack = R_{i,j}\lbrack t\rbrack + \alpha \sum_{(k,l) \in \mathcal{N}}\left( R_{i+k,j+l}\lbrack t\rbrack - R_{i,j}\lbrack t\rbrack \right)C_{i,j}^{k,l}
=R_{i,j}\lbrack t\rbrack+\alpha F_{i,j}(\sum_{(k,l) \in \mathcal{N}}R_{i+k,j+l}\lbrack t\rbrack F_{i+k,j+l}-R_{i,j}\lbrack t\rbrack\sum_{(k,l) \in \mathcal{N}}F_{i+k,j+l})
$ \alpha ：拡散係数
$ R_{i+k,j+l}\lbrack t\rbrack ：隣接セルから流れ込む熱量
$ -R_{i,j}\lbrack t\rbrack ：自身のセルからの熱の流出（散逸）を表す反応項
このシミュレーションにより、行き止まりや狭い通路のような場所では難易度スコア $ R が蓄積・保持されて高くなり、広場のような場所ではスコアが拡散して低くなる。
結果
https://gyazo.com/9cbe5a68d688dab66b280170c3415a87
↑メインの主張
↓応用例
2026/03/12
よく考えたら勾配降下法つかえるやん！ってことでやってみた
アバウトな難易度領域マップから迷路生成できるかも
https://gyazo.com/2a03561fd2c5def3eef14e49182d36ba
できたわ これってDiffusionやね
モデルの処理：入力迷路形状に対して、固定Kernel（上下左右１の3*3カーネル）を使ったConv2dを任意の回数再帰的に適用する（上記の処理をそのまま実装する）
モデルへの入力→迷路形状＋標準正規分布に従うノイズ（徐々にノイズの重みを小さくする）
生成タスクでは、迷路形状を学習可能なパラメータとする
迷路形状の各セルは通路である確率とする
標準正規分布に従うノイズを迷路形状の初期値とする
計算時には確率にするため、迷路形状にシグモイドを適用
モデルの出力→難易度マップ
損失関数
calculated, target難易度マップを互いにminmaxnormしたもので、L1Lossをとる（難易度は量なので）
やるならLogとるとかかな？
壁を溶かすようにして迷路を生成できないか？
$ F_{i,j}を$ F_{i,j}\lbrack t+1 \rbrack = F_{i,j}(R_{i,j}\lbrack t \rbrack), $ N_{i,j} = F_{i,j}(R)+\sum_{(k,l) \in \mathcal{N}} C_{i,j}^{k,l}と捉えたらどうだろう？
例えば、
$ F(R)=1-\frac{\exp(-wR^2)}{1+\exp(-w)}
https://gyazo.com/a4fd3184d36f7e78f02b103802ccf17d
↑0<f(0)=1-f(1)=1-f(-1)<<1となる連続な関数
検証結果
https://gyazo.com/12ea02bdb3b88fc729376ebd5590c43d
よきよき