maze

#!/usr/bin/env python
# amazer.py
#So far I've put in about 8 hours
# Copyright 2009 Chase Johnson
# Licensable under WTFPL v2
#http://www.reddit.com/r/programming/comments/a0x8g/hey_reddit_check_out_this_python_maze_solver_i/
"""
Everyone is permitted to copy and distribute verbatim or modified
copies of this license document, and changing it is allowed as long
as the name is changed.

           DO WHAT THE FUCK YOU WANT TO PUBLIC LICENSE
  TERMS AND CONDITIONS FOR COPYING, DISTRIBUTION AND MODIFICATION

 0. You just DO WHAT THE FUCK YOU WANT TO.
"""
import Image
from math import floor
from sys import setrecursionlimit
setrecursionlimit(10000000)
outCount = 0
outLimit = 100000
verbose = False
frameperiod = 200
cleanupFramePeriod = 1000
cleaningUp = False
Up, Down, Left, Right = range(4)
def process(name):
	im = Image.open(name)
	data = im.getdata()
	i = 0
	j = 0
	col = 0
	row = 0
	whitePixelsRight = []
	whitePixelsLeft = []
	whitePixelsUp = []
	whitePixelsDown = []
	pix = im.load()
	for pixel in data:
		i = i + 1
		col = col+1
		if(col > im.size[0]):
			col = 1
			row = row + 1
		j = im.size[0]*row+col
		if(isGreen(pixel)):
			if(isWhite(pix[col-2,row])):
				whitePixelsLeft.append((col-2,row))
			if(isWhite(pix[col-1, row-1])):
				whitePixelsUp.append((col-1,row-1))
			if(isWhite(pix[col, row])):
				whitePixelsRight.append((col,row))
			if(isWhite(pix[col-1, row+1])):
				whitePixelsDown.append((col-1,row+1))

	leftFronts = collect_fronts(whitePixelsLeft)
	rightFronts = collect_fronts(whitePixelsRight)
	upFronts = collect_fronts(whitePixelsUp)
	downFronts = collect_fronts(whitePixelsDown)

	if verbose: print "Number of wavefronts found: ", str(len(rightFronts) + len(leftFronts) + len(upFronts) + len(downFronts))
	move_wavefront(im, pix, rightFronts[0], Right)

def move_wavefront(im, pix, startFront, direction):
	global outCount
	global outLimit
	global cleaningUp
	global verbose
	global frameperiod
	outCount = outCount + 1
	if verbose: print "------------------- OUTPUT FRAME #" + str(outCount) + "-------------------"
	if outCount > outLimit:
		return False
	
	xMotion = 0
	yMotion = 0
	if direction == Right: xMotion = 1
	elif direction == Down: yMotion = 1
	elif direction == Up: yMotion = -1
	elif direction == Left:	xMotion = -1
		
	whitePixelsRight = []
	whitePixelsLeft = []
	whitePixelsUp = []
	whitePixelsDown = []
		
	front = list(startFront)
	if verbose: print "Starting traversal"
	while not front_contains_wall(im, pix, front):
		if verbose: print "no wall still at " + str(front)
		tempFront = []
		for pixel in front:
			pix[pixel[0],pixel[1]] = (0,255,0)
			tempFront.append((pixel[0]+xMotion, pixel[1]+yMotion))
		front = tempFront
		
	foundRed = False	
	#start over and check for fronts
	front = list(startFront)
	if verbose: print "Detecting wavefronts"
	while not front_contains_wall(im, pix, front):
		if verbose: print "no wall still at " + str(front)
		tempFront = []
		for pixel in front:
			tempFront.append((pixel[0]+xMotion, pixel[1]+yMotion))
			if(isGreen(pix[pixel[0],pixel[1]])):
				col = pixel[0]
				row = pixel[1]
				if(isWhite(pix[col-1,row])):
					whitePixelsLeft.append((col-1,row))
					if verbose: print "Found white pixel Left at " + str((col-1,row))
				if(isWhite(pix[col, row-1])):
					whitePixelsUp.append((col,row-1))
					if verbose: print "Found white pixel Up at " + str((col,row-1))
				if(isWhite(pix[col+1, row])):
					whitePixelsRight.append((col+1,row))
					if verbose: print "Found white pixel Up at " + str((col+1,row))
				if(isWhite(pix[col, row+1])):
					whitePixelsDown.append((col,row+1))
					if verbose: print "Found white pixel Up at " + str((col,row+1))
				if(isRed(pix[col-1,row])):
					foundRed = True
					if verbose: print "Found red pixel Left at " + str((col-1,row))
				if(isRed(pix[col, row-1])):
					foundRed = True
					if verbose: print "Found red pixel Up at " + str((col,row-1))
				if(isRed(pix[col+1, row])):
					foundRed = True
					if verbose: print "Found red pixel Up at " + str((col+1,row))
				if(isRed(pix[col, row+1])):
					foundRed = True
					if verbose: print "Found red pixel Up at " + str((col,row+1))	
		front = tempFront
		
	leftFronts = collect_fronts(whitePixelsLeft)
	rightFronts = collect_fronts(whitePixelsRight)
	upFronts = collect_fronts(whitePixelsUp)
	downFronts = collect_fronts(whitePixelsDown)

	numWaves = len(rightFronts) + len(leftFronts) + len(upFronts) + len(downFronts);
	
	if verbose: print "Number of wavefronts found: ", str(numWaves)
	if verbose: print "Left side fronts: "+ str(leftFronts)
	if verbose: print "Right side fronts: "+ str(rightFronts)
	if verbose: print "Up side fronts: "+ str(upFronts)
	if verbose: print "Down side fronts: "+ str(downFronts)
	
	trueReturned = False
	if(outCount % frameperiod == 0):
		im.save("output" + str(outCount).rjust(5, "0")+".png")
	if(cleaningUp and (outCount % cleanupFramePeriod ==0)): 
		im.save("output" + str(outCount).rjust(5, "0")+".png")
		
	if(foundRed):
		if verbose: print "========================== MAZE SOLVED =========================="
		cleaningUp = True
		return True
		
	for front in leftFronts:
		if(move_wavefront(im, pix, front, Left)):
			trueReturned = True
	for front in rightFronts:
		if(move_wavefront(im, pix, front, Right)):
			trueReturned = True
	for front in upFronts:
		if(move_wavefront(im, pix, front, Up)):
			trueReturned = True
	for front in downFronts:
		if(move_wavefront(im, pix, front, Down)):
			trueReturned = True
			
	if not trueReturned:
		if verbose: print "Re-coloring for dead path"
		front = list(startFront)
		while not front_contains_wall(im, pix, front):
			if verbose: print "no wall still at " + str(front)
			tempFront = []
			for pixel in front:
				pix[pixel[0],pixel[1]] = (128,128,128)
				tempFront.append((pixel[0]+xMotion, pixel[1]+yMotion))
			front = tempFront		
	
	if verbose: print "Returning " + str(trueReturned)
	return trueReturned

def front_contains_wall(im, pix, front):
	blackDetected = False
	for pixel in front:
		if isBlack(pix[pixel[0],pixel[1]]):
			blackDetected = True
			break
	return blackDetected

def collect_fronts(array):
	returnArray = []
	for pixel in array:
		added = False
		# check each array in leftFronts for one that contains an adjacent pixel to pixel
		for front in returnArray:
			for testPixel in front:
				if is_adjacent(testPixel, pixel):
					front.append(pixel)
					added = True
					break
		if not added:
			tempArray = [pixel]
			returnArray.append(tempArray)
	return returnArray
	
def is_adjacent(tuple1, tuple2):
	x1, y1 = tuple1
	x2, y2 = tuple2
	
	if x1 == x2 and abs(y1-y2)==1: return True
	elif y1 == y2 and abs(x1-x2)==1: return True
	else: return False
	
def compare_coordinates(tuple1, tuple2):
	x1, y1 = tuple1
	x2, y2 = tuple2
	if x1 > x2:
		return 1
	elif x1 < x2: 
		return -1
	elif x1 == x2: 
		if y1 > y2:
			return 1
		elif y1 < y2:
			return -1
		else: return 0
		
def isWhite(tuple):
	R, G, B = tuple
	return R+G+B > 600

def isBlack(tuple):
	R, G, B = tuple
	return R+G+B < 40

def isGreen(tuple):
	R, G, B = tuple
	return G > 0.8*(R+B)

def isRed(tuple):
	R, G, B = tuple
	return R > 0.8*(G+B)

def isBlue(tuple):
	R, G, B = tuple
	return B > 0.8*(R+G)

process("maze4.png")