壁のばし法で迷路生成してみた

壁のばし法で迷路を生成するコードを書きました。伸ばす先が無くなるまで伸ばす方法と、その前に違う壁を伸ばす方法があるようですが、今回は前者の方法を使いました。以下は迷路生成部分のコードです。

package net.seesaa.nekokiss.algorithm.make_maze.extend_wall; import java.awt.Point; import java.util.ArrayList; import java.util.List; import net.seesaa.nekokiss.util.Xor128; /* 壁伸ばし法で迷路を作るクラス */ public class Maze { static final Xor128 RND = new Xor128(); public final int width; public final int height; public final int size; private final boolean[] walls; // true が壁, false が床 /* width, height は必ず奇数で 5 以上の値にすること 例外処理してないので */ public Maze(int width, int height) { this.width = width; this.height = height; this.size = width * height; this.walls = new boolean[this.size]; } private static final int getRndV(int max) { return RND.next(max); } public final void generate() { // 上辺を壁にする for (int i = 1, max = this.width - 1; i < max; ++i) { this.walls[i] = true; } // 下辺を壁にする for (int i = this.size - this.width + 1, max = this.size - 1; i < max; ++i) { this.walls[i] = true; } // 左辺を壁にする for (int i = 0; i < this.size; i += this.width) { this.walls[i] = true; } // 右辺を壁にする for (int i = this.width - 1; i < this.size; i += this.width) { this.walls[i] = true; } // 始点候補の壁リスト List<Point> sl = new ArrayList<>(); // Startable List for (int x = 2, max = this.width - 1, bottom = this.height - 1; x < max; x += 2) { sl.add(new Point(x, 0)); sl.add(new Point(x, bottom)); } for (int y = 2, max = this.height - 1, right = this.width - 1; y < max; y += 2) { sl.add(new Point(0, y)); sl.add(new Point(right, y)); } // Present Point, Next Point Point pp, np; // cnt は伸ばした回数、max は壁を伸ばすことのできる回数 for (int cnt = 0, max = ((this.width >> 1) - 1) * ((this.height >> 1) - 1); ; ) { // 始点をランダムに選ぶ pp = sl.get(getRndV(sl.size())); // 可能な限り、壁を伸ばし続ける extend: while (true) { if (cnt >= max) { // これ以上壁を伸ばせない場合、終了 return; } // 方向をランダムに選び、時計回りに床かどうか調べる for (int j = 0, k = getRndV(4); j < 4 ; ++j, ++k) { switch (k) { case 0: // North case 4: if (pp.y - 2 < 1) { // 座標外か外壁の場合、他の方向を探す continue; } np = new Point(pp.x, pp.y - 2); if (this.isWall(np)) { // 伸ばす先のマスが壁の場合、他の方向を探す continue; } // 壁を伸ばす this.setWalls(new Point(pp.x, pp.y - 1), np); // 伸ばした先の壁が次の始点になる sl.add(np); pp = np; ++cnt; continue extend; case 1: // East case 5: if (pp.x + 3 >= this.width) { continue; } np = new Point(pp.x + 2, pp.y); if (this.isWall(np)) { continue; } this.setWalls(new Point(pp.x + 1, pp.y), np); sl.add(np); pp = np; ++cnt; continue extend; case 2: // South case 6: if (pp.y + 3 >= this.height) { continue; } np = new Point(pp.x, pp.y + 2); if (this.isWall(np)) { continue; } this.setWalls(new Point(pp.x, pp.y + 1), np); sl.add(np); pp = np; ++cnt; continue extend; case 3: // West case 7: if (pp.x - 2 < 1) { continue; } np = new Point(pp.x - 2, pp.y); if (this.isWall(np)) { continue; } this.setWalls(new Point(pp.x - 1, pp.y), np); sl.add(np); pp = np; ++cnt; continue extend; } break; } // ここに来た時点でこれ以上伸ばせないので、 // 現在の始点を候補から除外 sl.remove(pp); break; } } } public final int getIndex(int x, int y) { return x + y * this.width; } public final int getIndex(Point p) { return p.x + p.y * this.width; } public final boolean isWall(int x, int y) { return this.walls[this.getIndex(x, y)]; } public final boolean isWall(Point p) { return this.walls[this.getIndex(p)]; } public void clearWall(int x, int y) { this.walls[this.getIndex(x, y)] = false; } public void clearWall(Point p) { this.walls[this.getIndex(p)] = false; } public void setWall(int x, int y) { this.walls[this.getIndex(x, y)] = true; } public void setWall(Point p) { this.walls[this.getIndex(p)] = true; } /* 壁を伸ばす過程を利用したい場合、このメソッドを override する 必ず super.setWalls(Point, Point) を呼び出すこと 外壁には使わない */ protected void setWalls(Point p1, Point p2) { this.walls[this.getIndex(p1)] = true; this.walls[this.getIndex(p2)] = true; } }

今回は、コメントも書いて見ました。ここに載せていない GUI 部分には書いてませんが。乱数は XorShift を使っていますが、java 標準の乱数でもいいと思います。

maze150830.zip

実行ファイルとソースファイルが入っています。

続きを読む