from random import randint
import Image, ImageDraw

HOR = 0
VERT = 1

def szomszedok(hv, x, y):
	global cella, HOR, VERT
	if hv == VERT:
		return cella[y][x-1], cella[y][x]
	if hv == HOR:
		return cella[y-1][x], cella[y][x]

def csere(ezt, erre):
	global cella, cellaszam,sz,m
	for x,y in cellaszam[ezt]:
		cella[y][x] = erre
	cellaszam[erre] += cellaszam[ezt]
	cellaszam[ezt] = []
	return len(cellaszam[erre])

def general():
	global cella, sz,m, HOR, VERT, cellaszam, lab
	lab = ([[1 for horx in range(sz)] for hory in range(m+1) ], [[1 for vertx in range(sz+1)] for verty in range(m) ])
	cella = [[1+y*sz+x for x in range(sz)] for y in range(m) ]
	# also, felso vizszintes es jobb/bal fuggoleges eleket nem vesszuk bele
	fallista = [ (HOR,hory,horx) for hory in range(1,m) for horx in range(sz) ] + [(VERT,verty,vertx) for verty in range(m) for vertx in range(1,sz)  ]
	# kijarat
	lab [VERT][m-1][sz] = 0
	#bejarat
	lab[VERT][0][0] = 0
	cella[0][0] = 0 # bejarat cellaerteke legyen legkisebb
	cellaszam = [[] for y in range(m) for x in range(sz) ]
	cellaszam += [ [] ]
	
	for y in range(m):
		for x in range(sz):
			cellaszam[cella[y][x]].append( (x,y) )
	
	kesz = 0
	ifal = 0
	while not kesz:
		ifal = randint(0,len(fallista)-1)
		hv, y, x = fallista[ifal]
		egyik, masik = szomszedok(hv, x, y)
		if egyik != masik:
			lab[hv][y][x] = 0
			num = csere(max(egyik, masik), min(egyik, masik))
			if num == sz * m:
				kesz = 1
			
		del fallista[ifal]
		if len(fallista) == 0:
			print "!!! elfogytak falak, de nincs kesz"
			kesz = 1
	return lab

def utvonalKeresNorek(xy, xycel):
	global cella, sz, m, HOR, VERT, lab
	x, y = xy
	utvonal = [ [x,y,0] ]
	while len(utvonal) > 0 and (x,y) != xycel:
		x,y,mi = utvonal[-1]
		if 4 == mi: # probaltuk mar minden szomszedjat
			del utvonal[-1]
		elif 3 == mi: # balra probaljunk
			utvonal[-1][2] = 4
			if x > 0 and lab[VERT][y][x] == 0 and 0 == cella[y][x-1]:
				utvonal.append( [x-1,y,0] )
		elif 2 == mi: # lefele probaljunk
			utvonal[-1][2] = 3
			if y < m-1 and lab[HOR][y+1][x] == 0 and 0 == cella[y+1][x]:
				utvonal.append( [x,y+1,0] )
		elif 1 == mi: # jobbra probaljunk
			utvonal[-1][2] = 2
			if x < sz-1 and lab[VERT][y][x+1] == 0 and 0 == cella[y][x+1]:
				utvonal.append( [x+1,y,0] )
		elif 0 == mi: # lefele probaljunk
			cella[y][x] = 1
			utvonal[-1][2] = 1
			if y >0  and lab[HOR][y][x] == 0 and 0 == cella[y-1][x]:
				utvonal.append( [x,y-1,0] )
	return utvonal


def kiirUtvonal(xykezd, xycel, draw, mul):
	global cella
	for y in range(m):
		for x in range(sz):
			cella[y][x] = 0
	utvonal = utvonalKeresNorek(xykezd, xycel)
	for x,y,dummy in utvonal:
		draw.rectangle((mul*(x+1), mul*(y+1), mul*(x+2), mul*(y+2)), fill=210)
	
def kiir():
	global HOR, VERT, lab, sz, m
	mul = 5
	im = Image.new('L', ((sz+2)*mul, (m+2)*mul), 255)
	draw = ImageDraw.Draw(im)
	kiirUtvonal((0,0), (sz-1, m-1), draw, mul)

	for y in range(m+1):
		for x in range(sz):
			if lab[HOR][y][x]:
				draw.line(((x+1)*mul, (y+1)*mul, (x+2)*mul, (y+1)*mul), fill=0)

		if y < m:
			for x in range(sz+1):
				if lab[VERT][y][x]:
					draw.line(((x+1)*mul, (y+1)*mul, (x+1)*mul, (y+2)*mul))
	del draw 
	im.save('labirintus' + str(sz) + 'x' + str(m) + '.png')

sz = 100
m = 100
general()
kiir()