树搜索太多了。迷宫在解的路径上本质上是可分离的。

(感谢Reddit的rainman002为我指出了这一点。)

正因为如此，你可以快速使用连接组件来识别迷宫墙壁的连接部分。这将在像素上迭代两次。

如果您希望将其转换为解决方案路径的漂亮图表，那么您可以使用带有结构化元素的二进制操作来填充每个连接区域的“死胡同”路径。

下面是MATLAB的演示代码。它可以通过调整来更好地清理结果，使其更一般化，并使其运行得更快。(不是凌晨两点半的时候)

% read in and invert the image
im = 255 - imread('maze.jpg');

% sharpen it to address small fuzzy channels
% threshold to binary 15%
% run connected components
result = bwlabel(im2bw(imfilter(im,fspecial('unsharp')),0.15));

% purge small components (e.g. letters)
for i = 1:max(reshape(result,1,1002*800))
    [count,~] = size(find(result==i));
    if count < 500
        result(result==i) = 0;
    end
end

% close dead-end channels
closed = zeros(1002,800);
for i = 1:max(reshape(result,1,1002*800))
    k = zeros(1002,800);
    k(result==i) = 1; k = imclose(k,strel('square',8));
    closed(k==1) = i;
end

% do output
out = 255 - im;
for x = 1:1002
    for y = 1:800
        if closed(x,y) == 0
            out(x,y,:) = 0;
        end
    end
end
imshow(out);

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

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

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

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

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

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

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

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

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

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

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

这里有一个解决方案。

Convert image to grayscale (not yet binary), adjusting weights for the colors so that final grayscale image is approximately uniform. You can do it simply by controlling sliders in Photoshop in Image -> Adjustments -> Black & White. Convert image to binary by setting appropriate threshold in Photoshop in Image -> Adjustments -> Threshold. Make sure threshold is selected right. Use the Magic Wand Tool with 0 tolerance, point sample, contiguous, no anti-aliasing. Check that edges at which selection breaks are not false edges introduced by wrong threshold. In fact, all interior points of this maze are accessible from the start. Add artificial borders on the maze to make sure virtual traveler will not walk around it :) Implement breadth-first search (BFS) in your favorite language and run it from the start. I prefer MATLAB for this task. As @Thomas already mentioned, there is no need to mess with regular representation of graphs. You can work with binarized image directly.

下面是BFS的MATLAB代码:

function path = solve_maze(img_file)
  %% Init data
  img = imread(img_file);
  img = rgb2gray(img);
  maze = img > 0;
  start = [985 398];
  finish = [26 399];

  %% Init BFS
  n = numel(maze);
  Q = zeros(n, 2);
  M = zeros([size(maze) 2]);
  front = 0;
  back = 1;

  function push(p, d)
    q = p + d;
    if maze(q(1), q(2)) && M(q(1), q(2), 1) == 0
      front = front + 1;
      Q(front, :) = q;
      M(q(1), q(2), :) = reshape(p, [1 1 2]);
    end
  end

  push(start, [0 0]);

  d = [0 1; 0 -1; 1 0; -1 0];

  %% Run BFS
  while back <= front
    p = Q(back, :);
    back = back + 1;
    for i = 1:4
      push(p, d(i, :));
    end
  end

  %% Extracting path
  path = finish;
  while true
    q = path(end, :);
    p = reshape(M(q(1), q(2), :), 1, 2);
    path(end + 1, :) = p;
    if isequal(p, start) 
      break;
    end
  end
end

它真的非常简单和标准，在Python或其他语言中实现它应该没有困难。

这就是答案:

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

使用队列进行阈值连续填充。将入口左侧的像素推入队列，然后开始循环。如果一个排队的像素足够暗，它就被显示为浅灰色(高于阈值)，并且所有的邻居都被推到队列上。

from PIL import Image
img = Image.open("/tmp/in.jpg")
(w,h) = img.size
scan = [(394,23)]
while(len(scan) > 0):
    (i,j) = scan.pop()
    (r,g,b) = img.getpixel((i,j))
    if(r*g*b < 9000000):
        img.putpixel((i,j),(210,210,210))
        for x in [i-1,i,i+1]:
            for y in [j-1,j,j+1]:
                scan.append((x,y))
img.save("/tmp/out.png")

解决方案是灰色墙和彩色墙之间的走廊。注意这个迷宫有多种解决方案。而且，这只是看起来有效。