2

迷路を作成するために使用したい2次元配列があります。

各値は0または1にすることができます。ここで、0は壁があることを意味し、1は部屋があることを意味します。そして今、私はその配列内に「パス」を作成するためのアルゴリズムが必要です。

たとえば、空白の配列は次のようになります。

0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0

「パス」の例は次のとおりです。

0 0 0 0 0 0 0 0
0 0 0 1 1 0 0 0
0 0 0 0 1 0 1 0
0 0 0 1 1 1 1 0
0 0 0 1 0 1 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0

それは基本的にこれに帰着します：

1）すべてが0

2）ランダムな開始点があります。1

3）その時点から、ランダムな隣接値を作成する必要があります1。しかし：4つ以上の隣接するフィールドの正方形が1ANDであってはなりません：線形パスは必要ありません、迷路にしたいです

（すべてのアレイを迷路に使用する必要はありません。実際、そのアレイ内に一定量（たとえば、20または50）の部屋が必要だと言えばクールです）

これに使用できる優れたアルゴリズムやアイデアはありますか（特に私のリストの＃3）？

4

1 に答える 1

3

再帰的なバックトラッキング手順でこれを行うことができます。

algorithm gen-maze(pos):
    set pos to 1

    build a list of neighboring positions
    randomly shuffle this list
    for each neighbor n of pos in random order:
        if n is 0 and setting it to 1 doesn't create a square:
            gen-maze(n)

このアルゴリズムをランダムな位置から開始します。

説明については、深さ優先探索に関するWikipediaの記事を読み、アニメーションを必ず見てください。

于 2013-03-09T19:57:34.077 に答える