次のような迷路を生成したいと思います。
つまり、一方向のパスで構成され、その後接続されます。私はこのような迷路を生成するアルゴリズムを探しましたが、成功しませんでした。
具体的には、次のような迷路は必要ありません。
一方向にしか「走らない」からです。
また、この迷路の解決策で、プレイヤーが「バックトラック」する必要がある場合、つまり、常に上に移動するだけではない場合も便利です。
3715 次
6 に答える
4
- ポイントAとポイントBの間にランダムパスを作成します
- 満足するまで壁がパス上にない限り、ランダムに壁を追加します
于 2010-04-15T00:33:35.447 に答える
4
楽しかったです！私が提示するASCIIアート出力を完備...
█ ██████ █████████████████████ █
█ █ █ █
█ █ █ █
█ █ ██████████████████████████ █
█ █
█ █
██████ ██████ ███████████ ██████
█ █ █ █ █ █
█ █ █ █ █ █
███████████████████████████████ ██████
█ █
█ █
██████ █████████████████████ ██████
█ █ █
█ █ █
██████ ███████████ ███████████ █
█ █ █ █
█ █ █ █
█████████████████████ ██████ ██████
█ █ █ █
█ █ █ █
███████████████████████████████ ██████
█ █
█ █
private struct Cell
{
public bool visited;
public bool right;
public bool top;
}
static void Main(string[] args)
{
Random Rand = new Random();
int size = 8;
var maze = new Cell[size,size];
for (int x = 0; x < size; x++)
for (int y = 0; y < size; y++)
{
maze[x, y] = new Cell() { right = true, top = true, visited = false };
}
int count = size * size;
int positionX = Rand.Next(size);
// mark space below (outside matrix)
for (int y = 0; y < size; y++)
{
maze[positionX, y].top = false; maze[positionX, y].visited = true;
count--;
// move left or right n spaces
int n = Rand.Next(size); // random left or right by an amount n
int direction = (Rand.Next(2) == 0) ? 1 : -1;
while (positionX + direction > 0 && positionX + direction < size -1 && n-- > 0)
{
// moving sideways
if (direction == -1)
{
positionX += direction;
maze[positionX, y].right = false;
maze[positionX, y].visited = true;
count--;
}
else
{
maze[positionX, y].right=false;
positionX += direction;
maze[positionX, y].visited = true;
count--;
}
}
}
// Now pick a random place we have visited and extend into new territory
while (count > 0)
{
int x = Rand.Next(size);
int y = Rand.Next(size);
if (!maze[x, y].visited) continue; // not visited yet
// We are on a visited node, where can we go from here?
// Pick a direction to break down a wall - favor left right
if (Rand.Next(4) > 0)
{
if (Rand.Next(2) == 1 && x < size-1 && !maze[x+1,y].visited )
{ maze[x,y].right = false; maze[x+1,y].visited = true; count--;}
else if (x > 0 && !maze[x-1,y].visited)
{maze[x-1,y].right = false; maze[x-1,y].visited = true; count--;}
}
else
{
if (Rand.Next(2) == 1 && y < size - 1 && !maze[x, y + 1].visited)
{ maze[x, y].top = false; maze[x, y+1].visited = true; count--; }
else if (y > 0 && !maze[x, y-1].visited)
{ maze[x, y-1].top = false; maze[x,y-1].visited = true; count--; }
}
}
// Dump the maze
for (int y = 0; y < size; y++)
{
Console.Write("█");
for (int x = 0; x < size; x++)
Console.Write((maze[x, y].top) ? "█████" : " █");
Console.WriteLine();
for (int repeat = 0; repeat < 2; repeat++)
{
Console.Write("█");
for (int x = 0; x < size; x++)
{
Console.Write(maze[x, y].right ? " █" : " ");
}
Console.WriteLine();
}
}
于 2010-04-15T06:01:19.750 に答える
0
私があなたを正しく理解しているなら、あなたは決して下がる必要がないようにあなたの解決策を持ちたいと思うでしょう（入口が下にあり、出口が上にあるとき）。
簡単な方法は、最初に単純な水平マップを生成し、次のように各レイヤーにランダムな穴を1つ選択することだと思います。
+--------------- +
+ +
+--- ------------+
+ +
+-------------- -+
+ +
+-------- -------+
+ +
+ ---------------+
これで、ソリューションパスの行き先が定義されました。ここで、いくつかのジャンブリングを実行します。ランダムな水平エッジをどこかで削除し、新しい穴の上または下の行で、穴と実際のソリューションが進む場所の間でランダムに選択された、使用を防ぐ垂直エッジを追加します。（ソリューションパスの2つのセクション間の水平エッジを削除しないようにする必要があります。）
これはかなりうまくいくと思います。ただし、大きな（複数行の）誤ったパスは簡単には生成されない可能性があります。
于 2010-04-15T05:56:43.193 に答える
0
エラーのアルゴリズムを使用して、水平方向にバイアスを導入します。
于 2012-04-26T16:07:06.143 に答える
0
A* 検索を使用して、最後までの道を常に見つけられるようにしてから、すべての行にランダムに配置された 20 の壁を追加します。新しい行を下に配置した後、A* が最後に到達できない場合は、バックトラックを使用して、機能するまで新しい壁のセットを再生成します。最も効率的な方法ではないかもしれませんが、ほとんどの場合、かなりうまくいくと思います。
于 2010-04-15T00:41:44.850 に答える
0
ここに別のものがあります：
- 部屋の境界に壁を追加します。
- 部屋の境界と中央にあるいくつかのランダムなスポットを選びます。各スポットについて:
- その場所からまだ壁がない場所への方向がある場合は、ランダムな自由な方向を選び、そこに壁を「成長」させます。それ以外の場合は、このスポットをリストから削除してください。
- 20% の確率でつぼみを発芽させ、それが「はい」の場合は、そのスポットをリストに追加します。
- リストにさらにスポットがある場合は、次のスポットを選択して #2 に進みます。それ以外の場合は＃5を獲得しました。
- 空きスポットが残っている場合は、それらすべてをリストに入れます。フリースポットごとに：
- それらが出会うように、最も近い壁に向かって壁を「構築」します。
于 2010-04-15T00:47:24.800 に答える