Posted by casted on Wed 4 Nov 21:17
report abuse | View followups from casted and casted | download | new post
- #!/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')
Submit a correction or amendment below (click here to make a fresh posting)
After submitting an amendment, you'll be able to view the differences between the old and new posts easily.