我想生成一个看起来像这样的迷宫：
也就是说，它由一个方向上的路径组成，然后连接起来。我一直在寻找一种算法来生成这样的迷宫，但没有成功。
具体来说，我不想要这样的迷宫：
因为它不会只向一个方向“运行”。
此外，如果这个迷宫的解决方案需要玩家“回溯”——即不只是一直向上移动，那就太好了。
问问题
3715 次
6 回答
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 回答
4
- 在 A 点和 B 点之间创建一条随机路径
- 随机添加墙，只要它不位于路径上，直到您满意为止
于 2010-04-15T00:33:35.447 回答
0
使用Eller 算法并在水平方向引入偏差。
于 2012-04-26T16:07:06.143 回答
0
如果我对您的理解正确，您希望您的解决方案永远不必下降（当入口在底部而出口在顶部时）。
我认为一个简单的方法是先生成一个简单的水平地图，在每一层随机选择一个洞，像这样：
+--------------- +
+ +
+--- ------------+
+ +
+-------------- -+
+ +
+-------- -------+
+ +
+ ---------------+
您现在已经定义了解决方案路径的去向。现在只是做一些混杂：在某处删除随机水平边缘，然后在新孔上方或下方的行上添加阻止其使用的垂直边缘，在孔和真正解决方案所在的位置之间随机选择。（您需要确保不删除解决方案路径的两个部分之间的水平边缘。）
我认为这会很好。不过，它可能不会太容易生成大的（多行）错误路径。
于 2010-04-15T05:56:43.193 回答
0
只需使用 A* 搜索确保您总能找到通往终点的路径，然后为每一行添加 20 个随机放置的墙壁。如果在您向下放置新行后 A* 无法到达末尾，则使用回溯重新生成一组新墙，直到它起作用。也许不是最有效的方法，但我认为它在大多数情况下都能很好地工作。
于 2010-04-15T00:41:44.850 回答
0
这是另一个：
- 在房间的边界上添加墙壁。
- 在边界和房间中间选择几个随机点。对于每个点：
- 如果从那个地方有方向到还没有墙的地方，选择一个随机的自由方向并“长”一堵墙到那里。否则从列表中删除该点。
- 给它 20% 的机会发芽，如果是，则将该位置添加到列表中。
- 如果列表中有更多点，请选择下一个并转到#2。否则得到#5。
- 如果还有剩余的空闲位置，请将它们全部放入列表中。对于每个免费位置：
- 朝最近的墙“建造”一堵墙，以便他们相遇。
于 2010-04-15T00:47:24.800 回答