pastebin - collaborative debugging

pastebin is a collaborative debugging tool allowing you to share and modify code snippets while chatting on IRC, IM or a message board.

This site is developed to XHTML and CSS2 W3C standards. If you see this paragraph, your browser does not support those standards and you need to upgrade. Visit WaSP for a variety of options.

Python pastebin - collaborative debugging tool View Help


Posted by casted on Wed 4 Nov 21:17
report abuse | View followups from casted and casted | download | new post

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

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.

Syntax highlighting:

To highlight particular lines, prefix each line with @@


Remember me so that I can delete my post