python - 生成迷宫时如何防止角落碰触

我一直在尝试用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()

最佳答案

检查被占用的相邻单元格时，可以向前看更远一些，从而摆脱了碰触的角落。下线后

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中实现起来应该非常简单。

关于python - 生成迷宫时如何防止角落碰触，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/47085374/