Help us understand the problem. What is going on with this article?

Javaで穴掘り法の迷路作成を実装してみた。

More than 3 years have passed since last update.

忘備録程度にQiitaはじめます。

なんとなくロマン

 迷路作成って興味ありますよね。ないですか?
 アルゴリズムに基づいて迷路を作れるとか何でもできそうな気がしてきます。
 以前から迷路ってどうやって作るんだろうという疑問があり、方法を見て作ってみました。

穴掘り法

 今回は穴掘り法というもので作ってます。棒倒し法よりも人間らしい迷路が作れるとか。
 方法としては、以下のような流れで作ってます。

1.奇数×奇数のマップを作成。
2.自分の位置(偶数)を決めてまずそこを穴掘り。
3.ランダムに進む方向を決める。
4.進む方向2マス先が迷路の枠、もしくは外じゃないとき、2マス(重要)穴掘り。
5.3~4を再帰的に繰り返す。

 こんな感じです。簡単ですね。
 参考にしていたところでは1時間で簡単に実装できると書いてありました。アルゴリズムも複雑じゃないしできる人はぱぱっと作れるんでしょうね。
 穴掘り法によるダンジョンの自動生成 (Unity2Dのサンプルコードつき)

 ちなみに西森は半日かかりました。

 以下サンプルコードです。

Maze.java
package komari.kamikita;

import java.util.ArrayList;
import java.util.Collections;


/**
 * ファイル名:Maze.java
 * 迷宮のマップを穴掘り法で作成するプログラムです。
 * @author 西森無理
 */
public class Maze {
    // 迷宮の高さと幅。奇数じゃないといけないらしい。
    static final int height = 55, width = 59;

    public static void main(String[] args){
        // 迷宮のマップを格納する配列。
        int[][] maze = new int[height][width];

        // 迷宮で初めに穴を掘る場所。これは偶数でなければならないらしい。
        int row = maze.length / 2, col = maze[0].length / 2;

        // 初期位置の壁を掘る。
        maze[row][col] = 1;

        // 進む方向を格納するリスト。Collectionでシャッフルしたかったのでリストにしました。
        ArrayList<Integer> direction = new ArrayList<Integer>();

        // 0~3がそれぞれ東西南北に該当。
        direction.add(0);
        direction.add(1);
        direction.add(2);
        direction.add(3);

        // 再帰的に迷宮のマップを作成。
        createRoute(maze, row, col, direction);

        // 迷宮を出力。
        outputMaze(maze);
    }

    /**
     * 再帰的にマップを掘り進んでいきます。
     * 
     * @param maze
     *            迷宮のマップ
     * @param row
     *            マップの行
     * @param col
     *            マップの列
     * @param direction
     *            進む方向
     */
    public static void createRoute(int[][] maze, int row, int col, ArrayList<Integer> direction) {
        Collections.shuffle(direction);

        // ランダムに方向を見て、進める方向に2マス壁を掘る。
        for (int i = 0; i < direction.size(); i++) {
            if (canCreate(maze, direction.get(i), row, col)) {
                switch (direction.get(i)) {
                case 0:
                    maze[row][col - 1] = 1;
                    maze[row][col - 2] = 1;
                    col = col - 2;
                    break;
                case 1:
                    maze[row][col + 1] = 1;
                    maze[row][col + 2] = 1;
                    col = col + 2;
                    break;
                case 2:
                    maze[row + 1][col] = 1;
                    maze[row + 2][col] = 1;
                    row = row + 2;
                    break;
                case 3:
                    maze[row - 1][col] = 1;
                    maze[row - 2][col] = 1;
                    row = row - 2;
                    break;
                default:
                    break;
                }

                direction.add(0);
                direction.add(1);
                direction.add(2);
                direction.add(3);

                createRoute(maze, row, col, direction);
            }
        }
    }

    /**
     * 進む方向を見て、そちらが進めるかどうかを判定します。
     * 
     * @param maze
     *            迷宮のマップ
     * @param direction
     *            進む方向
     * @param row
     *            マップの行
     * @param col
     *            マップの列
     * @return 進めるとき1、進めないとき0
     */
    static boolean canCreate(int[][] maze, int direction, int row, int col) {
        switch (direction) {
        case 0:
            if (col - 2 <= 0) {
                return false;
            } else {
                if (maze[row][col - 2] == 0) {
                    return true;
                } else {
                    return false;
                }
            }
        case 1:
            if (col + 2 >= maze[0].length - 1) {
                return false;
            } else {
                if (maze[row][col + 2] == 0) {
                    return true;
                } else {
                    return false;
                }
            }
        case 2:
            if (row + 2 >= maze.length - 1) {
                return false;
            } else {
                if (maze[row + 2][col] == 0) {
                    return true;
                } else {
                    return false;
                }
            }
        case 3:
            if (row - 2 <= 0) {
                return false;
            } else {
                if (maze[row - 2][col] == 0) {
                    return true;
                } else {
                    return false;
                }
            }
        default:
        }
        return false;
    }

    /**
     * マップを出力します。
     * 
     * @param maze
     */
    public static void outputMaze(int[][] maze) {
        for (int i = 0; i < maze.length; i++) {
            for (int j = 0; j < maze[i].length; j++) {
                if (maze[i][j] == 0) {
                    System.out.print("■");
                } else {
                    System.out.print(" ");
                }
            }
            System.out.println();
        }
    }
}

 

出来上がり

ちなみに出来上がった迷路はこんな感じです。きれい。
 キャプチャaaaa.JPG

作り終わってみて

 コード自体は今見返すとかなり冗長な気がします。
 アルゴリズム見て簡単に作れるだろと思ってカタカタ始めたら案外はまりました。
 2マス一度に掘るっていうのにピンと来ずにそこではまってました。確かに1マスだけ掘ってたら風来のシレンのアリみたいな掘り方だってできるわけです。
 何回も大部屋がぽかーんと空く迷路見てて虚しくなりました。

 あとコードにバグがあるのでそれが一番の課題ですかね……。
 マップを奇数×奇数にしても外側の余白がおかしくなるときが……。

 ほかにも壁のばし法やクラスタリング法などあるみたいです。クラスタリング法は一度実践してみたい気もします。

バグについて(5/1追記)

 このコード自体に2つのバグがあることをここに報告します。
 まず1つめは、ランダム変数のリストを使いまわしていることです。再帰関数に参照を渡しており、なおかつそのあとにリストをシャッフルするので、穴が掘れた場所を見ない可能性が出てきます。
 さらに具合の悪いことに、再帰関数内でリストに値をaddしています。これをすれば方向を見ないことがなくなりますが、関数が深くなるにつれて同じ方向を何回も見ることに……。リストも増えていくので合理的ではありませんね。

 2つめは、位置設定です。参考元の記事では偶数位置で良かったのですが、このコードだと外側の枠を残すため、奇数位置に設定する必要があります。

 というバグを踏まえて、shiracamusさんが2通りのやり方でコードを実装してくれました(コメントを参照)。ありがとうございます。これ初めてコメントをいただいてから4時間程度で完成してます。純粋にすごい。

 まだ実を言うとコードを見切れていない(というより新しい概念に頭が追い付いていない)ので、これはどういう意味なんだ、というのを備忘録にして書こうと思います。
 qiitaのつながりすごい、改めてそう思った。

さらなるバグについて(5/3追記)

 アルゴリズムとして間違っているバグがあったので報告します。
 このコードでは再帰関数で自分の居場所(rowとcol)のみで居場所を決めていますが、そうしてしまうと各再帰関数で元いた場所が失われてしまうというバグがありました。
 こちらに関してもshiracamusさんが訂正をしてくださいました。本当にありがとうございます……。
 バグのコードは戒めとしてあえて残しておくので、ただしく動かしたい方はコメントの14番目のコードを参考にしてください。

Why do not you register as a user and use Qiita more conveniently?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away