Linear Targeting/Buggy Implementations

Buggy Implementation #1

I've just recently started working on Robocode and I came up with this algorithm for predicting a bot's position travelling at a constant velocity: Geoff

 do{	// Time it will take for a bullet to get to the current prediction	
   double bulletTravelTime = getDistance(getX(), getY(), predictX, predictY) / bulletSpeed;
   // Check where the enemy will be in that amount of time	
   predictX = Enemy.getX() + (Enemy.getVelX() * bulletTravelTime);	
   predictY = Enemy.getY() + (Enemy.getVelY() * bulletTravelTime);	
   // Check for likely contact with a wall and adjust the prediction	
   // accordingly	
   if (predictX < 18) predictX = 18;	
   if (predictY < 18) predictY = 18;	
   if (predictX &gt; getBattleFieldWidth() - 18) predictX = getBattleFieldWidth() - 18;	
   if (predictY &gt; getBattleFieldHeight() - 18) predictY = getBattleFieldHeight() - 18;
   // The miss factor is the difference between the time it takes	
   // for a bullet to get to the current prediction and the time it	
   // takes for a bullet to get to the new prediction	
   missFactor =	Math.abs(bulletTravelTime - getDistance(getX(), getY(), predictX, 
                predictY) / bulletSpeed);	
   bulletTravelTime = getDistance(getX(), getY(), predictX, predictY) / 14;
 } while (missFactor &gt; 0.01);

It works fairly well, but I'm sure that I can improve the way that missFactor is calculated. The thing that I don't understand is why it doesn't work 90% of the time against Walls. I've been staring at it/tweaking it for too long to think properly now ;-p.

duyn: I tacked it on top of one of my bots and it seems to work fine. Check that you're working with radians and using sin and cos in the right order:

double getVelX() { return velocity*Math.sin(headingRadians); }
double getVelY() { return velocity*Math.cos(headingRadians); }

Buggy Implementation #2

I've taken a little time to also figure out some more geometric ways of doing it- this system always hits walls if he doesn't turn (and sometimes also gets him coming out of a turn, but I wouldn't depend on it). I don't really add it into my bots, though, because it doesn't hit anyone except walls and the guys who stand still.

double bulletv = 20-3*power;		//find bullet speed
/*
 * all the logic isn't here, I'd need to draw a picture to give you any idea what's going on.
 * The idea is I've constructed a triangle where you are at one corner, your opponent is on the second corner, 
 * and your opponent will be hit by your bullet at the third corner.  I use the Law of Sines:
 *	A/sine(a) == B/sine(b) == C/sine(c)
 * where A is the length of the side opposite angle a, etc.  The distance he has to travel, the distance your bullet 
 * has to travel, and the funny angle at the point where he is now (between the direction he's going and a straight line
 * from you to him) is enough to find the angle you need to turn your gun.  The "funny angle" (I'll call it 'ang')
 * happens to be 180+getHeading()+e.getBearing()-e.getHeading() (Except I used radians).  The distance my opponent travels
 * is enemyv*t where enemyv is his velocity and t is the amount of time before he is hit.  The distance my bullet travels is
 * bulletv*t where bulletv is calculated above.  I know from the above Law of Sines that:
 *	enemyv*t/sine(theta) = bulletv*t/sine(ang)
 *	sine(theta) = enemyv*t/(bulletv*t)*sine(ang)
 * Notice that the time is conveniently cancelled out.  "sine" is the value of sine(theta):
 */
double sine = e.getVelocity()/bulletv*Math.sin(Math.PI+getHeadingRadians()+e.getBearingRadians()-e.getHeadingRadians());
//and finally, theta is the distance I have to turn my gun:
double theta = Math.asin(sine)+getHeadingRadians()+e.getBearingRadians()-getGunHeadingRadians();
else if (theta > 0)
	turnGunRightRadians(theta);

Of course, the weakness here is that it doesn't check walls here. That could also be mathematically added using the third angle/side combination in the Law of cosines. The final angle would be 180-ang-Math.abs(theta) or something, and the length of the opposite side is e.getDistance(). From there... let me see, I haven't tried this, but I'll just wing it and maybe it works:

double finalangle = Math.PI - Math.abs(theta) - (Math.PI+getHeadingRadians()+e.getBearingRadians()-e.getHeadingRadians());
//	distance/sine(finalangle) == enemydistance/sine(theta)
double enemydistance = sine*e.getDistance()/Math.sin(finalangle);
//find their current position
double enemyStartX = getX() + e.getDistance()*Math.sin(getHeadingRadians()+e.getBearingRadians());
double enemyStartY = getY() + e.getDistance()*Math.cos(getHeadingRadians()+e.getBearingRadians());
//find their final destination
double endX = enemyStartX + enemydistance*Math.sin(e.getHeadingRadians());
double endY = enemyStartY + enemydistance*Math.cos(e.getHeadingRadians());
//figure out if they're off the screen, using offsets like David did above
if (endX < 18 || endY < 18 || endX > getBattleFieldWidth()-18 || endY > getBattleFieldHeight()-18)
{
	// now I'm going to try and find an equation for the line the opponent follows to find where it intersects with the edge.
	// finding the slope:
	double m = Math.atan(e.getHeadingRadians());
	//finding the y-intercept:
	double b = enemyStartY-enemyStartX*m;
	//now if I went off a side wall, this part is easy...
	if (endX < 18)	//plug 18 in as x (in my equation, which is in y=mx+b form)
	{
		endX = 18;
		endY = m*endX+b;
	}
	else if (endX > getBattleFieldWidth()-18)
	{
		endX = getBattleFieldWidth()-18;
		endY = m*endX+b;
	}
	//now for the top/bottom cases:
	if (endY < 18)
	{
		endY = 18;
		//now solve for x:
		endX = (endY-b)/m;
	}
	else if (endY > getBattleFieldHeight()-18)
	{
		endY = getBattleFieldHeight()-18;
		endX = (endY-b)/m;
	}
	//now adjust theta to aim at (endX, endY):
	theta = Math.atan2(endX-getX(), endY-getY())-getGunHeadingRadians();
}
//now turn the gun right theta radians and you're ready to fire!

Lol, well, anyone can feel free to correct typos or math on that if there are mistakes, hope it's right, though.

--Kawigi

---

Buggy Implementation #3

In addition, a simple but effective algorithm is the following trigonometric approach (without taking into account the walls)...

// let (rX,rY) be the opponents position at last scan, rVel be the opponent velocity, etc.

double bPower = 3;//Math.random()*(3-0.1)+0.1;
double bVel = 20-3*bPower;

final double k = (getTime()-rTime)+1;
final double cosRTh = Math.cos(rTh);
final double sinRTh = Math.sin(rTh);
final double a = rX-getX()+k*rVel*sinRTh;
final double b = getY()-rY-k*rVel*cosRTh;
final double d = (rVel/bVel)*(a*cosRTh+b*sinRTh);
				
double newTh = (a*d-b*Math.sqrt(a*a+b*b-d*d))/(a*a+b*b);
newTh = (((d-a*newTh)/b<0) ? -Math.acos(newTh): Math.acos(newTh));
				
double th = newTh-getGunHeadingRadians();
th = (th>PI ? th-twoPI : (th<-PI ? th+twoPI: th)); // turn the quickest way towards target
								
setTurnGunRightRadians(th);

--EventHorizon

Buggy Implementation #4

My implementation works, except for the line-shape intersect calculation. It works most of the time, except sometimes it iterates farther and farther from the actual intersection. The code is:

		
		double x=getX() + Math.sin(e.getBearingRadians()+getHeadingRadians())*e.getDistance();
		double y=getY() + Math.cos(e.getBearingRadians()+getHeadingRadians())*e.getDistance();
		Point2D.Double enemyPosition=new Point2D.Double(x,y);
		Point2D.Double myPosition=new Point2D.Double(getX(),getY());
		
		double ang=Math.asin((e.getVelocity()*Math.sin(e.getHeadingRadians()-(e.getBearingRadians()+getHeadingRadians())))/(20-(3*3)));
		Line2D.Double enemyMovement=new Line2D.Double(enemyPosition, projectPoint(enemyPosition,e.getHeadingRadians(),2000*sign(e.getVelocity())));
		Line2D.Double bulletMovement=new Line2D.Double(myPosition, projectPoint(myPosition,getHeadingRadians() + e.getBearingRadians()+ang,2000));
		dist=new Line2D.Double(myPosition, enemyPosition);
		//Tango's lineintersect method
		Point2D.Double intersect=new Point2D.Double(0,0);//point you are actually firing at
		double num   =   (enemyMovement.getY2()-enemyMovement.getY1())*(enemyMovement.getX1()-bulletMovement.getX1()) -
		                 (enemyMovement.getX2()-enemyMovement.getX1())*(enemyMovement.getY1()-bulletMovement.getY1());
		
		double denom =   (enemyMovement.getY2()-enemyMovement.getY1())*(bulletMovement.getX2()-bulletMovement.getX1()) -
		                 (enemyMovement.getX2()-enemyMovement.getX1())*(bulletMovement.getY2()-bulletMovement.getY1());
		
		intersect.x = bulletMovement.getX1() + (bulletMovement.getX2()-bulletMovement.getX1())*num/denom;
		intersect.y = bulletMovement.getY1() + (bulletMovement.getY2()-bulletMovement.getY1())*num/denom;
		out.println("NoWalls  : " + intersect);
		//nanos iterative lineintersectwithshape method
		if(!field.contains(intersect)){ //is where you are firing at in the battlefield?
			int TRACE_DEPTH = 20;
			Point2D middle;
			boolean containsFirst;
			if ((containsFirst = field.contains(enemyMovement.getP1())) == field.contains(enemyMovement.getP2())){
			}
			for (int i = 0; i < TRACE_DEPTH; i++) {
				out.println("Iteration " + i);
				middle = new Point2D.Double((enemyMovement.getX1() + enemyMovement.getX2()) / 2, (enemyMovement.getY1() + enemyMovement.getY2()) / 2);
				if (containsFirst != field.contains(middle)){
					enemyMovement = new Line2D.Double(enemyMovement.getP1(), middle);
				}else{
					enemyMovement = new Line2D.Double(middle, enemyMovement.getP2());
				}
				out.println(((enemyMovement.getX1() + enemyMovement.getX2()) / 2) + "," + ((enemyMovement.getY1() + enemyMovement.getY2()) / 2));
			}
			out.println("Out of loop");
			intersect.x=(enemyMovement.getX1() + enemyMovement.getX2()) / 2;
			intersect.y=(enemyMovement.getY1() + enemyMovement.getY2()) / 2;	
		}
		ang=Math.atan2(intersect.getX()-myPosition.getX(),intersect.getY()-myPosition.getY());
		setTurnGunRightRadians(Utils.normalRelativeAngle(ang-getGunHeadingRadians()));
		setFire(3);

Of course, you would replace the three with the bullet power you're using. But help with the intersection? (It's in debug mode btw, which is why it's printing out all the text) --Starrynte