start = (402, 984)
end = (398, 24)
top, right, bottom, left = 22, 793, 986, 7
def forbidden(p):
x, y = p
return x < left or y < top or x > right or y > bottom or im.getpixel(p) == 0
prev = {start: None}
next = [start]
while next:
source = next.pop(0) # 与上一节唯一不同的地方!
if forbidden(source):
continue
if source == end:
break
for ox, oy in ((0, 1), (1, 0), (0, -1), (-1, 0)):
x, y = source
target = (x + ox, y + oy)
if target not in prev:
prev[target] = source
next.append(target)
path = []
p = end
while p in prev:
path.append(p)
p = prev[p]
path = list(reversed(path))
# 淡化背景, 所有像素值除2.
out = maze.point(lambda p: p / 2)
for p in path:
out.putpixel(p, (255, 255, 255))
show(out)