casted

#!/usr/bin/env python
# Keegan Carruthers-Smith 2009

import Image
import itertools
import sys

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.seen   = set()

        assert self.dfs(start_pos)

        image.save(out_path)


    def dfs(self, pos):
        seen = self.seen
        grid = self.grid

        seen.add(pos)

        if grid[pos] == 'end':
            return True

        for p in self.neighbours(pos):
            if grid[p] == 'wall' or p in seen:
                continue

            if self.dfs(p):
                self.pixels[p] = (0, 255, 0)
                return True

        return False


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