# Difference between revisions of "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 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)

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...

## 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); }
```

## 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):
*/
//and finally, theta is the distance I have to turn my gun:
else if (theta > 0)
```

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
//find their final destination
//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:
//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):
}
//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));

th = (th>PI ? th-twoPI : (th<-PI ? th+twoPI: th)); // turn the quickest way towards target

```

## 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:

```
Point2D.Double enemyPosition=new Point2D.Double(x,y);
Point2D.Double myPosition=new Point2D.Double(getX(),getY());

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());