TOP > VBでゲーム作っちゃる > 技術 > [VB6]迷路作成のアルゴリズム

[VB6]迷路作成のアルゴリズム

迷路にはいろいろな種類がありますが、今回は純粋な平面の迷路を取り扱います。

突然「迷路を作れ」って言われて紙と鉛筆を渡されても、大概の人はそれなりに迷路を書くことが出来ると思います。でも「迷路の作り方を教えて」って言われても説明は難しいですね。

迷路の書き方を調べると、大きく分けて2つの方法があると思います。

(1)壁を交わらないように書き足していく方法
(2)格子を書いてから壁を取っ払う方法

と言葉で書いてみてもいまいち分かりにくいですね。

(1)の方法はこんな感じになります。

fig.1

一方、(2)の方法はこんな感じになります。

fig.2

プログラミングではどちらの方法も存在しますが、今回は(2)の方法を説明しようと思います。

偏見かもしれませんが、(1)でつくる迷路は、分岐が多いわりに解きやすい迷路になるような気がします。分岐から行き止まりまでの道のりが短くなる傾向があるのかな。(2)でつくる迷路もやり方によって、魚の骨のように一方からは難しいが反対から辿ると簡単な迷路になることがあります。ここで紹介するアルゴリズムはそのような現象が生じないよう工夫しているものになります。


下記の図を使って考え方を整理しましょう。まずは迷路が格子で区切られていると考えます(左)。次にこの1つ1つの空間を部屋とみなします(中)。この例では 5×4 の20個の部屋となります。部屋と部屋の間は壁で仕切られていると考え、これからこれらの壁を壊していくことで迷路を完成させることにします。

fig.3

通常1つの部屋は上下左右の壁があると思われますが、ここでは1つの部屋は下と右の2つの壁しかないようなイメージを持つようにします(右)。各部屋において、上の壁は上隣の部屋のもの、左の壁は左隣の部屋のものとなるわけです。

でもよく見ると、一番上の行の部屋は上の壁がありません。また一番左の列の部屋も左の壁がありません。これでは不十分ですので、ダミーの部屋を用意して上の壁・左の壁を補います。またアルゴリズムの関係で下・右にもダミー部屋があるほうが都合がよいです。つまり本体の周りに1つずつ多く部屋が存在することになります。

fig.4
※グレー部がダミーとなる

ではいよいよ壁壊しの作業と参りましょう。ここで壁壊しの大事なルールがあります。それは、

手順1: 最初は全ての部屋が未訪問なので、任意に1つ選び訪問済みにする
手順2: 隣の部屋が訪問済みかどうかを判断する
●未訪問の部屋がある時 そのうち1つを選択し壁を壊してその部屋へ移動する。
移動後の部屋を訪問済みにし、手順2に戻る。
●周り全てが訪問済みの時 この部屋についての作業は終了し手順3へ進む
手順3: 全ての部屋が訪問済みとなったか確認する
●まだ未訪問の部屋が残っている時 任意の訪問済みの部屋を選択し、手順2に戻る
●全ての部屋が訪問済みの時 作成完了

これが壁壊しのルールです。不思議なことにこんなことを機械的に作業を行うと迷路が完成してしまうのですね。

処理例
fig.5
手順1 任意の1部屋を選択する(図中1)
手順2 未訪問を任意に選択し次々と移動する(赤で表記)。右下に到達し周りが全て訪問済みとなる。
手順3 訪問済み(赤の部屋)から任意の1部屋を選択する。図中3の部屋を選択してしまうと移動できないので選びなおす。図中2の部屋を選択して、手順2を実行した(追加分は橙で表記)。

アルゴリズムとして注意する点は、

・ダミー部屋は訪問してはいけないので、あらかじめ訪問済みにしておく。
・未訪問数をカウントしておく。訪問済みにするたびに減算し0になった時が全て訪問済みとする。
・手順3での部屋選択は、ランダムで抽出するのではなく配列を使って効率よく行う。

といった感じでしょうか。壁を壊す時に右や下なら自分の部屋の壁を壊しますが、上や左の壁を壊す時は隣の部屋の壁を壊すことに注意してください。


では実際に作ってみましょう。まずは部屋の配置をします。今回は15×15の迷路とします。訪問有無や壁情報はビットで管理します。ダミー部屋は訪問済みとし、本体の部屋は壁をセットします。

ここはどうしてもネストの深い処理になってしまうため、便宜上定数や変数をここに書き出しておきます。なお部屋をあらわす配列 room(i, j) は、i がx軸方向(水平方向)に左から右へ、j がy軸方向(垂直方向)に上から下へ付番するものとします。

Private room(16, 16) As Long '部屋情報(1〜15が本体、0と16はダミー)
Private Const VISITED As Long = &H4& '訪問済み
Private Const WALL_D As Long = &H2& '下壁あり
Private Const WALL_R As Long = &H1& '右壁あり
Private Const ARROW_U As Long = &H1& '上方向
Private Const ARROW_D As Long = &H2& '下方向
Private Const ARROW_L As Long = &H4& '左方向
Private Const ARROW_R As Long = &H8& '右方向
Dim ret As Long
Dim arrows As Long
Dim i As Long, j As Long
Dim v(15 * 15 - 1) As Long '対象とする部屋を順番に並べたもの
Dim vIdx As Long '配列vのカレントインデックス
Dim vCount As Long '未訪問部屋数

全体の構造は次のようになります。

'[(A) 初期値処理]

'[(B) 検索順作成]

'[(C) 開始点選択]

Do
  '[(D) 壁壊し処理]

  '[(E) 次の部屋選択]
Loop

'[(F) 描画処理]

(C)開始点選択が手順1に相当します。Do−Loop文は全ての部屋が訪問済みとなるまで繰り返すことになります。これを脱出した時は迷路が完成しています。(D)は手順2を、(E)は手順3を実施しています。これ以後は(A)〜(F)に分割して説明します。

(A) 初期値処理

ここでは各部屋の処理を行います。ダミー部屋は訪問済み(VISITED)を立てます。本体の部屋は壁(WALL_DおよびWALL_R)を立てます。ダミー部屋に壁はあってもなくてもかまいません。

  '[(A) 初期値処理]
  For i = 0 To 16
    '外枠(ダミー部屋)は訪問済みにしておく
    room(0, i) = VISITED
    room(i, 0) = VISITED
    room(16, i) = VISITED
    room(i, 16) = VISITED
  Next
  For j = 1 To 15
    For i = 1 To 15
      '本体は下壁と右壁をセットする
      room(i, j) = WALL_D Or WALL_R
    Next
  Next

(B) 検索順作成

手順3にて訪問済みの部屋を選択する処理があります。前述の手順では任意に部屋を選ぶとしていますが、ここで本当に選択すべき部屋は隣に未訪問部屋がある部屋です。したがって部屋の選択を完全なランダムで行うと、完成間際において選択すべきでない部屋を繰り返し選択し続ける確率が高まるので、作成処理に時間がかかってしまいます。部屋の選択は任意なので例えば左上から順番に選択するという方法でも良いのですが、作成される迷路に偏りがでることが予想されます(ある一方から放射状に伸びるような迷路となる)。

そこでランダム選択による不確定さと順番に選択する処理効率の良さを合わせた方法を採用しようと思います。それはあらかじめランダムに並べ替えた順序を用意してその順番に選択するのです。

ここでは本体の部屋(15×15 = 225つ)に対し左上から右に下に向かって番号(0〜224)を付与します。room(1, 1) = 0, room(2, 1) = 1, …, room(1, 2) = 15, room(15, 15) = 224となります。番号(0〜224)をを配列 v に格納し、並べ替えを行います。配列のインデックス vIdx を0から224まで動かし、v(vIdx)の値に相当する部屋が実際に選択する部屋とみなしていくことにします。

配列 v に番号を格納し並び替えをします。またインデックスvIdxを 0 にします。

  '[(B)検索順作成]
  For i = 0 To UBound(v)
    v(i) = i
  Next
  For i = 1 To UBound(v)
    j = Int(Rnd * (i + 1))
    ret = v(i)
    v(i) = v(j)
    v(j) = ret
  Next
  vIdx = 0

(C) 開始点選択

手順1に従い、最初の1部屋を選択し訪問済みにします。部屋の選択は(B)で作成した配列 v に従って選択します。それから未訪問部屋数 vCount を設定しておきます。全部屋(15×15)からこの1部屋をのぞいた数が現在の未訪問部屋数ですね。

  '[(C)開始点選択]
  i = (v(vIdx) Mod 15) + 1
  j = (v(vIdx) \ 15) + 1
  room(i, j) = room(i, j) Or VISITED
  '未訪問部屋数設定
  vCount = 15 * 15 - 1

配列 v から配列 room(i, j) の二次元分のインデックスを取り出す方法はよろしいでしょうか。roomの要素は1〜15をとるため、v値の商や剰余に対し1を加算する必要があります。

(D) 壁壊し処理

隣接する四方の部屋について訪問状況を調査する方法ですが、やりたいことは任意で選択した room(i, j) に対し、それぞれの隣の部屋が訪問済みかどうかを確認することです。調査には周囲4方向の部屋がVISITEDかどうかを見ることになります。

もし room(i, j) が全体の淵にある部屋の場合、感覚的には隣の(外側の)部屋が存在しないので、訪問済みかどうかの確認が取れなさそうです。しかし周りにダミー部屋を用意したことでこれらが隣接部屋として働きます。この結果部屋が本体の淵であろうとなかろうと画一的な方法で訪問状況の調査を行えます。もちろんダミー部屋はあらかじめ訪問済み扱いにしておくことになりますが、既に(A)で行っています。

淵であるから最初からチェックしないような制御を入れればダミー部屋も不要ですが、いちいち判定するのも大変ですからダミー部屋方式をオススメします。

  Do
    '[(D) 壁壊し処理]の始まり
    Do
      ret = 0
      '各部屋においてVISITEDのビットがなければ未訪問となる
      '上の部屋を調査
      If (room(i, j - 1) And VISITED) = 0 Then
        ret = ret Or ARROW_U '調査結果に未訪問方向ビットを立てる
      End If
      '下の部屋を調査
      If (room(i, j + 1) And VISITED) = 0 Then
        ret = ret Or ARROW_D '調査結果に未訪問方向ビットを立てる
      End If
      '左の部屋を調査
      If (room(i - 1, j) And VISITED) = 0 Then
        ret = ret Or ARROW_L '調査結果に未訪問方向ビットを立てる
      End If
      '右の部屋を調査
      If (room(i + 1, j) And VISITED) = 0 Then
        ret = ret Or ARROW_R '調査結果に未訪問方向ビットを立てる
      End If

このように4方向を調査し、未訪問ならば未訪問方向ビットを立てます。結果 ret が 0 ならば全て訪問済みとなりこの部屋からの移動は終了となります。0 以外ならばどれかの壁を壊すことができるので、立てた未訪問方向ビットのうち1つを選んで隣の部屋に移動すればよいことになります。次の処理で移動する方向を変数 arrows に代入します。

      If ret Then
        Do
          DoEvents
          arrows = 2 ^ Int(Rnd * 4) 'ARROW_U〜ARROW_Rのいずれかの値となる
        Loop Until (ret And arrows)
      Else
        arrows = -1
      End If

移動する方向が決まったら、壁壊し作業を行います。ただし壊す方向によって自分の部屋の壁なのか隣の部屋の壁なのか間違えないよう注意してください。また壁を壊した後、その方向の隣の部屋に移動して訪問済みフラグを立てています。

      '壁を取り除き次のターゲット部屋を選出する
      Select Case arrows
      Case ARROW_U:
        '上隣の部屋の下壁を壊す(ビットオフ)
        room(i, j - 1) = room(i, j - 1) And Not WALL_D
        j = j - 1 '移動
      Case ARROW_D:
        '自分の部屋の下壁を壊す(ビットオフ)
        room(i, j) = room(i, j) And Not WALL_D
        j = j + 1 '移動
      Case ARROW_L:
        '左隣の部屋の右壁を壊す(ビットオフ)
        room(i - 1, j) = room(i - 1, j) And Not WALL_R
        i = i - 1 '移動
      Case ARROW_R:
        '自分の部屋の右壁を壊す(ビットオフ)
        room(i, j) = room(i, j) And Not WALL_R
        i = i + 1 '移動
      Case Else:
        '[(D) 壁壊し処理]は終了
        Exit Do
      End Select
      '新ターゲットの部屋を訪問済みにする
      If (room(i, j) And VISITED) = 0 Then
        room(i, j) = room(i, j) Or VISITED
        vCount = vCount - 1 '未訪問部屋数を減算
      End If
    Loop
    '[(D) 壁壊し処理]の終わり

(E) 次の部屋選択

全方向訪問済みで(D)の処理が終了したら、次の「訪問済み」部屋を選択します。(B)で説明したとおり、配列 v の値に従って部屋を選択していきます。ただし配列は順番を示すだけであり「訪問済み」かどうかはわからないため、選択条件に合うかどうかは検証する必要があります。1順で完了するかどうかは分からないので、インデックスは巡回できるように工夫しておきます。

    '[(E) 次の部屋選択]の始まり
    If vCount = 0 Then       '全て訪問済みなので作成完了
      Exit Do
    Else
      Do
        DoEvents
        vIdx = vIdx + 1
        If vIdx > UBound(v) Then vIdx = 0 '巡回させる
        i = (v(vIdx) Mod 15) + 1
        j = (v(vIdx) \ 15) + 1
      Loop Until (room(i, j) And VISITED)
    End If
    '[(E) 次の部屋選択]の終わり
  Loop'手順2に戻るLoop
  'ここに到達したら作成完了

(F) 描画処理

最後に描画処理を行いましょう。まず外枠を描きます。次にそれぞれの本体部屋の下壁と右壁を描きます。下壁しかなければ"─"を描き、右壁しかなければ"│"、両方あれば"┘"だし、両方なければ描きません。これを全ての部屋について行います。ただし一番右の部屋の右壁は外枠上に描き、一番下の部屋の下壁も外枠上に描きます。

ところで迷路の作成の時に入口と出口を考えていませんでしたよね。今回作成したような迷路というのは、全ての道を通ることができ、かつループしない、あるいはよく迷路で言われる「常に右手(左手)に沿っていけばいつかはゴールにいける」タイプです。このタイプは入口と出口がどこにあっても、必ず入口から出口に到達できます。だって全ての道が通れるのですから。よって内部の壁を作成してから入口と出口を決めても差し支えないのです。したがって最後に入口と出口を開ければ迷路の完成です。以下は描画の一例です。

'[(F) 描画処理]
Private Sub DrawMaze()
  Const PX As Long = 150
  Const PY As Long = 50
  Const PW As Long = 20
  Dim i As Long, j As Long
  '本体部屋の壁を描画
  For i = 1 To 15
    For j = 1 To 15
      If room(i, j) And WALL_D Then
        Form1.Line (PX + (i - 1) * PW, PY + j * PW)-Step(PW, 0), &H0&
      End If
      If room(i, j) And WALL_R Then
        Form1.Line (PX + i * PW, PY + (j - 1) * PW)-Step(0, PW), &H0&
      End If
    Next
  Next
  '外枠描画
  Form1.Line (PX, PY)-Step(PW * 15, PW * 15), &H0&, B
  '入り口と出口を消す
  Form1.Line (PX, PY)-Step(0, PW), &HFFFFFF
  Form1.Line (PX + PW * 15, PY + PW * 15)-Step(0, -PW), &HFFFFFF
End Sub

HOMEこのページの先頭へ    BackSpace入り口に戻る
Copyright(c)GarGer-Studio 2003-2012