« 正20面体の頂点座標の求め方 | メイン | (FreeBSD)かなキー入力をするための設定 »

 8方向に掘り進めて迷路を作ってみる

昔、MSX-FANという雑誌に投稿されていたBASICのプログラムで、壁を8方向に掘り進めて迷路を作り、その一部分が画面に表示された状態でその中をさまようというゲームがあった。

ランダムな迷路を作る方法としては、格子状の壁を4方向に掘り進める方法はすぐに思いつく。既に掘り進めた通路のいずれかの壁をランダムに選び、その壁を取って通路が1マスだけ伸びるならその壁を取り払う(壁の向こうに既に通路があるとループができてしまうため)というのを繰り返せば良いのである。選んだ壁の向こうが未踏の地ならその壁を外す、というのを繰り返すとも言える。
他に、通路が4方向に進む迷路を作る方法としては、「棒倒し法」なる奇妙な方法があるようだが、いたずらに複雑な上にいびつな迷路になるので、取るに足りない。

しかし、雑誌に載っていたプログラムは、迷路を8方向に掘り進めた。そういうことができること自体が私にとっては不思議だった上、そのプログラムは今考えても戦慄が走る「1画面プログラム」すなわち40文字x23行に収まる激短プログラムだった。

プログラムのコードは見えていたのである。大概のプログラムは、手で打ち込んでいる内にどういう仕組みかは理解できた。理解できないのはマシン語が混ざっているものくらいだった。ALL BASICで手で打ち込んで実際に動かしてみてアルゴリズムが理解できなかったプログラムは、そのプログラムくらいしか記憶に無い。
加えて、その作者は当時の私と同じ奈良県民らしかったため、忘れられなかった。

それから約20年、そのプログラムのことを時々思い出しては、頭の中で考えて、その迷路を作る仕組みを不思議に思っていた。

昨日、またふとそのプログラムのことを思い出して、図を描いて考えてみたら、3分でわかった。

テストプログラム(Javaアプレット)の起動ページへ
ソースコード

ついでに自動的に解かせてみた。

要するに、隣り合う斜めの通路が接しないような幅で通路を掘れば良いのである。他に気を付けるのは、斜めのマスに通路を伸ばす時は直交する通路が無いことを確認することくらいで、基本的には4方向に掘り進める場合と同じように方眼のマス目を繋げていけば実現できる。

作図しなかったのが敗因だったようだ。
それでも1画面に収められていた驚異のコードは理解できなかったかも知れないが…

トラックバック

このエントリーのトラックバックURL:
http://ynomura.dip.jp/cgi-bin/mt/mt-tb.cgi/142

コメント投稿フォーム

※投稿されたコメントはオーナーが承認するまで表示されません。


Powered by Movable Type 3.35