在给定的图像中，表现和解决迷宫的最佳方法是什么?
Given an JPEG image (as seen above), what's the best way to read it in, parse it into some data structure and solve the maze? My first instinct is to read the image in pixel by pixel and store it in a list (array) of boolean values: True for a white pixel, and False for a non-white pixel (the colours can be discarded). The issue with this method, is that the image may not be "pixel perfect". By that I simply mean that if there is a white pixel somewhere on a wall it may create an unintended path.
另一种方法(经过思考后我想到的)是将图像转换为SVG文件——这是在画布上绘制的路径列表。这样，路径可以读入相同类型的列表(布尔值)，其中True表示路径或墙壁，False表示可移动空间。如果转换不是100%准确，并且没有完全连接所有的墙壁，就会出现一个问题。
转换为SVG的另一个问题是，这些线不是“完全”直的。这导致路径是三次贝塞尔曲线。对于一个由整数索引的布尔值列表(数组)，曲线将不容易转移，并且曲线上的所有点都必须计算，但不会与列表索引完全匹配。
我认为，虽然这些方法中的一种可能有效(虽然可能不是)，但对于如此大的图像，它们的效率非常低，并且存在更好的方法。如何才能做到最好(最有效和/或最简单)?有没有最好的办法?
然后是迷宫的解决。如果我用前两种方法中的任何一种，我最终都会得到一个矩阵。根据这个答案，表示迷宫的好方法是使用树，解决迷宫的好方法是使用a *算法。如何从图像中创建树?什么好主意吗?
博士TL;
最好的解析方法?转换成什么样的数据结构?结构如何帮助/阻碍解决问题?
更新
正如@Thomas推荐的那样，我已经尝试用numpy实现@Mikhail在Python中编写的内容。我觉得这个算法是正确的，但它不像我希望的那样工作。下面(代码)。PNG库为PyPNG。
import png, numpy, Queue, operator, itertools
def is_white(coord, image):
""" Returns whether (x, y) is approx. a white pixel."""
a = True
for i in xrange(3):
if not a: break
a = image[coord[1]][coord[0] * 3 + i] > 240
return a
def bfs(s, e, i, visited):
""" Perform a breadth-first search. """
frontier = Queue.Queue()
while s != e:
for d in [(-1, 0), (0, -1), (1, 0), (0, 1)]:
np = tuple(map(operator.add, s, d))
if is_white(np, i) and np not in visited:
frontier.put(np)
visited.append(s)
s = frontier.get()
return visited
def main():
r = png.Reader(filename = "thescope-134.png")
rows, cols, pixels, meta = r.asDirect()
assert meta['planes'] == 3 # ensure the file is RGB
image2d = numpy.vstack(itertools.imap(numpy.uint8, pixels))
start, end = (402, 985), (398, 27)
print bfs(start, end, image2d, [])
我试着用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])
注意:标记白色访问像素灰色。这消除了访问列表的需要，但这需要在绘制路径之前从磁盘上第二次加载图像文件(如果您不想要最终路径和所有路径的合成图像)。
我用过的空白迷宫。
