迷路を生成してみよう1

 

座標を表すのに横をx, 縦をy、ペアで(x,y)と書いたりしますが
2次元配列の場合に、dat[x][y] とするか dat[y][x]とするか
悩ましく思ったりしませんか?

毎度、管理人イガジーです。

2次元配列では、右側の添字の方が先に変化するイメージなので、
##############################
# 11 12 13 14 15 16 17 18 19 #
# 21 [] 23 [] 25 [] 27 [] 29 #
# 31 32 33 34 35 36 37 38 39 #
# 41 [] 43 [] 45 [] 47 [] 49 #
# 51 52 53 54 55 56 57 58 59 #
# 61 [] 63 [] 65 [] 67 [] 69 #
# 71 72 73 74 75 76 77 78 79 #
##############################

のように、dat[y][x] の方が自然に思えるのです。

さて、上の図は迷路データの持ち方を表す例なのですが
迷路の生成方法にはいくつかのアルゴリズムがあります。

その1つに、22, 24, 26, 28, 42, 44, …. に相当する[]を「格子点」とし
そこからランダムな方向(上下左右)に線(壁)を伸ばし、
大外の#(外壁) に到着したら終わりとする。という方法があります。

このデータの持ち方では、2つ単位で伸ばします。
例えば、46から上に伸ばす場合は、36, 26 の2つ伸ばします。
続いて26から右に伸ばす場合は、27, 28 の2つです。

伸ばす際には、伸ばしてきた自分自身の軌跡にはつながないように
しなければなりません。つないでしまうと、輪ができてしまい、
その中には入れなくなるからです。

次の図の様に●から伸ばして行き、運悪く★に来てしまった時は
自分自身にしか行き場が無いので、やり直ししなければなりません。

■ ■■■■■■■■
■         
■ ●   ■■■ 
■ ■   ■ ■ 
■ ■ ■■■ ■ 
■ ■ ■   ■ 
■ ■ ★ ■■■
■ ■   ■
■ ■■■■■
■

格子点の斜め方向(例えば、11,13,31,33 など)は、必ず空き(通路)
になるので無駄と言えば無駄ですが、気にしないことにします。

実際のプログラム例は、後日。

この記事へのコメントはこちら

メールアドレスは公開されませんのでご安心ください。
また、* が付いている欄は必須項目となりますので、必ずご記入をお願いします。

内容に問題なければ、下記の「コメント送信」ボタンを押してください。