#!/usr/bin/python

import random, os, sys
from xpai import *
from math import *

# Convert a decimal number to binary string
#
def bin(n):
    s = ''
    while n > 0:
        s = str(n % 2) + s
        n >>= 1
    return s

# GENETIC ALGORITHM

# This code makes extensive use of python's generators, so if you
# don't know how they work, look it up.

def roll(n=.5): return random.random() > n

def grabs(n, generator):
    s = ''
    for x in generator:
        if len(s) < n:
            s += str(x)
        else:
            return s

def bits(num):
    for s in bin(num)[2:]:
        yield int(s)

# We use a gray encoding scheme to get values from our genetic
# strings.
def decode(gray):
    b = ''
    for g in bits(gray):
        b += str(int(b[-1:]) ^ g) if len(b) > 0 else str(g)
    return int(b,2)

# An infinitely long random sequence
def randSeq(s):
    random.seed(s)
    state = random.getstate()
    while True:
        random.setstate(state)
        x = random.random()
        state = random.getstate()
        yield x

# An infinitely long piece of DNA
def randomDNA(s):
    for x in randSeq(s):
        yield 1 if x > .5 else 0

# Get a list of property names, return a dictionary associating those
# names with values pulled from a DNA string. We'll use 16 bits for
# each property. If you want less precision, try changing n to 8, or
# maybe even 4.

def mappings(props, dna, n=16):
    global currentIndividual
    m = {}
    currentIndividual = ''
    for p in props:
        bits = grabs(n, dna)
        currentIndividual += bits
        m[p] = float(decode(int(bits, 2))) / 2**n
    return m

def randomPop():
    global currentIndividual, currentFitness
    while True:
        yield(randomDNA(os.urandom(32)))
        testedIndividuals.append((currentIndividual, currentFitness))
        currentFitness = 0

# Mating produces two offspring
def formbabby(boy, girl):
    if roll(crossoverRate):
        return boy, girl
    mid = random.randint(0, len(boy))
    return boy[:mid] + girl[mid:], girl[:mid] + boy[mid:]

def mutate(indiv):
    mutant = ''
    for bit in indiv:
    	mutant += str(int(bit) ^ 1) if roll(mutationRate) else bit
    return mutant

# stochastic (roulette wheel) selection
def selectCandidates(tested):
    jack = roulette(tested)
    jill = roulette(filter(lambda x: x[0] != jack, tested))
    return jack, jill

def roulette(tested):
    lo = min([x[1] for x in tested])
    E = float(sum([f[1] - lo for f in tested]))
    P = [(f[1] - lo)/E for f in tested]
    W = [sum(P[:i]) for i in range(len(P))]
    
    spin = random.random()
    for indiv,slot in zip(tested, W):
        if spin > slot: sel = indiv[0]
        else:  return sel

# We only choose one child to keep :(
def nextGen(oldGen):
    global testedIndividuals,currentFitness
    new = []
    while len(new) < len(testedIndividuals):
        Barack, Michelle = selectCandidates(testedIndividuals)
        Sasha, Malia = formbabby(Barack, Michelle)
        new.append(mutate(Sasha) if roll() else mutate(Malia))
    for n in new:
        yield n
        testedIndividuals.append(n, currentFitness)
        currentFitness = 0
    
    # Continue yielding oldGen members if we run out. This way our
    # population remains seemingly 'infinite': we don't have to keep a
    # fixed size (so long as we start from a random population)
    for o in oldGen:
        yield o

# Here are the functions you'll actually be *using*
def newIndividual(*properties):
    for i in currentPopulation:
        return mappings(properties, i)

def popSize(): 
    return len(testedIndividuals)

def evolvePopulation():
    global currentPopulation,testedIndividuals
    currentPopulation = nextGen(currentPopulation)
    testedIndividuals = []

# Initialization. Set mutationRate and crossoverRate to 
# whatever you like between 0 and 1.

testedIndividuals = []
currentFitness = 0
currentIndividual = ''
currentPopulation = randomPop()

mutationRate = .03
crossoverRate = .6

# GA USAGE INSTRUCTIONS
#
# 1. Like above, choose mutationRate, crossoverRate, and initialize
#    your population with randomPop(). TODO: load/save functions
#
# 2. When you want new parameters, call newIndividual, and hand it
#    parameter names. It will give you a dictionary with their values
#    taken from genetic code. They will be values between 0 and 1, so
#    you'll have to scale them to your desired range.
#
#    p = newIndividual('Speed', 'Accuracy', 'Range')
#    max_speed = p['Speed'] * 15
#    shot_threshold = p['Accuracy'] * 45
#    shot_range = p['Range'] * 400
#    ...etc
#
# 3. The fitness value of an individual is the value of currentFitness
#    before you call newIndividual.
#
# 4. To get a new population, call evolvePopulation(). Check the
#    current population size with popSize()

# The remaining code is given as a usage example
def feeler(d, a):
    dx, dy = self_x() + d * cos(rad(a)), \
        self_y() + d * sin(rad(a))
    res = wallbetween(self_x(), self_y(), int(dx), int(dy))
    return res if res >= 0 else d

def ships():
    i = 0
    while ship_name(i) != None:
        yield i
        i += 1

def rships():
    i = 0
    while radar_x(i) > 0:
        yield i
        i += 1

def enemies():
    return [e for e in ships() if ship_team(e) != self_team()]

def radar_enemies():
    return [e for e in rships() if ship_team(e) != self_team()]

def clear_shot(e):
    return feeler(ship_aimdir(e), ship_dist(e)) == ship_dist(e)

alive = False
params = {}

def print_params(p):
    print "Got new individual #%d" % (popSize() + 1)
    for attr in p:
        print "\t%s:\t%s" % (attr, p[attr])

def AImain():
    global alive, params, currentFitness
    if popSize() > 60:
        evolvePopulation()
    
    # We get a new individual whenever someone dies. You may want to give
    # an individual n chances before getting a new one.
    if not alive and self_alive() == 1:
        alive = True
        params = newIndividual('Max Speed', 'Shot Escape', 'Wall Escape',\
                               'Feeler Length', 'Feeler Num', 'Vscale')
        print_params(params)
    alive = (self_alive() == 1)
    
    if self_alive() != 1: 
        return
    
    currentFitness += self_alive()
    
    shot_esc = int(params['Shot Escape'] * 150) + 30
    vel_scale = int(params['Max Speed'] * 10) + 1
    max_speed = int(params['Max Speed'] * 20) + 5
    wall_esc = int(params['Wall Escape'] * 150) + 30
    nfeelers = int(params['Feeler Num'] * 11) + 1
    flen = int(params['Feeler Length'] * 700)
    
    s = 360 / nfeelers
    h = self_heading()
    t = self_track()
    
    probe = lambda a: feeler(flen, angleadd(t, a))
    feel = [(i*s,probe(i*s)) for i in range(nfeelers)]
    walls = [(a,d) for a,d in feel if d < flen]
    
    e = enemies()
    r = radar_enemies()
    
    # The rest is a slightly modified Morton
    if -1 < shot_alert(0) < 80:
        escape = angleadd(shot_idir(0), shot_esc)
        self_turn(anglediff(h, escape))
        self_thrust(1 if anglediff(h, escape) < 90 else 0)
    
    elif len(e) > 0:
        self_turn(anglediff(h, ship_aimdir(e[0])))
        self_shoot(1 if anglediff(h, ship_aimdir(e[0])) < 30 else 0)
    
    elif len(r) > 0:
        self_turn(anglediff(h, radar_xdir(r[0])))
        if roll(float(max_speed) / max(self_vel() * vel_scale,1)):
            self_thrust(1 if anglediff(h, radar_xdir(r[0])) < 90 else 0)
        else:
            self_shoot(1 if anglediff(h, radar_xdir(r[0])) < 30 else 0)
    
    # Thrust if we're standing still, to get the ball rolling
    if self_vel() == 0:
        self_thrust(1 if roll(.2) else 0)
        return
    
    if len(walls) == 0:
        return
    
    # I had to change this part to support a variable number of 
    # wall feelers. Here's how it works:
    # - Incoming walls are sorted by angle difference to track
    # - An escape angle is calculated using the GA parameter
    # - The escape angle is scaled down by the distance to other walls
    #   that have an angle closer to track.
    # - The escape values are all summed into turn
    turn = 0
    weights = [1.0]
    walls.sort(lambda x,y: -1 if abs(anglediff(t,x[0])) < abs(anglediff(t,y[0])) else 1)
    
    for angle,dist in walls:
        weights.append(1.0 - dist / float(flen))
        escape = min(anglediff(h, angleadd(angle, wall_esc)), 20)
        for w in weights:
            escape *= w
        turn = angleadd(turn, int(escape))
    
    self_turn(turn)
    if roll(float(max_speed) / max(self_vel() * vel_scale,1)):
        self_thrust(1 if turn < 30 else 0)
    if roll(weights[1]):
        self_thrust(1)

# To run the program, run it just like xpilot:
# ./ga.py -join <server> -name <name>
set_AImain(AImain)
setargs(' '.join(sys.argv[1:]))
setmaxturn(20)
launch()