MAZE・迷路
最終更新日:08.12.27


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

		maze_init();

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

	}

これが迷路を作成するプログラムの全体像です。
Cで書いたもので、やっていることは、初期設定を行うファンクションであるmaze_init()をコールした後、 全ての(偶数, 偶数)のポイント(x, y)を、左上から順に起点として、maze_sub(x, y)をコールしています。
以下、maze_init()、maze_sub()の中身について、説明します。


■初期状態の作成:maze_init()
スタート状態 道を延ばしてつくる迷路の初期状態は、右の図の様に、最外周を全て道、そして、その中を最初の起点(このケースでは(2, 2))を除いて全て壁とした状態で始まります。

最外周を道としているのは、maze_sub()内での処理で、延ばしていく道が迷路の外へ飛び出して行かない様な監視を容易に行う、ちょっとしたテクニックです。 この枠無しでやってみるとかんりめんどうになり、このありがたさを実感することができます。

また、迷路中の1点(このケースでは(2, 2))の道は、道から道を延ばすアルゴリズムにより、完成した迷路中の全ての道がこの1点とつながることになります。


■(x, y)を起点とした動作:maze_sub(x, y)
フロー このアルゴリズムでは、必ず既に道であるポイントから道を延ばして行きます。 従って、(x, y)が道で無いときには、何もせずにこの処理を終了します。 このルールを無視すると、スタートとゴールがつながっていない様な迷路になってしまいますので、注意が必要です。

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

まず、上下左右の中から、道を延ばしていく方向をランダムに選びます。進行方向は、(px, py)で表すこととします。 このとき、上は(0, -1)、右は(1, 0)、下は(0, 1)、左は(-1, 0)になります。 方向が選択されたら、その方向の次の(偶数, 偶数)のポイント、すなわち(x1+px*2, y1+py*2)の状態をチェックします。
壁(kWall)であれば、(x1+px, y1+py)、(x1+px*2, y1+py*2)を道とし、起点(x1, y1)を(x1+px*2, y1+py*2)に移動して、 ランダムに進行方向を選択するところから繰り返します。
道(kRoad)であったときは、その方向へ延ばしていくことができないため、方向を選び直します。 4方向全てをむら無くチェックする必要があるため、ここでは、方向を回転させることで、新たな方向を選ぶ方法をとります。 すなわち、その時の進行方向が上の時は右を選択、右の時は下を選択、下の時は左を選択、左の時は上を選択といった具合です。 4方向全てをチェックしても進める方向が無いとき、すなわち道で囲まれて行き止まりとなったとき、maze_sub()の処理を終了します。

こうして、道となるべき全ての点に対して、maze_main()からコールされることで、迷路が完成します。
なお、実際に作ってみるとわかることですが、(x, y)を起点に道を延ばそうとしたときに、そこがまだ道になっていなかったときには、 そこから道を延ばすことができないため、このアルゴリズムでは、迷路が完成した時に(偶数, 偶数)の点でも道になっていないことがあります。


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