Share Pastebin
Guest
Public paste!

casted

By: a guest | Nov 4th, 2009 | Syntax: Python | Size: 1.87 KB | Hits: 92 | Expires: Never
Copy text to clipboard
  1. #!/usr/bin/env python
  2. # Keegan Carruthers-Smith 2009
  3.  
  4. import Image
  5. import itertools
  6. import sys
  7.  
  8. sys.setrecursionlimit(sys.maxint)
  9.  
  10. class MazeSolve(object):
  11.     def __init__(self, in_path, out_path):
  12.         image = Image.open(in_path)
  13.        
  14.         self.width  = image.size[0]
  15.         self.height = image.size[1]
  16.  
  17.         # Transform image into a grid
  18.         grid = {}
  19.         positions = itertools.product(range(self.height), range(self.width))
  20.         for pos, val in zip(positions, image.getdata()):
  21.             r, g, b = val
  22.             s = sum(val)
  23.             if s < 50:
  24.                 v = 'wall'
  25.             elif s > 600:
  26.                 v = 'floor'
  27.             elif r > 100:
  28.                 v = 'end'
  29.             elif g > 100:
  30.                 v = 'start'
  31.             else:
  32.                 v = None
  33.             grid[(pos[1], pos[0])] = v
  34.         self.grid = grid
  35.        
  36.         start_pos = (k for k, v in grid.items() if v == 'start').next()
  37.         assert start_pos
  38.  
  39.         self.pixels = image.load()
  40.         self.seen   = set()
  41.        
  42.         assert self.dfs(start_pos)
  43.  
  44.         image.save(out_path)
  45.  
  46.  
  47.     def dfs(self, pos):
  48.         seen = self.seen
  49.         grid = self.grid
  50.  
  51.         seen.add(pos)
  52.  
  53.         if grid[pos] == 'end':
  54.             return True
  55.  
  56.         for p in self.neighbours(pos):
  57.             if grid[p] == 'wall' or p in seen:
  58.                 continue
  59.            
  60.             if self.dfs(p):
  61.                 self.pixels[p] = (0, 255, 0)
  62.                 return True
  63.  
  64.         return False
  65.  
  66.  
  67.     def neighbours(self, pos):
  68.         for dx, dy in (-1, 0), (1, 0), (0, -1), (0, 1):
  69.             x = pos[0] + dx
  70.             y = pos[1] + dy
  71.  
  72.             if 0 <= x < self.width and 0 <= y < self.height:
  73.                 yield (x, y)
  74.  
  75.  
  76. if __name__ == '__main__':
  77.     MazeSolve('maze4.png', 'maze4_solve.png')