第13回　考える楽しさ、習う楽しさ「６．迷路を作ろう　その４」

13−６　迷路を作ろう　その４

多少、贅沢な悩みですが、その３で作った迷路に対して、手放しで満足を感じない部分があります。
ちょっと考えてみることにしましょう。

その３で登場した、経路を徹底的に検索するタイプのプログラムですが、徹底的に空いている部分を検索しますので、迷路作成の最初の方は１つの検索経路が長いのですが、終盤にさしかかると、検索できる経路が減ってくるため、１つの経路が短くなることが考えられます。
その３のプログラムでは、全部の基点を左上から右下まで順に検索しましたから、迷路作成の終盤、つまり、右側に近づにつれて、だんだんと壁が短くなるわけです。

　　　　

つまり、この迷路の左側と右側では壁の長さに「偏り」が発生するような気がするのですが、もちろん、隣方向の初期値をランダムで決めているので「常にそうなる」というわけではありません。
しかし、そういう傾向を含んでいるのは確かですので、何らかの形で対応をしておきたいところです。
そこで、次はこの部分を解決してみるわけですが、順番に基点を検索しているところが問題なのは明らかですから、これを、順番ではなく、ランダムに選択すればよいですね。

　　　　

でも、問題は具体的な方法です。
そこで、基点をランダムに選択して検索を行い、１つの検索が終わったら基点の状態を調べて、すべての基点にブロックが置かれた時点で終了にする、という方法を考えてみました。

　　　　

フローチャートにまとめると、比較的わかりやすくて、これなら問題が解決しそうです。
しかし、この方法には、大きな欠点があります。それは何でしょうか？
そうですね、今回の最初に登場した、ランダムな数列を作る、という例題で遭遇した問題と内容が同じですね。気がつきましたか？
始点となる基点を決めるために、乱数を使うのですが、迷路作成の後半になってくると、だんだんと空いている残りの基点が少なくなります。
そのため「ランダムに基点を選ぶ」という部分を何度も繰り返すことになりますので、この部分にボトルネックができてしまうわけです。
そこで、ランダム数列を作るときにも登場した手法を、ここでも生かしてみましょう。あらかじめ、検索する基点の順番をランダムな数列として作っておけばよいですね。

　　　　

これをプログラミングしてみました。

    Dim x as Integer
    Dim y as Integer
    Dim H as Integer
    
    Dim Dx as Integer
    Dim Dy as Integer
    
    Dim Px as Integer
    Dim Py as Integer

    Dim P as Integer

    Dim cT as Integer
    
    Dim Rx(11) as Integer
    Dim Ry(11) as Integer
    
    Dim i as Integer
    Dim j as Integer
    Dim swP as Integer
    
    '迷路の初期化
    Call init_maze()

    '基点の初期値を作成する
    For i = 1 To 11
        Rx(i) = i * 2 + 1
        Ry(i) = i * 2 + 1
    Next
    
    'ここはランダム数列へ並べ替えをするところ
    For i = 11 To 2 Step -1
        j = Int(Rand() * (i-1))+1
        swP = Rx(i)
        Rx(i) = Rx(j)
        Rx(j) = swP
    
        j = Int(Rand() * (i-1))+1
        swP = Ry(i)
        Ry(i) = Ry(j)
        Ry(j) = swP
    Next

    'ループ１
    For i = 3 To 23 Step 2
        'その３のルーチンを流用するための小技
        x = Rx((i-1) / 2)

        'ループ２
        For j = 3 To 23 Step 2
            'その３のルーチンを流用するための小技
            y = Ry((j-1) / 2)
        
            'もし注目する基点に何もなければ、検索処理を行う
            If maze(x, y) = 0 Then
                
                '現在の基点を変数(Px､Py)に代入（検索の基点の初期化）
                Px = x
                Py = y
                
                '検索処理
                Do
                    'まず、基点にブロックを置く
                    Call Put_Block(Px,Py)

                    'カウンタを初期化する
                    cT = 0


                    '注目する方向の初期値をランダムで決める
                    H = Int(Rand()* 4)
                    
                    Do
                        Dx = 0
                        Dy = 0
                    
                        '注目する方向に応じた座標の増加量を決める
                        Select Case H
                            Case 0 '右（現在位置から横へ）
                                Dx = 1
                            Case 1 '下（現在位置から下へ）
                                Dy = 1
                            Case 2 '左（現在位置から左へ）
                                Dx = -1
                            Case 3 '上（現在位置から上へ）
                                Dy = -1
                        End Select                        

                        'カウンタに１加える
                        cT = cT + 1

                        'カウンタが４か、隣方向の基点がブロック以外なら方向検索から抜ける
                        If cT=4 Or maze(Px + Dx * 2, Py + Dy * 2) <> 1 Then 
                            Exit Do
                        End If

                        '次の方向をセットする（右→下→左→上）
                        H = H + 1
                        If H > 3 Then H = 0
                        
                    Loop 

                    P = maze(Px + Dx * 2, Py + Dy * 2)

                    '隣の基点がブロック以外なら
                    If P <> 1 Then

                        'まず「隣」にブロックを描く
                        Call Put_Block(Px+Dx,Py+Dy)

                        '隣の基点が外壁だったら、ここで検索処理は終わり
                        If P = 2 Then
                            Exit Do
                        End If

                        'そうでない場合、つまり何もない場合、その位置を新しい基点にする
                        '検索処理は継続される
                        Px = Px + Dx * 2
                        Py = Py + Dy * 2
                    
                    Else
                        'もう、隣方向に空きの基点が存在しない時、検索処理終了
                        Exit Do
                    End If
                Loop

            End If
        Next
    Next

その２を改良してその３を作ったように、その４への改良も、部分的な追加で済ませられるように工夫してみました。
例えば、この部分です。

    'ループ１
    For i = 3 To 23 Step 2
        'その３のルーチンを流用するための小技
        x = Rx((i-1) / 2)

ひとつ前の、その３では、

    'ループ１
    For x = 3 To 23 Step 2

となっていた部分で、こちらの場合は、変数 x を直接ループさせていましたが、その４では、変数 x を ランダム数列 Rx()から与えるようにしてあります。

話は前後しますが、ランダム数列はRx()とRy()のそれぞれに、基点の横、縦方向の座標がランダムに入っています。
基点の座標は(3,3)〜(23,23)で、奇数の部分ですから、それぞれの初期値は、

    '基点の初期値を作成する
    For i = 1 To 11
        Rx(i) = i * 2 + 1
        Ry(i) = i * 2 + 1
    Next

としてあります。
ここでは、

i = 1, 2, 3, 4, …,10, 11

の時に、

Rx(i)= 3, 5, 7, 9, …,21, 23

となる奇数の数列を作っています。
この数列を後から利用しする場合は、ちょっと工夫をして、プログラムの変更が少なくなるようにしました。

x = Rx((i-1) / 2)

また、乱数の数列を作る時、最初の説明では、For〜Nextのループを小さい順にループさせましたが、ここでは、

    'ここはランダム数列へ並べ替えをするところ
    For i = 11 To 2 Step -1

と大きい順にしてあります。
これは、乱数を求めるときに、「１からＸまでの乱数」を求める方が楽だからです。
一番最初の例では、「その位置の後ろから３０までの乱数」でしたが、後ろからループさせる事で、「１からその位置の前まで」にする事ができて、プログラムがちょっと簡単になります。

    最初の並べ替えプログラム
        j = Int(Rand() * (30 - i - 1 )) + i + 1

    その４で使った並べ替えプログラム
        j = Int(Rand() * (i-1))+1

一目見ただけで、単純なのがどちらだか、わかるでしょう？
こんな、ホンのちょっとのことですが、繰り返し処理をする場合には、この「ちょっとの差」が重要だったりします。この辺りは、考えた人に脱帽ですね。

さて、予想通りプログラムは今までの中で一番長くなってしまいましたが、実際に、迷路を作っている様子は面白いですね。
そして、その４で完成した迷路は、今までの中で最高の完成度を誇るような気がしませんか？
難易度は、その３とそれほど変わらないといえば変わらないですけど、気分的には違いますね。

　　　　

前へ　　　　　目次へ　　　　　次へ
第13回　考える楽しさ、習う楽しさ「６．迷路を作ろう　その４」