5

ゴール

3D 迷路を生成するプログラムを作成していますが、作成アルゴリズムに少し問題があります。相互作用を容易にするために、入口と出口が 1 つずつある四角柱になります。

アルゴリズム

問題は、アルゴリズムの実際のコーディングです。これを使用する最善の方法はMazeBlock、迷路の方向を示す 6 つのブール値状態 (上、下、左、右、イン、アウト) を持つというクラスを作成することだと考えました。次に行ける。s の3D 配列を使用してMazeBlock、迷路を塗りつぶしたいと考えています。塗りつぶしの各反復で、ブロックの左、右、上、下、前、後ろをチェックして、その側に開口部があるかどうかを確認します。添付する。

迷路の内側に向かってランダムな開いたスロットを配置して、エッジを作成するものを既に持っています。私が問題を抱えているのは、実際の内部であり、迷路に 1 つの入り口、1 つの出口、およびそれを通過するための 1 つの解決策があることを確認することです (私はかつて、ポップアップブックの「難しい」3D 迷路を、意図した反対の数歩だけ進むことで解決しました)。方向。

質問

私が言っているように、アルゴリズムの基本的なアイデアはあると思いますが、それをコーディングする方法がわかりません。誰かがこのタスクを比較的迅速に達成する Java アルゴリズムを考え出すことができますか?

ソリューションでは、外部ライブラリを使用してはなりません。

4

1 に答える 1

8

ここで非常にうまく機能する多くの迷路生成アルゴリズムがあり、そのほとんどは、3D グリッドのグラフである種のスパニング ツリーを作成することに基づいています。

例として、次のようなセルの 2D グリッドがあるとします (これは実際に ASCII アートを使用してレンダリングできます!)。

*---*---*---*
|   |   |   |
*---*---*---*
|   |   |   |
*---*---*---*
|   |   |   |
*---*---*---*

これは、各セルが頂点で、セル間の各接続がエッジであるグラフと考えることができます。私たちの目標は、すべてのノードを接続するツリーを見つけることです。これを行うと、すべてのセルが相互に到達可能になります (ツリーが接続されているため) が、ループはありません (ツリーは最小接続グラフであるため)。使用できるさまざまなツリーがあります。たとえば、ここに 1 つのツリーがあります。

*---*---*---*
|   |   |   |
*   *   *   *
|   |   |   |
*   *   *   *
|   |   |   |
*   *   *   *

そして、ここに別のものがあります：

*   *---*   *
|   |   |   |
*---*   *   *
        |   |
*---*---*---*
    |       |
*---*   *---*

迷路セルを接続する何らかのツリーを探している場合、1 つのオプションは、グラフに対して深さ優先検索を使用し、訪問する必要があるエッジをランダムに並べることです。この戦略はよく知られている迷路生成アルゴリズムであり、行き止まりとわかりにくい分岐でいっぱいの、長く曲がりくねった迷路を生成します。

迷路を作成するために一般的に使用されるもう 1 つのアプローチは、グラフの最小スパニング ツリーを見つける問題に単純化することです。特に、すべてのセルがその隣接セルへのリンクを持つノードであるグラフを作成するとします。エッジごとにランダムな重みを選択し、グラフの最小全域木を構築します。このツリーにはサイクルがなく、各ノードから他の各ノードへの一意のパスがあります。つまり、迷路には一意のソリューションがあります。さらに、このアルゴリズムは非常に効率的です。サイズ nxnxn の 3D キューブでは、O(n 3 ) ノード、O(n 3 ) エッジがあり、いずれかを使用して O(n 3 lg n) 時間で MST を見つけることができます。Prim のアルゴリズムまたはKruskal のアルゴリズム. これらも高品質の迷路を生成しますが、それらのプロパティは、ランダム化された深さ優先検索を使用して作成された迷路とは大きく異なります。

お役に立てれば！

于 2011-01-14T00:18:02.347 に答える