import pygame, math, sys, random
import maze
RANGE_X = 1680;
RANGE_Y = 1000;

COL_UNVISITED = (0,0,0)
COL_VISITED = (255,255,255)

class Coord(object):
	x = 0
	y = 0
	visited = False
	def __init__(self, x, y):
		self.x = x;
		self.y = y;

	def __repr__(self):
		return "(X:" + str(self.x) + ",Y:" + str(self.y) + ",V:" + str(self.visited) + ")"

	def isVisited(self):
		return self.visited

	def visit(self, surface, visitFrom):
		self.visited = True
		surface.set_at(((self.x*2)+1,(self.y*2)+1),COL_VISITED)
		surface.set_at(((visitFrom.x*2)+1,(visitFrom.y*2)+1),COL_VISITED)
		getDir = (visitFrom.x - self.x,visitFrom.y - self.y)
		surface.set_at(((self.x*2+1)+getDir[0],(self.y*2+1)+getDir[1]),COL_VISITED)

def getDirection((x1,y1),(x2,y2)):
	d = (x1 - x2,y1 - y2)
	if(d[0] == 0 and d[1] < 0):
		return 0;
	if(d[0] > 0 and d[1] == 0):
		return 1;
	if(d[0] == 0 and d[1] > 0):
		return 2;
	if(d[0] < 0 and d[1] == 0):
		return 3;

def getNeighbours(x,y):
	nbpos = [(x,y-1),(x+1,y),(x,y+1),(x-1,y)]
	neighbours = [(0,0) for i in xrange(4)]
	for (vx,vy) in nbpos:
		if(vx >= 0 and vx < RANGE_X/4):
			if(vy >= 0 and vy < RANGE_Y/4):
				neighbours[getDirection((vx,vy),(x,y))] = (vx,vy)
	return neighbours

def isValidNeighbour(d,nbs):
	if d < 0:
		return False
	if nbs[d] == (0,0):
		return False
	else:
		return True

def getFreeNeighbours(field,x,y):
	nbs = getNeighbours(x,y)
	neighbours = []
	for (vx,vy) in nbs:
		if(vx+vy > 0):
			coord = field[vx][vy]
			if (coord.isVisited()) == False:
				neighbours.append(coord)
	return neighbours

def constructMaze(surface):
	history = []
	step = 0
	maxl = 0
	p = field[0][0]
	history.append(p)
	p.visit(surface,field[1][0])
	while 1:
		step+=1
		nbs = getFreeNeighbours(field,p.x,p.y)
		rnd = -1
		np = p
		pygame.time.delay(100)
		if(step%30==0):
			#pygame.time.delay(100)
			pygame.transform.scale(screenbuf,(RANGE_X+1, RANGE_Y+1),screen)
			pygame.display.update()
		if(len(nbs)-1) >= 0:
			rnd = random.randint(0,len(nbs)-1)
			np = field[nbs[rnd].x][nbs[rnd].y]
			np.visit(surface,p)
			p = np
			history.append(p)
		else:
			if(len(history) > maxl):
				maxl = len(history)
			history.remove(np)
			p = history[len(history)-2]
		if(len(history) == 1):
			#pygame.time.delay(200)
			pygame.transform.scale(screenbuf,(RANGE_X+1, RANGE_Y+1),screen)
			pygame.display.update()
			print("Done! step count: " + str(step))
			print("Max history length: " + str(maxl))
			break
	return field

screen = pygame.display.set_mode((RANGE_X+1, RANGE_Y+1))
screenbuf = pygame.Surface(((RANGE_X/2)+1, (RANGE_Y/2)+1))
field = [[Coord(x,y) for y in xrange(RANGE_Y/2)] for x in xrange(RANGE_X/2)]
screen.fill(COL_UNVISITED)
pygame.display.update()
bg = pygame.Surface((6,6))

while 1:
	for event in pygame.event.get():
		if event.type == (pygame.QUIT):
			sys.exit()
		if event.type == (pygame.KEYDOWN):
			constructMaze(screenbuf)
	pygame.display.update()
	pygame.time.delay(1000)