当产生迷宫时，我如何阻止角的接触？

Question

我一直试图在Python 3中开发一个迷宫生成器，而且我已经接近完成了。我有它的一点，我可以创建迷宫，如下图所示，但如果你仔细看，你可能会看到两个问题，我担心。在某些情况下，道路的拐角是触碰的。这是我明确地试图通过检查每个潜在的单元格，8个边和角来避免的。也有一些点，我可以看到，哪里有“岛屿”，有额外的细胞空间，但它是空的。如果你知道我怎么解决这个问题的话，那就太好了。谢谢!

​

​

import random
import numpy as np
from matplotlib import pyplot as plt

# Width and height of the maze
mx = 50
my = 50

# Maze Array
maze = np.zeros((mx, my))

# Directions to move in the maze
dx = [-1, 1, 0, 0, -1, 1, 1, -1]
dy = [0, 0, -1, 1, -1, 1, -1, 1]

# Visited Cells
stack = []

# Find Which Neighbour Cells Are Valid
def nextCell(cx, cy):

    # Set Current Cell To '1'
    maze[cy, cx] = 1

    # List Of Available Neighbour Cell Locations
    n = []

    # Check The 4 Available Neighbour Cells
    for i in range(4):

        nx = cx + dx[i]
        ny = cy + dy[i]

        # Check If Neighbours Cell Is Inbound
        if nx >= 1 and nx < my - 1 and ny >= 1 and ny < mx - 1:

            # Check If Neighbour Cell Is Occupied
            if maze[ny, nx] == 0:

                # Variable To Store Neighbour Cells Neighbours
                cn = 0

                # Loop Through Neighbour Cells Neighbours
                for j in range(8):

                    ex = nx + dx[j]
                    ey = ny + dy[j]

                    # Check If Neighbour Cells Neighbour Is Inbound
                    if ex >= 0 and ex < my and ey >= 0 and ey < mx:

                        # Check If Neighbour Cells Neighbour Is Occupied
                        if maze[ey, ex] == 1:
                            cn += 1

                # If Neighbour Cells Neighbour Has Less Than 2 Neighbours, Add Cell To List
                if cn <= 2:
                    n.append((ny, nx))



    # Return The List Of Valid Neighbours
    return n

# Generate The Maze
def GenerateMaze(sx, sy):

    # Initialize 'x,y' With Starting Location
    x = sx
    y = sy

    # Loop Until Maze Is Fully Generated
    while True:

        # Neighbour List
        n = nextCell(x, y)

        # Check If 'n'  Contains A Neighbour
        if len(n) > 0:
            stack.append((y, x))

            ir = n[random.randint(0, len(n) - 1)]

            x = ir[1]
            y = ir[0]

        # Go Back Through The Stack
        elif len(stack) > 1:
            stack.pop()

            x = stack[-1][1]
            y = stack[-1][0]

        # Maze Is Complete
        else:    
            break



if __name__ == "__main__":

    # Generate Maze
    GenerateMaze(random.randint(1,8), random.randint(1,8))

    # Show Plot
    plt.imshow(maze, interpolation='nearest')
    plt.show()

Answer 1

当你检查被占用的相邻细胞时，你可以向前看远一点就可以去除触角。在线后

if maze[ny, nx] == 0:

只需添加以下内容：

    # Abort if there is an occupied cell diagonally adjacent to this one
    if maze[ny+dy[i]+dx[i], nx+dx[i]+dy[i]] or maze[ny+dy[i]-dx[i], nx+dx[i]-dy[i]]:
        continue

结果如下：

​

​

我认为，摆脱这些岛屿要棘手得多。如果这是你真正想要避免的事情，我建议你以更有序的方式建造迷宫。维基百科有一个关于迷宫生成算法的页面。Kruskal的随机算法给出了很好的结果，在Python中实现应该非常简单。