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)