自動生成のダンジョンを作る②

Kruskal's Algorithm

前回の続きです。

ringogames.hatenablog.com

 

Kruskal's Algorithmアルゴリズムを例を使って解説していきます。

もっとも簡単な例として、3x3マスで構成される図のような迷路を考えていきます。

A~Iをタイル、それぞれを隔てる境界部分をエッジとし、以下説明を行います。

Kruskalのアルゴリズムでは、タイルを隔てるすべてのエッジに壁を立てた状態から、それを削除していくことによって、迷路を完成させます。そのため、まずすべてのエッジに壁を立てます。
上記例では、12個壁が作られました。この12個のエッジからまずひとつランダムにエッジ選択をし、処理を行います。

まず、最初にランダムな選択の結果、BとEの間のエッジが選択されたとします。この場合、このエッジに存在する壁を削除します。

壁がなくなり、BとEのタイルはつながった状態になっています。この状態になった場合、タイルのグループを変更し、BとEを同一グループのタイルとみなします。ここでは、どちらもBとしました。

次に残りの11個のエッジから1個選択します。

GとHの間のエッジが選択されたとします。先ほどと同様にそこに存在する壁を削除します。HとGも同一のグループとなります。

残りのエッジは10本になりました。この操作を残り10本のエッジについても繰り返していきます。

ただし、毎回壁を削除するわけではありません。

次に図の赤エッジが選択されたとします。

このエッジに隣接するタイルはどちらもAです。エッジに隣接するタイルが同一のグループに所属する場合は、壁を削除する操作をスキップします。

これがこのアルゴリズムのポイントとなります。

処理を続けていきます。


これで、すべてのタイルが同じグループに所属しました。

すべてのタイルが同じグループに所属したら、迷路の完成となります。

まとめると

  • NxNのタイルに存在するすべてのエッジに関して1個ずつランダムに選択し、タイルを隔てている壁の削除を行っていく。
  • エッジに隣接する2つのタイルが異なるグループの際は、壁を削除、同一グループの際は、壁をキープする。
  • この処理をすべてのエッジに関して行い、すべてのタイルが同一グループに所属すれば、迷路は完成。

ということになります。

アルゴリズムとしては非常に簡単なものとなっています。

次回は、これを理解したうえで、実際にコーディングをしていきます。