python - 生成迷宫时如何防止角点接触

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

结果如下:

我认为，摆脱岛屿有点棘手。如果您确实想避免这种情况，我建议您以更有序的方式构建迷宫。维基百科有一个关于maze generation algorithms的页面。随机 Kruskal 算法给出了非常好的结果，并且在 Python 中实现应该非常简单。