MAZE・迷路
最終更新日:08.12.27


第三章 「壁を延ばして迷路を作る」
■基本構成
	void maze_main( void )
	{
		short		x, y;

		maze_init();

		for (x = 3; x < gSizeX-3; x += 2)
			for (y = 3; y < gSizeY-3; y += 2)
				maze_sub(x, y);

	}

これが迷路を作成するプログラムの全体像です。
全体の流れとしては、道を延ばす迷路とほぼ同じですが、起点の取り方が、道を延ばす迷路では(偶数, 偶数)だったのに対し、こちらでは(奇数, 奇数)になっています。
以下、maze_init()、maze_sub()の中身について、説明します。


■初期状態の作成:maze_init()
スタート状態 壁を延ばしてつくる迷路の初期状態は、右の図の様に、外周を壁とした状態で始まります。
更にその外周が右の図では道となっていますが、これは道を延ばす迷路と共用化させるためだけのものです。 このアルゴリズムで考える時には不要なものですので、全体の動作が理解できたら、メモリ節約の為にも、削除に挑戦してみて下さい。


■(x, y)を起点とした動作:maze_sub(x, y)
フロー こちらのアルゴリズムでも、道であるところから壁を延ばして行きます。 ただ、チェックしている点が本来壁になるべき点なのか、道になるべき点なのかが先ほどのアルゴリズムと違っていますので、意味あいは全く違っています。 このアルゴリズムにより、まず(x, y)が道で無いときには、何もせずにこの処理を終了します。

道(kRoad)であった時は、x1 = x, y1 = yとし、(x1, y1)をこの関数内での起点とします。
以後、(x1, y1)を移動させながら、迷路を作っていきます。

まず、上下左右の中から、ランダムに壁(作りかけの壁:kPreWall)を延ばしていく方向(px, py)を選びます。 そして、その方向の次の(奇数, 奇数)のポイント、すなわち(x1+px*2, y1+py*2)の状態をチェックします。
道(kRoad)であれば、(x1+px, y1+py)、(x1+px*2, y1+py*2)を作りかけの壁(kPreWall)とし、起点(x1, y1)を(x1+px*2, y1+py*2)に移動して、 ランダムに進行方向を選択するところから繰り返します。
壁(kWall)であったときは、めでたしめでたし、その壁とこれまで延ばしてきた壁をつなげると共に、 作りかけの壁としてこれまで区別してきた壁を、既成の壁とします。
それ以外、すなわち作りかけの壁(kPreWall)であったときは、そちらへ延ばすことができませんので、方向を選び直します。やはり、 4方向全てをむら無くチェックする必要があるため、方向を回転させることで、新たな方向を選ぶ方法をとります。 4方向全てをチェックしても進める方向が無いとき、すなわち作りかけの壁で囲まれて行き止まりとなったとき、これまで延ばしてきた作りかけの壁を元の状態、 すなわち道に戻し、x1 = x, y1 = yとして、maze_sub()をはじめからやり直します。

こうして、壁となるべき全ての点に対して、maze_main()からコールされることで、迷路が完成します。


| HOME | MAZE・迷路 | 迷路 第四章 |
E-MAIL:aanda@nifty.com(AKIO HOSOKAWA)