迷路を生成してみよう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)にします。
向きを変えても、自分自身にぶつかってしまう場合は
(昨日の図を参照)、やり直しします。
それらを含めたプログラム例は、また後日。
この記事へのコメントはこちら