使用Prim算法创建“难”迷宫

Question

I希望使用Prim算法创建迷宫。我已经成功地完成了这个任务，但现在我正在尝试通过改变选择潜在单元格加入迷宫的方式来使它更加“困难”。在我看来，“困难”处于两个极端之间：

极端＃1是完全随机选择潜在通道列表中的单元格，在该列表中每个分支以大约相等的速度发展。这有很多不同的分支，但一旦到达起点，您就可以沿着直线朝向所需位置。下面是显示此方法的图片：

极端情况 #2 是选择列表中最后添加的事项，从而创建一个漫长、繁琐、易于迷失的迷宫。当你只选择放入潜在通道列表中的最后一项时，就会形成这种情况。下图展示了这种方法：

我试图通过优先放置最近的单元格来实现平衡，但难以创建分支，正如第一个迷宫所示，但仍然需要一条环绕整个迷宫的路径。

最有趣的尝试方法是我尝试让50%的概率是上个方块被放置，如果失败则50%的概率是下一个，依此类推。但是，我将[-0]的索引放在了最前面，使得第一个方块有50%的概率被添加，接着是最后一个，然后是倒数第二个，以此类推。这创造了一个有趣的迷宫，但当我“修复”它时，迷宫看起来很像第二个极端。

我尝试的另一种方法是我代码中使用的方法：

for i in range(1, len(potential_passage_list) + 1):
        if randint(0, int(len(passage_list) / 50)) == 0:
            maze_passage(potential_passage_list[-i][0], potential_passage_list[-i][1])

这是为了尝试有一个合理的可能性，将一个块添加到潜在通道列表中并放置。

那么，我的问题是，如何创建一个包含许多分支但具有不可预测模式的“困难”迷宫？可以使用哪些算法来实现？

我正在使用Python 3和Pygame库来显示所有内容。

这是我的代码，如果您能理解它：

import pygame
from random import shuffle, randint

# variables
######
# changeable variables
cell_size = 7  # cannot be less than 3
maze_length = 160 * cell_size + 1
maze_height = 100 * cell_size + 1
######

# colours
black = (0, 0, 0)
white = (245, 245, 245)
red = (255, 0, 0)
blue = (0, 0, 255)

# other variables
passage_list = []
potential_passage_list = []
impossible_passage = []
random_cell = []
done = False

# initialize pygame and display screen
pygame.init()
screen = pygame.display.set_mode((maze_length, maze_height))
pygame.display.flip()


def one_connection(cell_x, cell_y):
    # ensure that it will only touch one passage
    count = 0

    if [cell_x + cell_size, cell_y] in passage_list:
        count += 1
    if [cell_x - cell_size, cell_y] in passage_list:
        count += 1
    if [cell_x, cell_y + cell_size] in passage_list:
        count += 1
    if [cell_x, cell_y - cell_size] in passage_list:
        count += 1

    if count <= 1:
        return True
    else:
        return False


def valid_cell(cell_x, cell_y):
    # check if already in potential_passage_list
    if [cell_x, cell_y] in potential_passage_list:
        impossible_passage.append([cell_x, cell_y])
    # check if in impossible list
    elif [cell_x, cell_y] in impossible_passage:
        impossible_passage.append([cell_x, cell_y])
    # check if out of boundary
    elif cell_x < 0 or cell_x >= maze_length - cell_size or cell_y < 0 or cell_y >= maze_height - cell_size:
        impossible_passage.append([cell_x, cell_y])
    # ensure that it will only touch one passage
    elif not one_connection(cell_x, cell_y):
        impossible_passage.append([cell_x, cell_y])
    # check if it isolates any walls / cut off unconnected corners
    elif (([cell_x + cell_size, cell_y + cell_size] in passage_list and [cell_x + cell_size, cell_y] not in
           passage_list and [cell_x, cell_y + cell_size] not in passage_list) or
          ([cell_x + cell_size, cell_y - cell_size] in passage_list and [cell_x + cell_size, cell_y] not in
           passage_list and [cell_x, cell_y - cell_size] not in passage_list) or
          ([cell_x - cell_size, cell_y + cell_size] in passage_list and [cell_x - cell_size, cell_y] not in
           passage_list and [cell_x, cell_y + cell_size] not in passage_list) or
          ([cell_x - cell_size, cell_y - cell_size] in passage_list and [cell_x - cell_size, cell_y] not in
           passage_list and [cell_x, cell_y - cell_size] not in passage_list)):

        impossible_passage.append([cell_x, cell_y])
    # check if already in passage_list
    elif [cell_x, cell_y] not in passage_list:
        return True


# functions
def maze_passage(cell_x, cell_y):
    # reset block_passage_list
    block_passage_list = []

    # remove from list so it does not interfere with valid_cell procedure
    potential_passage_list.remove([cell_x, cell_y])
    if valid_cell(cell_x, cell_y):
        # display rectangle
        pygame.draw.rect(screen, white, [cell_x, cell_y, cell_size, cell_size])
        pygame.display.update()

        passage_list.append([cell_x, cell_y])

        # add valid walls to block_passage_list
        if valid_cell(cell_x + cell_size, cell_y):
            block_passage_list.append([cell_x + cell_size, cell_y])
        if valid_cell(cell_x - cell_size, cell_y):
            block_passage_list.append([cell_x - cell_size, cell_y])
        if valid_cell(cell_x, cell_y + cell_size):
            block_passage_list.append([cell_x, cell_y + cell_size])
        if valid_cell(cell_x, cell_y - cell_size):
            block_passage_list.append([cell_x, cell_y - cell_size])

        shuffle(block_passage_list)

        for j in block_passage_list:
            potential_passage_list.append(j)


# create initial cell
start_cell = [randint(0, int(maze_height / cell_size))*cell_size, randint(0, int(maze_height / cell_size))*cell_size]
potential_passage_list.append([start_cell[0], start_cell[1]])


# loop for creating maze
while not done:
    for event in pygame.event.get():
        # exit screen when exit pressed in pygame
        if event.type == pygame.QUIT:
            done = True

    # select cell
    for i in range(1, len(potential_passage_list) + 1):
        if randint(0, int(len(passage_list) / 50)) == 0:
            maze_passage(potential_passage_list[-i][0], potential_passage_list[-i][1])
            break

    # check if maze completion finished
    if not potential_passage_list:
        # create start and end
        passage_list.sort()
        pygame.draw.rect(screen, red, [passage_list[0][0] + 1, passage_list[0][1] + 1, cell_size - 2, cell_size - 2])
        pygame.draw.rect(screen, blue, [passage_list[-1][0] + 1, passage_list[-1][1] + 1, cell_size - 2, cell_size - 2])
        pygame.display.update()

欢迎使用我的代码，随意修改并分享你认为有效的部分。

谢谢！

- Juicetin

---

为了回答你的问题，我认为你需要定义一些术语。什么是“hard”？它是指我们确定一个用于穿越迷宫的算法，并确定哪些迷宫需要最长时间，同时又是“不可预测”的吗？还有一个需要定义的东西，我不确定该提出什么定义。抱歉没有直接回答你的问题，但我认为这是一个有趣的问题。 - Countingstuff

“难”是人类认为的难。据我理解，这由两个因素组成：“不可预测性”和“分支”。 “可预测性”是指猜测迷宫走向的容易程度。在第一张图片中，迷宫非常可预测，因为从起点到终点几乎是一条对角线，但第二张图片则是不可预测的，因为它朝着随机方向前进。 “分支”是指迷宫分成不同路径的次数和深度。第一个迷宫有许多深入的分支，但第二个迷宫没有，使得计算路径变得容易。 - Juicetin

@Justin：在没有大规模秩序的情况下，我认为难度的一个合理定义是A*算法（使用欧几里得启发式）所需步骤数除以正确路径长度。 - Davis Herring

根据我的理解，因为A*算法总是能找到最优路径，所以这个值不会变成其他的吧？如果我错了，请纠正我。 - Juicetin

@Justin：但它会扩展不在最短路径上的其他节点（然后在卡住时回溯）。我将每个节点都视为一个“步骤”，就好像算法正在用手指追踪各种路径一样。 - Davis Herring

Answer 1

我喜欢使用Kruskal算法，并指定不同配置中删除边缘的不同选择权重，而不是优先考虑最近与旧单元格。

这样可以创建具有各种不同特征的迷宫。您可以在此处尝试演示：https://mtimmerm.github.io/webStuff/maze.html

如果您喜欢扩展现有路径的选项（滑块1、2和3），则会制作更难的迷宫。

- Matt Timmermans