import galcon
import math
import random

class Base_Sunbot(galcon.Bot):
	def __init__(self,level,speed=1):
		self.level = level
		self.speed = speed
	
	def init(self):
		self.frame = random.randrange(0,FPS)

###############################################################################
# Bot: Alien
###############################################################################

class Bot_Alien(Base_Sunbot):
	def init(self):
		Base_Sunbot.init(self)
		
		#for i in range(50): print
		
		self.planet_n = 0
		for p in self.level.planets.values():
			self.planet_n = max(self.planet_n, p.n+1)
		
		self.mplanets = [Mplanet(self.level, p) for p in self.level.planets.values()]
		self.mplanets_n = self.planet_n*[None]
		for m in self.mplanets:
			self.mplanets_n[m.planet.n] = m

		self.max_planet2_dist = 0
		for p in self.level.planets.values():
			for q in self.level.planets.values():
				self.max_planet2_dist = max(self.max_planet2_dist, dist(p.pos, q.pos))
	
	def waypoint(self, from_, to, captures):
		deviation = math.cos(40 * math.pi/180)
		
		waypoint = from_.waypoints[to.planet.n]
		if waypoint: return waypoint

		c = dist(from_.planet.pos, to.planet.pos)
		best_a = c
		for q in self.friendly_mplanets + captures:
			if q == from_: continue
			if q == to: continue
			a = dist(from_.planet.pos, q.planet.pos)
			if a > best_a: continue
			b = dist(q.planet.pos, to.planet.pos)
			if b > c: continue
			c1 = (a*a/c - b*b/c + c) / 2
			if c1 < a * deviation: continue
			c2 = (b*b/c - a*a/c + c) / 2
			if c2 < b * deviation: continue
			waypoint = q
			best_a = a
		
		if not waypoint: waypoint = to
		from_.waypoints[to.planet.n] = waypoint
		return waypoint
	
	def avg_eta(self, orig, dest):
		if isinstance(orig,galcon.Planet):
			o = orig.pos
		else:
			o = orig.get_rect().center
		
		if isinstance(dest,galcon.Planet):
			d = dest.pos
		else:
			d = dest.to.pos
		
		time = dist(o, d) / (self.level.options.scale * FPS)
		return max(time, 1)
	
	def min_eta(self, fleet, planet):
		d = planet.pos
		
		r = fleet.get_rect()
		if d[0] > r.right:
			x = r.right
		elif d[0] < r.left:
			x = r.left
		else:
			x = r.centerx
		
		if d[1] < r.top:
			y = r.top
		elif d[1] > r.bottom:
			y = r.bottom
		else:
			y = r.centery
		o = (x, y)
		
		time = dist(o, d) / (self.level.options.scale * FPS)
		return max(time - 1, 0)
	
	def loop(self):
		self.frame += self.speed
		if self.frame < FPS: return
		else: self.frame -= FPS
		
		#for i in range(50): print
		
		# check whether any planets have changed ownership
		planets_changed = False
		my_planets_changed = False
		for m in self.mplanets:
			if m.user == m.planet.user: continue
			planets_changed = True
			if m.user == self or m.planet.user == self:
				my_planets_changed = True
			m.user = m.planet.user
		
		# recalculate everything based on planet ownership
		if planets_changed:
			self.friendly_planets = []
			self.enemy_planets = []
			self.neutral_planets = []
			for p in self.level.planets.values():
				if p.user.n == 0:
					self.neutral_planets.append(p)
				elif p.user == self:
					self.friendly_planets.append(p)
				else:
					self.enemy_planets.append(p)
			
			self.friendly_mplanets = []
			self.enemy_mplanets = []
			self.neutral_mplanets = []
			for m in self.mplanets:
				if m.user.n == 0:
					self.neutral_mplanets.append(m)
				elif m.user == self:
					self.friendly_mplanets.append(m)
				else:
					self.enemy_mplanets.append(m)
			
			for m in self.friendly_mplanets + self.neutral_mplanets:
				m.closest_enemy = None
				m.eta_to_closest_enemy = 1000
				for n in self.enemy_mplanets:
					eta = self.avg_eta(m.planet, n.planet)
					if eta > m.eta_to_closest_enemy: continue
					m.closest_enemy = n
					m.eta_to_closest_enemy = eta
		
		# calculate planet values
		for m in self.mplanets:
			m.value = 0
			cost = 0
			for n in self.mplanets:
				dist_weight = self.max_planet2_dist - dist(m.planet.pos, n.planet.pos)
				m.value += dist_weight * n.planet.production
				if n.user.team == self.team: continue
				cost += dist_weight * n.planet.ships
			if cost == 0: continue
			m.value /= cost
			m.value *= m.planet.production
			m.value /= m.planet.ships + 1
		
		# forecast future ship quantities
		for m in self.mplanets:
			m.reset_forecast()
		for f in self.level.fleets.values():
			m = self.mplanets_n[f.to.n]
			if f.user.team == f.to.user.team:
				m.anticipate(f.ships, self.avg_eta(f, m.planet))
			else:
				m.anticipate(-f.ships, self.min_eta(f, m.planet))
		
		# choose attack targets
		for m in self.friendly_mplanets:
			m.neutral_targets = []
			for n in self.neutral_mplanets:
				eta = self.avg_eta(m.planet, n.planet)
				if eta >= m.eta_to_closest_enemy: continue
				buffer = min(m.eta_to_closest_enemy, n.eta_to_closest_enemy)
				if n.get_forecast(eta)-1 > buffer * (n.planet.production+1) / 50: continue
				priority = n.value / eta
				m.neutral_targets.append((priority, n, eta))
			m.neutral_targets.sort(byzero)
		
		# build neighbors list
		for m in self.friendly_mplanets:
			if not planets_changed: break
			m.neighbors = []
			for n in self.friendly_mplanets:
				if m == n: continue
				eta = self.avg_eta(m.planet, n.planet)
				if eta >= m.eta_to_closest_enemy: continue
				m.neighbors.append((eta, n))
			m.neighbors.sort(byzero)
		
		if my_planets_changed:
			for m in self.friendly_mplanets:
				m.waypoints = self.planet_n*[None]
		
		departures = []
		captures = []
		
		# reinforce
		for m in self.friendly_mplanets:
			needed = m.required_reinforcements()
			for eta,n in m.neighbors:
				if eta > n.eta_to_closest_enemy: continue
				if needed < 1: break
				available = n.max_departure_size(eta)
				if available < 1: continue
				sending = min(needed, available)
				needed -= sending
				departures.append((n,m,sending))
				n.anticipate(-sending, 0)
				m.anticipate(sending, eta)
		
		# plan attacks
		for m in self.friendly_mplanets:
			ships = m.planet.ships
			for priority,n,eta in m.neutral_targets:
				if ships < 1: break
				required = n.get_forecast(eta) + 1.5
				available = m.max_departure_size(eta)
				sending = min(required, available)
				ships -= sending
				departures.append((m,n,sending))
				captures.append(n)
			if m.planet.ships < 1: continue
			if not m.closest_enemy: continue
			available = m.max_departure_size(m.eta_to_closest_enemy)
			departures.append((m,m.closest_enemy,available))
		
		# execute attacks
		for from_,to,size in departures:
			size = int(size)
			if size < 1: continue
			to = self.waypoint(from_, to, captures)
			self.level.fleet(self, from_.planet, to.planet, size)

class Mplanet:
	def __init__(self, level, planet):
		self.level = level
		self.planet = planet
		self.user = None
	
	def reset_forecast(self):
		self.forecast = 31*[self.planet.ships]
		for i in xrange(1, 30):
			if self.user.n == 0: break
			self.forecast[i] += i * self.planet.production/50
	
	def time_to_fall(self):
		for i in xrange(0, 30):
			if self.forecast[i] < 0:
				return i
		return None
	
	def max_departure_size(self, time):
		time = int(time)
		time = max(time, 0)
		time = min(time, 30)
		size = self.planet.ships
		for i in xrange(0, time):
			if size > self.forecast[i]:
				size = self.forecast[i]
		return max(size-1, 0)

	def anticipate(self, size, time):
		time = int(time)
		time = max(time, 0)
		time = min(time, 30)
		for i in xrange(time, 30):
			self.forecast[i] += size

	def get_forecast(self, time):
		time = int(time)
		time = max(time, 0)
		time = min(time, 30)
		return self.forecast[time]

	def required_reinforcements(self):
		size = 0
		for i in xrange(0, 30):
			if size > self.forecast[i]:
				size = self.forecast[i]
		return int(-size)


###############################################################################
# Bot: Ants
###############################################################################

class Bot_Ants(Base_Sunbot):
	def loop(self):
		self.frame += self.speed
		if self.frame < FPS: return
		else: self.frame -= FPS
		
		for p in self.level.planets.values():
			if p.user != self: continue
			if p.ships < p.production/10: continue
			best_target = None
			for q in self.level.planets.values():
				if q.user == self: continue
				value = dist(p.pos, q.pos) / (self.level.options.scale * FPS)
				if q.user.n == 0:
					value += 25*q.ships/(q.production+1)
				if best_target:
					if value > best_value: continue
				best_target = q
				best_value = value
			if not best_target: continue
			#self.level.fleet(self, p, self.waypoint(p, best_target), p.ships)
			self.level.fleet(self, p, best_target, p.ships/2)


###############################################################################
# Generic functions
###############################################################################

def dist(a, b):
	return math.hypot(a[0]-b[0], a[1]-b[1])

def byzero(a, b):
	return int(b[0]-a[0])