#!/usr/bin/env python
# Keegan Carruthers-Smith 2009
import Image
import itertools
import sys
from collections import deque
sys.setrecursionlimit(sys.maxint)
class MazeSolve(object):
def __init__(self, in_path, out_path):
image = Image.open(in_path)
self.width = image.size[0]
self.height = image.size[1]
# Transform image into a grid
grid = {}
positions = itertools.product(range(self.height), range(self.width))
for pos, val in zip(positions, image.getdata()):
r, g, b = val
s = sum(val)
if s < 50:
v = 'wall'
elif s > 600:
v = 'floor'
elif r > 100:
v = 'end'
elif g > 100:
v = 'start'
else:
v = None
grid[(pos[1], pos[0])] = v
self.grid = grid
start_pos = (k for k, v in grid.items() if v == 'start').next()
assert start_pos
self.pixels = image.load()
self.bfs(start_pos)
image.save(out_path)
def bfs(self, pos):
grid = self.grid
pixels = self.pixels
parent = {}
# Push pos onto the queue, so we can start searching from there.
queue = deque([pos])
parent[pos] = None
while queue:
pos = queue.popleft()
if grid[pos] == 'end':
break
for p in self.neighbours(pos):
if grid[p] == 'wall' or p in parent:
continue
parent[p] = pos
queue.append(p)
while pos:
pixels[pos] = (0, 255, 0)
pos = parent[pos]
def neighbours(self, pos):
for dx, dy in (-1, 0), (1, 0), (0, -1), (0, 1):
x = pos[0] + dx
y = pos[1] + dy
if 0 <= x < self.width and 0 <= y < self.height:
yield (x, y)
if __name__ == '__main__':
MazeSolve('maze4.png', 'maze4_solve.png')