Linear Targeting/Buggy Implementations

Hey, I've been suffering with trig, and I need help. I've been trying to create a linear targeting Virtual Gun for BulletSimBot, because the one it has at the moment is slightly inaccurate, and now it's many, many times more inaccurate... I need help! What's wrong with this? It ends up shooting opposite of where I want it to!

	//This calculates the angle the scanned robot would shoot at if he were using linear targeting, but fails miserably.
	public double linear(ScannedRobotEvent e, double power) {
		double absoluteBearing = getHeadingRadians() + e.getBearingRadians();
		double angleToFire = Utils.normalRelativeAngle(absoluteBearing + (e.getVelocity() * Math.asin(Math.sin(e.getHeadingRadians() - 
			absoluteBearing) / (20 - power * 3))));
		return angleToFire;
	}

Any help? PS: Am I supposed to move all of the numbers or something so that I'm number one and so on? --Awesomeness 03:11, 23 January 2010 (UTC)

No, you should actually move this to the bottom and label it number five. But I think think this belong to this page at all. --Nat Pavasant 12:02, 23 January 2010 (UTC)

Well, that "Utils.normalRelativeAngle" should be "Utils.normalAbsoluteAngle" since angleToFire is an absolute angle, unlike gunturn. Other than that it looks right to me. If that doesn't fix it, I'd suspect whatever code is making use of the 'angleToFire'. --Rednaxela 03:29, 23 January 2010 (UTC)

Changing it didn't seem to change the result at all. Can you test it? It's not working... And I tested the bullet simulator, it works fine. --Awesomeness 04:03, 23 January 2010 (UTC)

I think you want to calculate the angle **enemy** will shoot at you, not the angle you are shooting at enemy. So...

	//This calculates the angle the scanned robot would shoot at if he were using linear targeting, but fails miserably.
	public double linear(ScannedRobotEvent e, double power) {
		double absoluteBearing = Utils.normalAbsoluteAngle(getHeadingRadians() + e.getBearingRadians() + Math.PI);
		double angleToFire = Utils.normalAbsoluteAngle(absoluteBearing + (getVelocity() * Math.asin(Math.sin(e.getBearingRadians()) / (20 - power * 3))));
		return angleToFire;
	}

Well, in case you confused; since the targeting formula:

<math>

velocity \times \sin (targetHeading - targetAngle) \over {bulletVelocity} </math>

(TeX seems to be error, here is plain text version: velocity × sin(targetHeading - targetAngle) / bulletVelocity)

And thus the angle from enemy to you is your angle to enemy plus PI rad (= 180 degrees), yield targetAngle = getHeadingRadians() + e.getBearingRadians() + Math.PI

targetHeading is your own heading, since you are targeting your own robot. Put those things into the formula above will result in this sin expressions:

sin(getHeadingRadians() - getHeadingRadians() - e.getBearingRadians() - Math.PI) == sin(-e.getBearingRadians() - Math.PI) == Math.sin(e.getBearingRadians()).

Thus the final code being as my code above. --Nat Pavasant 12:00, 23 January 2010 (UTC)

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 > getBattleFieldWidth() - 18) predictX = getBattleFieldWidth() - 18;	
   if (predictY > 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 > 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