迷路の生成：壁を崩す順番と乱数の種で、迷路の性格はどこまで変わるか

迷路は「壁を崩して作る木」です

ここで扱うのは、ループがなく、どのマスからどのマスへも道がちょうど1本だけ通じている迷路です。全マスが壁で囲まれた状態から始めて、壁を崩してマス同士をつなぎ、全部が1つにつながった時点で終わります。N個のマスをループなしでつなぐ崩し方は、必ず「N−1か所を崩す」形になります。

数学の言葉では、この構造を全域木（すべての点を、輪を作らずにつなぐ枝の集まり）と呼びます。つまり迷路づくりは、マス目から全域木を1本選ぶ作業です。全域木は無数にあるので、どの1本を選ぶかの方針が、そのまま迷路の性格になります。

この見方には実用上の利点があります。スタートとゴールを決めれば、正解ルートは必ず1本に決まります。ゴールに到達できない迷路が生まれることもありません。ゲームに載せるときの安心材料として覚えておくと便利です。

崩す順番が性格を決めます

壁を崩す方針には、よく知られたものがいくつかあります。以下は一般に言われる傾向です。数値の裏付けはこの記事では示さないので、後の手順で自分の環境で確かめてください。

• 深さ優先、崩し方の要点：直前に開けたマスから、行ける限り進み続ける。行き止まりで戻る、一般に言われる雰囲気：長くうねる通路が続き、分かれ道が少ない
• ランダム選択（Prim風）、崩し方の要点：つながったマスの集まりから、ランダムに1つ選んで枝を伸ばす、一般に言われる雰囲気：短い枝が多く、細かい行き止まりが散らばる
• 壁のランダム順（Kruskal風）、崩し方の要点：壁をランダムな順に見て、すでに同じ集まりに属するマス同士なら崩さない、一般に言われる雰囲気：偏りが少なく、短い枝が多い
• 二択（Binary Tree）、崩し方の要点：各マスが「北」か「東」の壁だけを崩す、一般に言われる雰囲気：最上段と最右列が一本道になる、見た目の偏りが強い

二択の方法は、偏りの理由が一番分かりやすい例です。最上段のマスには北がないので東にしか進めず、最上段が端から端まで1本の通路になります。最右列も同じ理由で北にしか進めません。アルゴリズムの規則が、完成した絵にそのまま表れます。

深さ優先が長い通路になるのは、「最新のマスから伸ばす」ためです。行き止まりに当たるまで枝を伸ばし続けるので、1本が長くなり、枝分かれは戻ったときにしか生まれません。逆に、集まりの中からランダムに選ぶ方法は、あちこちから少しずつ枝が生えるので、短い枝が増えます。

どちらの方式も、「次にどのマスから伸ばすか」の選び方が違うだけです。この違いは、後で示すコードでは1行の差として確かめられます。

同じ方法でも、乱数の種で雰囲気が揺れます

コンピュータの乱数は、種（シード）という数から決まった並びを計算して作ります。同じ種なら、同じアルゴリズムで同じ迷路が再現できます。種を変えれば、別の並びで別の迷路になります。

ここで知りたいのは、同じアルゴリズムの中で種を変えたときの揺れ幅です。揺れが小さければ、アルゴリズムを選ぶだけで性格が決まります。揺れが大きければ、「当たり」の種を選ぶ工程が、ゲームの設計に必要になります。どちらになるかは盤の大きさや方法で変わるため、この記事では結果を書きません。測る指標は次の3つが手軽です。

• 最短経路の長さ：スタートからゴールまで、最短で何マス進むか。長いほど「歩かされた」感触になります。
• 行き止まりの数：道がつながっている先が1つしかないマスの数。多いほど「迷わされる」感触になります。
• 最長の直線：まっすぐ続く通路の最大の長さ。長いほど見通しがよくなります（この記事のコードでは数えません。余裕があれば追加してください）。

これらの数値は、見た目の印象を比べるための物差しです。「雰囲気」という曖昧な言葉を、同じ条件で比べられる数に置き換える役割を持っています。

手元で確かめる：種を20個回して数えます

次のコードを maze.html として保存し、ブラウザで開いてください。外部ライブラリは使いません。上の MODE を "newest"（深さ優先）と "random"（ランダム選択）で切り替えて比べられます。

<canvas id="c" width="320" height="320"></canvas>
<pre id="o"></pre>
<script>
const N=15,S=20,MODE="newest",SHOW=1; // MODE: "newest" か "random"
function rng(a){return()=>{a|=0;a=a+0x6D2B79F5|0;let t=Math.imul(a^a>>>15,1|a);t=t+Math.imul(t^t>>>7,61|t)^t;return((t^t>>>14)>>>0)/4294967296}}
function make(seed){
  const r=rng(seed),open=Array.from({length:N*N},()=>[]);
  const seen=new Set([0]),st=[0];
  while(st.length){
    const i=MODE==="newest"?st.length-1:Math.floor(r()*st.length);
    const c=st[i],x=c%N,y=c/N|0;
    const nb=[[1,0],[-1,0],[0,1],[0,-1]].map(([dx,dy])=>[x+dx,y+dy])
      .filter(([a,b])=>a>=0&&b>=0&&a<N&&b<N&&!seen.has(b*N+a));
    if(!nb.length){st.splice(i,1);continue}
    const [a,b]=nb[Math.floor(r()*nb.length)],n=b*N+a;
    open[c].push(n);open[n].push(c);seen.add(n);st.push(n);
  }
  return open;
}
function dist(open){
  const d=new Array(N*N).fill(-1);d[0]=0;const q=[0];
  for(let i=0;i<q.length;i++)for(const n of open[q[i]])if(d[n]<0){d[n]=d[q[i]]+1;q.push(n)}
  return d[N*N-1];
}
function draw(open){
  const g=document.getElementById("c").getContext("2d");
  g.beginPath();
  open.forEach((o,c)=>{const x=c%N,y=c/N|0,X=x*S+10,Y=y*S+10;
    if(x==0){g.moveTo(X,Y);g.lineTo(X,Y+S)}
    if(y==0){g.moveTo(X,Y);g.lineTo(X+S,Y)}
    if(x==N-1||!o.includes(c+1)){g.moveTo(X+S,Y);g.lineTo(X+S,Y+S)}
    if(y==N-1||!o.includes(c+N)){g.moveTo(X,Y+S);g.lineTo(X+S,Y+S)}});
  g.stroke();
}
let t="種 最短 行き止まり\n";
for(let s=1;s<=20;s++){const m=make(s);t+=s+" "+dist(m)+" "+m.filter(o=>o.length==1).length+"\n"}
document.getElementById("o").textContent=t;draw(make(SHOW));
</script>

記録の取り方

手順は次のとおりです。

1. MODE="newest" のまま開き、画面の表（種1〜20）を、最短経路の長さと行き止まりの数の2列で表計算ソフトなどに写します。
2. MODE="random" に書き換えて読み込み直し、同じ表をもう1つ作ります。
3. 各列の最小・最大・平均を出します。最大と最小の差が、そのアルゴリズムの「揺れ幅」です。
4. SHOW を変えて、最短が最も長い種と最も短い種を描き、見た目の違いを自分の目で見比べます。

結果の読み方

• 2つの方式で平均が大きく離れていれば、アルゴリズムが傾向を決めています。揺れ幅が平均の差より小さければ、種による個体差は傾向の内側に収まっています。
• 同じ方式の中でも揺れ幅が平均の差に近ければ、種の選び方がゲームの手触りを左右します。ゴールまでの最短を下限と上限で絞って、条件に合う種だけ採用する作り方が現実的になります。
• 行き止まりが多い方式の最短が短く、少ない方式の最短が長いかは、自分の数字で確認してください。この対応を前提にした設計を、確認せずに決めるのは避けたほうが安全です。

起こりやすい誤り

• 種を20個だけで断定する：標本が小さいと、偶然の偏りが混ざります。気になる差が出たら、種を100個や1,000個に増やして再確認します。
• スタートとゴールの位置を変える：この比較は左上から右下で固定しています。位置を変えると最短の分布も変わるので、比べるときは条件を揃えます。
• 盤の大きさを混ぜる：15×15の結果を、31×31にそのまま当てはめないでください。サイズを変えたら表を作り直します。
• Math.random() に置き換える：種を指定できないため、同じ迷路を再現できず、比較も共有もできません。

ゲームに載せるとき：測る物差しは遊びの目的と対になります

迷路の最短距離は、遊びの目的によって価値が変わります。例として、公式作品「月夜の配達」を取り上げます。確認済みの仕様から読み取れるのは次の点です。

• 小包は3つで、バッグは2枠です。
• 燃料は有限で、1区間の移動で燃料を1使います。
• 残り最短距離や、次の一歩を照らすヒントが用意されています。
• 各夜の最少区間数は、プレイ中だけ記録されます。

これらの設計から読み取れるのは、「経路の長さ」が遊びの中心の物差しになっていることです。燃料の制約があるため、最短に近い道を探す行為に意味が生まれます。この作品の経路が迷路生成の手法で作られているかどうかは、確認済み事項には含まれません。この部分は作品を開いて確かめてください。

自作の迷路ゲームでも同じ考え方が使えます。燃料や制限時間のような制約を置くなら、最短経路が短すぎる種は退屈になり、長すぎる種は詰みに近づきます。先ほどの表で上限と下限を決め、範囲に収まる種だけを使えば、難易度を数字で管理できます。

クラウドセーブは作品ごとにJSONで128KiBまで使えます。使う種の番号を数個保存するだけなら、容量は問題になりません。ただし、アップロードした作品でSDKが自動で追加されることと、URL投稿の作品で作者がSDKを読み込む必要があることは、投稿時に確認してください。

次の行動

まず上のコードを保存して、2つの方式で種20個の表を作り、最短経路と行き止まりの揺れ幅を比べてみてください。次に、自分のゲームに合う条件（最短の範囲など）を決めて、その範囲に収まる種だけを選ぶ処理を足します。形になったら単独のHTMLにまとめ、アソバースに投稿できます。投稿は入力、表示の確認、公開の3段階で、公開にはメールアドレスの確認が必要です。