迷路を生成してみよう2

 

アルゴリズム(処理の流れ)を文字で書くのは難しく
また、それを読んでも理解しにくいものです。

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

昨日は、長々と迷路の生成方法(アルゴリズム)の説明を
書いたのですが、「さっぱりわからん」と感じた方も多いことでしょう m(_ _)m

実際に単純な処理から作ってみて、不都合が生じた部分を改良する
というアプローチの方が分かりやすいかもしれません。
という訳で、まずは単純な方法(アルゴリズム)で作ってみましょう。

import java.util.Random;

public class MazeT0 {
	Random rnd;
	int xt,yt,xn,yn;
	int [][]mz;

/* 横11列, 縦9行の場合
 ■ 01 ■ ■ ■ ■ ■ ■ ■ ■ ■
 ■ 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 ■
 ■ ■ ■ ■ ■ ■ ■ ■ ■ 89 ■
 */
	final int unset=0, wall=1;

	MazeT0(){ // constructor
		rnd=new Random();
	}

	void generate(int ynn, int xnn){
		xt=xnn; yt=ynn;
		xn=xt*2+3;
		yn=yt*2+3;
		mz=new int[yn][xn];
		for (int x=0;x<xn;++x) {
			mz[0][x]=mz[yn-1][x]=wall; // 外枠 上辺と下辺
		}
		for (int y=1;y<(yn-1);++y) {
			// Arrays.fill(mz[y],unset);
			mz[y][0]=mz[y][xn-1]=wall; // 外枠 左辺と右辺
		}

		for (int j=0;j<yt;++j){ // 各格子点から
			int y=j*2+2;
			for (int i=0;i<xt;++i){
				int x=i*2+2;
				trace(y,x); // 壁を伸ばしてゆく
			}
		}
		mz[0][1]=mz[yn-1][xn-2]=unset; // 入り口と出口をあける
		dispmz(mz); // 表示
	}

	void trace(int yy,int xx) {
		// 乱数で方向を決めて、中間点を描画するだけの不完全版
		// このロジックでは外壁につながらない「島」ができる
		int dx,dy;
		while (mz[yy][xx]==unset) {
			mz[yy][xx]=wall; // 格子点描画

			dx=dy=0;
			int dir=rnd.nextInt(4); // 伸ばす方向を乱数で決める
			if (dir==0) dy=-1; // 上へ
			else if (dir==1) dx=1; // 右へ
			else if (dir==2) dy=1; // 下へ
			else dx=-1; // 左へ

			xx+=dx; yy+=dy;
			mz[yy][xx]=wall; // 中間点描画
			xx+=dx; yy+=dy; // 次の格子点
		}
	}

	void dispmz(int [][]zz){
		for (int y=0;y<yn;++y) {
			for (int x=0;x<xn;++x) {
				if (zz[y][x]==wall) System.out.print("■");  // 壁
				else System.out.print(" ");  // 通路
			}
			System.out.println();
		}
	}
	public static void main(String[] args) {
		MazeT0 mt=new MazeT0();
		mt.generate(3,4);
	}
}

格子点から乱数で決めた方向に壁を伸ばすという処理です。
これを実行すると、例えば次のような結果が得られます。

■ ■■■■■■■■■
■         ■
■ ■■■■■■■ ■
■ ■     ■ ■
■ ■ ■■■ ■ ■
■   ■     ■
■ ■■■ ■ ■■■
■ ■   ■   ■
■■■■■■■■■ ■

外壁に接していない壁(島)ができてしまっています。
乱数で決めた方向が、伸ばしてきた元側(つまりバックする方向)
になったら、伸ばすのを中止するからです。
また、運が悪いとループ(輪)ができることもあります。

この対処をするには、描画済みの壁(wall)と、伸ばしている壁を
区別できるようにしなければなりません。そして、伸ばしている壁
(自分自身)に接続しそうになったら、向きを変えるようにします。

具体的には、上記のtrace()メソッドの while ループを
次のような感じにします。

while (mz[yy][xx]==unset) {
	mz[yy][xx]=making; // 格子点描画

	dx=dy=0;
	int dir=rnd.nextInt(4); // 伸ばす方向を乱数で決める
	if (dir==0) dy=-1; // 上へ
	else if (dir==1) dx=1; // 右へ
	else if (dir==2) dy=1; // 下へ
	else dx=-1; // 左へ

	if (mz[yy+dy+dy][xx+dx+dx]==making) { // 描画中の自分に接するなら
								// 方向を変える
		for (int t=1;t<4;++t) {
			int t2=(dir+t)%4;
			dx=dy=0;

			if (t2==0) dy=-1; // 上へ
			else if (t2==1) dx=1; // 右へ
			else if (t2==2) dy=1; // 下へ
			else dx=-1; // 左へ

			if (mz[yy+dy+dy][xx+dx+dx]!=making) { // 2つ先が自分ではなければ
				break; // for
			}
		}// end for t
	}// endif mz[][]==1 伸ばした先が自分の軌跡だった時の処理はここまで

そして、壁を伸ばし終わったら making(2) を wall(1)にします。

向きを変えても、自分自身にぶつかってしまう場合は
(昨日の図を参照)、やり直しします。

それらを含めたプログラム例は、また後日。

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

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

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