给定图像表示和解决迷宫的最佳方法是什么?
给定一张 JPEG 图像(如上所示),读取它、将其解析为某种数据结构并解决迷宫的最佳方法是什么?我的第一直觉是逐像素读取图像并将其存储在布尔值列表(数组)中:True
对于白色像素,以及False
对于非白色像素(可以丢弃颜色)。这种方法的问题是图像可能不是“像素完美”。我的意思只是说,如果墙上某处有白色像素,它可能会创建一条意外的路径。
另一种方法(经过一番思考后想到)是将图像转换为 SVG 文件 - 这是在画布上绘制的路径列表。这样,路径可以读入相同类型的列表(布尔值),其中True
表示路径或墙壁,False
表示可行驶的空间。如果转换不是 100% 准确,并且没有完全连接所有墙壁,从而产生间隙,则此方法会出现问题。
转换为 SVG 的另一个问题是线条不是“完全”笔直。这导致路径成为三次贝塞尔曲线。使用由整数索引的布尔值列表(数组),曲线将不容易传输,并且必须计算曲线上的所有点,但不会与列表索引完全匹配。
我认为虽然其中一种方法可能有效(尽管可能无效),但考虑到如此大的图像,它们的效率非常低下,并且存在更好的方法。如何最好地(最有效和/或以最小的复杂性)完成此操作?有没有最好的方法?
然后就是迷宫的解决。如果我使用前两种方法中的任何一种,我基本上都会得到一个矩阵。根据这个答案,表示迷宫的一个好方法是使用树,解决它的一个好方法是使用A*算法。如何从图像中创建一棵树?有任何想法吗?
TL;DR
最好的解析方式?变成什么数据结构?所述结构如何帮助/阻碍解决?
UPDATE
我尝试过用 Python 实现 @Mikhail 编写的内容,使用numpy
,正如@Thomas 推荐的那样。我觉得这个算法是正确的,但它并没有像希望的那样工作。 (代码如下。)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, [])