自動生成のダンジョンを作る②
Kruskal's Algorithm
前回の続きです。
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つのタイルが異なるグループの際は、壁を削除、同一グループの際は、壁をキープする。
- この処理をすべてのエッジに関して行い、すべてのタイルが同一グループに所属すれば、迷路は完成。
ということになります。
アルゴリズムとしては非常に簡単なものとなっています。
次回は、これを理解したうえで、実際にコーディングをしていきます。