6

3次元の迷路を生成するアルゴリズムはありますか？基本的に2D迷路と同じですが、Z深度軸をトラバースできますか？ただし、開始から終了までの考え方は同じです。バックトラックは引き続き使用できますか？

3D迷路を生成するには、どのアルゴリズムを使用する必要がありますか？

ここを参照してください。つまり、立方体の面を繰り返すだけでなく、立方体にも入ることができます。

4

3 に答える 3

8

ここでクラスカルのアルゴリズムを使用して、数年前に2D迷路を作成しました。あなたが説明した3Dケースでこれが機能しなかった理由はないはずです。基本的に、セルを立方体と見なし、（すべてのセルに対して）+/- x、y、およびz方向に6つの壁を持つ大きな配列があります。アルゴリズムは最初、あらゆる場所のすべての壁から始まり、迷路内のすべてのセルが接続されるまで壁をランダムに非表示にします。

于 2011-12-10T00:35:41.907 に答える
0

私は、何よりもRPGLE（言語を学びながら自己運動として行ったもの）で2D迷路を生成するためのコードを持っています。私が書いた方法のために、一般的なアルゴリズムに必要な唯一の変更は、追加の次元としてZ次元を追加することです...

全体の長さは20ページです（これには入出力が含まれますが）ので、ここにいくつかのコードがあります。これを必要な言語に翻訳できるはずです。私はスパゲッティコードBASICから翻訳しました（gotoここではかなり酷使されていましたが、楽しい演習でした）。

//set out maximum maze size
maximumMazeSquareCounter = mazeHorizontalSize * mazeVerticalSize + 1;
// generate a starting horizontal positiongetRandomNumber(seed : randomNumber);
currentHorizontalPosition = %inth(randomNumber * (mazeHorizontalSize - 1)) + 1;
currentVerticalPosition = 1;
mazeSquareCounter = 1;
// generate the top row of the maze (with entrance)
mazeTopRow = generateEntrance(currentHorizontalPosition);
//write to the printer file
writeMazeDataLine(mazeTopRow);
mazeSquareCounter += 1;
//set the first position in the maze(the entry square
setPathPoint(currentHorizontalPosition : currentVerticalPosition);
//do until we've reached every square in the maze
dou mazeSquareCounter >= maximumMazeSquareCounter;
//get the next available random direction
mazeDirection = getNextRandomDirection(getNextAvailableDirection(currentHorizontalPosition : currentVerticalPosition));
//select what to do by the returned results
select;
//when FALSE is returned - when the maze is trapped
when mazeDirection = FALSE;
//if not at the horizontal end of the maze
if currentHorizontalPosition <> mazeHorizontalSize;
//add one to the position
currentHorizontalPosition += 1;
//else if not at the vertical end of the maze
elseif currentVerticalPosition <> mazeVerticalSize;
//reset the horizontal position
currentHorizontalPosition = 1;
//increment the vertical position
currentVerticalPosition += 1;
//otherwise
else;
//reset both positions
currentHorizontalPosition = 1;
currentVerticalPosition = 1;
endif;
//when 'N' is returned - going up (other directions removed)
when mazeDirection = GOING_NORTH;
//set the point above current as visited
setPathPoint(currentHorizontalPosition : currentVerticalPosition - 1);
//set the wall point to allow passage
setWallDirection(currentHorizontalPosition : currentVerticalPosition : GOING_NORTH);
//change the position variable to reflect change
currentVerticalPosition -= 1;
//increment square counter
mazeSquareCounter += 1;
endsl;
enddo;
//generate a random exit
// get a random number
getRandomNumber(seed : randomNumber);
// set to the horzontal position
currentHorizontalPosition = %inth(randomNumber * (mazeHorizontalSize - 1)) + 1;
//set the vertical position
currentVerticalPosition = mazeVerticalSize;
//set wall to allow for exit
setWallDirection(currentHorizontalPosition : currentVerticalPosition : GOING_SOUTH);

全体は2つの2次元配列（RPGに相当）によって支えられています。1つは「正方形」を占める壁用で、もう1つはその正方形が訪問されたかどうか用です。迷路は、すべての正方形が訪問された後に作成されます。保証されたワンパスのみ、ワームは迷路を回します。

これを3次元にするには、3次元配列を使用し、必要な次元インデックスを追加します。

于 2011-12-10T00:36:26.223 に答える
0

正方形のグリッド上の2D迷路用にアルゴリズムを設計しましたが、これが立方体グリッド上の3D迷路でも機能しない理由はありません。

最初に壁のセルが完全に配置された3Dグリッドから始めます。

..。

グリッドの端でエージェントを開始します。エージェントは、移動中にX、Y、Z、-X、-Y、または-Z方向のクリアウォールを直線で移動します。

アクション「N」は、各ステップで発生する可能性がわずかです。

アクション「M」は、エージェントの直前のセルが壁であり、その前のセルが空の場合に発生します。

「N」はランダムに選択されます。

  1. そのエージェントを削除する
  2. 左または右に90度回転
  3. 同じ正方形にエージェントを作成すると、左、右、または両方（2つのエージェント）が90度回転します。

「M」はランダムに選択されます。

  1. そのエージェントを削除する
  2. そのエージェントの前の壁を削除してから、そのエージェントを削除します
  3. 何もせず、続けます
  4. 左または右に90度回転します。
  5. 同じ正方形にエージェントを作成すると、左、右、または両方（2つのエージェント）が90度回転します。

迷路は独特であり、「M」のトリガーを調整することによって（有効なジャンクションを処理するため）、また1から8が発生する可能性を調整することによって、その特性は非常に柔軟です。1つまたは2つのアクションを削除するか、独自のアクションを導入することをお勧めします。たとえば、1つは小さなクリアを行うか、1つのステップを回避します。

'N'のトリガーは、別の種類のランダム性にすることもできます。たとえば、以下の例を使用して、まだ長い直線部分があるかなり枝分かれした迷路を作成できます。

float n = 1;

while (random_0_to_1 > 0.15)
{
    n *= 1.2;
}

return (int)n;

私の簡単な説明から、いくつかの小さな調整が必要になります。たとえば、アクション「M」のトリガーは、望ましいジャンクションの種類に応じて、チェックするセルに隣接するセルもチェックする必要があります。

迷路にサイクルを含めるには5または6のいずれかが必要であり、迷路に行き止まりを含めるには、5および6に対する少なくとも1つの代替の「M」アクションが必要です。

チャンス/アクションと「M」トリガーのいくつかの選択は、機能しない迷路を作る傾向があります。たとえば、解決できないか、空のセルまたは壁のセルでいっぱいですが、多くは一貫して素晴らしい結果を生成します。

于 2018-01-19T16:26:01.623 に答える