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

13−３　迷路を作ろう　その１

さて、長い前置きでしたが、やっと本題の迷路を考えることにしましょう。
とはいえ、唐突に、何をどうやって考えてよいのかわかりませんよね。
そもそも、

迷路が迷路になりうるのは、何故？

ということを考えてみようとしても、なかなかすっきりした答えにたどり着けません。
まぁ、とりあえず、そういう時は、逆に考えてみましょう。

迷路に「ならない」場合は、どういう場合だろう？

ということです。
このことを考えてみると、下の図のように、単にブロックが並んでいるだけだと、迷路にならないことがわかります。
（ただし、極端な方向音痴だと、迷うかもしれませんが）

　　　　

次に、この空いている部分に適当にブロックを入れたら、迷路になるんじゃないかな、と考えてみました。

　　　　

何とか、迷路になりそうですね。安直ですが、この考え方で作ってみましょう。

先ほど考えた手順どおり、まず、迷路にならない状態を作ってみます。
これは、図で明らかなように、座標が奇数の部分にブロックを置けばよさそうです。

　　　　

外壁はブロックですから、実際の最も左上のブロックは(3,3)、右下は(23,23)ですね。
したがって、これらのブロックを置くプログラムは、For〜Nextを使って次のようになります。

    Dim x as Integer
    Dim y as Integer
    
    Call init_maze()
    
    For y=3 to 23 step 2
        For x=3 to 23 step 2
            Call Put_Block(x,y)
        Next
    Next

さて、この状態にブロックを置いて迷路を作る場合、置いてよい場所と、そうでない場所がある事に気付きます。

　　　　

この色分けした図でもわかるように、赤い部分に置くと、通路を不自然にふさいでしまうので、これは禁則とすべきでしょう。
交差点の真中に、唐突にブロックがあっても、仕方ないですからね。
各座標の偶数・奇数に注目してまとめると、こんな表ができます。

　横座標
偶数奇数
　縦　
座
標		偶数×○
奇数○○

この表から、縦と横、少なくともどちらか一方が奇数であればブロックとして置いてもよさそうです。
つまり両方とも偶数の場所には、置いてはいけない、ということです。
ある数字が偶数か奇数かを判別する方法ですが、これは簡単です。２で割った余りが１なら奇数、０なら偶数です。
NS Basicでは Mod()という関数で余りを求めることができ、Ｎを２で割った余りは、Mod(N,2)で求めることができます。
（※ＶＢなどでは、N mod 2 求めることができますので、こちらは『演算子』の扱いになりますね。）

プログラムは、とりあえずシンプルにブロックを置くようにしてみました。

    Dim x as Integer
    Dim y as Integer
    Dim i as Integer
    
    Call init_maze()
    
    For y=3 to 23 step 2
        For x=3 to 23 step 2
            Call Put_Block(x,y)
        Next
    Next

    For i=0 to 100
        x=rand()*22+3
        y=rand()*22+3
        If mod(x,2)=1 Or mod(y,2)=1 Then
            Call Put_Block(x,y)
        End If
    Next

様子を見るために100回のループにしましたが、これでも一通りの迷路らしいものができるようです。
（あ、正確には、101回のループですね。）

　　　　

さて、この方法からブロック置く位置の重複を除外するなど、もう少し発展させれば、完成度の高い迷路ができるかと思います。
しかしその「もう少し」が難しそうなのです。
何度か迷路を作っていて気づいたのですが、たまに、こういう状態が出来てしまいました。

　　　　

この行き詰まった所ができないようにするためには、ブロックを置く前に、何らかのチェックをしなければなりません。
しかし、ちょっと考えてみても、その方法は簡単ではなさそうです。
もしかしたら、スタートからゴールまでの道が寸断される場所にブロックが置かれてしまう可能性もあるでしょう。
ということで、この考え方はあっさり捨てて、別の方法を考えることにしましょう。
ここで苦労をするより、まずは、他の方法を模索した方がよさそうです。やはり、人間、あきらめることも肝心です。

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