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

(感谢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);

这里有一个解决方案。

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或其他语言中实现它应该没有困难。

这就是答案:

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

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

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

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

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

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

我试着用A-Star搜索来解决这个问题。下面是Joseph Kern对框架和算法伪代码的详细实现:

def AStar(start, goal, neighbor_nodes, distance, cost_estimate):
    def reconstruct_path(came_from, current_node):
        path = []
        while current_node is not None:
            path.append(current_node)
            current_node = came_from[current_node]
        return list(reversed(path))

    g_score = {start: 0}
    f_score = {start: g_score[start] + cost_estimate(start, goal)}
    openset = {start}
    closedset = set()
    came_from = {start: None}

    while openset:
        current = min(openset, key=lambda x: f_score[x])
        if current == goal:
            return reconstruct_path(came_from, goal)
        openset.remove(current)
        closedset.add(current)
        for neighbor in neighbor_nodes(current):
            if neighbor in closedset:
                continue
            if neighbor not in openset:
                openset.add(neighbor)
            tentative_g_score = g_score[current] + distance(current, neighbor)
            if tentative_g_score >= g_score.get(neighbor, float('inf')):
                continue
            came_from[neighbor] = current
            g_score[neighbor] = tentative_g_score
            f_score[neighbor] = tentative_g_score + cost_estimate(neighbor, goal)
    return []

因为a - star是一个启发式搜索算法，你需要想出一个函数来估计剩余的代价(这里是距离)，直到达到目标。除非你对次优解决方案感到满意，否则不应该高估成本。保守的选择是曼哈顿(或出租车)距离，因为它代表了网格上使用的Von Neumann社区的两点之间的直线距离。(在这种情况下，这不会高估成本。)

然而，这大大低估了现有迷宫的实际成本。因此，我添加了另外两个距离度量的平方欧几里得距离和曼哈顿距离乘以4进行比较。然而，这些可能会高估实际成本，因此可能会产生次优结果。

代码如下:

import sys
from PIL import Image

def is_blocked(p):
    x,y = p
    pixel = path_pixels[x,y]
    if any(c < 225 for c in pixel):
        return True
def von_neumann_neighbors(p):
    x, y = p
    neighbors = [(x-1, y), (x, y-1), (x+1, y), (x, y+1)]
    return [p for p in neighbors if not is_blocked(p)]
def manhattan(p1, p2):
    return abs(p1[0]-p2[0]) + abs(p1[1]-p2[1])
def squared_euclidean(p1, p2):
    return (p1[0]-p2[0])**2 + (p1[1]-p2[1])**2

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

# invoke: python mazesolver.py <mazefile> <outputfile>[.jpg|.png|etc.]

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

distance = manhattan
heuristic = manhattan

path = AStar(start, goal, von_neumann_neighbors, distance, heuristic)

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

path_img.save(sys.argv[2])

下面是一些可视化结果的图片(灵感来自Joseph Kern发布的图片)。每次主while循环迭代10000次后，动画都会显示一个新帧。

广度优先搜索:

a星曼哈顿距离:

a星平方欧几里得距离:

a星曼哈顿距离乘以4:

结果表明，对于所使用的启发式方法，迷宫中被探索的区域有很大的不同。因此，欧几里得距离的平方甚至会产生与其他指标不同的(次优)路径。

Concerning the performance of the A-Star algorithm in terms of the runtime until termination, note that a lot of evaluation of distance and cost functions add up compared to the Breadth-First Search (BFS) which only needs to evaluate the "goaliness" of each candidate position. Whether or not the cost for these additional function evaluations (A-Star) outweighs the cost for the larger number of nodes to check (BFS) and especially whether or not performance is an issue for your application at all, is a matter of individual perception and can of course not be generally answered.

A thing that can be said in general about whether or not an informed search algorithm (such as A-Star) could be the better choice compared to an exhaustive search (e.g., BFS) is the following. With the number of dimensions of the maze, i.e., the branching factor of the search tree, the disadvantage of an exhaustive search (to search exhaustively) grows exponentially. With growing complexity it becomes less and less feasible to do so and at some point you are pretty much happy with any result path, be it (approximately) optimal or not.

这个解决方案是用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])

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

我用过的空白迷宫。

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

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

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

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

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