初投稿です！！
こんな迷路ができました。
作ろうと思ったきっかけ
以前にHTML5とJSで、棒倒し法を使った迷路ゲームをつくって文化祭に出展したことがありました。
しかし、棒倒し法で作った迷路は解がとても単純になってしまうため、解が複雑な穴掘り法でやってみたいと思ったからです。
穴掘り法って？
■すごくざっくり言うと穴掘り法はこんなアルゴリズム (もしかしたら間違っているかも
)
縦、横共に大きさが5以上で奇数の大きさのマップを作成する。
すべて壁で埋める
マップの端っこ以外で、X座標、Y座標が共に奇数の場所を無作為に選び、穴を開ける。
★端っこ以外で、X,Y座標が奇数で(今回は左上端を0,0とする)、まだ壁が残っているところがあるか確かめる
あったら：マップの端っこ以外で、X座標、Y座標が共に奇数の場所ですでに穴が開いているところを無作為に選ぶ。
| 四方の2マス先にまだ壁が残っているところがあるか確かめる
| あったら：掘れる方向中からランダムにまっすぐ2マス掘る
| なかったら：★に戻る
なかったら：迷路完成
……ですが、こんな素直に実装するのは難しいので、いろいろ工夫してやっていきます。
中身
メインのクラス
MainClass.java
package automaze;
public class MainClass {
public static void main(String[] args) {
Maze maze=new Maze(21,21);//今回は試しに21×21の迷路を作る。
maze.show();
}
}
Mazeクラス
Maze.java
package automaze;
public class Maze {
private int pointX; //ブロックを置いたり消したりする目印。
private int pointY;
private int width; //横幅と高さ。
private int height;
private byte[][] map; //マップを格納する配列
public Maze(int w, int h) { //コンストラクター
width = w;
height = h;
if (w % 2 != 0 && h % 2 != 0 && 5 <= w && 5 <= h) {
map = new byte[width][height];
make();
} else {
System.out.println("縦・横共に5以上の奇数で作成してください。");
}
}
int randomPos(int muki) { //x,y座標共に奇数なランダムな座標を返す
int result = 1 + 2 * (int) Math.floor((Math.random() * (muki - 1)) / 2);
return result;
}
private void make() { //マップを作成する
pointX = randomPos(width);
pointY = randomPos(height);
for (int y = 0; y < height; y++) { //すべて壁で埋める。
for (int x = 0; x < width; x++) {
map[x][y] = 1;
}
}
map[pointX][pointY] = 0;
dig();
}
private void dig() {
if (isAbleContinueDig() && map[pointX][pointY] == 0) {
map[pointX][pointY] = 0;
int direction = (int) Math.floor(Math.random() * 4);
switch (direction) {
case 0:
if (pointY != 1) {
if (map[pointX][pointY - 2] == 1) {
map[pointX][pointY - 1] = 0;
pointY -= 2;
break;//u
}
}
case 1:
if (pointY != height - 2) {
if (map[pointX][pointY + 2] == 1) {
map[pointX][pointY + 1] = 0;
pointY += 2;
break;//d
}
}
case 2:
if (pointX != 1) {
if (map[pointX - 2][pointY] == 1) {
map[pointX - 1][pointY] = 0;
pointX -= 2;
break;//l
}
}
case 3:
if (pointX != width - 2) {
if (map[pointX + 2][pointY] == 1) {
map[pointX + 1][pointY] = 0;
pointX += 2;
break;//r
}
}
}
map[pointX][pointY] = 0;
dig();
} else if (isAbleDig()) {
pointX = randomPos(width);
pointY = randomPos(height);
dig();
}
}
private boolean isAbleDig() { //まだ掘るところがあるか確かめる
boolean result;
int cnt = 0;
for (int y = 0; y < height; y++) {
for (int x = 0; x < width; x++) {
if (x % 2 != 0 && y % 2 != 0) {
if (map[x][y] != 0) {
cnt++;
}
}
}
}
if (cnt == 0) {
result = false;
} else {
result = true;
}
return result;
}
private boolean isAbleContinueDig() {//四方に掘れるところが残っているかどうか判断する
if (pointY != 1) {
if (map[pointX][pointY - 2] == 1) {
return true;
}
}
if (pointY != height - 2) {
if (map[pointX][pointY + 2] == 1) {
return true;
}
}
if (pointX != 1) {
if (map[pointX - 2][pointY] == 1) {
return true;
}
}
if (pointX != width - 2) {
if (map[pointX + 2][pointY] == 1) {
return true;
}
}
return false;
}
public void show() {
for (int y = 0; y < map[0].length; y++) {
System.out.println("");
for (int x = 0; x <map.length; x++) {
if (map[x][y] == 1) {
System.out.print("##");
} else {
System.out.print(" ");
}
}
}
}
public byte[][] getMaze() {
return map;
}
}
完成して気づいたこと
もうちょっと短くできないかなぁ、と思っています。
あと、掘る関数を再帰的に呼び出してるのが原因か、ちょっと大きい迷路を作ろうとしただけでstackoverflowerrorを吐きます。
直し次第この記事も編集します。while文を使ったら何とかなりそう……、とぼんやり思っています。
気が向いたらやるかもしれないこと
- スタート・ゴールを自動で設置
- 最短経路を求める
- ゲームとしてプレイできるようにする。
私の環境
OS ：Windows10
IDE：Eclipse 2020-03