チワ裏

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

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

第5回です。順調に更新が遅れています。
予想以上にstep 2の実装が大変でした...。

今回は自作迷路生成アルゴリズムのstep 2について書いていきます。

step 2

前回のstep 1までで、フィールドを不定形な形に分割することが実現できました。
こんな感じですね。↓


step 1では領域同士が何も関係をもっていないので、今回は連結する際に必要な情報を生成していきます。

連結の方針としては、

  • step 1で生成された情報を用いて接続できるセルを判定
  • 出来るだけ最長経路に(経由するセルの数が多く)なるように調整する
  • デットエンド(行き止まり)の長さを短く

を目標にして実装していきます。

step 1の生成する情報

step 1ではセルを成長させていって、セルが他の領域に衝突したときに、衝突した領域の番号と座標、方向を記録しています。
特に、領域番号からはどの領域同士が連結できるかを知れるので活用していきます。

ただしここで注意点↓

f:id:tiwaluna:20171214225905p:plain

上図にあるように、領域の形が不定形なので、いくつかの特徴が現れます。
図の左は領域の並びになっています。

不定形でない、各領域が正方形で敷き詰められていた場合、あるセルから上下左右の領域に接続できることは自明ですが
今回の場合、図の赤矢印にあるように、本来は接続できた10番↔15番の接続が16番の領域が遮るせいでできなくなっています。
また、図の青矢印では、8番↔12番が斜めに接続できるようになっています。

特に赤矢印の性質により、接続の難易度が上がっています。
解決策としては、必ず上下左右の領域がくっつくように調節するなどがとれるかと思いますが、今回は未接続な状況のまま接続に挑戦しました。

経路をできるだけ長く作る

このアルゴリズムの大きな目標として、迷路の長さを保証する。というものを設定しました。

領域同士の接続からできるだけ長くなるような経路をつくることで実現しようと思います。
単純に考えて、それぞれの領域に「重み」をつけることで、接続経路を誘導することが可能だと思ってました。
いざ実装しようとイキってコードを書いていましたが...


甘かったです。


上の図で説明したように、そもそも領域同士が接続できている保証が無いという致命的な状態になっています。
なので、単純な方法で接続しようとすると、

  • 経路生成失敗 25%
  • 経路が短すぎる(失敗) 35%
  • いちおう形になる 40%

失敗率60%という散々な結果になってしまいました。

解決策

失敗した方法での原因は、重みつきで制限されながらすべての領域を巡回しようとしていたことでした。
そもそもゴールにたどり着けていないこと(経路生成失敗)が多いので、
改善するために

  • とりあえずゴールまでたどり着きやすくする
  • おおまかにジグザグな経路を取らせることである程度の経路を保証できるように
  • 余ったセルはデットエンドとして処理する

という考えでアルゴリズムを組みなおしました。

図示するとこんな感じです↓

大まかに横幅2マスごとにエリア(A0 ~ A2)を定義します。
エリア内でゴールとなる座標、G0 ~ G2を目指します。
ゴールに着いたら、右に一マス移動することで、次のエリアに移動できます。
G2は迷路全体のゴールなので、たどりついた時点で処理を終了させます。

以上のアルゴリズムにより、おおまかに上→下→上のジグザグした動きを作れます。
通路幅があるので、失敗率も低くすることができます。可能ならば横に移動させることを優先させて、経路を長くしやすくできます。
また、図では縦方向のみですが、横方向からも考えられます(右→左→右)
縦方向への生成が失敗したら、横方向からの接続を試すこともで成功確率を上げます。

以上の改良によって、失敗確率が4.6%程度に減少し、失敗しなかった場合は最低17個の領域を巡回する経路を得られるようになりました。

接続に使われなかった領域は適当な隣接領域と接続することで、セル全体が繋がれるようにできます。この場合には短いデットエンドを得ることができます。

まとめ

これで領域同士の接続ができるようになりました。
非常に長々とした分かりにくい説明でもうしわけないです。

欠点としては、低確率で失敗することがあることですね。
二回連続で失敗する確率は約0.2%になりますが、0%にするにはstep 1を改良する必要がありますね。

結構ノリで考えている迷路生成アルゴリズムなので、まともに使えるアルゴリズムの制作難度の高さを痛感しています...。

次回にstep 3を実装してこの迷路生成アルゴリズムは終了になります。
今回はここまでです。めっちゃ疲れた...