casted

#!/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 = ((x, y) for y in range(self.height)
                            for x in 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] = 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')