Talk:Waves/Precise Intersection

Credits - Waves/Precise Intersection Old wiki page: Rednaxela/SuperBotwidth Original author(s): Rednaxela

Credits - Waves/Precise Intersection Old wiki page: Garm/BotwidthCalculation Original author(s): Krabb

Credits - Waves/Precise Intersection Old wiki page: Skilgannon/PreciseIntersect Original author(s): Skilgannon

Wave Surfing

So far I know a few robots use Precise Intersection in their wave surfing. Unfortunately their code is either too messy (Wintermute) or too granular (RougeDC) that I don't know which class to look. So I asked here. (Diamond is too new to look into for this)

Normally you surf waves 'till the wave passed centre of the robot. But with precise wave intersection, in order to gain pixel-perfect surfing, you need to surf the wave until they passed the robot. So if anybody does this or the other way? --Nat Pavasant 11:20, 20 October 2009 (UTC)

I was planning to add all 3 to Wintermute, ie, branch when the wave first strikes, branch when the wave passes midway, and branch when the wave exits, but after adding in a stop branch for every tick on the second wave it was too slow to do that without skipping turns. I think it now branches at the mid-point only...--Skilgannon 13:21, 20 October 2009 (UTC)

My experience, precise intersect or not, is that I've seen a measurable decrease in performance any time I try surfing waves any longer than I do now. I surf until they are less than one bullet velocity away, meaning they will pass my center before I can move again. I have some thoughts on this. If you weight by distance or by time to impact, the weight of the wave after it passes your center will be very high, while the chance of it hitting you if it hasn't already is very low. Giving it less weight somehow might help. Also, be careful not to give it negative weight, since your time to impact or distance calculation may give a value less than zero. --Voidious 13:32, 20 October 2009 (UTC)

If you guys surf the wave only half-way, then how are you calculating precise botwidth in the danger calculation? --Nat Pavasant 14:33, 20 October 2009 (UTC)

In Diamond 1.47's bot width calculation, I start with the first tick the bullet will cross my front bumper and go until the tick where it will cross my center. I tried until it crossed the rear bumper and it performed worse. Again, it's probably because it's so rare you will be hit there that weighting all the ticks evenly is just inaccurate, probabilistically. The next iteration of my precise intersect experiments doesn't have that issue, and I will again try considering all possible intersections. --Voidious 14:52, 20 October 2009 (UTC)

In Wintermute I take any additional danger that may happen after branching into account with my second-wave surfing - the method returns a range of hits over both waves, then adds them all together. --Skilgannon 08:02, 21 October 2009 (UTC)

And what about when you surf only single wave? --Nat Pavasant 08:33, 21 October 2009 (UTC)

Then it just continues through until the wave is completely past =) There's no reason to reverse unless there's another wave coming, in which case I would be branching and my statement above would apply =) --Skilgannon 09:54, 21 October 2009 (UTC)

I mean when your surfing algorithm only surfs single wave, not when you have only one surfable wave. Because that's what I'm implementing (because it is goto-surfing, I can't surf second wave without skipped turn =)) --Nat Pavasant 10:00, 21 October 2009 (UTC)

In DrussGT I take a bunch of points and predict what GF would be hit if I fed it to my GoTo method. If you're only dealing with one wave then it's quite easy, simply keep predicting until the wave has passed your future bot. I found it is best to start surfing the next wave as the old one passes the center of your bot. --Skilgannon 18:44, 21 October 2009 (UTC)

Slightly offtopic: Nat, you should take a look at the conversation I had with Voidious about how to surf multiple waves with goto surfing. You can cut down on the combinatorial explosion by not recursing if the danger for the first wave is already higher than the current minimum total. « AaronR « Talk « 21:12, 22 October 2009 (UTC)

Thank you. I have already known that, from Druss's code (I've read Druss's code at least 10+ times) --Nat Pavasant 11:41, 23 October 2009 (UTC)

In YersiniaPestis I surf the wave until it passes completely, if I don't it gets hit more by simple targeters, I think is because YP doesn't go that far from the danger spots so when it starts surfing the second wave it ran towards the bullet near him. But as far as having a precise window calculated, you can keep track of the waves until it passes you even if you don't consider that wave for surfing it anymore. --zyx 20:51, 20 October 2009 (UTC)

I looked it up and I use Precise Intersection since GresSuffurd 0.1.1 (october 2006), but only in simplified form and only in my gun (e.g. almost Precise Intersection). Reading the reactions above, I already know where my focus for the first few weeks will lie: introducing PI in my surfing. --GrubbmGait 00:19, 21 October 2009 (UTC)

Psudocode

I really like Precise Intersection. Here is some javalike psudocode to help explain this to those who see things better in code.

• IntersectRectCircle(Rect rect,Point center,double radius) is a function that returns an array of points where the circle defined by center and radius, intersects the Rect rect. Otherwise it returns an array of length 0.
• GetRectCorners(Rect rect) is a function that returns an array of 4 points, each making up the corners of Rect rect.
• Rect and Point are generic classes that define a copy of what they say. Point is equivalent to a Point2D.Double and a Rect is equivalent to a Rectangle2D.Double

class Wave {
	Point center;
	public long fireTime;
	public double bearing;
	public double speed;
	
	/**
	 * You will need to divide these min and max angles by the maximum escape
	 * angle to get the guess factor, however since they are all part of this
	 * wave, you do not need to convert them immediately to guess factors.
	 */
	public double min; /* Set these to a good initial value */
	public double max; /* like positive and negative infinity */
	
	boolean intersectStarted = false;

	/**
	 * Return true if the intersection is complete
	 */
	public boolean intersect(Point target, long time) {
		Rect boundingbox = new Rect(target.x - 18, target.y - 18, 36, 36);
		Point[] current = IntersectRectCircle(boundingbox, center, getDistance(time));
		Point[] last = IntersectRectCircle(boundingbox, center, getDistance(time - 1));
		
		if(current.length > 0 || last.length > 0) {
			Point[] corners = GetRectCorners(boundingbox);
			
			/* Check the bearings on all the current points */
			for(Point p : current) {
				double angle = Utils.normalRelativeAngle(bearingFromTo(center, p) - bearing);
				if(angle < min) min = angle;
				if(angle > max) max = angle;
			}
			
			/* Check the bearings on all the last points */
			for(Point p : last) {
				double angle = Utils.normalRelativeAngle(bearingFromTo(center, p) - bearing);
				if(angle < min) min = angle;
				if(angle > max) max = angle;
			}
			
			/* Check the bearings on the bounding boxes corners */
			for(Point p : corners) {
				/* Make sure that the corner is between the distance of the current and last. */
				if(center.distance(p) <= getDistance(time) && center.distance(p) >= getDistance(time-1)) {
					double angle = Utils.normalRelativeAngle(bearingFromTo(center, p) - bearing);
					if(angle < min) min = angle;
					if(angle > max) max = angle;
				}
			}
			
			intersectStarted = true;
		} else if(intersectStarted) {
			return true;
		}
		return false;
	}
	
	public double getDistance(long time) {
		return (time - fireTime) * speed;
	}
}

— Chase-san 02:20, 17 July 2010 (UTC)

Smashing it down to bins

Although the concept is very clear to me, calculating the precise intersection between a bot and a wave is one step to far for my mind. Also, why bother calculating it with 6 figures behind the comma, and then force it with a sledgehammer into those coarse bins. With some straight-forward programming and some brute CPU power you can get the same results. I must give a warning though: this looks a lot like virtual bullets, firing one bullet per bin.

When the wave is less than 2 ticks away from the opponent, the calculation should start. Starting with the bin where the center of the opponent is, the bullet is checked for if it lies in the robot bounding box. If it is, this bin is noted as 'left bin' and 'right bin' and then the bullet (bin) on the left is checked. It this still in the bounding box, then this bin is noted as left and the next left bin is checked, and so on. The same for the bins on the right side. On the next tick, the same goes again, starting from the 'left bin' to the left and the 'right bin' to the right. This is repeated every tick untill the wave has passed the opponent. Now you have the bins that would have noted a 'hit' if you indeed fired at one of them. In a slightly other form, this is present in the gun of GresSuffurd since October 2006. But this only adressed the first point mentioned on the Precise Intersection page, so it is better called Not so precise intersection.

To have a precise intersection, also the movement of the bullet and the movement of the bot must be taken into account. The movement of the bullet can be calculated quite simple. Just repeat the above with the distance increased by 'bulletvelocity' (point of T+1). The movement of the bot seems more difficult to calculate, but think about this situation: the bullet has passed a corner of the bot, and the bot moves towards the bullet, intersecting the calculated angle behind the bullet. It just means you have to look backwards to check if the bot was hit in the back. So repeating the same steps as above with the distance decreased by 'bulletvelocity' (point of T-1) would do the trick. This adresses the second point mentioned on the master page.

How can the third point taken care of? Brute-force calculating! Just repeat the above with several points between the 'T-1' point and the 'T+1' point and we have an 'almost precise intersection' ready. Better would be to check if the 'bulletline' would intersect the robot bounding box, but that function I could not find.

The routine implementing this will be part of a next version of GresSuffurd. If I made wrong assumptions, please let me know, I'm still not too old to learn. --GrubbmGait 23:02, 28 January 2011 (UTC)

Neat! I think this approach is a sensible one for bots that use bins (all my uses of precise intersection have never been with any form of bins in the same robot). One note though, is that when checking if the bullet is in the bounding box, be sure to treat the bullet as a line, not a point. The graphics of robocode are rather misleading, since bullets are treated as continuous line segments for purposes of collisions. You may be accounting for this, but just thought I'd mention it since it's not clear whether you are. --Rednaxela 00:37, 29 January 2011 (UTC)

Hey, I also think this is pretty cool! I do have some corrections:

• To really be precise, you should start 3 or even 4 ticks ahead in some situations. A min speed bullet (11) could be a distance of 35 from the enemy bot's center, making it > 3 ticks away. But before the enemy bot moves again, this bullet will move and check for collisions, so in effect the wave's closest point (with respect to collisions) is already 24 from the bot's center. The distance from a bot's center to its corner is ~25, so it could intersect.
• If a bot moves into the bullet line, it is not a collision. Each tick, the bullet moves forward, forming a line segment, and it is checked if this line segment intersects the bot bounding box, then the enemy bot moves. So you don't really need to check the T-1 thing. Just check T, T+1, and some points in between, checking if any of them lie within the current enemy bounding box. (And do that each tick, like you said.)
• This page is kind of confusing - in my opinion, it should talk about "this tick" and "next tick", never "last tick"...

I also have only done this in a bot without bins (Diamond), and only in the movement. I was surprised it helped as much as it did... Good luck!

--Voidious 01:36, 29 January 2011 (UTC)

Oh yeah, and this might save you some brute forcing. :-) java.awt.geom.Line2D.intersects(...) --Voidious 01:56, 29 January 2011 (UTC)

Sorry for triple post - clearly you've got my brain churning over this. :-) Note that because Robocode's coordinates start from bottom left, you should use x/y of bottom left corner, not top left like the API says... Same with how we use Rectangle2D's. Or you could just brute force... :-P --Voidious 02:05, 29 January 2011 (UTC)

Thanks for the tip! I was just about to give up on the built-in Rectangle2D and Ellipse2D intersection when I ran across your comment. Changing to the bottom left instead of top left solved my problems. Ncj 09:54, 30 January 2011 (UTC)

Thanx for the comments, now the implementation can be quite small and fast.
@Rednaxela: I know, but I couldn't find Rectangle2D.intersects( line2D). The other way round is just so obvious I hadn't thought of it . . . duh
@Voidious: Regarding point 1, you're absolutely right. On the second point you are probably right, it seems logical to me, but I found the page also a bit unclear regarding this. Third point, well, you're right (again)
Now let's see howmany points it will gain me in the rumble . . . --GrubbmGait 09:51, 29 January 2011 (UTC)

Yes thanks for your comments :) They've nicely followed my own recent work the last couple of days :) I also used the Line2D.intersec.... For simplicity I currently just check all the bins, instead of the whole center, left, right thing.. Being I won't be firing waves and only surfing, my "sim" starts with onHitByBulletEvent, logs the bulletLine.intersect/contains in a buffer (this and 2 more ticks) , and adds the those binsHIT to my stats , all in the same loop.. The code is surprising very simple and short, works great -Jlm0924 22:55, 29 January 2011 (UTC)

Ok, just assembled some java(pseudo)code, so it can be used. I think it is selfexplaining, most variables you just need in a Wave. The comments above have been processed. When the wavepasscheck returns true, the minimum and maximumbin should be processed and the wave can be removed. --GrubbmGait 11:32, 4 April 2011 (UTC)

class Wave {
	public long   fireTime;
	public double bulletVelocity;
	public double HOTAngle;
	public double maxEscAngle;
	public int    minimumBin;
	public int    maximumBin;
	
	public Wave( double bulletpower, Point myPos, Point enemyPos);
		this.fireTime = robot.getTime();
		this.bulletVelocity = Rules.getBulletSpeed( bulletpower);
		this.fireLocation.setLocation( myPos);
		this.HOTAngle = doGetAngle( myPos, enemyPos);
		this.maxEscAngle = Math.asin( 8.0 / bulletVelocity);
		this.minimumBin = BINS;
		this.maximumBin = 0;
	
	public boolean wavepasscheck( Point2D.Double enemyPos, long currTime) {
		double waveDistance = bulletVelocity * ( currTime - fireTime);
	   	if (waveDistance > fireLocation.distance( enemyPos) + 40) {
			return true;		// wave has passed, process min/max in stats
		}
		if (waveDistance > fireLocation.distance( enemyPos) - 3 * bulletVelocity) {
			Rectangle2D.Double enemySpace = new Rectangle2D.Double(
				enemyPos.x - 18, enemyPos.y - 18, 36, 36);
			Line2D.Double  bullet  = new Line2D.Double();
			for (int tbin = 0; tbin < BINS; tbin++) {
				double tguessfactor = (double)(tbin - MIDBIN) / MIDBIN;
				double tangleOffset = enemyDirection * tguessfactor * maxEscAngle;
				double thead = Utils.normalRelativeAngle( HOTAngle + tangleOffset);
				bullet.setLine( doProjectPos( fireLocation, thead, waveDistance),
						doProjectPos( fireLocation, thead, waveDistance + bulletVelocity));
				if (bullet.intersects( enemySpace)) {
					if (tbin < minimumBin) minimumBin = tbin;
					if (tbin > maximumBin) maximumBin = tbin;
				}
			}
		}
		return false;
	}
}

Targeting

I was wondering how much, if any, improvement people have gained by using this in their targeting. It seems to me that this would be unlikely to cause anything more than 0.05 APS increase, and because of the extra processing needed for precise intersection combined with 2 to 4 virtual waves hitting every tick, you could for example, use a larger k in a kNN algorithm which would help your gun more than the added precision. Any thoughts?--AW 15:02, 15 August 2011 (UTC)

I agree it's not worth much in the gun. I added it from Diamond 1.5.29 to 1.5.30, and here's the comparison: [1]. Before that, I made waves break (bullet velocity / 2) before they passed the center of the enemy bot, so on average, the center of the bullet line segment is at the enemy's center. You have so much data in targeting that it should average out pretty quickly. That said, I like precision and err on the side of what feels right when there's no data to prove which way to go, so I left it in. --Voidious 16:41, 15 August 2011 (UTC)

I've also found it's not worth much in targeting. Here's how I see it... If you have perfect knowledge of what the enemy will do, it doesn't matter if you use precise intersection because your bullet will be well within the intersection range anyway. For surfing however, even if you have perfect knowledge of what they do, precise intersection can allow dodging close calls that may otherwise have hit. Essentially, targeting is more forgiving of small inaccuracies in angles.

Regarding the extra processing needed, how much overhead it is depends highly on the specific targeting method you're using it in. If you're applying it to guessfactor targeting, you only need to do the precise intersection calculation 3 or 4 times per tick (once for each wave intersection occurring on that tick). In contrast, if you're applying it to a play-it-forward targeting system (i.e. PM), then you'd have to compute 3 or 4 precise intersection calculation for each possible future you're projecting (for some kNN-PIF implementations this means several hundred precise intersection calculations). The overhead is pretty tiny really for guessfactor targeting, but can be huge with some kNN-PIF targeting. --Rednaxela 22:55, 15 August 2011 (UTC)