User:Chase-san/NewTech/KakeruCode

Code for version MC25

/**
 * Copyright (c) 2011 Chase
 * 
 * This software is provided 'as-is', without any express or implied
 * warranty. In no event will the authors be held liable for any damages
 * arising from the use of this software.
 * 
 * Permission is granted to anyone to use this software for any purpose,
 * including commercial applications, and to alter it and redistribute it
 * freely, subject to the following restrictions:
 * 
 *    1. The origin of this software must not be misrepresented; you must not
 *    claim that you wrote the original software. If you use this software
 *    in a product, an acknowledgment in the product documentation would be
 *    appreciated but is not required.
 * 
 *    2. Altered source versions must be plainly marked as such, and must not be
 *    misrepresented as being the original software.
 * 
 *    3. This notice may not be removed or altered from any source
 *    distribution.
 */
/*
 * Dear Future Chase,
 * 
 * I cannot even begin to express how deeply sorry I am.
 * But I assure you, at the time, I (probably) knew what I was doing.
 * 
 * -Chase
 * 
 * P.S. I am trying to leave comments,
 *      but you know how bad I am at those.
 */

package cs.move;

import java.awt.Color;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;

import cs.Chikaku;
import cs.geom.*;
import cs.utils.*;

import ags.utils.KdTree;
import ags.utils.KdTree.Entry;
import robocode.*;
import robocode.util.Utils;

/**
 * Movement
 * <br/><br/>
 * In Japanese, Kakeru means "Dash" (in some cases)
 * @author Chase
 */
public abstract class Kakeru extends Chikaku {
	private static final int MaxTurnHistoryLength = 20;
	private static final int MaxHeatWaveQueueLength = 4;
	private static final int AverageSingleRoundTime = 1200;
	private static final int NearestNeighborsToUseInSurfing = 16;

	/**
	 * Keep in mind with heat waves we will have waves 2 rounds earlier
	 * the the gun heat would otherwise indicate
	 */
	private static final int TimeBeforeFirstWaveToStartTurning = 4;

	private static final MaximumDeque<Double> enemyBulletPower;
	private static final KdTree<Data> tree;

	static {
		enemyBulletPower = new MaximumDeque<Double>(MaxHeatWaveQueueLength);
		enemyBulletPower.addLast(3.0);

		int dimensions = new Data().getDataArray().length;
		tree = new KdTree.SqrEuclid<Data>(dimensions, 0);

		Data data = new Data();
		data.weight = 0.1;
		tree.addPoint(data.getDataArray(), data);
	}

	private final LinkedList<Wave<Data>> enemyWaves;
	private final MaximumDeque<State> history;
	private Vector lastEnemyPosition;
	private double lastEnemyEnergy;
	private double lastEnemyVelocity;
	private double enemyGunHeat;

	private int orbitDirection = 1;
	private boolean haveFiredImaginaryWave = false;

	public Kakeru() {
		enemyWaves = new LinkedList<Wave<Data>>();
		history = new MaximumDeque<State>(MaxTurnHistoryLength);
		lastEnemyPosition = new Vector(-1,-1);
		lastEnemyEnergy = 100;
	}

	@Override
	public void onRoundStarted(Event e) {
		super.onRoundStarted(e);

		/* Set it to be the same as our gun heat on round start! */
		enemyGunHeat = status.getGunHeat();
	}

	@Override
	public void onScannedRobot(ScannedRobotEvent e) {
		super.onScannedRobot(e);

		double angleToEnemy = e.getBearingRadians() + status.getHeadingRadians();
		double enemyVelocity = e.getVelocity();

		State state = new State();

		state.myPosition = myPosition;
		state.enemyPosition = myPosition.projectNew(angleToEnemy, e.getDistance());
		state.data.lateralVelocity = status.getVelocity()*Math.sin(e.getBearingRadians());
		state.data.advancingVelcity = status.getVelocity()*Math.cos(e.getBearingRadians());
		state.data.globalTime = globalTime;

		history.addFirst(state);

		int direction = Tools.sign(state.data.lateralVelocity);

		orbitDirection = direction;

		if(Math.abs(enemyVelocity) == 0 && lastEnemyVelocity > 2) {

			//Hit the wall!
			lastEnemyEnergy -= Rules.getWallHitDamage(lastEnemyVelocity);
		}

		/*
		 * Fire new imaginary wave if we can, heat waves
		 * are always 2 ticks previous to a real one 'possibly'
		 * being fired
		 */
		if(!haveFiredImaginaryWave) {
			if(enemyGunHeat <= 2.0*peer.getGunCoolingRate()) {
				haveFiredImaginaryWave = true;

				double power = 0;
				for(Double d : enemyBulletPower)
					power += d;
				power /= enemyBulletPower.size();

				/* Create the Wave */
				Wave<Data> wave = createMovementWave(power,direction);
				wave.set(simulatedEnemyPosition);
				wave.imaginary = true;

				/*
				 * Only +1 because real waves are -1 in time,
				 * meaning that by the time we detect them, it has
				 * already been 1 turn since it was fired, meaning
				 * heat waves +2 makes it only +1 here. :-)
				 */
				wave.fireTime = time + 1;
				wave.directAngle = wave.angleTo(state.myPosition);

				wave.data = state.data;

				enemyWaves.add(wave);
			}
		}

		/* Check for new enemy wave */
		double enemyEnergy = e.getEnergy();
		double energyDelta = lastEnemyEnergy - enemyEnergy;
		if(energyDelta > 0 && energyDelta <= 3.0) {

			enemyGunHeat += Rules.getGunHeat(energyDelta);
			haveFiredImaginaryWave = false;

			State old = history.get(2);
			direction = Tools.sign(old.data.lateralVelocity);

			/* Create the Wave */
			Wave<Data> wave = createMovementWave(energyDelta,direction);
			wave.set(lastEnemyPosition);

			wave.fireTime = time - 1;
			wave.directAngle = wave.angleTo(old.myPosition);

			wave.data = old.data;

			enemyBulletPower.addLast(wave.power);
			enemyWaves.add(wave);
		}

		lastEnemyPosition = state.enemyPosition;
		lastEnemyVelocity = enemyVelocity;
		lastEnemyEnergy = enemyEnergy;

	}

	private Wave<Data> createMovementWave(double power, int direction) {
		Wave<Data> wave = new Wave<Data>();
		wave.power = power;
		wave.speed = Rules.getBulletSpeed(wave.power);
		wave.escapeAngle = Math.asin(8.0/wave.speed) * direction;
		return wave;
	}

	@Override
	public void onTurnEnded(Event e) {
		super.onTurnEnded(e);

		/* Don't move if we are scanning, this is mostly start
		 * of round fast radar finding protection
		 */
		if(initialTick != 0)
			return;

		/* We track the gun heat because it is important
		 * for our heat/imaginary waves
		 */
		enemyGunHeat -= coolingRate;
		if(enemyGunHeat <= 0)
			enemyGunHeat = 0;

		/* Take are of all waves that cannot possibly even conceivably hit us anymore */
		checkWaves();

		/* Run our 'actual' movement */
		doMovement();
	}

	private void checkWaves() {
		Iterator<Wave<Data>> waveIterator = enemyWaves.iterator();
		while(waveIterator.hasNext()) {
			Wave<Data> wave = waveIterator.next();

			double radius = wave.getRadius(time);

			/* /////////////////////// */
			/* DRAW WAVE */
			g.setColor(new Color(128,128,128));
			double escape = Tools.abs(wave.escapeAngle);
			g.drawArc(
					(int)(wave.x - radius), (int)(wave.y - radius),
					(int)(radius*2), (int)(radius*2),
					(int)Math.toDegrees(wave.directAngle-escape),
					(int)Math.toDegrees(escape*2));
			/* END DRAW WAVE */
			/* /////////////////////// */

			if(wave.imaginary) {
				/*
				 * if the wave is imaginary (a heat wave)
				 * we should remove it automatically after
				 * 2 ticks which is when we will detect their
				 * actual wave, if they fire
				 */
				if(time - wave.fireTime > 2) {
					waveIterator.remove();
				}
			} else
				/* Clean up waves that can no longer hit us */
				if(wave.didIntersect(myPosition, time)) {
					waveIterator.remove();
				}
		}
	}

	private Wave<Data> findBestSurfableWave() {
		double halfBotWidth = 18 + Math.sin(lastEnemyPosition.angleTo(myPosition))*7.4558441;
		//find the wave soonest to hit us
		Wave<Data> wave = null;
		double bestETA = Double.POSITIVE_INFINITY;
		for(Wave<Data> check : enemyWaves) {
			double distance = myPosition.distance(check) - check.getRadius(time);
			double ETA = distance / check.speed;

			if(distance < 0 && Math.abs(distance) + check.speed > halfBotWidth)
				continue;

			if(ETA < bestETA) {
				//If we are already surfing a strong wave
				//that will hit at almost the same time
				//do not switch to this wave, more powerful
				//waves are slower and thus will always be
				//shot first for this to occur, which is why
				//we don't need an else on the ETA < bestETA

				//This is mostly just a hack for some score
				if(wave != null && ETA > bestETA - 3) {
					if(check.power > wave.power) {
						wave = check;
						bestETA = ETA;
					}
				} else {
					wave = check;
					bestETA = ETA;
				}
			}
		}

		return wave;
	}


	private void checkMove(Simulate sim, Wave<Data> wave, int orbitDirection) {
		Move move = predictMove(sim.position,wave,
				sim.heading,sim.velocity,orbitDirection);

		sim.angleToTurn = move.angleToTurn;
		sim.direction = move.direction;
		sim.maxVelocity = Tools.min(sim.maxVelocity, move.maxVelocity);
	}

	/**
	 * Calculate the driving
	 */
	protected Move predictMove(Vector myPosition, Vector orbitCenter,
			double myHeading, double myVelocity, int orbitDirection) {
		Move data = new Move();

		/* Better safe then very very sorry */
		if(orbitDirection == 0)
			orbitDirection = 1;

		double angleToRobot = orbitCenter.angleTo(myPosition);

		/*
		 * if the orbit direction is clockwise/counter, we want to try and
		 * point our robot in that direction, which is why we multiply by it
		 */
		double travelAngle = angleToRobot + (Math.PI/2.0) * orbitDirection;

		/* DONE add distancing to drive method */
		/* TODO add a better distancing method */
		double distance = myPosition.distance(orbitCenter);
		final double best = 500.0;
		double distancing = ((distance-best)/best);

		travelAngle += distancing*orbitDirection;

		/* DONE add a wall smoothing method */
		/* TODO add a better wall smoothing method */
		while(!field.contains(myPosition.projectNew(travelAngle, 140))) {
			travelAngle += 0.08*orbitDirection;
		}

		data.angleToTurn = Utils.normalRelativeAngle(travelAngle - myHeading);
		data.direction = 1;

		/*
		 * If our backend is closer to direction, use that instead, and
		 * inform the caller that we are going to be going in reverse instead
		 */
		if(Tools.abs(data.angleToTurn) > Math.PI/2.0) {
			data.angleToTurn = Utils.normalRelativeAngle(data.angleToTurn - Math.PI);
			data.direction = -1;
		}

		/*
		 * Slow down so we do not ram head long into the walls and can instead turn to avoid them
		 * FIXME We only have to do this because of the wall smoothing, fix that to get rid of this!
		 */
		if(!field.contains(myPosition.projectNew(myHeading, myVelocity*3.25)))
			data.maxVelocity = 0;

		if(!field.contains(myPosition.projectNew(myHeading, myVelocity*5)))
			data.maxVelocity = 4;

		return data;
	}

	private void doMovement() {
		Wave<Data> wave = findBestSurfableWave();
		if(wave == null) {
			doWavelessMovement();
			return;
		}

		g.setColor(Color.WHITE);
		g.draw(field.toRectangle2D());

		doSurfingMovement(wave);
	}

	private void doSurfingMovement(Wave<Data> wave) {
		/* Do the actual surfing and such */
		g.setColor(Color.ORANGE);

		peer.setMaxVelocity(Rules.MAX_VELOCITY);

		Risk[] directions = new Risk[] {
				checkWaveRisk(wave,orbitDirection,0),
				checkWaveRisk(wave,orbitDirection,Rules.MAX_VELOCITY),
				checkWaveRisk(wave,-orbitDirection,Rules.MAX_VELOCITY),
		};

		int bestIndex = 0;
		double minRisk = Double.POSITIVE_INFINITY;
		for(int i = 0; i < directions.length; ++i) {
			if(directions[i].risk < minRisk) {
				bestIndex = i;
				minRisk = directions[i].risk;
			}
		}

		Move move = predictMove(myPosition,lastEnemyPosition,
				status.getHeadingRadians(),status.getVelocity(),
				directions[bestIndex].orbitDirection );

		peer.setMaxVelocity(Tools.min(directions[bestIndex].maxVelocity,move.maxVelocity));
		peer.setTurnBody(move.angleToTurn);
		peer.setMove(1000*move.direction);
		peer.setCall();
	}

	private Risk checkWaveRisk(Wave<Data> wave, int orbitDirection, double maxVelocity) {
		/*
		 * Simplify the output to our direction chooser
		 */
		Risk waveRisk = new Risk();
		waveRisk.orbitDirection = orbitDirection;
		waveRisk.maxVelocity = maxVelocity;

		/*
		 * Create a simulator for our movement
		 */
		Simulate sim = createSimulator();
		sim.maxVelocity = maxVelocity;
		sim.direction = orbitDirection;

		/*
		 * Used for our distance danger
		 */
		double currentDistance = wave.distance(sim.position);
		double predictedDistance = 0;
		int intersected = 0;

		long timeOffset = 0;

		/*
		 * Reset the factors, so we do not get cross risk check contamination
		 */
		wave.resetFactors();

		/*
		 * Since our radar is limited to 1200 and the slowest bullet moves at
		 * 11 per second, calculating past 110 is pointlessly impossible, so
		 * it is a safe number to use as our break point.
		 */
		while(timeOffset < 110) {
			//DRAW DANGER MOVEMENT
			g.drawOval((int)sim.position.x-3, (int)sim.position.y-3, 6, 6);

			if(wave.doesIntersect(sim.position, time+timeOffset)) {
				++intersected;
				predictedDistance += wave.distance(sim.position);
			} else if(intersected > 0) {
				predictedDistance /= intersected;

				waveRisk.risk += checkIntersectionRisk(wave,predictedDistance);
				break;
			}

			checkMove(sim,wave,orbitDirection);
			sim.step();
			sim.maxVelocity = maxVelocity;

			++timeOffset;
		}

		if(intersected > 0) {
			double distanceRisk = currentDistance / predictedDistance;
			distanceRisk *= distanceRisk;

			//distanceRisk = (distanceRisk + 1.0) / 2.0;
			//System.out.println(distanceRisk);

			waveRisk.risk *= distanceRisk;
		}


		return waveRisk;
	}

	private double checkIntersectionRisk(Wave<Data> wave, double predicted) {
		double risk = 0;
		double factorCenter = (wave.minFactor + wave.maxFactor) / 2.0;

		double factorRange = Tools.abs(wave.maxFactor - wave.minFactor);
		double bandwidth = factorRange / Tools.abs(wave.escapeAngle);

		List<Entry<Data>> list = tree.nearestNeighbor(wave.data.getWeightedDataArray(),
				NearestNeighborsToUseInSurfing, false);

		for(Entry<Data> e : list) {
			Data data = e.value;

			double entryRisk = 0.1/(1.0+Tools.abs(data.guessfactor-factorCenter));

			if(wave.minFactor < data.guessfactor && wave.maxFactor > data.guessfactor) {
				entryRisk += 0.9;
			}

			double timeWeight = 1.0+AverageSingleRoundTime/(double)(globalTime-data.globalTime);

			//kernel calculation neh?

			double density = 0;

			for(Entry<Data> ex : list) {
				double ux = (e.value.guessfactor-data.guessfactor) / bandwidth;
				double sw = ex.value.weight / (1.0+ex.distance);
				density += Math.exp(-0.5*ux*ux)*sw;
			}

			//System.out.println(density);

			double weight = (data.weight / (1.0+e.distance)) * timeWeight * density;

			//System.out.println(weight);
			//System.out.println(entryRisk);

			risk += 1.0-(1.0/(1.0+weight*entryRisk));
		}

		return risk/NearestNeighborsToUseInSurfing;
	}

	private void doWavelessMovement() {
		final int initialTurns = (int)Math.ceil(3.0/coolingRate+4.0);
		double safeTurns = status.getGunHeat()/coolingRate;

		if(time < initialTurns) {
			/* Do we have enough time to move around before they can start firing? */
			if(safeTurns > TimeBeforeFirstWaveToStartTurning) {
				doMinimalRiskMovement();
			} else {
				Move data = predictMove(myPosition,lastEnemyPosition,
						status.getHeadingRadians(),status.getVelocity(),orbitDirection);
				peer.setTurnBody(data.angleToTurn);
				peer.setMaxVelocity(0);

				peer.setMove(0);
				//peer.setTurnBody(0);
				peer.setMaxVelocity(0);
			}
		} else {
			/*
			 * Things are no longer safe, set our movement to `sane`
			 * 
			 * TODO: RAM if enemy is disabled
			 */
			if(status.getOthers() == 0) {
				/*
				 * No bullets in the air, enemy dead, we can do our victory DANCE (YAY!)
				 */
				doVictoryDance();
			} else {
				//Some other thing to do when nothing is in the air??
				doMinimalRiskMovement();
			}
		}
	}

	protected void doMinimalRiskMovement() {
		double heading = status.getHeadingRadians();
		double velocity = status.getVelocity();

		Rectangle escapeField = new Rectangle(30,30,fieldWidth-60,fieldHeight-60);
		g.setColor(Color.WHITE);
		g.draw(escapeField.toRectangle2D());

		//Do minimal risk movement
		Vector target = myPosition.copy();
		Vector bestTarget = myPosition;
		double angle = 0;
		double bestRisk = checkWavelessRisk(bestTarget);
		double enemyDistance = myPosition.distance(lastEnemyPosition)+18;
		while(angle < Math.PI*2) {
			double targetDistance = Tools.min(200,enemyDistance);

			target.setProject(myPosition, angle, targetDistance);
			if(escapeField.contains(target)) {
				double risk = checkWavelessRisk(target);
				if(risk < bestRisk) {
					bestRisk = risk;
					bestTarget = target.copy();
				}
				g.setColor(Color.BLUE);
				g.drawRect((int)target.x-2, (int)target.y-2, 4, 4);

			}
			angle += Math.PI/32.0;
		}
		g.setColor(bodyColor);
		g.drawRect((int)bestTarget.x-2, (int)bestTarget.y-2, 4, 4);

		double travelAngle = myPosition.angleTo(bestTarget);

		double forward = myPosition.distance(bestTarget);

		double angleToTurn = Utils.normalRelativeAngle(travelAngle - status.getHeadingRadians());
		int direction = 1;

		if(Tools.abs(angleToTurn) > Math.PI/2.0) {
			angleToTurn = Utils.normalRelativeAngle(angleToTurn - Math.PI);
			direction = -1;
		}

		//Slow down so we do not ram head long into the walls and can instead turn to avoid them
		double maxVelocity = Rules.MAX_VELOCITY;

		if(!field.contains(myPosition.projectNew(heading, velocity*3.25)))
			maxVelocity = 0;

		if(!field.contains(myPosition.projectNew(heading, velocity*5)))
			maxVelocity = 4;

		if(angleToTurn > 1.0) {
			maxVelocity = 0;
		}

		peer.setMaxVelocity(maxVelocity);
		peer.setTurnBody(angleToTurn);
		peer.setMove(forward*direction);
	}

	private double checkWavelessRisk(Vector pos) {
		double risk = lastEnemyEnergy/pos.distanceSq(lastEnemyPosition);

		for(Line edge : field.getLines()) {
			risk += 5.0/(1.0+edge.ptSegDistSq(pos));
		}

		g.setColor(Color.RED);
		/*
		 * get points between enemy location and corner and add risk!!!!
		 * these are bad places to be! Our hitbox is larger here if nothing else!
		 */
		for(Vector corner : field.getCorners()) {
			corner.add(lastEnemyPosition);
			corner.scale(0.5);
			if(corner.distanceSq(lastEnemyPosition) < 22500 /* 150 */) {
				g.drawRect((int)corner.x-2, (int)corner.y-2, 4, 4);
			}
			risk += 5.0/(1.0+corner.distanceSq(pos));
		}

		return risk;
	}

	/**
	 * Account for our bullets hitting the enemy
	 */
	@Override
	public void onBulletHit(BulletHitEvent e) {
		super.onBulletHit(e);

		/* Get the power of the bullet of ours that hit */
		double bulletPower = e.getBullet().getPower();

		/* Determine how much damage our bullet does to the enemy
		 * and adjust our stored copy to reflect the amount lost
		 */
		lastEnemyEnergy -= Rules.getBulletDamage(bulletPower);
	}

	/**
	 * Account for one of our bullets hitting an enemy bullet.
	 */

	@Override
	public void onBulletHitBullet(BulletHitBulletEvent e) {
		super.onBulletHitBullet(e);

		handleBullet(e.getHitBullet());
	}

	/**
	 * Account for one of the enemies bullets hitting us.
	 */
	@Override
	public void onHitByBullet(HitByBulletEvent e) {
		super.onHitByBullet(e);

		/*
		 * Increase the enemy energy based on how powerful the bullet that
		 * hit us was this is so we can get reliable energy drop detection
		 */
		lastEnemyEnergy += Rules.getBulletHitBonus(e.getPower());

		handleBullet(e.getBullet());
	}

	/**
	 * Handle an actual enemy bullet
	 */
	private void handleBullet(Bullet b) {
		Vector bulletPosition = new Vector(b.getX(),b.getY());

		/* Find the matching wave */
		Iterator<Wave<Data>> waveIterator = enemyWaves.iterator();
		while(waveIterator.hasNext()) {
			Wave<Data> wave = waveIterator.next();

			/* the current distance of the wave */
			double radius = wave.speed*(time - wave.fireTime);

			/* check if the power is close enough to be our wave. This
			 * margin is small, only to allow room for rounding errors
			 */
			if(Tools.abs(b.getPower()-wave.power) < 0.001) {

				/* check if the bullets distance from the center of
				 * the wave is close to our waves radius. This margin
				 * is small, only to allow room for rounding errors
				 */
				if(Tools.abs(wave.distanceSq(bulletPosition)-radius*radius) < 0.1) {
					/* FIXME extensively test this detection method */

					/* Alternate method, but why recalculate something? Could be used as an extra check. */
					/* updateTree(wave,wave.angleTo(bulletPosition)); */
					updateTree(wave,b.getHeadingRadians());

					waveIterator.remove();

					return;
				}
			}
		}

		/* If not found say so, cause someone (me) SCREWED UP!!! */
		println("Error: Unknown Bullet Collision");
		println("\tBullet:["+b.getX()+","+b.getY()+"] @ h"+b.getHeadingRadians()+" @ p" + b.getPower());
	}

	private void updateTree(Wave<Data> wave, double angleToBullet) {
		double angleOffset = Utils.normalRelativeAngle(angleToBullet - wave.directAngle);

		wave.data.guessfactor = angleOffset / wave.escapeAngle;

		//TODO
		//tree.addPoint(wave.data.getDataArray(), wave.data);
		tree.addPoint(wave.data.getWeightedDataArray(), wave.data);
	}
}


/**
 * Data gained from movement prediction
 */
class Move {
	double angleToTurn = 0;
	double maxVelocity = Rules.MAX_VELOCITY;
	int direction = 1;
}

class Risk {
	double risk;
	double maxVelocity;
	int orbitDirection;
}

public class State {
	Vector myPosition;
	Vector enemyPosition;
	Data data = new Data();
}

public class Data {
	long globalTime;

	double lateralVelocity;
	double advancingVelcity;
	double guessfactor;

	double weight = 1.0;

	public double[] getDataArray() {
		return new double[] {
				Math.abs(lateralVelocity)/8.0,
				(advancingVelcity+8.0)/16.0,
		};
	}

	public double[] getDataWeights() {
		return new double[] {
				1,
				1,
		};
	}

	public double[] getWeightedDataArray() {
		double[] data = getDataArray();
		double[] weights = getDataWeights();
		for(int i=0;i<data.length;++i) {
			data[i] *= weights[i];
		}
		return data;
	}
}

public class Wave<T> extends Vector {
	public long fireTime;
	public double escapeAngle;
	public double directAngle;
	public double speed;
	public double power;
	public boolean imaginary = false;
	
	public T data;
	
	public double getRadius(long time) {
		return speed*(time - fireTime);
	}
	
	
	public int intersected = 0;
	/**
	 * Used to determine if we can safely remove this wave
	 */
	public final boolean didIntersect(Vector target, long time) {
		hitbox.set(target, 36, 36);
		
		double radius = getRadius(time);
		double nextRadius = getRadius(time+1);
		Vector[] current = Tools.intersectRectCircle(hitbox, this, radius);
		Vector[] next = Tools.intersectRectCircle(hitbox, this, nextRadius);
		
		if(current.length != 0 || next.length != 0) {
			++intersected;
		} else {
			if(intersected > 0) {
				return true;
			}
		}
		
		return false;
	}
	
	public static Rectangle hitbox = new Rectangle();
	/**
	 * Used for calculating where a bullet will intersect a target
	 */
	public final boolean doesIntersect(Vector target, long time) {
		hitbox.set(target, 36, 36);
		
		double radius = getRadius(time);
		double nextRadius = getRadius(time+1);
		Vector[] current = Tools.intersectRectCircle(hitbox, this, radius);
		Vector[] next = Tools.intersectRectCircle(hitbox, this, nextRadius);
		
		if(current.length != 0 || next.length != 0) {
			for(Vector v : current)
				expandFactors(v);
			
			for(Vector v : next)
				expandFactors(v);
			
			Vector[] corners = hitbox.getCorners();
			for(Vector v : corners) {
				double distance = distanceSq(v); 
				if(distance < nextRadius*nextRadius
				&& distance > radius*radius) {
					expandFactors(v);
				}
			}
			
			return true;
		}
		
		return false;
	}
	
	public double minFactor = Double.POSITIVE_INFINITY;
	public double maxFactor = Double.NEGATIVE_INFINITY;
	
	/**
	 * Expand the guessfactors based on target location
	 */
	private void expandFactors(Vector pos) {
		double angle = Utils.normalRelativeAngle(angleTo(pos) - directAngle) / escapeAngle;
		if(angle < minFactor) minFactor = angle;
		if(angle > maxFactor) maxFactor = angle;
	}
	
	/**
	 * Reset our factors for calculating position (important!)
	 */
	public void resetFactors() {
		minFactor = Double.POSITIVE_INFINITY;
		maxFactor = Double.NEGATIVE_INFINITY;
	}
}