Archived talk:Linear Targeting 20071111

From old LinearTargeting page

I tried implementing this but I get an error saying that I haven't done anything in a so much time. -- Kinsen

The easiest way is to rip it out of WaveSurfingChallenge Bot B. As this code is public that is allowed. I should replace the 'fire' by 'setFire' by the way. --GrubbmGait

---

Isn't this code used in MyFirstTeam? --T.

Nope... I just checked MyFirstTeam (MyFirstLeader and MyFirstDroid), and all it does is have the droids fire directly at enemy bots. (The leader sends messages to teammates with a point, and they fire at it.) -- Voidious

---

I was implementing this algorithm into my bot for use against linear movers and I got a curious result against Sample.Walls. Apparently Sample.Walls when it is moving along the edge of the battlefield is closer than 18 pixels to the edge of the battlefield, thus the code above breaks out of the while loop after one iteration, causing almost HOT against it! I assume that 18 pixels is the bots length but that bots are actualy not square? I couldnt find any dimensions for the bots in the FAQ or the Wiki so where did the 18 pixels come from? --wolfman

The dimension of the bot is a non-rotating square of 36x36 (see BeginnersFAQ), therefor the 18. Alas doubles are not that precise, so the calculated predicted position could be something like 17.997. In my bots I use 17 instead of 18, but using 17.9 would also do. -- GrubbmGait

Yup that makes sense. Perhaps the code above needs to be changed to 17?

As an aside I might try speeding up this type of targeting trying the following: Use the trig method first. If the location using the trig method is outside the battlefield (using a simple bounds check) then use the iterative method instead? It would be faster for some situations but slower when the target will intersect the wall because of the added overhead of the trig method plus the iterative. Might be worth profiling to see how often each method is called in a typical match.

Oh and after reading my change maybe the fastest method is to get the location using the trig way, check to see if the predicted location is outside the bounds, then if so use a simple 2D line-box intersection method to find the location where the source -> target line meets the battlefield bounds. Non iterative but produces the same result. Usefull in slowbots that use this targeting method. I need to check but I am hoping that the java.geom API includes a 2D line-box intersection method to make life easy! :)

--wolfman

• wolfman: I think you mean target -> predicted target position, not source->predicted target position. --Starrynte

Maybe something like this?

double ang=sign(enemyVelocity)*Math.asin(Math.abs(enemyVelocity) / (20.0 - 3.0 * bulletPower)); //note sign() returns the sign of a number, and is different from Math.sin, and this is the trig way without checking
Line2D.Double enemyMovement=new Line2D.Double(enemyPosition, projectPoint(enemyPosition,enemyHeading,1000));
Line2D.Double bulletMovement=new Line2D.Double(myPosition, projectPoint(myPosition,Math.atan2(enemyPosition.getX()-myPosition.getX(),enemyPosition.getY()-myPosition.getY())+ang,1000);
//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;
//nanos iterative lineintersectwithshape method
if(!field.contains(intersect)){ //is where you are firing at in the battlefield?
	int TRACE_DEPTH = 16;
	Point2D middle;
	boolean containsFirst;
	if ((containsFirst = field.contains(enemyMovement.getP1())) == field.contains(enemyMovement.getP2())){
	}
	for (int i = 0; i < TRACE_DEPTH; 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());
		}
	}
	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(ang-getGunHeadingRadians());
setFire(bulletPower);

Didn't check it at all, but correct me if i had mistakes...Btw you can change the iterative line intersect with shape method into the non-iterative one. Alot of functions need to be added, and you'll need to import java.awt.geom.*; --Starrynte (post edited)

Using the law of Sines, you can calculate this directly (which is how nanos do linear aiming)

Let the B be the location of the target and A be our location. Let C be the interect location taking into account the bullet and enemy velocity.

  a  
C---B
 \  |
 b\ |c
   \|
    A

Neat, now, lets redefine the triangle points to be internal angles.

The law of Sines states that

a / sin(A) = b / sin(B) = c / sin(C) = 2 * Radius of a circle touching all 3 points.

The "lead angle" is A - the term we need to solve for.

a = the enemy velocity., b = bullet velocity, B = enemyHeading - his bearing (the Angle on the bow for submarine buffs). Then,

A = arcSin((a * sin(B) / b)

This doesn't calculate time for arrival nor intercept point, but that could be calculated easily with the resultant aim vector. The above code runs quick and is very small. --Miked0801

This is a nice way to understand it! I've been having fun with the law of sines in my surfing lately. Notice on /NanoLinearTargeting that Kev discovered you can drop the arcsin; it makes almost no difference for the range of numbers robots use in this case. -- Simonton

Thanks for the tip! That's a few more bytes to try and catch up to you with. --Miked0801

From old LinearTargeting/Discussion page

Just a question to all you guys: How accurate are these LinearTargetters? against bots like PatternMatcherChallenge? I've been running my LinearTargeting against PMC and Rapture 2.13 and I'm hitting about 33%. Is this good for a linear against complex movement or what? I'd post my accuracy vs. sample.Walls but it's too weak, especially since I haven't changed calculations if I predict they'll be outside the battlefield.

[GRYB] Goofy

Linear targetters aren't particularly accurate in the grand scheme of things. The assumption that an opponent will continue moving precisely as it was was you fired doesnt tend to work well against oscillators and bots that fight at distance. There are many ways to improve the accuracy, one way is to iterate through and try to find the point at which the bullet will actually hit the opponent (as in the simplest scenario you just assume the distance will be constant), another is to keep an average of the enemy velocity and use that in your calculations rather than the current velocity. As for your hit rate, it would be difficult to grade it really. It is difficult to analyse hit rates, it depends on the power of the bullets you fire (as power is proportional to speed) and the range at which you were firing (its easier to hit at close range). If you wanted to test the accuracy of your gun the best way would most probably be the TargetingChallenge. It has a clear set of rules, and a good test bed of targets, allowing you to easily compare your results to others. Good luck... --Brainfade

A lot of earlier bots did variations on linear targeting where they did a certain percentage of linear lead from head-on, and if they missed, they would adjust the lead to be less, and if they hit, they would adjust the lead to be more, until they locked in on some percentage that seemed to work ok. In general, this percentage ends up being lower at long distances, and optimally close to full lead when you're close up. Note that once you take this and realize that you don't actually need to fire a bullet to see if one would hit if fired in a certain direction - this lead to the idea of VirtualBullets used to either rate several simple targeting algorithms to see which is best against a given opponent or for GuessFactorTargeting, which was first implemented by firing a "virtual bullet" at every angle (at regular intervals) from -linear lead to +linear lead and figuring out which ones would have hit, then firing at the mode of that data. -- Kawigi

/me nods. Okay, I'm checking out targetting challenge now, Brainfade, thanks for pointing that one out to me. Kawigig: Yeah, I first wanted to implement waves (I'm hand-coding all these to get better practice. Just stealing ideas for now.) but that kept failing and until I get a better learning system didn't seem particularly possible for me. I was really proud of my "success" with LinearTargetting. With respect to my accuracy: It's a pretty blanket 33% against Rapture regardless of bullet power. Against PMC and using PMC rules (.5 power), I get about 53%. Though I can actually kill the PMC if I use power 3 bullets (at 33%). Thanks for the heading, guys. --Goofy

• • @ Goofy, Thats the best way to learn. Stealing ideas is OK though =^> -- jim

Kawigi's algorithm is buggy, I fixed one mistake but something else is wrong. If you're going to use one of the ones on this page I suggest you use mine, or for extra bonus points, debug Kawigi's and post the fixed version. His runs faster so it would be great if someone could correct it. --David Alves

Can you post your algo on this page David? -- PEZ

"If you're going to use one of the ones on this page I suggest you use mine"... Look near the top, it's the second one. :-) --David Alves

Yeah, this page is a bit messy. I did look for your contribution... =) -- PEZ

Here's my code for it. Uses the trig method then checks for walls.

package ntc;
import robocode.*;
import java.awt.geom.*;
import java.awt.Color;

//run, movement, etc

public void onScannedRobot(ScannedRobotEvent e) {
		setTurnRadarLeft(getRadarTurnRemaining());
		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(),1000));
		Line2D.Double bulletMovement=new Line2D.Double(myPosition, projectPoint(myPosition,getHeadingRadians() + e.getBearingRadians()+ang,1000));
		dist=new Line2D.Double(myPosition, enemyPosition);
		eM=enemyMovement;
		bM=bulletMovement;
		//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;
		//nanos iterative lineintersectwithshape method
		if(!field.contains(intersect)){ //is where you are firing at in the battlefield?
			int TRACE_DEPTH = 8;
			Point2D middle;
			boolean containsFirst;
			if ((containsFirst = field.contains(enemyMovement.getP1())) == field.contains(enemyMovement.getP2())){
			}
			for (int i = 0; i < TRACE_DEPTH; 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());
				}
			}
			intersect.x=(enemyMovement.getX1() + enemyMovement.getX2()) / 2;
			intersect.y=(enemyMovement.getY1() + enemyMovement.getY2()) / 2;	
		}
		point=intersect;
		ang=Math.atan2(intersect.getX()-myPosition.getX(),intersect.getY()-myPosition.getY());
		setTurnGunRightRadians(robocode.util.Utils.normalRelativeAngle(ang-getGunHeadingRadians()));
		setFire(3);
		out.println(intersect);
		out.println(enemyPosition);
	}

	public void onPaint(java.awt.Graphics2D g) {
		g.setColor(Color.red);
		g.fillOval((int)point.getX()-10,(int)(getBattleFieldHeight()-point.getY())-10,10,10);
		g.drawLine((int)eM.getP1().getX(),(int)(getBattleFieldHeight()-eM.getP1().getY()),(int)eM.getP2().getX(),(int)(getBattleFieldHeight()-eM.getP2().getY()));
		g.setColor(Color.green);
		g.drawLine((int)bM.getP1().getX(),(int)(getBattleFieldHeight()-bM.getP1().getY()),(int)bM.getP2().getX(),(int)(getBattleFieldHeight()-bM.getP2().getY()));
		g.setColor(Color.cyan);
		g.drawLine((int)dist.getP1().getX(),(int)(getBattleFieldHeight()-dist.getP1().getY()),(int)dist.getP2().getX(),(int)(getBattleFieldHeight()-dist.getP2().getY()));
    }

	Point2D.Double projectPoint(Point2D.Double sourceLocation, double angle, double length) {
        return new Point2D.Double(sourceLocation.getX() + Math.sin(angle) * length,
            sourceLocation.getY() + Math.cos(angle) * length);
    }
}

In the graphics, the red dot is where it's aiming for, the red line is the straight line iteration of the enemy movement, green line is path of bullet (without taking walls into account), and blue line is simply connecting you and the enemy so if you need to test the MEA you can use that...Although this does not use MEA --Starrynte