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

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

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

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

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

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

这里有一个解决方案。

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

这就是答案:

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

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")

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

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

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

这里有一些想法。

(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.

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

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

我用过的空白迷宫。

我试着用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 (GitHub)

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

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

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

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

这是一个用R的解。

### download the image, read it into R, converting to something we can play with...
library(jpeg)
url <- "https://i.stack.imgur.com/TqKCM.jpg"
download.file(url, "./maze.jpg", mode = "wb")
jpg <- readJPEG("./maze.jpg")

### reshape array into data.frame
library(reshape2)
img3 <- melt(jpg, varnames = c("y","x","rgb"))
img3$rgb <- as.character(factor(img3$rgb, levels = c(1,2,3), labels=c("r","g","b")))

## split out rgb values into separate columns
img3 <- dcast(img3, x + y ~ rgb)

RGB到灰度，见:https://stackoverflow.com/a/27491947/2371031

# convert rgb to greyscale (0, 1)
img3$v <- img3$r*.21 + img3$g*.72 + img3$b*.07
# v: values closer to 1 are white, closer to 0 are black

## strategically fill in some border pixels so the solver doesn't "go around":
img3$v2 <- img3$v
img3[(img3$x == 300 | img3$x == 500) & (img3$y %in% c(0:23,988:1002)),"v2"]  = 0

# define some start/end point coordinates
pts_df <- data.frame(x = c(398, 399),
                     y = c(985, 26))

# set a reference value as the mean of the start and end point greyscale "v"s
ref_val <- mean(c(subset(img3, x==pts_df[1,1] & y==pts_df[1,2])$v,
                  subset(img3, x==pts_df[2,1] & y==pts_df[2,2])$v))

library(sp)
library(gdistance)
spdf3 <- SpatialPixelsDataFrame(points = img3[c("x","y")], data = img3["v2"])
r3 <- rasterFromXYZ(spdf3)

# transition layer defines a "conductance" function between any two points, and the number of connections (4 = Manhatten distances)
# x in the function represents the greyscale values ("v2") of two adjacent points (pixels), i.e., = (x1$v2, x2$v2)
# make function(x) encourages transitions between cells with small changes in greyscale compared to the reference values, such that: 
# when v2 is closer to 0 (black) = poor conductance
# when v2 is closer to 1 (white) = good conductance
tl3 <- transition(r3, function(x) (1/max( abs( (x/ref_val)-1 ) )^2)-1, 4) 

## get the shortest path between start, end points
sPath3 <- shortestPath(tl3, as.numeric(pts_df[1,]), as.numeric(pts_df[2,]), output = "SpatialLines")

## fortify for ggplot
sldf3 <- fortify(SpatialLinesDataFrame(sPath3, data = data.frame(ID = 1)))

# plot the image greyscale with start/end points (red) and shortest path (green)
ggplot(img3) +
  geom_raster(aes(x, y, fill=v2)) +
  scale_fill_continuous(high="white", low="black") +
  scale_y_reverse() +
  geom_point(data=pts_df, aes(x, y), color="red") +
  geom_path(data=sldf3, aes(x=long, y=lat), color="green")

拖鞋!

这就是如果你不填充一些边界像素会发生的事情(哈!)…

完全披露:在我找到这个问题之前，我问过并回答过一个非常相似的问题。然后通过SO的魔法，发现这是其中一个顶部的“相关问题”。我想我可以用这个迷宫作为一个额外的测试案例……我很高兴地发现，我的答案也适用于这个应用程序，只需要很少的修改。

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