好的解决方案是，不是通过像素来寻找邻居，而是通过单元格来完成，因为一个走廊可以有15px，所以在同一个走廊中，它可以采取向左或向右的动作，而如果它像一个立方体一样进行位移，它将是一个简单的动作，如向上，向下，向左或向右

来吧:迷宫-求解器-python (GitHub)

我玩得很开心，并扩展了约瑟夫·克恩的答案。不要贬低它;我只是为其他人做了一些小的补充，谁可能有兴趣玩这个。

这是一个基于python的求解器，它使用BFS来查找最短路径。当时我的主要补充内容是:

图像在搜索(即。转换为纯黑白) 自动生成GIF。 自动生成AVI。

就目前情况而言，这个示例迷宫的开始/结束点是硬编码的，但我计划扩展它，以便您可以选择适当的像素。

好的解决方案是，不是通过像素来寻找邻居，而是通过单元格来完成，因为一个走廊可以有15px，所以在同一个走廊中，它可以采取向左或向右的动作，而如果它像一个立方体一样进行位移，它将是一个简单的动作，如向上，向下，向左或向右

我会选择矩阵-布尔斯。如果您发现标准的Python列表在这方面效率太低，您可以使用numpy。改为Bool数组。一个1000x1000像素的迷宫的存储空间只有1mb。

不要费心创建任何树或图数据结构。这只是思考它的一种方式，但不一定是在记忆中表示它的好方法;布尔矩阵更容易编码，效率更高。

然后用A*算法求解。对于距离启发式，使用曼哈顿距离(distance_x + distance_y)。

用(行，列)坐标的元组表示节点。每当算法(维基百科伪代码)调用“邻居”时，循环四个可能的邻居就很简单了(注意图像的边缘!)。

如果你发现它仍然太慢，你可以在加载它之前尝试缩小图像的比例。小心不要在这个过程中丢失任何狭窄的路径。

也许在Python中也可以进行1:2的降尺度，以检查实际上没有丢失任何可能的路径。一个有趣的选择，但它需要更多的思考。

这个解决方案是用Python编写的。感谢米哈伊尔对图像准备的指导。

一个动画宽度优先搜索:

完成的迷宫:

#!/usr/bin/env python

import sys

from Queue import Queue
from PIL import Image

start = (400,984)
end = (398,25)

def iswhite(value):
    if value == (255,255,255):
        return True

def getadjacent(n):
    x,y = n
    return [(x-1,y),(x,y-1),(x+1,y),(x,y+1)]

def BFS(start, end, pixels):

    queue = Queue()
    queue.put([start]) # Wrapping the start tuple in a list

    while not queue.empty():

        path = queue.get() 
        pixel = path[-1]

        if pixel == end:
            return path

        for adjacent in getadjacent(pixel):
            x,y = adjacent
            if iswhite(pixels[x,y]):
                pixels[x,y] = (127,127,127) # see note
                new_path = list(path)
                new_path.append(adjacent)
                queue.put(new_path)

    print "Queue has been exhausted. No answer was found."


if __name__ == '__main__':

    # invoke: python mazesolver.py <mazefile> <outputfile>[.jpg|.png|etc.]
    base_img = Image.open(sys.argv[1])
    base_pixels = base_img.load()

    path = BFS(start, end, base_pixels)

    path_img = Image.open(sys.argv[1])
    path_pixels = path_img.load()

    for position in path:
        x,y = position
        path_pixels[x,y] = (255,0,0) # red

    path_img.save(sys.argv[2])

注意:标记白色访问像素灰色。这消除了访问列表的需要，但这需要在绘制路径之前从磁盘上第二次加载图像文件(如果您不想要最终路径和所有路径的合成图像)。

我用过的空白迷宫。

这里有一些想法。

(1。图像处理:)

1.1将图像加载为RGB像素图。在c#中，使用system.drawing.bitmap是很简单的。在不支持简单成像的语言中，只需将图像转换为可移植像素图格式(PPM)(一种Unix文本表示，产生大文件)或一些容易读取的简单二进制文件格式，如BMP或TGA。Unix中的ImageMagick或Windows中的IrfanView。

1.2如前所述，您可以将数据简化，将每个像素的(R+G+B)/3作为灰度调的指标，然后将其阈值设置为黑白表。假设0=黑，255=白，那么接近200的值就可以去掉JPEG工件。

(2)。解决方案:)

2.1深度优先搜索:初始化一个空堆栈起始位置，收集可用的后续移动，随机选择一个并推入堆栈，直到到达终点或死角。在通过弹出堆栈的死胡同回溯中，你需要跟踪地图上访问的位置，这样当你收集可用的移动时，你就不会重复相同的路径。制作动画很有趣。

2.2广度优先搜索:前面提到过，类似于上面，但只是使用队列。动画也很有趣。这就像图像编辑软件中的洪水填充。我认为你可以用这个技巧在Photoshop中解决一个迷宫。

2.3墙的追随者:从几何上讲，迷宫是一个折叠/弯曲的管子。如果你把手放在墙上，你最终会找到出口。这并不总是有效。有一些假设关于:完美的迷宫，等等，例如，某些迷宫包含岛屿。一定要查一下;这很吸引人。

(3)。评论:)

This is the tricky one. It is easy to solve mazes if represented in some simple array formal with each element being a cell type with north, east, south and west walls and a visited flag field. However given that you are trying to do this given a hand drawn sketch it becomes messy. I honestly think that trying to rationalize the sketch will drive you nuts. This is akin to computer vision problems which are fairly involved. Perhaps going directly onto the image map may be easier yet more wasteful.