Eller 算法的问题 - 迷宫生成

Question

我正在尝试使用埃勒算法创建一个迷宫。互联网上关于这个特定算法的信息并不多。所以我对这个算法有一些困难，因为有些事情我不完全理解。但无论如何，这就是我现在所拥有的：

\n\n

class Cell:\n    def __init__(self, row, col, number, right_wall, bottom_wall):\n        self.row = row\n        self.col = col\n        self.number = number    # defines which set this block is in\n        self.right_wall = right_wall\n        self.bottom_wall= bottom_wall\n\n# every block includes 5x5 px white space + 1px on it\'s left and 1px on it\'s bottom for walls (if the block has ones)\ndef create_block(row, col, right_wall, bottom_wall):\n    for i in range(row-2, row+4):   # since the path is 5px wide\n        for j in range(col-2, col+4):   # i go to a central pixel of block\'s white space and make it thick\n            maze[i, j] = [255, 255, 255]    # in other words i draw 2px border around central pixel\n    if right_wall:  # if the block has wall on it\'s right\n        create_right_wall(row, col, 1)  # draw right wall with a function\n    if bottom_wall: # if the block has wall on it\'s bottom\n        create_bottom_wall(row, col ,1) # draw bottom wall with a function\n\n\ndef create_right_wall(row, col, color):\n    if color == 0:  # if color parameter = 0\n        for i in range(row-2, row+4):\n            maze[i, col+3] = [0, 0, 0]  # I draw (create) black wall\n    else:\n        for i in range(row-2, row+4):\n            maze[i, col+3] = [255, 255, 255]    # I draw white wall (if I need to delete a wall)\n\n\ndef create_bottom_wall(row, col, color):\n    if color == 0:\n        for i in range(col-2, col+4):\n            maze[row+3, i] = [0, 0, 0]\n        if row + 4 < maze_height and maze[row+4, col-3][0] == 0:    # sometimes there\'s 1px gap between bottom walls\n            maze[row+3, col-3] = [0, 0, 0]  # so I fill it with black pixel\n    else:\n        for i in range(col-2, col+4):\n            maze[row+3, i] = [255, 255, 255]    # draws white wall (deleting wall)\n\n\ndef creating():\n    current_point = [3, 3]  # where the top-left block appears ([3,3] is for the block\'s center)\n\n    set_count = 1   # to have unique set numbers, it increases every time after it has been used\n\n    for row in range(height):   # going from top to bottom\n        # I print some unnecessary information just to know what\'s happening\n        print("- - - - - - - - - - - - - - - - - - - - - - - - - - - - - row", row) # current row being created\n        if row == 0:    # if it\'s the first row\n            for col in range(width):\n                create_block(current_point[0], current_point[1], False, False)\n\n                blocks[row].append(Cell(current_point[0], current_point[1], set_count, False, False))\n                set_count += 1  # since the set number has been used, the next block will have another one\n\n                current_point[1] += 6   # the center of the next block is 6px away from the center of the current one\n\n        elif row == height - 1: # if it\'s the last row\n            for i in range(width):\n                create_block(current_point[0], current_point[1], False, False)\n                blocks[row].append(Cell(current_point[0], current_point[1], blocks[row-1][i].number, False, True))\n\n                current_point[1] += 6\n\n                # I don\'t know why I do this. Just trying to create the last line correctly\n                if (not blocks[row-1][i].bottom_wall and not blocks[row-1][i + 1].bottom_wall) and \\\n                        (blocks[row-1][i].number == blocks[row-1][i + 1].number):\n                    create_right_wall(blocks[row][i].row, blocks[row][i].col, 0)\n            break   # since it\'s the last row, don\'t do anything else\n\n\n\n        else:\n            for col in range(width):\n                create_block(current_point[0], current_point[1], False, False)\n\n                print("block on top has set:", blocks[row-1][col].number, end=" ")\n\n                if blocks[row-1][col].bottom_wall:  # if upper block has bottom wall\n                    blocks[row].append(Cell(current_point[0], current_point[1], set_count, False, False))\n                    print("upper block has a bottom wall, so set for the current block is", set_count)\n                    set_count += 1\n                else:   # if not, the current block\'s set will be the same as for the upper one\n                    blocks[row].append(Cell(current_point[0], current_point[1],\n                                            blocks[row-1][col].number, False, False))\n                    print("current block set", blocks[row-1][col].number)\n\n                current_point[1] += 6\n\n            # just to show set numbers for current row\n            for i in blocks[row]:\n                print(i.number, end=" ")\n\n\n        # putting a wall between blocks of the same set (we don\'t want to have loops in our maze)\n        for i in range(len(blocks[row]) - 1):\n            if blocks[row][i].number == blocks[row][i+1].number:\n                blocks[row][i].right_wall = True\n                create_right_wall(blocks[row][i].row, blocks[row][i].col, 0)\n                print("put a wall between", i+1, "\xd0\xb8", i+2, "because", blocks[row][i].number, "=",\\\n                      blocks[row][i+1].number)\n\n\n        for i in range(len(blocks[row]) - 1):\n            if random.choice([0, 1]) == 0 and blocks[row][i].number != blocks[row][i+1].number:\n                blocks[row][i + 1].number = blocks[row][i].number\n                print("connect block", i + 1, "and", i + 2)\n            else:\n                blocks[row][i].right_wall = True\n                create_right_wall(blocks[row][i].row, blocks[row][i].col, 0)\n\n\n        # to know what set nu,bers we have in the current row\n        sets_in_row = []\n        for i in blocks[row]:\n            print(i.number, end=" ")\n            sets_in_row.append(i.number)\n\n        sets_in_row = sorted(set(sets_in_row), key=lambda x: sets_in_row.index(x))\n        print(sets_in_row)\n\n\n        current_bl = 0  # current block in a\n        for mn in sets_in_row:  # for every set number in a row\n            current_mn_length = sum([p.number == mn for p in blocks[row]])  # how many blocks has this set number\n            if current_mn_length > 1: # if the current set has more than 1 block\n                quantity = random.randrange(1, current_mn_length)   # random number of bottom walls\n                # whick blocks in the current set will have a bottom wall\n                bloxxxx = random.sample(list(range(current_bl, current_bl + current_mn_length)), quantity)\n\n                # just to know how it\'s going\n                print("\\nblock:")\n                for y in range(current_bl, current_bl + current_mn_length):\n                    print("pos:", y + 1, end=" ")\n                    print("  num:", blocks[row][y].number,)\n\n\n                print("bottom walls for")\n                for i in bloxxxx:\n                    print(i+1, end=" ")\n\n                print()\n\n                for b in bloxxxx:\n                    blocks[row][b].bottom_wall = True\n                    create_bottom_wall(blocks[row][b].row, blocks[row][b].col, 0)\n\n                current_bl += current_mn_length\n\n            else:\n                print("\\n set length of", current_bl + 1, "=", current_mn_length, "so no bottom wall\\n")\n                current_bl += current_mn_length\n\n        current_point[0] += 6   # go to the center of the next row block\n        current_point[1] = 3    # go to the center of the first block of the next row\n\n\nwhile True:\n    width = int(input("Width: "))\n    height = int(input("height: "))\n\n    maze_width = width * 6 + 1\n    maze_height = height * 6 + 1\n\n    maze = np.full((maze_height, maze_width, 3), 0, dtype=np.uint8)\n    paths = []\n    all_positions = width * height\n    break\n\nblocks = [[] for h in range(height)]\n\ncreating()\n\nfor h in range(maze_height):\n    maze[h][maze_width-1] = [0, 0, 0]\n\nfor w in range(maze_width):\n    maze[maze_height-1][w] = [0, 0, 0]\n\nimg = Image.fromarray(maze, \'RGB\')\nimg.save(\'maze.png\')\nimg.show()\n

\n\n

我尝试解释每一行，以便您可以理解我的代码中发生的情况。我知道我有很多不必要的代码。那是因为我尝试了很多方法来生成正确的迷宫。

\n\n

问题是迷宫并不总是正确生成的。例如，这个有循环。但不应该。

\n\n

\n\n

看看这个\n这个有循环和隔离块。那是因为设定的数字。在这个迷宫中，第二行有这些组：

\n\n

\n在我随机连接块后，一行 2 已被 22 分隔开。因此第二个块不是集合编号 2 中唯一的一个。

\n\n

请帮我修复我的代码。如果您对我的代码有任何疑问，我将尽力为您提供更多相关信息。

\n

Answer 1

我刚刚遇到了同样的问题！

\n

经过长时间的思考，我得出的结论是，网上提供的教程都没有正确解释“连接集”方面！这就是以与您展示的方式相同的方式创建循环的原因。

\n

让我尝试简化这里的算法步骤：

\n

\n
1. 将一排分成不同的组，放置右墙。
\n
2. 每组至少有一个底部开口。
\n
3. 将具有相同集合的单元分开以防止循环。
\n
4. 从步骤 1 开始
\n

\n

现在需要考虑一个关键方面：集合是一行中标有相同“数字”（代表集合）的所有单元格的总和。\n因此，如果您有：

\n

    | 1   1   1 | 2 | 1 |\n

\n

集合 1 是所有带有 1 的单元格，包括最后一个单元格。\n因此，如果您想向下打开一个单元格，您也可以选择打开最后一个单元格底部，如下所示：

\n

    | 1   1   1 | 2 | 1 |\n    |-----------| \xe2\x86\x93 | \xe2\x86\x93 |\n

\n

这很有效，因为第 1 组至少有一个空位。

\n

现在循环的问题是当你连接集合时：

\n

    | 1   1   1 | 2 | 1 |\n    | \xe2\x86\x93 |-------| \xe2\x86\x93 | \xe2\x86\x93 | \xe2\x86\x90 let's make 2 down openings for set 1\n    | 1   4   5 |(2   1)| \xe2\x86\x90 let's say you want to merge set 1 and 2\n    | 2   4   5 | 2   2 | \xe2\x86\x90 also change the set of the first cell!\n

\n

您需要将行中所有单元格的集合更改为与被替换的单元格相同的集合！

\n

这在教程中从未显示过，但在算法解释中有所说明！

\n

这样，当您走下迷宫时，“第一个单元格与最后两个单元格向上连接”的信息将被保留，如果设置 2 向下扩展到第三个单元格，系统会提示您放置一堵墙以保留循环像这样：

\n

    | 1   1   1   1   1 |\n    | \xe2\x86\x93 | \xe2\x86\x93 | \xe2\x86\x93 |---| \xe2\x86\x93 |\n    | 1 | 1 | 1 | 2 | 1 |\n    | \xe2\x86\x93 |-------| \xe2\x86\x93 | \xe2\x86\x93 |\n    | 1   4   4 |(2   1)|\n    | 2 | 4   4 | 2   2 |\n    | \xe2\x86\x93 |---| \xe2\x86\x93 | \xe2\x86\x93 |---|\n    |(2   5)  4 | 2   6 |\n    | 2   2 | 4 | 2 | 6 |\n    |---| \xe2\x86\x93 | \xe2\x86\x93 | \xe2\x86\x93 | \xe2\x86\x93 |\n    | 7  (2   4)|(2   6)|\n    | 7 | 2   2 | 2   2 |\n    | \xe2\x86\x93 |---| \xe2\x86\x93 | \xe2\x86\x93 |---|\n    |(7   8)  2  (2   9)| \xe2\x86\x90 here you HAVE to put a wall between the two 2!\n    | 7   7 | 2 | 2   2 |\n    |---| \xe2\x86\x93 | \xe2\x86\x93 |-------|\n    | a   7   2   b   c | \xe2\x86\x90 last row connect all sets\n    | a   a   a   a   a |\n

\n

由此产生的迷宫将是这样的：

\n

    _____________________\n    |                   |\n    |   |   |   |---|   |\n    |   |   |   |   |   |\n    |   |-------|   |   |\n    |   |       |       |\n    |   |---|   |   |---|\n    |       |   |   |   |\n    |---|   |   |   |   |\n    |   |       |       |\n    |   |---|   |   |---|\n    |       | Y |     X |\n    |---|   |   |-------|\n    |                   |\n    |-------------------|\n

\n

看看没有循环，X 仍然与迷宫的其余部分相连，因为在最后一步中，我们对第 2 组中的 Y 单元做了一个向下的开口！

\n

如果我们没有正确合并这些集合，结果会是这样的：

\n

    _____________________\n    |                   |\n    |   |   |   |---|   |\n    |   |   |   |   |   |\n    |   |-------|   |   |\n    |   |       |       |\n    |   |---|   |   |---|\n    |       |   |   |   |\n    |---|   |   |   |   |\n    |   |       |       |\n    |   |---|   |   |---|\n    |       | 1   2   2 | \xe2\x86\x90 1 and 2 are actually in the same set!\n    |---|   |   |-------|\n    |                   |\n    |-------------------|\n

\n

希望这会有所帮助，尽管已经很晚了！

\n