# LinearTargeting/BuggyImplementations

Robo Home | LinearTargeting | Changes | Preferences | AllPages

If anyone has time, these 2 algorithms are buggy. It would be great if someone could fix them, since they are both faster than the code I provided on the LinearTargeting page. --David Alves

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

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

Robo Home | LinearTargeting | Changes | Preferences | AllPages
Edit text of this page | View other revisions
Last edited July 30, 2007 0:25 EST by Starrynte (diff)
Search: