【C#】穴掘り法を使ってランダムに迷路を作成する

C#

 

ランダムな迷路を作成する(穴掘り法)

 

穴掘り法は前の記事で書いた棒倒し法よりも若干複雑な迷路作成法になりますが、その分、よりランダムで本格的な迷路を作ることが出来ます。

 

穴掘り法により迷路作成のアルゴリズムを簡単に説明します。

 

N×Nマスの迷路を作成する。

まず、初期設定としてすべてのマスは壁となっている状態です。この状態から穴を掘っていく(壁をなくしていく)ことで迷路を作成します。

 

最初に穴を掘る出発点をマスの中からランダムに選びます。マスの座標はそれぞれ(i, j)としますが、この時 i 、jはともに偶数でなければいけません。

 

出発点から上下左右のうち、2マス進める方向を見つけたら、その方向に穴を掘って2マス進みます。進んだ場所から同じように上下左右の中から進める場所にランダムに2マス穴を掘りながら進んでいきます。

 

この時、上下左右のどちらにも掘れない場合は、来た道をそのまま2マス分戻り、その場所でもう一度、上下左右に行けるかを確認し、行けるならその方向に穴を掘り、そこでも掘れない場合はもう2マス戻ります。

 

つまり、穴掘り法による迷路の生成アルゴリズムは、

  1. 現在いる場所から穴を掘れる方向があるならその方向に掘る
  2. 上下左右のすべてにおいて穴を掘れない時は、来た道を2マス戻って再び1の作業を再開する

という案外シンプルなルールを実装することになります。

 

穴掘り法のソースコード

 

上で紹介したルールについて、

1は、上下左右をランダムに選んでもし選んだ方向が2マス分壁だったらその方向に掘り、もし壁じゃなく穴になっている場合は掘ることはできないので別の方向を探す、という処理を実装します。

 

2は、スタックを使います。穴を掘り進める中で自分が今まで1の作業をしてきた場所を入れておき、もし今いる場所で「これ以上掘り進めない」となったら、スタックから過去にいた場所を取り出し、そこから1を再開する、という処理の実装です。

 

 

なんだかやたら長くなってますけど、要は上で書いた2つのルールを忠実に実装したものです。(多分もっと短くできるんだろーなー)

 

前回の棒倒し法で、「シード値付けられたら面白い」ということをいっていたので、今回は迷路の大きさと一緒にシード値も任意で決められるようになり、よりランダム感が増しました!

 

 

なんか、こういう目で見てわかる系のアルゴリズムなら飽きることなく勉強できますね。

以上!

コメント