#!/usr/bin/python
# Picture Evolution -- in Python!
# Version 0.8
# by Jason Thibeault
# 	... not that I should be bragging about this.  :)

import os
try:
	import Numeric as N
	import pygame
	from random import Random
	from pygame.locals import *
	from time import sleep
	import math
	import copy
	#import Image
except ImportError:
	raise ImportError, "Could not import Numeric, Copy, PyGame, Random or Math.  Please ensure these are installed with your Python environment."

txtTargetFile = "megaman.png"

MALE = 0
FEMALE = 1
genderarray = ("M","F")

#parameters for the population
popWidth = 100 # how wide the creature is
popHeight = 100 # how tall the creature is
popSize = 21  # this is the number of creatures to max the population out at
popGenerations = 999999 #number of generations to simulate 
popMinChanceEaten = 0
popMaxChanceEaten = 95

popSelection = 'Brutal' # either Linear, Halfcurve, or Brutal
	#Linear = chance of being eaten is a linear chance between min and max
	#Halfcurve = steep but gradiated curve with much higher chance of being eaten for less fit, lower but non-zero for better fit
	#Brutal = bottom half of fitness list gets eaten, period
	
popUnlucky = 3 # percentage of "unlucky" deaths that have nothing to do with your fitness
popMin = [0,0]
popMin[MALE] = 2
popMin[FEMALE] = 2

#parameters for the random factors
polyMinPoints = 3
polyMaxPoints = 7
polyColorShift = 50
genMinChanceMaleKids = 20
genMaxChanceMaleKids = 80
genDefChanceMaleKids = 50
genMinGeneticDrift = 3
genMaxGeneticDrift = 8
genDefGeneticDrift = 3
genMaxPolygons = 50
genBGColorShift = 50 #how much color should be able to shift when background gets mutated
# this is for how likely it is a polygon passes in its entirety
brdPercentMalePolygon = 40 
brdPercentFemalePolygon = 40
#the remainder is for hybrid polygons

#mutation chances -- should all add up to (nearly) 100%, the remainder is the chance of a dud mutation
mutBGChange = 10
mutGainPoly = 28
mutLosePoly = 5
mutChangePoly = 20
mutShufflePoly = 12
mutChangeDrift = 10
mutChangeMaleChance = 10
#remainder from all these is dud chance

VerboseDebug = False
Debug = True

Metrics = True

screenwidth = 790
screenheight = 640
screen = pygame.display.set_mode((screenwidth,screenheight), DOUBLEBUF|HWSURFACE) #FULLSCREEN|

RNG = Random()


class Polygon:
	def __init__(self,**options):
		self.alpha = options.get("alpha",0) 				#default to opaque if not specified
		self.color = options.get("color",(0,0,0)) 			#default to black if not specified
		self.points = options.get("points",[(0,0),(0,0),(0,0)]) 	#default to three points, all zeroed, meaning a useless polygon

class PicDNA:
	def __init__(self,**options):
		self.gender = options.get("gender", MALE) 			#default to male if not specified coz I'm sexist
		self.geneticdrift = options.get("geneticdrift", genDefGeneticDrift) 		#default to lowest if not specified
		self.chancemalekids = options.get("chancemalekids", genDefChanceMaleKids) 	#default to 50% if unspecified
		self.bgcolor = options.get("bgcolor",(0,0,0))			#default to black if unspecified
		self.numpolygons = options.get("numpolygons",0)			#default to no polygons
		self.polygon = range(0, self.numpolygons)
		for i in range(0, self.numpolygons):				#read polygons from list, or initialize to a blank one otherwise
			self.polygon[i] = options.get("poly" + str[i], Polygon())

class Picture:
	def __init__(self,**options):
		self.DNA = options.get("dna",PicDNA())
		self.picdata = RenderImage(self.DNA)
		self.fitness = 0 #just initializing the data, not always used depending on the routine
		self.chanceeaten = 0 #ditto
		self.eaten = False #ditto
		self.unlucky = False #ditto
		self.age = 1 #ditto

def GenerateRandomDNA():
	gendna = PicDNA()
	gendna.gender = RNG.randint(0,1) 	#random male or female (0 or 1)
	gendna.geneticdrift = RNG.randint(polyMinPoints,polyMaxPoints)
	gendna.chancemalekids = RNG.randint(genMinChanceMaleKids,genMaxChanceMaleKids)
	gendna.bgcolor = (RNG.randint(0,255),RNG.randint(0,255),RNG.randint(0,255))
	gendna.numpolygons = RNG.randint(0,genMaxPolygons)
	gendna.polygon = range(0, gendna.numpolygons)
	for i in range(0,gendna.numpolygons):
		numpoints = RNG.randint(polyMinPoints,polyMaxPoints)
		point = range(0,numpoints)
		for j in range(0, numpoints):
			point[j] = (RNG.randint(1,popWidth),RNG.randint(1,popHeight))
		randalpha = RNG.randint(0,255)
		randcolor = (RNG.randint(0,255),RNG.randint(0,255),RNG.randint(0,255))
		gendna.polygon[i]= Polygon(alpha = randalpha, color = randcolor, points = point[:])
	return copy.deepcopy(gendna)

def MutateDNA(dna = PicDNA()):
	for i in range(1, dna.geneticdrift + 1):
		if VerboseDebug: print "mutation #" + str(i)
		whichmutation = RNG.randint(1,100)

		cumulativeChance = 0
		if whichmutation<=mutBGChange: # background color shift
			if VerboseDebug: print "mutating bg color shift"	
			minred = dna.bgcolor[0]-genBGColorShift
			maxred = dna.bgcolor[0]+genBGColorShift
			if minred < 0: minred = 0
			if maxred > 255: maxred = 255
		
			mingreen = dna.bgcolor[1]-genBGColorShift
			maxgreen = dna.bgcolor[1]+genBGColorShift
			if mingreen < 0: mingreen = 0
			if maxgreen > 255: maxgreen = 255

			minblue = dna.bgcolor[2]-genBGColorShift
			maxblue = dna.bgcolor[2]+genBGColorShift
			if minblue < 0: minblue = 0
			if maxblue > 255: maxblue = 255

			dna.bgcolor = (RNG.randint(minred,maxred), RNG.randint(mingreen,maxgreen), RNG.randint(minblue,maxblue))
		cumulativeChance += mutBGChange
		
		if whichmutation>cumulativeChance and whichmutation <= (cumulativeChance + mutGainPoly): # gain a polygon
			if VerboseDebug: print "adding a polygon"
			#randomize a polygon
			if dna.numpolygons < genMaxPolygons:
				numpoints = RNG.randint(polyMinPoints,polyMaxPoints)
				point = range(0,numpoints)
				for j in range(0, numpoints):
					point[j] = (RNG.randint(1,popWidth),RNG.randint(1,popHeight))
				randalpha = RNG.randint(0,255)
				randcolor = (RNG.randint(0,255),RNG.randint(0,255),RNG.randint(0,255))
				dna.polygon.insert(RNG.randint(0,dna.numpolygons),Polygon(alpha = randalpha, color = randcolor, points = point[:]))
				dna.numpolygons += 1
		cumulativeChance += mutGainPoly

		if whichmutation>cumulativeChance and whichmutation<=(cumulativeChance + mutLosePoly): # remove a polygon
			if VerboseDebug: print "removing a polygon"
			if dna.numpolygons > 0:
				dna.numpolygons -= 1
				del dna.polygon[RNG.randint(0,dna.numpolygons)]
		cumulativeChance += mutLosePoly

		if whichmutation>cumulativeChance and whichmutation<=(cumulativeChance + mutChangePoly): # change a polygon
			if VerboseDebug: print "changing a polygon"
			#this one is complicated - first pick a polygon
			if dna.numpolygons > 0:
				whichpoly = RNG.randint(0,dna.numpolygons-1)
				if VerboseDebug: print " whichpoly = " + str(whichpoly) + ", numpolys = " + str(dna.numpolygons)
				for i in range(0, 2):
					whichpolychange = RNG.randint(1,5)
					if whichpolychange==1: # add a point
						if VerboseDebug: print " -- add a point"
						if len(dna.polygon[whichpoly].points)<10:
							wheretoinsert=RNG.randint(0,len(dna.polygon[whichpoly].points)-1)
							dna.polygon[whichpoly].points.insert(wheretoinsert,(RNG.randint(1,popWidth),RNG.randint(1,popHeight)))	

					if whichpolychange==2: # remove a point	
						if VerboseDebug: print " -- remove a point"
						if len(dna.polygon[whichpoly].points)>polyMinPoints:
							whichtodelete=RNG.randint(0,len(dna.polygon[whichpoly].points)-1)
							del dna.polygon[whichpoly].points[whichtodelete]
	
					if whichpolychange==3: # change a point
						if VerboseDebug: print " -- change a point"
						whichtochange=RNG.randint(0,len(dna.polygon[whichpoly].points)-1)
						dna.polygon[whichpoly].points[whichtochange] = (RNG.randint(1,popWidth),RNG.randint(1,popHeight))
	
					if whichpolychange==4: # change color
						if VerboseDebug: print " -- change color"
						minred = dna.polygon[whichpoly].color[0]-polyColorShift
						maxred = dna.polygon[whichpoly].color[0]+polyColorShift
						if minred < 0: minred = 0
						if maxred > 255: maxred = 255
			
						mingreen = dna.polygon[whichpoly].color[1]-polyColorShift
						maxgreen = dna.polygon[whichpoly].color[1]+polyColorShift
						if mingreen < 0: mingreen = 0
						if maxgreen > 255: maxgreen = 255
	
						minblue = dna.polygon[whichpoly].color[2]-polyColorShift
						maxblue = dna.polygon[whichpoly].color[2]+polyColorShift
						if minblue < 0: minblue = 0
						if maxblue > 255: maxblue = 255
	
						dna.polygon[whichpoly].color = (RNG.randint(minred,maxred), RNG.randint(mingreen,maxgreen), RNG.randint(minblue,maxblue))

					if whichpolychange==5: # change alpha
						if VerboseDebug: print " -- change alpha"
						dna.polygon[whichpoly].alpha = RNG.randint(0,255)
		cumulativeChance += mutChangePoly

		if whichmutation>cumulativeChance and whichmutation<=(cumulativeChance + mutShufflePoly): # rearrange polygons
			if VerboseDebug: print "rearranging polygons"
			RNG.shuffle(dna.polygon)
		cumulativeChance += mutShufflePoly

		if whichmutation>cumulativeChance and whichmutation<=(cumulativeChance + mutChangeDrift): # genetic drift change
			if VerboseDebug: print "changing genetic drift rate"
			dna.geneticdrift += RNG.randint(-2,2)
			if dna.geneticdrift > genMaxGeneticDrift: dna.geneticdrift = genMaxGeneticDrift
			if dna.geneticdrift < genMinGeneticDrift: dna.geneticdrift = genMinGeneticDrift
		cumulativeChance += mutChangeDrift

		if whichmutation>cumulativeChance and whichmutation<=(cumulativeChance + mutChangeMaleChance): # gender percentage change
			if VerboseDebug: print "changing chance of male kids"
			dna.chancemalekids += RNG.randint(-10,10)
			if dna.chancemalekids > genMaxChanceMaleKids: dna.chancemalekids = genMaxChanceMaleKids
			if dna.chancemalekids < genMinChanceMaleKids: dna.chancemalekids = genMinChanceMaleKids
		cumulativeChance += mutChangeMaleChance

		if whichmutation>cumulativeChance: # dud!
			if VerboseDebug: print "this mutation did nothing"

	return dna

def RenderImage(dna = PicDNA()):
	picture = pygame.Surface((popWidth,popHeight),pygame.SRCALPHA,32)
	scratchspace = pygame.Surface((popWidth,popHeight),pygame.SRCALPHA,32)
	picture.fill(dna.bgcolor)
	
	clock = pygame.time.Clock()
	scratchspace.convert_alpha(picture)

	for i in range(0, dna.numpolygons):
		scratchspace.fill((0,0,0,0))
		if VerboseDebug: print "** rendering polygon #" + str(i) + ", out of numpolygons " + str(dna.numpolygons)
		pygame.draw.polygon(scratchspace, (dna.polygon[i].color[0],dna.polygon[i].color[1],dna.polygon[i].color[2],dna.polygon[i].alpha), dna.polygon[i].points)
		picture.blit(scratchspace,(0,0))
	return picture

def DebugprintDNA(dna = PicDNA()):
	#this is for if Debug: printing all the attributes of a picture's DNA to the debug prompt
	if Debug: 
		print "Gender: " + str(genderarray[dna.gender])
		print "Genetic drift level: " + str(dna.geneticdrift)
		print "Chance of male children: " + str(dna.chancemalekids)
		print "Background color: " + str(dna.bgcolor)
		print "Number of polygons: " + str(dna.numpolygons)
	for i in range(0, dna.numpolygons):
		if Debug: print " - polygon " + str(i) + ":  alpha " + str(dna.polygon[i].alpha) + ", color " + str(dna.polygon[i].color) + ", points " + str(dna.polygon[i].points)

def CheckFitness(pic = pygame.Surface((1,1)), environment = pygame.Surface((1,1))):
	if VerboseDebug: print "checking fitness"
	fitness = 0
	for y in range(1,popHeight):
		for x in range(1,popWidth):
			pixelgenerated = pic.get_at((x,y))
			pixeltarget = environment.get_at((x,y))
			deltaRed = pixelgenerated[0] - pixeltarget[0]
			deltaGreen = pixelgenerated[1] - pixeltarget[1]
			deltaBlue = pixelgenerated[2] - pixeltarget[2]
			fitness += (deltaRed * deltaRed) + (deltaGreen * deltaGreen) + (deltaBlue * deltaBlue)
	#lower numbers are better fit -- less delta between them
	return fitness

def main():
	# Initialise screen
	pygame.init()

	clock = pygame.time.Clock()

	pygame.display.set_caption('Let\'s randomly generate a picture')

	DoStuff()
	#TestBreeding()
	#TestFitness()

	pygame.display.flip()

	running = True

	# Keypress event loop
	while running:

	        #input handling
	        for event in pygame.event.get():
	        	if event.type == KEYDOWN:
	        		if event.key == K_ESCAPE:
                			running = False
				if event.key == K_SPACE:
					#TestBreeding()
					pygame.display.flip()

	        	if event.type == QUIT:
        			running = False

def DoStuff():

	if Debug: print " - Beginning picture-evolution - "	
	#generate initial $popSize random population entries
	population = range(0,popSize);
	for i in range(0,popSize):
		population[i] = Picture(dna = GenerateRandomDNA());

	picTarget = pygame.transform.scale(pygame.image.load(txtTargetFile), (popWidth,popHeight))
	picGen = Picture(dna = GenerateRandomDNA())

    	# debug font
    	font = pygame.font.Font("tahoma.ttf", 10)
	fontmed = pygame.font.Font("tahoma.ttf",32)
	fontbig = pygame.font.Font("tahoma.ttf",64)

	if Metrics: 
		metriccsv = open(os.path.join("output","metric.csv"),"w")
		metriccsv.write('Generation, # Males, # Females, Avg Fitness, # Eaten, # Unlucky\n') 

	#stuff needed for within the loop that can be pre-calculated
	chancestep = (popMaxChanceEaten - popMinChanceEaten) / popSize
	if VerboseDebug: print "max chance for linear curve (if used): " + str(popMaxChanceEaten) + ", min chance: " + str(popMinChanceEaten) + ", chance step: " + str(chancestep)
	

	numDisplayRows = int(popSize / 7)+ 1 #min one row, seven per row

	displaypos = range(0,popSize)
	for i in range(0,popSize):
		displaypos[i] = (((((i+7)%7)*110)+10),((int(i/7)+1)*130)) # FIXME - needs to take into account picture width and height, and break out row size to a variable

	breakoutofloop = False
	for gen in range(1,popGenerations): #max number of generations
		sleep(0) #for niceness!
		if Debug: print " ************   G E N E R A T I O N   " + str(gen) + " ************ "
		if Metrics: metriccsv.write('%d, ' % (gen))
		#test everyone's fitness, count number of males and number of females, build a fitness array
		numgender = [0,0]
		fitnessarray = range(0,popSize)
		for i in range(0,popSize):
			population[i].fitness = CheckFitness(picTarget, population[i].picdata)
			if population[i].DNA.gender == MALE: numgender[MALE] += 1 
			else: numgender[FEMALE] += 1
			fitnessarray[i] = [population[i].fitness,i]
		if Debug: print "number of females: %d, number of males: %d" % (numgender[FEMALE],numgender[MALE])
		if Metrics: metriccsv.write('%d, %d, ' % (numgender[MALE],numgender[FEMALE]))

		if Debug: print "Fitness of each picture: " + str(fitnessarray)

		#sort the fitness array and assign a chance of being eaten to each picture
		fitnessarray.sort()
		for i in range(0,popSize):
			#assign based on selection method
			if popSelection == 'Linear': 
				population[fitnessarray[i][1]].chanceeaten = popMinChanceEaten + (i*chancestep)
			if popSelection == 'HalfCurve':
				population[fitnessarray[i][1]].chanceeaten = ((popMaxChanceEaten-popMinChanceEaten)/((popSize-i))+popMinChanceEaten) #this gives a non-linear curve with harsh chances for least fit
			if popSelection == 'Brutal':
				if i < (popSize/2):
					population[fitnessarray[i][1]].chanceeaten = 0
				else:
					population[fitnessarray[i][1]].chanceeaten = 100
			
			if VerboseDebug: print "population index %d chance eaten: %d" % (fitnessarray[i][1], population[fitnessarray[i][1]].chanceeaten)

		#finally, evaluate each chance of being eaten / unlucky until down to minimum for that population's gender
		# -- note making a population floor for a gender is a necessary but evil bit of forcing, given the population's so small and we don't
		#    want either the population to bottom out and end the sim, nor do we want the gene pool to dwindle to the point where the entire population
		#    is wiped out and the only genes left in the pool are those of a progenitor that survived being wiped out
		deadpool = []
		for i in range(0,popSize):
			if numgender[population[i].DNA.gender] > popMin[population[i].DNA.gender]:
				eatenroll = RNG.randint(0,100)
				if VerboseDebug: print "picture %d: roll %d, chance eaten %d" % (i, eatenroll, population[i].chanceeaten)
				if eatenroll < population[i].chanceeaten: #survives on a tie
					population[i].eaten = True
					deadpool.append(i)
					if Debug: print "picture " + str(i) + " was eaten!"
				else:
					unluckyroll = RNG.randint(0,100) # reroll for luck, don't bother with this if it doesn't survive being eaten first
					if VerboseDebug: print "picture " + str(i) + ": roll " + str(unluckyroll) + ", chance unlucky " + str(popUnlucky)
					if unluckyroll < popUnlucky: #unlucky chance, survives on a tie
						population[i].unlucky = True
						deadpool.append(i)
						if Debug: print "picture " + str(i) + " was unlucky and died!"
					else:
						population[i].age += 1						
						if VerboseDebug: print "picture %d survived, incrementing age to %d" % (i, population[i].age)
			else:
				if Debug: print "couldn't test picture %d as population floor of %d for %s gender was reached" % (i, popMin[population[i].DNA.gender], genderarray[population[i].DNA.gender])

		deadpool.reverse() #reverse them for easier deleting later
		if Debug: print "deadpool: " + str(deadpool)
		
		#display them all on-screen, max 7 to a row
		screen.fill((255,255,255))
		titleprint = fontbig.render("Gen " + str(gen), 1, (0,0,128))
		titlepos = titleprint.get_rect()
		titlepos.left = 20
		titlepos.top = 10
		screen.blit(titleprint,titlepos)
		screen.blit(picTarget, (650,10))
		averagefitness = 0
		numeaten = 0
		numunlucky = 0
		for i in range(0,popSize):
			sleep(0) #for niceness!
			screen.blit(population[i].picdata,displaypos[i])
			infoprint = font.render(str(genderarray[population[i].DNA.gender]) + " age: %d  fit: %d" % (population[i].age, population[i].fitness),1,(0,0,0))
			infopos = infoprint.get_rect()
			infopos.left = displaypos[i][0]
			infopos.top = displaypos[i][1]+101
			screen.blit(infoprint,infopos)
			if population[i].eaten: 
				pygame.draw.line(screen, (192,0,0), displaypos[i], (displaypos[i][0]+100,displaypos[i][1]+100), 3)
				pygame.draw.line(screen, (192,0,0), (displaypos[i][0]+100,displaypos[i][1]), (displaypos[i][0],displaypos[i][1]+100), 3)
				infoprint = font.render("Eaten!",1,(192,0,0))
				infopos = infoprint.get_rect()
				infopos.left = displaypos[i][0]
				infopos.top = displaypos[i][1]+112
				screen.blit(infoprint,infopos)
				numeaten += 1
			if population[i].unlucky: 
				pygame.draw.line(screen, (128,0,255), displaypos[i], (displaypos[i][0]+100,displaypos[i][1]+100), 3)
				pygame.draw.line(screen, (128,0,255), (displaypos[i][0]+100,displaypos[i][1]), (displaypos[i][0],displaypos[i][1]+100), 3)
				infoprint = font.render("Unlucky!",1,(128,0,255))
				infopos = infoprint.get_rect()
				infopos.left = displaypos[i][0]
				infopos.top = displaypos[i][1]+112
				screen.blit(infoprint,infopos)
				numunlucky += 1

			averagefitness += population[i].fitness
		
		averagefitness = averagefitness/popSize		
		if Metrics: metriccsv.write('%d, %d, %d\n' % (averagefitness, numeaten, numunlucky))

		if Debug: print "Average fitness of this generation: %d" % averagefitness

		fitnessprint = fontmed.render("Average fitness: %d" % averagefitness, 1, (0,0,0))
		fitnesspos = fitnessprint.get_rect()
		fitnesspos.left = 200
		fitnesspos.top = 80
		screen.blit(fitnessprint,fitnesspos)

		pygame.display.flip()

		#save picture to output file
		pygame.image.save(screen, os.path.join("output","gen%08d.png" % (gen)))

		#now let's start the groundwork for the next generation
		for i in deadpool: #delete everyone in deadpool
			population.remove(population[i])
		origpopulation = len(population)
		if VerboseDebug: print "population size currently " + str(origpopulation) + ", generating " + str(len(deadpool)) + " children"

		sleep(0) #for niceness!

		for i in deadpool: # bring us back up to 20
			#select a random male and female for mating
			notmale = True
			notfemale = True
			while notmale:
				pickedmale = RNG.randint(0,origpopulation-1)
				if population[pickedmale].DNA.gender == MALE: notmale = False
			while notfemale:
				pickedfemale = RNG.randint(0,origpopulation-1)
				if population[pickedfemale].DNA.gender == FEMALE: notfemale = False
			if Debug: print "Creating offspring between male " + str(pickedmale) + " and female " + str(pickedfemale)
			#bow chicka waw waw
			population.append(Picture(dna = CreateOffspring(population[pickedmale].DNA, population[pickedfemale].DNA)))

		#check all pygame events first!
	        for event in pygame.event.get():
	        	if event.type == KEYDOWN:
	        		if event.key == K_ESCAPE:
					breakoutofloop = True
		if breakoutofloop: break

	if Metrics: metriccsv.close


def TestBreeding():
	#cross-breeding test
	if Debug: print "testing breeding"
	testmale = Picture(dna = GenerateRandomDNA())
	testfemale = Picture(dna = GenerateRandomDNA())
	newdna = CreateOffspring(testmale.DNA, testfemale.DNA)
	testoffspring = Picture(dna = newdna)

	screen.blit(testmale.picdata, (0, 0))
	screen.blit(testfemale.picdata, (popWidth, 0))

	screen.blit(testoffspring.picdata, (popWidth + 10, popHeight + 10))


def randselect(a,b):
	#for when you want a randomized integer between two numbers, and don't know which one's the higher number, or if they're the same
	if a == b: return a
	elif a < b: return RNG.randrange(a, b)
	else: return RNG.randrange(b, a)

def CreateOffspring(picmale = PicDNA(), picfemale = PicDNA()):
	if VerboseDebug: print "beginning offspring generation routine"
	
	offspring = PicDNA()

	#first, let's figure out how many polygons the offspring is going to have -- should be a random number between male's and female's
	offspring.numpolygons = randselect(picmale.numpolygons,picfemale.numpolygons);
	if VerboseDebug: print "- male numpolys is " + str(picmale.numpolygons) + ", female's is " + str(picfemale.numpolygons) + ", offspring's is " + str(offspring.numpolygons)

	#determine background color -- range between male's and female's red, green, and blue
	offspring.bgcolor = (randselect(picmale.bgcolor[0],picfemale.bgcolor[0]),randselect(picmale.bgcolor[1],picfemale.bgcolor[1]),randselect(picmale.bgcolor[2],picfemale.bgcolor[2]))
	

	#for each polygon, pick either one of the male's, one of the female's, 
	# or merge one of the male's and one of the female's at a specific location -- 
	# but don't reuse locations, and pick which slot to use at random
	if (picmale.numpolygons >= picfemale.numpolygons): selectorder = range(0,picmale.numpolygons)
	else: selectorder = range(0,picfemale.numpolygons)
	RNG.shuffle(selectorder)

	for i in range(0, offspring.numpolygons):
		if VerboseDebug: print "offspring's polygon " + str(i) + " -- num of slots to pick from is " + str(len(selectorder))
		if VerboseDebug: print " -- selectorder is " + str(selectorder)
		if VerboseDebug: print " -- picking polygon slot " + str(selectorder[i])
		select = RNG.randint(0,100)
		if VerboseDebug: print "select roll", select, " male's numpolygons ", picmale.numpolygons, "female's numpolygons", picfemale.numpolygons, "selected slot", selectorder[i]
		#trying to select male's polygon, default to picking the male's if the selected slot is greater than the number of female's polygons
		if (select <= brdPercentMalePolygon and selectorder[i] < picmale.numpolygons) or selectorder[i] > picfemale.numpolygons:
			if VerboseDebug: print "-- picking the male's polygon"
			offspring.polygon.append(copy.deepcopy(picmale.polygon[selectorder[i]]))

		#trying to select female's polygon, default to picking the female's if the selected slot is greater than the number of male's polygons
		elif (select > brdPercentMalePolygon and select <= (brdPercentMalePolygon + brdPercentFemalePolygon) and selectorder[i] < picfemale.numpolygons) or selectorder[i] > picmale.numpolygons:
			if VerboseDebug: print "-- picking the female's polygon"
			offspring.polygon.append(copy.deepcopy(picfemale.polygon[selectorder[i]]))

		#hybrid a polygon, only if the slot exists in both male and female
		elif selectorder[i] < picmale.numpolygons and selectorder[i] < picfemale.numpolygons:	
			if VerboseDebug: print "-- hybridizing the male's and female's polygon"
			offspring.polygon.append(PolygonHybrid(picmale.polygon[selectorder[i]], picfemale.polygon[selectorder[i]]))
		#tried to hybrid polygon but didn't have two polygons to hybridize, pass one by default
		else:
			if selectorder[i] >= picmale.numpolygons: 
				if VerboseDebug: print "-- tried hybrid, picked slot %d, picking the female's polygon by default" % (selectorder[i])
				offspring.polygon.append(copy.deepcopy(picfemale.polygon[selectorder[i]]))
			else: 
				if VerboseDebug: print "-- tried hybrid, picked slot %d, picking the male's polygon by default" % (selectorder[i])
				offspring.polygon.append(copy.deepcopy(picmale.polygon[selectorder[i]]))


		
	#determine its sex by selecting the average of male's and female's percentage
	# for gender assignment, then give it a percentage somewhere within their range
	genderismale = (RNG.randint(0,100)<=((picmale.chancemalekids + picfemale.chancemalekids)/2))
	if genderismale: offspring.gender = MALE
	else: offspring.gender = FEMALE

	#now, we mutate it -- can't just let it go untouched, can we?
	return MutateDNA(copy.deepcopy(offspring))

def PolygonHybrid(malepoly = Polygon(), femalepoly = Polygon()):
	if VerboseDebug: print "beginning hybridizing polygons routine"
	offspring = Polygon()
	offspring.alpha = (randselect(malepoly.alpha,femalepoly.alpha))
	offspring.color = (randselect(malepoly.color[0],femalepoly.color[0]),randselect(malepoly.color[1],femalepoly.color[1]),randselect(malepoly.color[2],femalepoly.color[2]))
	#here we pick points at random from male or female polygon
	pointlist = malepoly.points + femalepoly.points
	selectorder = range(0,len(pointlist))
	RNG.shuffle(selectorder)
	offspringnumpoints = randselect(len(malepoly.points),len(femalepoly.points))
	offspring.points = range(0,offspringnumpoints)
	for i in offspring.points:
		if VerboseDebug: print "-- selecting point " + str(i) + " - picking point " + str(selectorder[i]) + " which is " + str(pointlist[selectorder[i]])
		offspring.points[i]=pointlist[selectorder[i]]
	if VerboseDebug: print "-- points list is now: " + str(offspring.points)
	return copy.deepcopy(offspring)

def TestFitness():
	if VerboseDebug: print "testing fitness"
	# this is going to be a duplication of the experiment that started my oneupsmanship
	picTarget = pygame.transform.scale(pygame.image.load(txtTargetFile), (popWidth,popHeight))
	picGen = Picture(dna = GenerateRandomDNA())
	pygame.image.save(picGen.picdata, os.path.join("output","iteration1.png"))
    	# debug font
    	font = pygame.font.Font(None, 14)

	oldFitness = CheckFitness(picTarget, picGen.picdata)
	for i in range(1,popGenerations):

		picGenNew = Picture(dna = MutateDNA(copy.deepcopy(picGen.DNA)))
		newFitness = CheckFitness(picTarget, picGenNew.picdata)
            	debugprint = font.render(str(oldFitness) + "                     " + str(newFitness) + "                        iteration " + str(i), 1, (255,255,255))
               
            	debugpos = debugprint.get_rect()
            	debugpos.left = 0
            	debugpos.top = 220

		#screen.fill((0,0,0))
		#screen.fill((0,0,0),(100,110,200,210))
		screen.fill((0,0,0),(0,220,400,230))
		screen.blit(picTarget, (0,0))            	
		screen.blit(debugprint, (debugpos))

		screen.blit(picGen.picdata, (0,popHeight + 10))
		screen.blit(picGenNew.picdata, (popWidth,popHeight + 10))
		pygame.display.flip()

		if Debug: print "old fitness = " + str(oldFitness) + ", new fitness = " + str(newFitness)
		if newFitness < oldFitness:
			picGen = picGenNew
			oldFitness = newFitness
			if Debug: print "new mutation advantageous, selecting new iteration"
			pygame.image.save(picGen.picdata, os.path.join("output","iteration" + str(i) + ".png"))
	if Debug: print "done " + str(popGenerations) + " iterations, quitting... that's enough work for now!"


def TestMutations():
	#mutation test
	picture = Picture(dna = GenerateRandomDNA())
	screen.blit(picture.picdata, (0,0))
	population = range(0,4)
	for i in range(0,4):
		population[i] = range(0,4)

	for i in range(0,4):
		for j in range(0,4):
			if i == 0 and j == 0:
				population[i][j]=picture
			else:
				population[i][j]=Picture(dna = MutateDNA(copy.deepcopy(picture.DNA)))
			#picture = population[i][j] #added to forward-mutate
			screen.blit(population[i][j].picdata, ((popWidth*i),(popHeight*j)))
			if Debug: print "Picture at ", i, j			
			DebugprintDNA(population[i][j].DNA)


def TestDNAGenAndRender():
	#starting out -- just generate 16 random picture then display them, output their variables to the debug

	pictemp = range(0,4)
	for i in range(0,4):
		pictemp[i] = range(0,4)

	for i in range(0,4):
		for j in range(0,4):
			pictemp[i][j] = Picture(dna = GenerateRandomDNA())
			screen.blit(pictemp[i][j].picdata, ((popWidth*i),(popHeight*j)))
			if Debug: DebugprintDNA(pictemp[i][j].DNA)

        pygame.display.flip()


main()