プチコン３号　５日目　迷路を作ってみる

前回、背景グラフィックスを描いてスクロールさせてみましたが、今度はこれを応用して迷路を抜けるゲームを何回かかけて作ってみたいと思います。
そこで、まずは迷路を自動生成するプログラムを作ってみました。

迷路の生成アルゴリズムは、いろいろあります。
今回は、そのなかでももっとも単純なものを使いました。

まず部屋が縦横に規則正しく並んでいて、各部屋は「西」と「北」に壁があるものと考えます。
図では、青が西の壁、赤が北の壁です。

次に、各部屋について、西か北、どちらかの壁をランダムに壊します。
ただし、隣に部屋が無い壁は壊すことができません。
すると、たとえば下図のようになります。
これで迷路の出来上がりです。

この方法で作る迷路は欠点があります。
一番上の行は、北の壁が壊せないので常に西の壁が壊されます。
一番左の列は、西の壁が壊せないので常に北の壁が壊されます。
各部屋の北か西の壁を必ず壊さなければならないので、東や南にしか出口のない部屋が作れません。

こういった欠点のない様々な迷路の生成アルゴリズムが考案されています。
興味のある方は、下記のページをごらんください。
英語ですが、動作するサンプルが豊富で楽しめます。

"Algorithm" is Not a Four-Letter Word

さて、上記のアルゴリズムをBASICで書いてみました。
表示部分も含めて何とか１画面に納まりました。

M_W=49:M_H=24
DIM R[M_W+2,M_H+2]
FOR J=0 TO M_H+1
FOR I=0 TO M_W+1
IF I==0 OR I==M_W+1 OR J==0 OR J==M_H+1 THEN
R[I,J]=0
ELSE
R[I,J]=3
ENDIF
NEXT
NEXT
FOR J=1 TO M_H
FOR I=1 TO M_W
R_N=R[I,J-1]
R_W=R[I-1,J]
IF R_N==0 AND R_W>0 THEN R[I,J]=1
IF R_N>0 AND R_W==0 THEN R[I,J]=2
IF R_N>0 AND R_W>0 THEN R[I,J]=1+RND(2)
NEXT
NEXT
FOR J=1 TO M_H
FOR I=1 TO M_W
IF R[I,J]==3 THEN PRINT "┌";
IF R[I,J]==2 THEN PRINT "─";
IF R[I,J]==1 THEN PRINT "│";
NEXT
PRINT "│"
NEXT
PRINT "─"*M_W

まず、ずっと飛ばして最後のFOR～NEXTループを見てください。
これは迷路の画面表示部分です。
壁の有無について、以下のように数字を割り当てました。
・北、西に壁：３
・北に壁：２
・西に壁：１
FOR～NEXTループでは、この数字に従って罫線を１文字出力しています。
なお、罫線は記号入力モードで入力できます。記号入力モードにするには、EDITボタンの上のハートマークのキーを押します。

部屋の状態は、上記の３つの数に加えて
・部屋がない：０
という数値も割り当てます。
数値０の部屋を、迷路を取り囲むように配置します。

すると、初期状態（全部の部屋の北・西の壁がある状態）は下図のようになります。（迷路のサイズは５×５にしています。）

それでは、プログラムの最初から説明していきます。
先頭部分、M_HとM_Wが迷路（Maze）の大きさです。
M_Hが縦の大きさ（Height）、M_Wが横の大きさ（Width）を表します。
今回は、プチコンの画面サイズが50文字×30行なので、それより小さくしています。
次に、迷路の部屋を現す配列を宣言しています。
サイズが「M_W+2,M_H+2」となっているのは、迷路の周囲を取り囲む「０」の部屋の分を含めているためです。

続いて、配列を初期状態にします。配列と迷路の部屋との対応は下図のようになっています。

一番上の行（J==0）と一番下の行（J==M_H+1）、一番左の列（I==0）と一番右の列（I==M_H+1）は０、それ以外は３にします。

FOR J=0 TO M_H+1
FOR I=0 TO M_W+1
IF I==0 OR I==M_W+1 OR J==0 OR J==M_H+1 THEN
R[I,J]=0
ELSE
R[I,J]=3
ENDIF
NEXT
NEXT

次に、「０」の部屋以外の各部屋について、北の壁と西の壁のどちらかを消します。
実際には、配列の要素の値を１または２にしていきます。

R_N=R[I,J-1]
R_W=R[I-1,J]
IF R_N==0 AND R_W>0 THEN R[I,J]=1
IF R_N>0 AND R_W==0 THEN R[I,J]=2
IF R_N>0 AND R_W>0 THEN R[I,J]=1+RND(2)

R_Nは部屋の北隣の部屋の状態、R_Wは部屋の西隣の部屋の状態です。

北隣が０で西隣が０以外なら、西の壁を壊します。（北の壁がある状態＝１）
西隣が０で北隣が０以外なら、北の壁を壊します。（西の壁がある状態＝２）
両方とも０以外の場合は、状態１と状態２のどちらかをランダムに選びます。
RND(2)は0以上2未満の整数をランダムに返しますので、1+RND(2)で1か2のどちらかの値になります。

以上で迷路ができました。
表示部分は最初に解説しましたので、プログラムはこれで終わりです。

次は、キャラクターを操作して迷路を抜けるプログラムを作りたいと思います。