チワ裏

とあるゲーム作りたい人のチラシの裏

開発日記 その4 自作迷路生成アルゴリズム step 1

第四回です。
今回はこのゲームの根幹となるアルゴリズムについて書いてきます。

迷路生成のアルゴリズムはネット上にかなりの数がありますよね。
しかし、そのまま利用しただけでは普通の迷路ゲームになってしまいます。
今回の制作するゲームとしては不十分ですし、再帰処理で行われてるとゲーム要素の注入が面倒になります。

そこで、前に書いた再帰分割法の「分割」という考え方や、既存の迷路のアルゴリズムを組み合わせてオリジナルのものを作っていこうと思います。

方針

このゲームでは迷路をランダムな形状で最短距離の指定の長さを保証し管理しやすい構造で、作っていくことが目標です。
上記を実現するためにこのアルゴリズムは 3つのstep に分かれています。

  • step 1 不定形セルの生成
  • step 2 領域の接続
  • step 3 領域内を迷路で埋める

今回はstep 1を解説していきます。

Step 1

まず、ランダムな形状を実現するために平面のフィールドを不定形なエリアに区切っていきます。
計算で不定形な図形を生成するのは非効率なので、乱数を使って実現します。


(フィールドのイメージ)

f:id:tiwaluna:20171210144331p:plain
このようにフィールドのある座標に開始点を付けます。(図では赤く着色)
このアルゴリズムでは1マスを「セル」と名付けます。

上下左右の方向に確率でセルを伸ばしていきます。


等間隔に開始点を発生させて、セルごとに伸びる確率をランダムに設定するとこうなります。
これによって、不定形な形状の領域が作れました。
また、領域ごとに通し番号をつけます。画像の場合、領域が全部で25個あるので、左下が0で右上が24になります。


次に情報の生成です。
次のstep 2では生成したセル同士を連結したいので、連結に必要な情報を抽出します。
必要な情報は、領域同士が隣り合う境界部分です。(画像の色つけした領域の境界部分の座標)

  • 隣の領域の番号
  • 座標
  • 連結方向

を取得します。

取得するタイミングは、セルを伸ばすときに別のセルに衝突したときに取得します。
そのときの衝突した領域の番号、伸ばした方向、座標を取得します。


境界部分を着色するとこうなります。
連結時には、連結先の領域番号を参照して、座標と方向から連結処理を行えます。


今回はここまでです...
次回の更新でstep 2の解説をします!(step 2の実装に詰まっている)

メモ

今回の記事で使用した画像は、アルゴリズムのデバック用のスクリプトで生成したものです。
step 1で生成されたセル番号を配列に格納しておいて、
それをスクリプトで参照して、値の変更が行われたら対応する色(マテリアル)で着色しています。
コルーチンを使ってオブザーバーパターン的に実装してます。

一からアルゴリズムを作っていくのは今回が初めてなんですが、こういった視覚的なデバックがあるととても便利ですね。
文字のみ(Debug.Log)だとレイアウトが崩れたり、柔軟な表示ができないので、デバックコードの重要性がわかりました。

(step 2の実装はデバック用のコードをはじめに作らなかったせいで5時間ほど無駄してしまった...)