package edu.berkeley.nlp.starcraft.micro;

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;

import org.bwapi.proxy.model.Color;
import org.bwapi.proxy.model.DamageType;
import org.bwapi.proxy.model.Game;
import org.bwapi.proxy.model.Position;
import org.bwapi.proxy.model.TilePosition;
import org.bwapi.proxy.model.Unit;
import org.bwapi.proxy.model.UnitType;
import org.bwapi.proxy.model.UpgradeType;
import org.bwapi.proxy.model.WeaponType;

import edu.berkeley.nlp.starcraft.OvermindUnit;
import edu.berkeley.nlp.starcraft.drawing.DrawUtils;
import edu.berkeley.nlp.starcraft.drawing.DrawingContext;
import edu.berkeley.nlp.starcraft.drawing.GameDrawingContext;
import edu.berkeley.nlp.starcraft.map.MapUtils;
import edu.berkeley.nlp.starcraft.micro.ThreatFilters.ThreatFilter;
import edu.berkeley.nlp.starcraft.micro.missions.Mission;
import edu.berkeley.nlp.starcraft.micro.missions.SurgicalStrikeMission;
import edu.berkeley.nlp.starcraft.micro.missions.WipeOutClusterMission;
import edu.berkeley.nlp.starcraft.model.Model;
import edu.berkeley.nlp.starcraft.model.ThreatTracker;
import edu.berkeley.nlp.starcraft.model.clusters.TargetUnitCluster;
import edu.berkeley.nlp.starcraft.overmind.Overmind;
import edu.berkeley.nlp.starcraft.overmind.Underling;
import edu.berkeley.nlp.starcraft.pathing.BuildTilePathfinder;
import edu.berkeley.nlp.starcraft.pathing.Pathfinder;
import edu.berkeley.nlp.starcraft.resources.ResourceInventory;
import edu.berkeley.nlp.starcraft.simulation.Simulation;
import edu.berkeley.nlp.starcraft.util.ConvexHull;
import edu.berkeley.nlp.starcraft.util.Log;
import edu.berkeley.nlp.starcraft.util.Pair;
import edu.berkeley.nlp.starcraft.util.PriorityQueue;
import edu.berkeley.nlp.starcraft.util.Timer;
import edu.berkeley.nlp.starcraft.util.UnitUtils;
import edu.berkeley.nlp.starcraft.util.Vector;

public class MicroSquadManager implements Underling {
	public static final Log logger = Log.getLog("micro.MicroSquadManager");
	public static boolean trackMainSquad = false;

	private static boolean useLinearStarcraftPredictions = false;
	private static boolean QUIET = true;	
	private static final boolean PRINT_CURRENT_MISSION = false;	

	private final Model m;

	private Position homeBase;
	private Squad squad;

	int timeSinceChange = -1;
	double distanceTraveled = 0;
	double speedEstimate = 0;
	Position start;
	Position end;
	boolean going = true;

	boolean runonce = true;

	private int availableMutasDistanceThreshold = 500;
	private double availableMutasDiscount = 0.9;
	
	private int minSquadHarassStrength = 5;
	private int maxSquadLimit = 16;
	private int squadStep = 4;
	private double minSquadHarassHP = minSquadHarassStrength
			* UnitType.ZERG_MUTALISK.maxHitPoints();
	private int minSquadStrength = 5;
	private int minSquadConfidentStrength = 18; // 18 mutas don't need to be
	// conservative

	private int riskBases = -1;
	private int killTargets = -1;
	private int harassTargets = -1;

	// strategic targeting
	private boolean drawTargeting = true;
	private static final String gTargetingWindowName = "Targeting";
	private static final int CLUSTER_UPDATE_FREQUENCY = 17;
	private Mission currentMission = null;
	private TargetUnitCluster targetCluster = null;
	private Position targetPosition;
	private Collection<TargetUnitCluster> basesAtRisk;
	private Collection<TargetUnitCluster> killableTargets;
	private Collection<TargetUnitCluster> harassmentTargets;
	private Map<Unit, Integer> hidingWorkers = new HashMap<Unit, Integer>();
	private int hidingTimerLength = 240;

	private int maxForceSize;
	private double maxForceHP;

	public enum Status {
		STARTING, RETREATING, HARASSING, ATTACKING, DEFENDING, WANDERING
	};

	private Status status = Status.STARTING;
	private boolean wandering = false;
	private boolean completedBaseLocationCircuit = false;
	private List<TilePosition> baseLocations;
	private boolean[] baseLocationsChecked;
	private int currentBaseLocation = -1;
	
	private Pathfinder pathfinder = new BuildTilePathfinder();
	
	
	private boolean drawMission = true;
	private ConvexHull lastHull;
	private Collection<Unit> lastThreats;

	public MicroSquadManager(Position homebase, Squad squad) {
		m = Model.getInstance();
		homeBase = homebase;
		this.squad = squad;
		m.squadTracker.registerMainSquad(squad);
		status = Status.WANDERING;
		updateWanderingPosition();
		// checkClusterAssignment();
		updateMission();

		/*
		 * // TODO: Comment out to not do windowed drawing.
		 * WindowDrawingContexts.setWindowLocation(gTargetingWindowName, new
		 * Point(0, 400));
		 * WindowDrawingContexts.setWindowSize(gTargetingWindowName, new
		 * Dimension(200, 180)); //
		 */
	}

	private void pickNextTarget() {
		Position squadPosition = squad.getPosition();

		if (!completedBaseLocationCircuit) {
			if (baseLocations == null) {
				Set<TilePosition> possibleEnemyBaseLocations = new HashSet<TilePosition>(
						m.baseTracker.getLocationsToBaseInfos().keySet());
				possibleEnemyBaseLocations.removeAll(m.baseTracker
						.getOrderedEnemyBaseLocations());
				baseLocations = new ArrayList<TilePosition>(
						possibleEnemyBaseLocations);
				baseLocationsChecked = new boolean[baseLocations.size()];
			} else {
				baseLocationsChecked[currentBaseLocation] = true;
			}
			if (allTrue(baseLocationsChecked)) {
				completedBaseLocationCircuit = true;
			} else {
				currentBaseLocation = getClosestLocation(squadPosition,
						baseLocations, baseLocationsChecked);
				Position position = new Position(baseLocations
						.get(currentBaseLocation));
				logger.info("Checking next possible enemy base location: "
						+ positionString(position));
				setTarget(position);
				return;
			}
		}
		Position position = new Position(new TilePosition(Overmind.random
				.nextInt(Game.getInstance().mapWidth()), Overmind.random
				.nextInt(Game.getInstance().mapHeight())));
		logger.info("Checking random location: " + positionString(position));
		setTarget(position);
	}

	private int getClosestLocation(Position squadPosition,
			List<TilePosition> candidates, boolean[] checked) {
		TilePosition squad = new TilePosition(squadPosition);
		int bestPosition = -1;
		double bestDistance = Double.MAX_VALUE;
		for (int i = 0; i < candidates.size(); i++) {
			if (checked[i])
				continue;
			TilePosition p = candidates.get(i);
			double d = squad.getDistance(p);
			if (d < bestDistance) {
				bestDistance = d;
				bestPosition = i;
			}
		}
		return bestPosition;
	}

	private boolean allTrue(boolean[] checked) {
		for (boolean b : checked) {
			if (!b)
				return false;
		}
		return true;
	}

	private String positionString(Position position) {
		return "(" + position.x() + ", " + position.y() + ")";
	}

	private void setTarget(Position position) {
		targetPosition = position;
		squad.setDestination(targetPosition);
	}

	private TilePosition flip(TilePosition p) {
		Game g = Game.getInstance();
		return new TilePosition(g.mapWidth() - p.x(), g.mapHeight() - p.y());
	}

	@Override
	public void onFrame(int frameNum) {
		Timer timer = new Timer(logger);
		if (squad instanceof AerialSquad) {
			((AerialSquad)squad).checkBullets();
		}
		if (squad.size() > 0
				&& (frameNum % CLUSTER_UPDATE_FREQUENCY == 0 || (currentMission != null && currentMission
						.complete()))) {
			// Check if we need to switch status
			// checkClusterAssignment();
			updateMission();
			timer.tick("updateMission");
		}

		if (status == Status.WANDERING && squad.atDestination()) {
			updateWanderingPosition();
			timer.tick("wandering");
		}
		
		// process the squad's command
		squad.onFrame(frameNum);
		timer.tick("squad onFrame");

		if (drawMission) {
			drawMission();
			timer.tick("draw");
		}

		if (trackMainSquad) {
			Position position = squad.getPosition();
			Game.getInstance().setScreenPosition(
					Math.max(0, position.x() - 300),
					Math.max(0, position.y() - 200));
		}
	}

	private void drawMission() {
		if (lastHull != null) {
			lastHull.draw();
		}
		if (lastThreats != null) {
			for (Unit u : lastThreats) {
				if (Model.getInstance().opponentTracker.exists(u)) {
					DrawUtils.drawUnitDimension(GameDrawingContext.INSTANCE, u, 0, Color.RED, false);
				}
			}
		}
	}

	private void updateWanderingPosition() {
		Position pos = squad.getPosition();
		TargetUnitCluster enemyBaseCluster = getEnemyBaseCluster();
		if (enemyBaseCluster == null) {
			pickNextTarget();
			return;			
		}
		if (lastHull == null) {
			lastHull = getConvexHullOfThreats(enemyBaseCluster);
		}
		if (lastHull.isEmpty()) {
			squad.setDestination(enemyBaseCluster.getCenter());
			return;
		}
		Vector closestPointOnHull = lastHull.ClosestPointOnHull(pos.toVector());
		
		Vector offset = closestPointOnHull.sub(pos.toVector()).normalize(200);
		Position destination = closestPointOnHull.toPosition();
		int attempts = 0;
		while (attempts++ < 200 && Model.getInstance().threatTracker.getBuildTileAirThreat(MapUtils.convertPositionToBuildTilePosition(destination)) > 0) {
			if (destination.x() <= 100 || destination.x() >= Game.getInstance().getMapWidth() * Game.TILE_SIZE - 100) {
				if (destination.y() <= 100 || destination.y() >= Game.getInstance().getMapHeight() * Game.TILE_SIZE - 100) { // in a corner! oh no!
					break;
				}
				offset = offset.dy >= 0 ? new Vector(0, 200) : new Vector(0, -200);
			} else if (destination.y() <= 100 || destination.y() >= Game.getInstance().getMapHeight() * Game.TILE_SIZE - 100) {
				offset = offset.dx >= 0 ? new Vector(200, 0) : new Vector(-200, 0);
			}
			destination = clip(offset.addTo(destination));
			squad.setDestination(destination);
			return;
		}
		Position furthest = UnitUtils.getFarthest(pos, lastHull.getPointsAsUnits()).getLastKnownPosition();
		Vector margin = lastHull.normalFromNearestVertex(furthest.toVector());
		squad.setDestination(clip(margin.normalize(500).addTo(furthest)));
		return;
	}

	private ConvexHull getConvexHullOfThreats(TargetUnitCluster enemyBaseCluster) {
		List<Unit> enemies = new ArrayList<Unit>();
		for (Unit u : enemyBaseCluster.getAllEnemyUnits()) {
			if (u != null) {
				if (u.getType().equals(UnitType.PROTOSS_PHOTON_CANNON) && u.wasCompleted()) {
					if (!u.isUnpowered()) {
						enemies.add(u);
					}
				} else if (!u.getType().isBuilding() || u.wasCompleted()) {
					if (u.getType().airWeapon().targetsAir() || u.getType().equals(UnitType.TERRAN_BUNKER)) {
						enemies.add(u);
					}
				}
			}
		}
		ConvexHull hull = new ConvexHull(enemies);
		return hull;
	}

	private Position clip(Position pos) {
		Position clipped = pos;
		if (clipped.x() < 100) {
			clipped = new Position(100, clipped.y());
		}
		if (clipped.x() >= Game.getInstance().getMapWidth() * Game.TILE_SIZE - 100) {
			clipped = new Position(Game.getInstance().getMapWidth()
					* Game.TILE_SIZE - 100, clipped.y());
		}
		if (clipped.y() < 100) {
			clipped = new Position(clipped.x(), 100);
		}
		if (clipped.y() >= Game.getInstance().getMapHeight() * Game.TILE_SIZE) {
			clipped = new Position(clipped.x(), Game.getInstance()
					.getMapHeight()
					* Game.TILE_SIZE - 100);
		}
		return clipped;
	}

	private static double utilityThreshold = 0;

	private void updateMission() {
		Mission newMission = chooseMission();
		if (newMission == null && currentMission != null) {
			currentMission = newMission;
			targetCluster = null;
			status = Status.WANDERING;
			updateWanderingPosition();
			squad.setTargetCluster(targetCluster, status);
		}
		if (newMission != null && !newMission.equals(currentMission)) {
			currentMission = newMission;
			targetCluster = newMission.getCluster();
			status = Status.ATTACKING;
			squad.setTargetCluster(targetCluster, status);
			setTarget(targetCluster.getCenter());
			resetCurrentWanderingCircuit();
		}
	}

	private Mission chooseMission() {
		Collection<Mission> missions = getMissions();
		Mission bestMission = null;
		double bestUtility = Double.NEGATIVE_INFINITY;
		int i=0;
		for (Mission m : missions) {
			i++;
			double utility = getFightUtility(squad.getUnits(), Model
					.getInstance().opponentTracker.getAllKnownUnits(), m
					.getOrderedTargetList());
			if (!QUIET) {
				logger.info(utility + ": (" + i + "/" + missions.size() + ") " + m);
			}
			if ((utility > utilityThreshold || Game.getInstance().self().supplyUsed() >= 380 || m.getProtectedUnits().size() > 0) && utility > bestUtility) {
				bestUtility = utility;
				bestMission = m;
			}
		}
		if (bestMission != null) {
			lastThreats = constructThreatList(Model.getInstance().opponentTracker.getAllKnownUnits(), flatten(bestMission.getOrderedTargetList()));
			if (PRINT_CURRENT_MISSION) {
				logger.info("Best of " + missions.size() + ": " + bestMission);
			}
		} else {
			lastThreats = null;
		}
		return bestMission;
	}

	private Collection<Mission> getMissions() {
		Set<Mission> set = new HashSet<Mission>();
		if (currentMission != null && !currentMission.complete())
			set.add(currentMission);
		for (TargetUnitCluster c : Model.getInstance().opponentTracker.getEnemyClusters()) {
			if (!c.isEmpty()) {
				if (c.hasEnemyBase()) {
					ConvexHull hull = getConvexHullOfThreats(c);
					for (Unit targetOnHull : hull.getPointsAsUnits()) {
						if (!(UnitUtils.isUntargetable(targetOnHull) || Model.getInstance().opponentTracker.isDoomed(targetOnHull))) {
							set.add(new SurgicalStrikeMission(targetOnHull, new ArrayList<Unit>()));
						}
					}
					for (Unit u : c.getAllEnemyUnits()) {
						if ((hull.isEmpty() || hull.DistanceToHull(u.getLastKnownPosition().toVector()) > 16) &&
								(u.isVisible() || u.getType().isWorker() || u.getType().isBuilding()) &&
								!(UnitUtils.isUntargetable(u)|| Model.getInstance().opponentTracker.isDoomed(u))) {
							set.add(new SurgicalStrikeMission(u, new ArrayList<Unit>()));
						}
					}
					lastHull = hull;
				} else {
					for (Unit u : c.getAllEnemyUnits()) {
						if (u.isVisible() && !(UnitUtils.isUntargetable(u)|| Model.getInstance().opponentTracker.isDoomed(u))) {
							Set<Unit> friendlyUnits = c.hasFriendlyBase() ? c.getFriendlyUnits() : new HashSet<Unit>();
							set.add(new SurgicalStrikeMission(u, friendlyUnits));
						}
					}
				}
			}
		}
		return set;
	}

	private double getFightTimeInSeconds(Collection<Unit> targets, double mutasAvailable) {
		double time = 0;
		for (Unit e : targets) {
			if (!e.isVisible())
				e = e.getPreviousUnitData();
			if (e == null)
				continue;
			int hitPoints = e.getHitPoints() + e.getShields();
			double myDps = (Game.getInstance().self().getWeaponDamage(
					WeaponType.GLAVE_WURM) - (e.getShields() > 0 ? Math.max(e.getShieldUpgradeLevel(), e.getArmor()) : e.getArmor()))
					* (24.0 / WeaponType.GLAVE_WURM.damageCooldown())
					* mutasAvailable;
			time += hitPoints / myDps;
		}
		return time;
	}

	private double getFightUtility(Collection<OvermindUnit> myUnits,
			Collection<Unit> enemyUnitsToConsider,
			List<Collection<Unit>> orderedEnemyTargets) {
		double fightUtility, fightTime;
		Collection<Unit> flattened = flatten(orderedEnemyTargets);

		// Old fight utility and time
		Set<Unit> enemyThreats = constructThreatList(enemyUnitsToConsider,
				flattened);
		double mutaUtility = UnitUtils.getUtility(UnitType.ZERG_MUTALISK)
				* squad.size();
		double mutasRequired = mutasNeededToWin(enemyThreats);
		Pair<Unit, Double> closestAndDistance = UnitUtils.getClosestAndDistance(squad.getPosition(), flattened);
		double mutasAvailable = mutasAvailable(closestAndDistance.getFirst().getLastKnownPosition());
		if (mutasRequired > mutasAvailable) {
			logger.debug("Mission: " + flattened );
			logger.debug("Threats: " + enemyThreats);
			logger.debug("Mutas: " + mutasAvailable + "Mutas needed: " + mutasRequired +
					" Muta loss: " + mutaUtility);
			return -mutaUtility;
		}
		double targetUtility = totalUtility(flattened);
		fightTime = getFightTimeInSeconds(flattened, mutasAvailable);
		double travelTime = closestAndDistance.getSecond() / (UnitType.ZERG_MUTALISK.topSpeed() * 24.0);
		double vsMutasDps = dpsVsSquad(enemyThreats);
		double damageToMutas = ((fightTime + travelTime) * vsMutasDps) - (travelTime * dpsVsSquad(flattened));
		double mutaCost = damageToMutas / UnitType.ZERG_MUTALISK.maxHitPoints()
				* UnitUtils.getUtility(UnitType.ZERG_MUTALISK);

		fightUtility = targetUtility - mutaCost;
		

		// If the home base is under attack, how much damage will it take if we
		// ignore it
		Set<Unit> threatsToHomeBase = new HashSet<Unit>(getHomeCluster()
				.getAllEnemyUnits());
		threatsToHomeBase.removeAll(flattened); // If we're trying to kill these
												// guys, we're not ignoring the
												// home base
		double ignoreCost = 0;
		if (!threatsToHomeBase.isEmpty()) {		
			double ignoreDamage = 0;
			double vsBaseDps = computeDamagePotential(threatsToHomeBase, false,
					false);
			ignoreDamage = vsBaseDps * (fightTime + travelTime);
			ignoreCost = lostUtility(getHomeCluster().getFriendlyUnits(),
					ignoreDamage);
		}
		
		
		double oldFightUtility = fightUtility;
		double oldFightTime = fightTime;
		double oldTotalUtility = (fightUtility - ignoreCost);
		double oldTotalTime = (fightTime + travelTime);

		double totalTime, totalUtility;
		
		// Compute the linear starcraft thing
		if (useLinearStarcraftPredictions) {
			Simulation sim = Model.getInstance().simulationManager.doFightSim(
					myUnits, enemyUnitsToConsider, orderedEnemyTargets);

			fightUtility = sim.getUtility() - sim.getStartUtility();
			fightTime = sim.getTime() / 24.0; // fight timing is just the
					   							              // shooting
			totalUtility = fightUtility;
			totalTime = fightTime;
			
			// FIXME: what if given no units?
			
			// Simulate threats to home base
			if (!threatsToHomeBase.isEmpty()) {
				logger.debug("Base under attack: simulate loss until we get there.");
				travelTime = closestAndDistance.getSecond() / UnitType.ZERG_MUTALISK.topSpeed();
				totalTime += travelTime;
				
				Set<Unit> friendliesInHomeBase = new HashSet<Unit>(getHomeCluster().getFriendlyUnits());
				
				Simulation simBase = Model.getInstance().simulationManager.doBaseSim(friendliesInHomeBase, threatsToHomeBase, totalTime);
				
				double baseUtility = simBase.getUtility() - simBase.getStartUtility();

				totalUtility += baseUtility;
			}
			
			
			// sim.printState();
			if (!QUIET) {
				List<ResourceInventory> orderedList = new ArrayList<ResourceInventory>();
				for (Collection<Unit> units : orderedEnemyTargets) {
					orderedList.add((new ResourceInventory())
							.incrementCounts(units));
				}
				logger.debug("Q:" + " myUnits=" + new ResourceInventory(myUnits)
						+ " orderedEnemyTargets=" + orderedList
						+ " enemyUnitsToConsider="
						+ (new ResourceInventory(enemyUnitsToConsider)));
				logger.debug("Sim state delta: us="
						+ ResourceInventory.getDifference(
								new ResourceInventory(sim.getUsUnits()),
								new ResourceInventory(myUnits))
						+ " them="
						+ ResourceInventory.getDifference(
								new ResourceInventory(sim.getThemUnits()),
								new ResourceInventory(enemyUnitsToConsider)));
				logger.debug("A: fightUtility=" + fightUtility + " totalUtility=" + totalUtility 
						+ " fightTime=" + fightTime + " totalTime=" + totalTime);
				logger.debug("A: oldFightUtility=" + oldFightUtility + " oldTotalUtility=" + oldTotalUtility 
						+ " oldFightTime=" + oldFightTime + " oldTotalTime=" + oldTotalTime);
			}
		} else {
			totalUtility = oldTotalUtility;
			totalTime = oldTotalTime;
		}
		
		double utility = totalTime>0 ? totalUtility / totalTime : 0;
		
		logger.debug("Mission: " + flattened );
		logger.debug("Threats: " + enemyThreats);
		logger.debug("Mutas: " + mutasAvailable +
				" Muta loss: " + mutaCost + " Kill utility: " + targetUtility + " Fight time: " + fightTime +
				" Travel time: " + travelTime + " utility: " + utility);
		
		return utility;
	}

	private double mutasAvailable(Position targetPosition) {
		OvermindUnit closest = UnitUtils.getClosestOvermind(targetPosition, squad.getUnits());
		int count = 0;
		for (OvermindUnit u : squad.getUnits()) {
			if (closest.getDistance(u) <= availableMutasDistanceThreshold) {
				count++;
			}
		}
		return count - availableMutasDiscount;
	}

	private double lostUtility(Collection<Unit> friendlyUnits, double damage) {
		if (damage == 0)
			return 0;
		PriorityQueue<Unit> pq = new PriorityQueue<Unit>();
		for (Unit f : friendlyUnits) {
			pq.add(f, UnitUtils.getUtility(f.getType())
					/ (double) (f.getType().maxHitPoints() + f.getType()
							.maxShields()));
		}
		double damageRemaining = damage;
		double totalLoss = 0;
		while (pq.hasNext() && damageRemaining > 0) {
			Unit f = pq.next();
			double damageInflicted = Math.min(damageRemaining, f.getHitPoints()
					+ f.getShields());
			totalLoss += UnitUtils.getUtility(f.getType())
					* damageInflicted
					/ (double) (f.getType().maxHitPoints() + f.getType()
							.maxShields());
			damageRemaining -= damageInflicted;
		}
		return totalLoss;
	}

	private double totalUtility(Collection<Unit> set) {
		double sum = 0;
		List<Unit> attackingUs = new ArrayList<Unit>();
		for (Unit e : set) {
			sum += UnitUtils.getUtility(e.getType());
			Unit lastTarget = Model.getInstance().opponentTracker.lastTarget(e);
			if (lastTarget != null && lastTarget.getPlayer().equals(Game.getInstance().self()) && lastTarget.getType().equals(UnitType.ZERG_MUTALISK)) {
				attackingUs.add(e);
			}
		}
		sum += dpsVsSquad(attackingUs) * 5 * UnitUtils.getUtility(UnitType.ZERG_MUTALISK) / UnitType.ZERG_MUTALISK.maxHitPoints();
		// Assume that we prevent 5 seconds worth of future damage from anything shooting at us
		return sum;
	}

	private Set<Unit> constructThreatList(
			Collection<Unit> enemyUnitsToConsider, Collection<Unit> targets) {
		int threatSlack = 48; // Some slack because mutas just don't behave optimally and can get shot
		
		Set<Unit> threats = new HashSet<Unit>();
		if (targets.isEmpty())
			return threats;
		threats.addAll(targets);
		Position startPosition = squad.getPosition();
		Position endPosition = UnitUtils.getClosest(startPosition, targets).getLastKnownPosition();
		Position closeEnoughPosition = Vector.diff(endPosition, startPosition).normalize(UnitUtils.getRange(WeaponType.GLAVE_WURM, Game.getInstance().self())).addTo(endPosition);
		for (Unit e : enemyUnitsToConsider) {
			double distance = Vector.PointToLineSegmentDistance(startPosition.toVector(), closeEnoughPosition.toVector(), e.getLastKnownPosition().toVector());
			double threatRange = UnitUtils.getAirRange(e) + UnitUtils.diagonalLength(e.getType()) + UnitUtils.diagonalLength(UnitType.ZERG_MUTALISK) + threatSlack;
			if (distance <= threatRange) {
				threats.add(e);
			}
		}
		return threats;
	}

	private Collection<Unit> flatten(List<Collection<Unit>> orderedEnemyTargets) {
		List<Unit> list = new ArrayList<Unit>();
		for (Collection<Unit> c : orderedEnemyTargets) {
			list.addAll(c);
		}
		return list;
	}

	private TargetUnitCluster getHomeCluster() {
		return m.opponentTracker.clusterManager.getHomeBaseCluster();
	}

	private TargetUnitCluster getEnemyBaseCluster() {
		for (TargetUnitCluster c : m.opponentTracker.clusterManager
				.getAllClusters()) {
			if (c.hasEnemyBase())
				return c;
		}
		return null;
	}

	private TargetUnitCluster getStragglerCluster() {
		for (TargetUnitCluster c : m.opponentTracker.clusterManager
				.getAllClusters()) {
			if (!(c.hasFriendlyBase() || c.hasEnemyBase()))
				return c;
		}
		return null;
	}

	private void drawTargeting() {
		// draw line to target cluster
		Game.getInstance().drawLineMap(targetCluster.getCenter().x(),
				targetCluster.getCenter().y(), squad.getPosition().x(),
				squad.getPosition().y(), Color.RED);

		// draw visibile enemies
		for (Unit u : targetCluster.getVisibleEnemyUnits()) {
			Game.getInstance().drawCircleMap(u.getPosition().x(),
					u.getPosition().y(), 2, Color.BLUE, false);
		}

		// draw potential threat enemies
		for (Unit u : targetCluster.getPotentialThreatUnits()) {
			Game.getInstance().drawCircleMap(u.getPosition().x(),
					u.getPosition().y(), 3, Color.RED, false);
		}

		int i = 0;
		// /*
		// Draw on screen.
		DrawingContext context = GameDrawingContext.INSTANCE;
		int Xoff = 450;
		int Yoff = 210;
		// */
		/*
		 * // Draw on window. DrawingContext context =
		 * WindowDrawingContexts.getDrawingContext(gTargetingWindowName); int
		 * Xoff = 10; int Yoff = 10; //
		 */
		context.drawTextScreen(Xoff, Yoff + 10 * i++, "Squad :" + squad.size()
				+ "/" + squad.getSquadHP());
		context.drawTextScreen(Xoff, Yoff + 10 * i++, "Harassment Limit: "
				+ minSquadHarassStrength);
		context.drawTextScreen(Xoff, Yoff + 10 * i++, "Status: " + status);
		context.drawTextScreen(Xoff, Yoff + 10 * i++, "Targets: b: "
				+ riskBases + " k: " + killTargets + " h : " + harassTargets);

		for (TargetUnitCluster b : basesAtRisk) {
			Game.getInstance().drawTextMap(b.getCenter().x() - 20,
					b.getCenter().y() - 30, " FB Under Attack");
		}

		for (TargetUnitCluster b : killableTargets) {
			Game.getInstance().drawTextMap(b.getCenter().x() - 20,
					b.getCenter().y() - 20, " Killable Target");
		}

		for (TargetUnitCluster b : harassmentTargets) {
			Game.getInstance().drawTextMap(b.getCenter().x() - 20,
					b.getCenter().y() - 10, " Harassment Target");
		}
	}

	private Collection<TargetUnitCluster> getBasesAtRisk() {
		Collection<TargetUnitCluster> potentialBases = m.opponentTracker
				.getEnemyClusters();
		Set<TargetUnitCluster> basesAtRisk = new HashSet<TargetUnitCluster>();

		for (TargetUnitCluster c : potentialBases) {

			// defend the base if we can win, or if it's the home base
			if (isUnderAttack(c)
					&& hasFriendlyBase(c)
					&& (c.equals(m.opponentTracker.clusterManager
							.getHomeBaseCluster()) || canWeWin(c.getThreats(),
							Status.DEFENDING))) {
				basesAtRisk.add(c);
			}
		}

		return basesAtRisk;
	}

	private boolean canWeWin(Collection<Unit> cluster, Status status) {
		if (squad.size() >= minSquadConfidentStrength)
			return true;
		return squad.size() >= mutasNeededToWin(getThreats(cluster, status));
	}

	private double mutasNeededToWin(Collection<Unit> threats) {
		double mutasNeeded = 0;
		for (Unit e : threats) {
			mutasNeeded += mutasNeeded(e.getType());
		}
		return mutasNeeded;
	}

	private double mutasNeeded(UnitType type) {
		if (type.equals(UnitType.TERRAN_MARINE))
			return 0.5;
		if (type.equals(UnitType.TERRAN_GHOST))
			return 1.0;
		if (type.equals(UnitType.TERRAN_GOLIATH))
			return 1.5;
		if (type.equals(UnitType.TERRAN_WRAITH))
			return 1.0;
		if (type.equals(UnitType.TERRAN_VALKYRIE))
			return 2.0;
		if (type.equals(UnitType.TERRAN_BATTLECRUISER))
			return 4.0;
		if (type.equals(UnitType.TERRAN_BUNKER))
			return 5.0;
		if (type.equals(UnitType.TERRAN_MISSILE_TURRET))
			return 3.0;
		if (type.equals(UnitType.PROTOSS_DRAGOON))
			return 1.0;
		if (type.equals(UnitType.PROTOSS_ARCHON))
			return 1.5;
		if (type.equals(UnitType.PROTOSS_HIGH_TEMPLAR))
			return 1.0;
		if (type.equals(UnitType.PROTOSS_HIGH_TEMPLAR))
			return 1.0;
		if (type.equals(UnitType.PROTOSS_SCOUT))
			return 1.0;
		if (type.equals(UnitType.PROTOSS_CORSAIR))
			return 1.5;
		if (type.equals(UnitType.PROTOSS_CARRIER))
			return 4.0;
		if (type.equals(UnitType.PROTOSS_ARBITER))
			return 3.0;
		if (type.equals(UnitType.PROTOSS_PHOTON_CANNON))
			return 4.0;
		if (type.equals(UnitType.ZERG_HYDRALISK))
			return 0.75;
		if (type.equals(UnitType.ZERG_MUTALISK))
			return 1.0;
		if (type.equals(UnitType.ZERG_SCOURGE))
			return 0.5;
		if (type.equals(UnitType.ZERG_DEVOURER))
			return 2.0;
		if (type.equals(UnitType.ZERG_SPORE_COLONY))
			return 4.0;
		return 0;
	}

	private Collection<Unit> getThreats(Collection<Unit> unitSet, Status status) {
		switch (status) {
		case HARASSING:
			ThreatFilter f = new ThreatFilters.DefendingDronesFilter();
			List<Unit> threats = new LinkedList<Unit>();
			for (Unit e : unitSet) {
				if (f.isThreat(e, squad.getUnits())) {
					threats.add(e);
				}
			}
			return threats;
		case ATTACKING:
		case DEFENDING:
		default:
			return unitSet;
		}
	}

	private boolean isUnderAttack(TargetUnitCluster c) {
		if (c.getAllEnemyUnits().isEmpty())
			return false;
		if (targetCluster.equals(c))
			return true; // if we're already defending this base, keep doing so
		int totalMineralCost = 0;
		for (Unit enemy : c.getAllEnemyUnits()) {
			if (WeaponType.NONE.equals(enemy.getType().groundWeapon())) {
				continue;
			}
			totalMineralCost += enemy.getType().mineralPrice()
					/ (enemy.getType().isTwoUnitsInOneEgg() ? 2 : 1);
		}
		return totalMineralCost >= underAttackThreshold(c);
	}

	private int underAttackThreshold(TargetUnitCluster c) {
		return isMainBase(c) ? 50 : 400;
	}

	private Collection<TargetUnitCluster> getKillableTargets() {
		Collection<TargetUnitCluster> potentialTargets = m.opponentTracker
				.getEnemyClusters();
		Set<TargetUnitCluster> killableTargets = new HashSet<TargetUnitCluster>();

		for (TargetUnitCluster c : potentialTargets) {
			if (c.getAllEnemyUnits().isEmpty())
				continue;

			// be conservative until we get up to a critical mass of mutas
			if (canWeWin(c.getThreats(), Status.ATTACKING)) {
				killableTargets.add(c);
			}
		}

		return killableTargets;
	}

	private Collection<TargetUnitCluster> getHarassmentTargets() {
		Collection<TargetUnitCluster> potentialTargets = m.opponentTracker
				.getEnemyClusters();
		Set<TargetUnitCluster> harassmentTargets = new HashSet<TargetUnitCluster>();

		for (TargetUnitCluster c : potentialTargets) {
			if (hasEnemyBase(c) && hasEnemyWorkers(c)
					&& canWeWin(c.getThreats(), Status.HARASSING)) {
				harassmentTargets.add(c);
			}
		}

		return harassmentTargets;
	}

	private void updateTargets() {
		basesAtRisk = getBasesAtRisk();
		killableTargets = getKillableTargets();
		harassmentTargets = getHarassmentTargets();

		riskBases = basesAtRisk.size();
		killTargets = killableTargets.size();
		harassTargets = harassmentTargets.size();

	}

	private void checkClusterAssignment() {
		updateHidingWorkers();
		updateTargets();

		TargetUnitCluster newCluster = null;
		Status newStatus = Status.RETREATING;

		// Targeting: first choose among bases under attack, then choose among
		// killable targets, then finally harass

		List<TargetUnitCluster> candidates = new ArrayList<TargetUnitCluster>(
				basesAtRisk.size() + harassmentTargets.size()
						+ killableTargets.size());
		List<Status> candidateStatuses = new ArrayList<Status>(basesAtRisk
				.size()
				+ harassmentTargets.size() + killableTargets.size());
		List<Position> candidatePositions = new ArrayList<Position>(basesAtRisk
				.size()
				+ harassmentTargets.size() + killableTargets.size());
		List<Double> candidateCosts = new ArrayList<Double>(basesAtRisk.size()
				+ harassmentTargets.size() + killableTargets.size());

		double costMultiplier = 2;
		for (TargetUnitCluster c : basesAtRisk) {
			candidates.add(c);
			candidateStatuses.add(Status.DEFENDING);
			candidatePositions.add(getClusterPosition(c, Status.DEFENDING));
			candidateCosts.add(costMultiplier * getDefendCost(c));
		}
		for (TargetUnitCluster c : harassmentTargets) {
			candidates.add(c);
			candidateStatuses.add(Status.HARASSING);
			candidatePositions.add(getClusterPosition(c, Status.HARASSING));
			candidateCosts.add(costMultiplier * getHarassCost(c));
		}
		for (TargetUnitCluster c : killableTargets) {
			candidates.add(c);
			candidateStatuses.add(Status.ATTACKING);
			candidatePositions.add(getClusterPosition(c, Status.ATTACKING));
			candidateCosts.add(costMultiplier * getKillCost(c));
		}
		for (int i = 0; i < candidates.size(); i++) {
			logger.debug("Candidate: " + candidateStatuses.get(i) + " at ("
					+ candidatePositions.get(i).x() + ","
					+ candidatePositions.get(i).y() + ") Cost: "
					+ candidateCosts.get(i));
		}

		// TODO fix hard-coded viaAir assumption
		Pair<Integer, Double> bestCluster = pathfinder.getBestGoal(squad
				.getPosition(), candidatePositions, candidateCosts, true,
				ThreatTracker.MUTALISK_THREAT_MULTIPLIER);
		if (bestCluster != null && bestCluster.getFirst() >= 0) {
			newCluster = candidates.get(bestCluster.getFirst());
			newStatus = candidateStatuses.get(bestCluster.getFirst());
			Position pos = candidatePositions.get(bestCluster.getFirst());
			logger.debug("Best cluster at position (" + pos.x() + "," + pos.y()
					+ ") with status " + newStatus + ".  Path cost: "
					+ bestCluster.getSecond() + " Goal cost: "
					+ candidateCosts.get(bestCluster.getFirst()));
		}

		if (!(status.equals(newStatus) && targetCluster.equals(newCluster))) {
			if ((newStatus == Status.ATTACKING && (squad.size() < minSquadStrength || squad
					.getSquadHP() < minSquadStrength
					* UnitType.ZERG_MUTALISK.maxHitPoints() * 0.5))
					|| (newStatus == Status.HARASSING && (squad.size() < minSquadHarassStrength || squad
							.getSquadHP() < minSquadHarassHP))) {
				newStatus = status;
				newCluster = targetCluster;
			}
		}

		// if we're losing strength while harassing, retreat and make us need to
		// be stronger to harass
		if (status == Status.HARASSING
				&& (squad.getSquadHP() <= maxForceHP * .5 || squad.size() <= maxForceSize * .75)) {
			minSquadHarassHP = maxForceHP * 1.2;
			minSquadHarassStrength = (int) (maxForceSize * 1.2);
			newStatus = Status.RETREATING;
			newCluster = null;
			// logger.info("Microsquad: retreating from harassment, want: "+minSquadStrength
			// + " have " + squad.size());
		}

		// if we're losing strength while attacking, retreat and make us need to
		// be stronger to harass
		if (status == Status.ATTACKING
				&& (squad.getSquadHP() <= maxForceHP * .33 || squad.size() <= maxForceSize * .5)) {
			minSquadConfidentStrength = Math.max(minSquadConfidentStrength,
					(int) (maxForceSize * 1.5));
			newStatus = Status.RETREATING;
			newCluster = null;
			// logger.info("Microsquad: retreating from harassment, want: "+minSquadStrength
			// + " have " + squad.size());
		}

		if (newCluster == null) {
			newStatus = Status.RETREATING;
			newCluster = m.opponentTracker.clusterManager.getHomeBaseCluster();

			// logger.info("Microsquad: no target picked, retreating");
		}

		if (targetCluster == null || !newStatus.equals(status)
				|| !newCluster.equals(targetCluster)) {
			status = newStatus;
			targetCluster = newCluster;
			squad.setTargetCluster(targetCluster, status);
			setTarget(status == Status.HARASSING ? UnitUtils.getClosestMineral(
					targetCluster.getCenter()).getLastKnownPosition()
					: targetCluster.getCenter());
			resetCurrentWanderingCircuit();
		} else if (status == Status.ATTACKING && squad.atDestination()
				&& !squad.killingStuff()) {
			wandering = true;
			pickNextTarget();
		} else if (wandering && squad.killingStuff()) {
			wandering = false;
			resetCurrentWanderingCircuit();
		} else if (status == Status.HARASSING && squad.atDestination()
				&& !squad.killingStuff()) {
			for (Unit w : targetCluster.getEnemyWorkers()) {
				hidingWorkers.put(w, 0);
			}
		}
	}

	private Position getClusterPosition(TargetUnitCluster c, Status status) {
		if (targetCluster.equals(c) && squad.atDestination())
			return squad.getPosition();
		switch (status) {
		case DEFENDING:
			Unit closest = UnitUtils.getClosest(squad.getPosition(), c
					.getPotentialThreatUnits());
			return Vector.diff(closest.getLastKnownPosition(),
					squad.getPosition()).normalize(224).addTo(
					closest.getLastKnownPosition());
		case HARASSING:
			return UnitUtils.getClosestMineral(c.getCenter())
					.getLastKnownPosition();
		case ATTACKING:
		default:
			return c.getCenter();

		}
	}

	private double getKillCost(TargetUnitCluster c) {
		double riskToMutas = computeDamagePotential(c.getAllEnemyUnits(), true,
				false);
		double riskToFriendlies = c.getFriendlyUnits().isEmpty() ? 0.0
				: computeDamagePotential(c.getAllEnemyUnits(), false, false);
		return riskToMutas - riskToFriendlies;
	}

	private double getHarassCost(TargetUnitCluster c) {
		double riskToMutas = computeDamagePotential(c.getAllEnemyUnits(), true,
				true); // TODO: fix
		// air
		// assumption
		double miningPotential = c.getEnemyWorkers().size() * 8;
		return riskToMutas - miningPotential;
	}

	private double getDefendCost(TargetUnitCluster c) {
		double damagePotential = 2 * computeDamagePotential(c
				.getAllEnemyUnits(), false, false);
		if (isMainBase(c))
			damagePotential *= 3;
		return -damagePotential;
	}

	private boolean isMainBase(TargetUnitCluster c) {
		for (Unit f : c.getFriendlyUnits()) {
			UnitType t = f.getType();
			if (t.equals(UnitType.ZERG_SPIRE) || t.equals(UnitType.ZERG_LAIR)
					|| t.equals(UnitType.ZERG_HIVE))
				return true;
		}
		return false;
	}
	
	private double dpsVsSquad(Collection<Unit> threats) {
		double totalDps = 0;
		for (Unit u : threats) {
			WeaponType w = u.getType().airWeapon();
			if (u.getType().equals(UnitType.TERRAN_BUNKER)) {
				w = WeaponType.GAUSS_RIFLE;
			}
			if (u.getType().isBuilding() && u.isUnpowered()) {
				w = WeaponType.NONE;
			}
			if (w.equals(WeaponType.NONE))
				continue;
			double shotsPerSecond = 24.0 / w.damageCooldown();
			double dps = (u.getPlayer().getWeaponDamage(w) - Game.getInstance().self().getUpgradeLevel(UpgradeType.ZERG_FLYER_CARAPACE))
					* (w.damageType().equals(DamageType.EXPLOSIVE) ? 0.5 : 1.0 ) * shotsPerSecond;
			if (u.getType().equals(UnitType.TERRAN_BUNKER)) {
				dps *= 4;
			}
			totalDps += dps;
		}
		return totalDps;
	}


	private double computeDamagePotential(Collection<Unit> threats,
			boolean vsAir, boolean harassTargetsOnly) {
		ThreatFilter f = null;
		if (harassTargetsOnly) {
			f = new ThreatFilters.DefendingDronesFilter();
		}
		double totalDps = 0;
		for (Unit u : threats) {
			WeaponType w = vsAir ? u.getType().airWeapon() : u.getType()
					.groundWeapon();
			if (u.getType().equals(UnitType.TERRAN_BUNKER)) {
				w = WeaponType.GAUSS_RIFLE;
			}
			if (u.getType().isBuilding() && u.isUnpowered()) {
				w = WeaponType.NONE;
			}
			if (w.equals(WeaponType.NONE))
				continue;
			if (harassTargetsOnly && u.getType().isBuilding()
					&& !f.isThreat(u, squad.getUnits())) {
				continue;
			}
			double shotsPerSecond = 24.0 / w.damageCooldown();
			double dps = u.getPlayer().getWeaponDamage(w) * shotsPerSecond;
			if (u.getType().equals(UnitType.TERRAN_BUNKER)) {
				dps *= 4;
			}
			totalDps += dps;
		}
		return totalDps;
	}

	private double computeHpToKill(TargetUnitCluster c,
			boolean harassTargetsOnly) {
		ThreatFilter f = null;
		if (harassTargetsOnly) {
			f = new ThreatFilters.DefendingDronesFilter();
		}
		double total = 0;
		for (Unit u : c.getAllEnemyUnits()) {
			if (harassTargetsOnly
					&& !(u.getType().isWorker() || f.isThreat(u, squad
							.getUnits()))) {
				continue;
			}
			if (!u.isVisible()) {
				u = u.getPreviousUnitData();
			}
			if (u == null) {
				continue;
			}
			total += u.getHitPoints() + u.getShields();
		}
		return total;
	}

	private void updateHidingWorkers() {
		for (Unit w : new ArrayList<Unit>(hidingWorkers.keySet())) {
			int frames = hidingWorkers.get(w) + 1;
			if (frames >= hidingTimerLength) {
				hidingWorkers.remove(w);
			} else {
				hidingWorkers.put(w, frames);
			}
		}
	}

	public Status getStatus() {
		return status;
	}

	private boolean hasFriendlyBase(TargetUnitCluster newCluster) {
		// for (Unit f : newCluster.getFriendlyUnits()) {
		// if (f.getType().isBuilding()) return true;
		// }
		// return false;

		return newCluster.hasFriendlyBase();

	}

	private boolean hasEnemyBase(TargetUnitCluster newCluster) {
		// for (Unit f : newCluster.getAllEnemyUnits()) {
		// if (f.getType().isResourceDepot()) return true;
		// }
		// return false;

		return newCluster.hasEnemyBase();

	}

	private boolean hasEnemyWorkers(TargetUnitCluster newCluster) {
		return newCluster.hasEnemyWorkers(hidingWorkers.keySet());
	}

	private void resetCurrentWanderingCircuit() {
		if (baseLocations != null) {
			logger.info("Found something to shoot!  Resetting circuit of possible base locations.");
			completedBaseLocationCircuit = false;
			baseLocations = null;
			baseLocationsChecked = null;
			currentBaseLocation = -1;
		}
	}

	public void addUnit(OvermindUnit u) {
		squad.addUnit(u);
	}

	public void removeUnit(OvermindUnit u) {
		squad.removeUnit(u);
	}
}
