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

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

「その１」では「あきらめも肝心」ということを学びましたが、実は、迷路を作る上で重要なヒントも隠されていました。
それは

縦横が共に奇数の位置には、必ずブロックがある

ということです。
その１でも登場しましたが、下の図のような状態では迷路にはなりませんが、ここから発展して完成する予定の迷路は、すべてこの状態への上書きになります。

　　　　

今後は、この点を「基点」と呼ぶことにしましょう。そうすると、完成した迷路上の壁は、すべての「基点」を含んでいる、と言い換えることができます。

さて、ここで、１つの基点に注目してみましょう。とりあえず、左上の基点(3,3)です。

　　　　

そこから、ランダムに上下左右の注目すべき位置を決めます。例えば「右」としましょう。
基点(3,3)から、右隣にある基点を考えます。これは、基点(5,3)ですが、この位置には、ブロックはまだ置かれていません。
そういう場合、その基点(5,3)との間の(4,3)の位置にブロックを置き、注目する位置を基点(5,3)に移します。

　　　　

次に移動した先の基点(5,3)から同様にランダムに上下左右の位置を決めます。次は「下」にします。
すると、下方向の隣にある基点(5,5)には、やはりまだブロックがありませんから、基点(5,5)との間の(5,4)にブロックを置き、注目を基点(5,5)に移します。
再び、ランダムで方向を選びますが、ここで「上」だとしましょう。
そうすると、上方向の基点(5,3)は既にブロックが置かれていますので、この時点で基点(3,3)から始まる一連の旅は終了です。

　　　　

次に、基点を(3,5)に移して、同様に続けます。

　　　　

基点(3,5)から、ランダムに決めたのが「左」だとします。すると、そこは外壁ですから、外壁(1,5)と間の(2,5)にブロックを置いて、ここの検索は終わりにします。

　　　　

このように、存在するすべての基点を、同様に処理をすれば、迷路が完成することになります。
この方法は、ブロックをフラフラと歩くように検索しますから、ランダムウォークなどと言うこともあります。
なんだか、「その１」に比べて、一気に難しくなったような気がしますが、こういうときのためにフローチャートを活用しましょう。

さて、存在する基点を全部調べますから、何らかの繰り返し処理が必要ですね。
基点は縦と横の座標がありますので、全体の大きなイメージは、こんな感じになります。

　　　　

この２重のループの中で、順に基点を調べていくわけですが、もし、注目した基点に既にブロックが置かれていたら、そこは無視してもよいですね。
したがって、注目すべき基点にブロックがないときだけ検索の処理を行います。
まず、検索処理の最初は、その基点にブロックを置くことです。

　　　　

そして、ブロックを置いたら、上下左右の注目すべき方向を乱数で決めます。
決まったら、その方向で隣にある基点をチェックします。

　　　　

注目した隣の基点にブロックが置かれていない状態、つまり、外壁か何もない状態だったら、ブロックを描く処理を行う必要があります。
ブロックを描く場合は、まず、基点のすぐ隣にブロックを描きます。
次に、その隣の基点に何もなければ、その位置を新しい基点にして検索処理を繰り返します。
一方、その隣の基点が外壁だったら、もうブロックを描く必要はありませんので、この基点からの検索は終わりです。
もちろん、最初に注目した時点で、隣の基点にブロックがあった場合も、検索終了ですね。

　　　　

言葉で書くとややこしいですが、フローチャートにまとめると、スッキリしますね。

　　　　

実際に、これをプログラミングしてみると、

    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
    
    '迷路の初期化
    Call init_maze()

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

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

                    '注目する方向をランダムで決める
                    H = Int(Rand()* 4)
                    
                    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

                    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

長いですが、フローチャートを見ながら解読してみてください。それほど難しくないと思います。

この考え方で作った迷路は、例えば、こんなモノができます。

　　　　

いかがでしょう？一気に迷路らしくなってきましたね。これだと、並みの方向音痴でなくても、迷ってしまうのではないでしょうか？
そして、このように、考え方を改良して迷路らしくなったときには感動モノでしょう。さて、感動の余韻を味わいながら更に上を目指すことにしましょう。

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