谷歌面试题: 迷宫随机生成算法

据说这个是谷歌 Google 的第一轮面试题. 一般这种题目就是: 设计一个迷宫算法 (Design a Maze). 面试中应该先问清楚需求 (Ask Clarifying Questions): 迷宫需要有几条出路? (假定至少1条), 多大的迷宫? 多复杂的迷宫等等.

最容易想到的就是随机生成1和0的地图，其中1是墙，0是空路，不过这种方法生成随机的效率实在是太低，你可以跑了半天也无法生成一个有效的迷宫，我们假定有效的迷宫是至少含一条路径。

def maze(width, height):
    m = None
    while not check(m):
        m = generate_random_matrix(width, height)
    return m

当迷宫无效的时候我们还可以随机的把一些墙变成空格，这样在进行若干次后肯定有路径，不过这样的迷宫不可控，因为很有可能生成的迷宫很稀疏 (Sparse)，一点也不像迷宫。

def maze(width, height):
    m = generate_random_matrix(width, height)
    while not check(m):
       m = remove_a_random_wall(m)
    return m

效率比较高的一种算法是：先随机生成一条或者几条有效路径，然后生成若干条干扰路径，然后再把剩下的填成墙。

在生成路径的时候我们可以从顶部（然后可以旋转或者水平垂直镜像生成其它可能）随机往下左或者右三个方向走，并且我们需要记录走过的格子(哈希集合)，这样就不会重复走。随机走然后直到走出界。生成干扰路径只需要最后面随机在路么中间加堵墙（或者多个）。

当然需要避免在生成干扰路径的时候加的墙也同时把我们需要的有效路径给堵死了，只需要避免在岔口填墙就可以了。

以下是 OpenAI/ChatGPT 给出的解决方案。

• 创建一个迷宫: 创建一个二维数组, 用来表示迷宫的每个位置, 0表示可以通过, 1表示不可以通过.
• 随机生成迷宫: 使用随机数来生成迷宫, 将一定比例的位置设置为1, 其余位置设置为0.
• 添加起点和终点: 将起点和终点的位置设置为0, 以便可以通过.
• 添加障碍物: 在迷宫中添加一些障碍物, 使得起点和终点之间的路径更加复杂.
• 添加传送门: 在迷宫中添加一些传送门, 使得玩家可以从一个位置跳转到另一个位置, 从而更加有趣.

[caption id="attachment_151919" align="alignnone" width="580"] Random Maze Generate Algorithm[/caption]

英文: Teaching Kids Programming – How to Design a Random Maze? Random Maze Generation Algorithm

博文: https://justyy.com/archives/61133