User talk:Nat

From Robowiki
Jump to navigation Jump to search
Archived Talk:
2009/04/06 - 2009/06/20

Let see if I get confirmation email. » Nat | Talk » 14:34, 23 July 2009 (UTC)

I think it ignores your own edits. So here you go. =) --Voidious 14:37, 23 July 2009 (UTC)
Thank you, it does ignore owner edits. » Nat | Talk » 14:40, 23 July 2009 (UTC)

Birthday 2009

Attention guys, today is a very special day! At least to me, because today (July 3) is my birthday! Mind giving me a little "Happy Birthday"? LOL » Nat | Talk » 11:15, 3 July 2009 (UTC)

Happy Birthday!--CrazyBassoonist 12:44, 3 July 2009 (UTC)

Lol, happy birthday man! Hope it's a good one ;) --Spinnercat 15:28, 3 July 2009 (UTC)

Happy birthday =) --Skilgannon 15:40, 3 July 2009 (UTC)

Happy Birthday, Nat. Don't party too hard. =) --Voidious 17:26, 3 July 2009 (UTC)

Happy Birthday Nat, hope you have fun ;-) --zyx 18:25, 3 July 2009 (UTC)

                     {}
                     ||
                 ____||_____
            {}  {~ ~ ~ ~ ~ ~}  {}
            ||  { ~ ~ ~ ~ ~ }  ||
          __||__{___________}__||__
         {\/\/\/\/\/\/\/\/\/\/\/\/\}
      {} {        H a p p y       \} {}
      || {\/\/\/\/\/\/\/\/\/\/\/\/\} ||
    __||_{_________________________}_||__
   {\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\}
   {                                     }
   {         B i r t h d a y ! ! !       }
   {                                     }
   {/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/}
   {_____________________________________}

-- Synapse 21:17, 3 July 2009 (UTC)

Haha, happy birthday Nat. Hope it's a good one! --Rednaxela 23:50, 3 July 2009 (UTC)

Thanks guy. Actually I don't have a party, nor cake (except the one above), nor presents =) I've got my present 3 months ago (new notebook that I'm currently sitting in front of) and I hate party! It take the time that I usually sit in front of my computer away. However, this isn't a good one. I've got a cold! Or at least I hope it only cold, not swine flu ;-) » Nat | Talk » 01:38, 4 July 2009 (UTC)

MicroBot Wave Surfing

Anyone have 10TB of memory and hard disk to spare? I need that to perform my own microbot wave surfing. The large part of Wave Surfing is precise prediction, which nonetheless can't fit in micro. I wonder if I cached all the prediction and just access it at runtime. Now I roughly calculated. Let see, I restricted the location, absBearing, velocity and distance to all integer. Total possible location on the map is 764*564 = 430896 locations, multiply by 360 absBearing, ~950 distance, 17 velocity. Saves in short (2 bytes), contain x and y will result in around 764*564*360*950*17*2*2 = 10020917376000 B = 9786052125 KiB = ~9,556,692 MiB = ~9,333 GiB = ~9.114 TiB.

Anyone have ideas how can I reduced those number? If I use 80*60 possible locations, 36 possible absBearing, 17 velocity and 19 possible distance, it still cost 43MB Note that this need to be preloaded into the robot, not calculating on-the-fly. Nat | Talk » 05:17, 20 June 2009 (UTC)

I've done a fair amount of work with precalculated movement table things. I once got a precalculated movement table down to about 2MB, but that's still too big for ethical pre-loading, AND the optimizations it used took rather large codesize to turn into something usable in battle. I don't think you're going to be able make this realistically work Nat honestly. --Rednaxela 05:27, 20 June 2009 (UTC)

=( Well, thanks for the info. » Nat | Talk » 05:50, 20 June 2009 (UTC)

I'll let you borrow my tables when I get around to adding micros to my list ;) --Miked0801 09:02, 20 June 2009 (UTC)

I'm not talking about the VCS table, I'm talking about movement table i.e. the table that allow you to know what is your position next tick if you are at (x,y) with a velocity of v and the enemy is at θ with a distance of d or something. It is the replacement of Precise Prediction used in minibot and megabot. » Nat | Talk » 09:25, 20 June 2009 (UTC)

I haven't dealed with wavesurfing yet, but do you need precise prediction? Is there anything less complex that could replace it? Anyway, take a look at kb.WaveShark, it's supposed to be a wavesurfer. --HUNRobar 14:38, 20 June 2009 (UTC)

LOL, it is kc.WaveShark. Actually it is that robot which inspire me about this. » Nat | Talk » 14:40, 20 June 2009 (UTC)

Pugilist is an example of a wave surfing without precise prediction I think, that might be able to give some inspiration --Rednaxela 15:53, 20 June 2009 (UTC)

Thanks. I have looked at it now, the prediction thing is still too large I think. But I'll give it a try... » Nat | Talk » 16:09, 20 June 2009 (UTC)

Bi-hourly release

Wonder is this is right thing to do or not. Because the number of clients running among this day, I can release my robot bi-hourly. But since I'm not running those clients, I not sure if this is right thing to do or not. » Nat | Talk » 11:42, 21 June 2009 (UTC)

if there are no other bots waiting, not a problem. But, my bot has been waiting for a bit to get to 2k battles in nanos. If you need this much info and are feeling guilty, use roboresearch for your tests. You'll get your answers just as quick without the guilt. --Miked0801 15:26, 21 June 2009 (UTC)
Sorry. When I checked and see the "PAIRINGS COMPLETE" text, I decided that the ranking is completed. Actually I'm not needing it fast, just roughly seen where it place is enough for me to decided what to do with next version, and I usually take only 10 minutes to do it. I'll try to run it on RoboResarch next time. Thanks. » Nat | Talk » 15:39, 21 June 2009 (UTC)
I think the rule of thumb used to be maximum one release per day? There are quite a few bots in the nano & micro categories still below 2000 battles. If you're feeling guilty, run a client and help out... --Darkcanuck 17:28, 21 June 2009 (UTC)

Number of Edits

Hmm... I wonder if the number of edits at Special:Preferences correct? Mine is currently 1,653 (at the time of writing, so perhaps this shall count as another one), but the Special:Statistics said that total edits is currently 9,954. I don't think I make an edit that much. » Nat | Talk » 13:36, 29 July 2009 (UTC)

{{Wikipedia}} template use

Hey Nat, I really recommend you don't use the {{Wikipedia}} template on the Twin Duel and RoboRumble pages like that. The reason being, the text "Wikipedia has an article about: Twin Duel" is very much NOT true, as it's only a minor section. I don't think it's sensible to use this template for one-section-only links. See Talk:Anti-Gravity_Movement#Wikipedia_link --Rednaxela 15:24, 12 August 2009 (UTC)

I see. Thanks, perhaps new template with "Wikipedia has a section about: Twin Duel ... in page Robocode" is better =) I'll remove them. Thanks again. » Nat | Talk » 15:31, 12 August 2009 (UTC)

SDS + Zoom = ?

For any who doesn't know what is SDS and Zoom Targeting, I'll explain briefly. SDS (Symbolic Dynamic Segmentation) is a data management system that you will map the data to a string that represent a state of the data. When you need data, just match the current state with the state of each data. If they are no match or too few matches, just strip last character out and do the match again. Do this until you have enough matches you want.

Zoom Targeting looks similar but indeed it isn't. It have fixed number of 'zoom' level, each level with different preciseness of the states. The deeper the zoom level, the more precise the state is. When you zoom in, it will act more like wave-based pattern matching. When you zoom out it will act more like statistical gun.

Now I'm thinking of combine them together. Like SDS-based data storing and using Zoom Targeting algorithm to choose number of segmentation to use? Any ideas?

Also, please help me think of a name. I'm considering of 'Statistical Zoom Data Management Algorithm' but it won't fit at all. » Nat | Talk » 07:32, 3 September 2009 (UTC)

OOP vs. Pluggable?

Hmm... I want to know, do you guys prefer more OOP or more Pluggable? I mean, I'm development a very pluggable robot (I mean, they have very little shared class) and still OOP-ed (mean that it have clean structure). (While I must accept that current top robot, DrussGT is the most pluggable =)) I realised that my repeat my code a lot. Currently the core of my GF gun contains 6 files: EnemyMovementProfile (interface), GuessFactorGun, GunScanLog, GunScan, GunWave and GunStats (interface). My movement engine has almost exact file with almost exactly the same content (EnemyMovementProfile vs SelfMovementProfile; GuessFactorGun vs WaveSurfingmovement; Gun... vs Movement...). And I can merge a lot of it into single file (or using abstract class) easily. In this case, do you guys choose to use the very pluggable structure with less OOP or more OOP with less pluggability? » Nat | Talk » 10:54, 5 September 2009 (UTC)

I think mixing movement and targeting classes is providing an opportunity for bugs to creep in, because there are many small differences. So for good programming practices try to keep them separate, but that doesn't mean that they shouldn't have many small subclasses. And DrussGT isn't that pluggable, for an example of pluggable look at Dookious or CassiusClay, my next release will be working on that though =) --Skilgannon 11:28, 5 September 2009 (UTC)

One thing I hate about Dookious is loads of utility class in the *.util package. With DrussGT, movement need DrussGT and BufferManager, while gun need DrussGunDC, PreciseUtil and PreciseWave. Dookious, err, have too many files too lazy to copy over =) » Nat | Talk » 11:34, 5 September 2009 (UTC)

I don't really understand - why do you think OOP and pluggable are opposites? A good OOP design will also be pluggable. Dookious certainly tries to be both (and succeeds, I think). Coding style is a personal preference, but since you're asking =) ... My advice would be to use OOP design principles as best you can. OOP is an important thing for any aspiring programmer to understand, and Robocode is a great place to practice those concepts. Also, having code copied in multiple places is a Very Bad Thing, if you ask me (or just about any programmer)! And why not have movement and targeting share code when it makes sense? Of course, pay attention to subtle differences in targeting/movement, but a lot of stuff can be safely shared. --Voidious 16:25, 5 September 2009 (UTC)

I think I have difference definition of Pluggable =) Basically, I mean that Dookious isn't pluggable because I need to copy a whole util package too, which contains a lot of unnecessary classes. DrussGT is pluggable in my mind because I can copy it over without any unnecessary classes. OK, pluggable redefined... Thanks for your opinion. » Nat | Talk » 02:26, 6 September 2009 (UTC)

What I believe you mean, is the scale from Monolithic, to Monolithic Modules, to Granular Modules, to Very Granular Modules. DrussGT would be in the general region of "Monolithic Modules", whereas Dookious would be closer to "Granular Modules", some others like most of my large ones might go into "Very Granular Modules", and things like nanobots are almost always in "Monolithic" of course. Anyway, I believe which is best depends on the complexity of the bot (no point in very granular modules when things are simple enough anyway), and personal preferences. It's quite easy for either too monolithic or too granular to make code hard to maintain/read, but ultimately what's right depends on the bot and the authod in question. --Rednaxela 04:33, 6 September 2009 (UTC)

Yes, thanks. It took me long enough to look into a dictionary (I have been googling for those terms for quite a time and found nothing) =) » Nat | Talk » 07:31, 6 September 2009 (UTC)

Trig Help!

Anyone please help me with this: given the angle a1 and a2 and the distance d, how can I calculate the distance r if the shape is a segment of a circle?

http://nat.robothai.net/robocode/trig-help.png

» Nat | Talk » 06:11, 20 September 2009 (UTC)

Is this the only info you have nat, or do you also know exactly where the origins of a1 and a2 lie on the circle? --Positive 09:23, 20 September 2009 (UTC)
Yes, this is all information I have. I'm not sure it can be calculated. In my melee gun development, I use very rough (but better than linear) approx. for interpolation, but if I can calculate this, it will be much more accurate. » Nat Pavasant » 09:34, 20 September 2009 (UTC)
NatMathTry.gif
I think the answer is that the length, r, is Math.asin((d/a)/2)*2. Where d is the mentioned distance and a is the radius of the circle. You use the Math.asin function the calculate the angle z in radians. Multiplying the angle z by two gives the total length of r. Correct me if I'm wrong. :)
Hmm... I think you are correct, only that I don't know the radius of the circle... Note that a1 and a2 is the angle from line d to the dotted line, not r, so... I'm not sure, but I think a1 is equal to a2? But it still doesn't help. » Nat Pavasant » 10:22, 20 September 2009 (UTC)

It might just be my internet connection, but I can't get your image to load. If you upload it to the wiki I might be able to help. --Skilgannon 20:44, 20 September 2009 (UTC)

South Africa? I know some countries can't access this host (Netherlands, for one). Basically, the green lines/text, gray dotted line, and the curve r from Red's pic are mine. » Nat Pavasant » 11:22, 21 September 2009 (UTC)

I belive I've solved it Nat. Here's a picture with the solution, and some rough work overlayed on the original image :)

Reds solution.png

--Rednaxela 22:17, 20 September 2009 (UTC)

Thank you very much! But can you explain what is c please? I don't understand it. Thank you again. » Nat Pavasant » 11:22, 21 September 2009 (UTC)

c is circumference. He was just deriving the formula for arclength, which is radius*theta where theta is in radians. Also, b1 and b2 form an isosceles triangle with the radius, so b1 = b2 thus a1 = a2, so the formula can be simplified a bit =) --Skilgannon 11:31, 21 September 2009 (UTC)

Oh, thank you. *slap myself hard* How could I forget the formula for circumference? Hmm... I think I said somewhere about that a1 == a2 so the final answer will be <math>r = {{2a \times d}\over{\sqrt{2 - 2 \times cos(2a)}}}</math> where <math>a</math> is the angle. Will try this with the movement interpolater tonight =) » Nat Pavasant » 11:43, 21 September 2009 (UTC)

Movement Interpolater

Well, I just uploaded my File:Nat.Interpolater 1.0.jar. But there are still a few problems which I can't figure out what and how to fix it. First is when enemy change its direction, it mostly predict in something messy. Second is sometimes it don't get into fullAccl/Decel (look at the source code) mode. Thank you in advance. » Nat Pavasant » 16:02, 22 September 2009 (UTC)

Non-related to Robocode, but it would be fun if we can get this new technology (especially the interpolation for an unobserved location) for Robot's movement interpolation. --Nat Pavasant 11:56, 1 October 2009 (UTC)

Twin Duel battle selection

Hey Nat - I noticed you're running a lot of Twin Duel battles. I noticed that when everyone has enough battles, only four bots were getting battles from my clients, and it looks to be the same for you right now if you check the rankings. If you want to contribute battles evenly, I think you'll need to raise the BATTLESPERBOT to something higher. --Voidious 14:56, 23 September 2009 (UTC)

Yeah I noticed that too. It seems that I'm not able to finish my twin duel team shortly so I stop running it, for now. » Nat Pavasant » 15:10, 23 September 2009 (UTC)

Fast Play-it forward algorithm

Anyone know how to do fast Play-It Forward (like in Shadow?) I tried many ways, but still doesn't do as good as step-by-step method, which is so slow (my 13-dimension KdTree is slow enough) I tried to understand what ABC say at oldwiki:DCBot too, but fail. Any ideas? ABC? Nat Pavasant 23:49, 27 September 2009 (UTC)

I'm not sure how Shadow does it, but the way I way I do it is along the lines of the following: 1) Estimate the bullet-travel-time based on current distance and bullet speed, 2) skip that much time forward in the log, 3) check if the wave has passed, isn't there yet, or is just right, and if it's not just right make a revised bullet-travel-time estimate and go back to step #2, otherwise continue, 4) Only now, check if the final point is within the battlefield. To my understanding, this is along the same lines of how Shadow does it, but I'm not certain. It's requires iterations, but is far far faster than traditional play-it-forward. Also, while it isn't as strict when checking paths don't go out of bounds, it that tiny loss in accuracy is well worth it for the speed it gives for things like melee. --Rednaxela 00:42, 28 September 2009 (UTC)

I think this is how old Shadow does, I think new one do something like convert the current vel/heading to the relative point. When aiming, just add series of relative points and rotate the result location or something, but I never successful implementing this. Nat Pavasant 00:45, 28 September 2009 (UTC)

I fail to see how what you describe could be any faster. What I do is just calculate relative point between the two points in the log, and rotate that, and add to current location. Storing it as a series of relative points in the log would make it slower so far as I can tell, since it doesn't remove any steps yet adds an extra step of doing the summation. --Rednaxela 00:52, 28 September 2009 (UTC)

No, it is like:

double bulletD = 0;
int round = scan.round;
double x = 0, y = 0;
while (M.sqr(bulletD) < Point2D.distanceSq(x, y, last.distance, 0)) {
	bulletD += bulletV;
	x += scan.relativePoint.getX();
	y += scan.relativePoint.getY();
	scan = scan.next;
	if (scan == null || scan.round != round)
		return null;
}
Point2D newEnemyLocation = new Point2D.Double(x, y);
newEnemyLocation = rotate(newEnemyLocation, last.heading);
newEnemyLocation = new Point2D.Double(newEnemyLocation.getX()
		+ r._enemyLocation.getX(), newEnemyLocation.getY()
		+ r._enemyLocation.getY());
if (!_fieldRect.contains(newEnemyLocation)) {
	return null;
}

This is my not-really-working code, but I hope it can describe what I'm telling. Nat Pavasant 00:55, 28 September 2009 (UTC)

I don't see how that could work. The geometry of distanceSq(x, y, last.distance, 0) seems completely broken. That does give me an idea of what would work though: Instead of rotating the relative point every time, just rotate your firing point into the perspective of the old log. That would allow checking the distance between the future enemy location and the firing point very efficently. --Rednaxela 01:06, 28 September 2009 (UTC)

Well, because (x,y) start at zero, and the relative point is rotate((xDelta,yDelta),enemyHeading). Thus, my current position will be at (enemyDistance, 0) Note that last is the last scan in the log, i.e., current scan. Or am I wrong here? Nat Pavasant 01:12, 28 September 2009 (UTC)

I'm pretty sure the rotation should be the difference between the current enemyHeading and the enemyHeading at the start of the log sequence, thus no that wouldn't make sense much sense. What I proposed is similar to your code snipped though except: 1) the rotation is fixed as I note, and 2) your current location is your relative location, rotated to be from the rotation of the starting log entry --Rednaxela 03:01, 28 September 2009 (UTC)

scan.relativePoint = getVector(scan.headingDelta, scan.velocity); is how my relative point storage work. Nat Pavasant 03:51, 28 September 2009 (UTC)

Ahh, that makes more sense, and in that case, I see why your code doesn't really work: Adding the x and y values for the delta heading vectors like that together cannot yield a correct answer. Since it's delta heading vectors, when reconstructing a path, each vector needs to be rotated by the ones prior to it... and fixing that would make this method slowish again. --Rednaxela 04:30, 28 September 2009 (UTC)

Oh yeah... Thank you.

Anyway, do you understand how this work:

Yes, but that description is a mix of DCBot's and Shadow's current method. In DCBot I used the "iterative search" to speed up the trig needed to convert the enemy's past position to the position it would be in the current situation. Doing that step by step is slow, like you mentioned. But then I remembered I could just convert my relative position to the enemy once at the beginning and then the play-back of the enemy movement becomes just additions of dx/dy. And the final firing angle conversion is just 1 addition. It's so simple! I don't know how I didn't come up with it earlier. Now that I think of it, I can probably compare squared distances and save a sqrt per step. About the rotated battlefield, I thought about that, but that would reintroduce the trig complexity and would probably end up slower than the original method. -- ABC

? Nat Pavasant 04:35, 28 September 2009 (UTC)

Well "convert my relative position to the enemy once at the beginning" sounds exactly like what I proposed above, however I'm not sure what is meant by "And the final firing angle conversion is just 1 addition" since I still think that last step would involve trig... --Rednaxela 05:02, 28 September 2009 (UTC)

I got a working implementation of what ABC does. Take a look at oldwiki:DrussGT/HelpRequests for a coded version of this. (The problem I actually had was that I was recording heading in degrees, not radians). --Skilgannon 05:49, 28 September 2009 (UTC)

Thank you! --Nat Pavasant 06:29, 28 September 2009 (UTC)

Ahah! Shadow'smethod is indeed exactly what I described with projecting the firing location into the perspective of the history. :) Now... what will make the fastest projection perhaps... will be combining that method with the fast-forward base on bullet-travel-time estimation :) --Rednaxela 06:14, 28 September 2009 (UTC)

Well, I think in this case the overhead/re-calculation of the BFT estimation will make it slower than ABC's method. --Nat Pavasant 06:29, 28 September 2009 (UTC)

Yep, I do exactly like Skilgannon's code. It's very fast, don't know if the iterative BFT search would make it faster, for long BFTs it probably would. --ABC 11:30, 28 September 2009 (UTC)

How about jumping forward BFT ticks and then just doing the regular tick-by-tick simulation (either forwards or backwards) from there? I think that would probably be fastest. --Skilgannon 14:33, 28 September 2009 (UTC)

Actually, that's what Glacier currently does (except that it's horribly inefficent and doesn't do those nice optimizations to get the trig out of the loops). It's true that that hybrid may be slightly faster, but I'm thinking the difference would be marginal at best and that purely using BFT search iterations is just so much simpler. For sake of simplicity, I think I probably won't keep that hybrid search once I optimize my PIF. That is... unless I go crazy like I did with the kd-tree :) --Rednaxela 15:09, 28 September 2009 (UTC)

I wonder which is faster, this:

protected Point2D playItForward(Trace start, Trace current, Point2D fireLocation, Rectangle2D field, double bulletVelocity) {
	int currentRound = start.round;
	double distance = current.distance(fireLocation);
	double angle = M.getAngle(current, fireLocation);
	double deltaHeading = start.heading - current.heading;
	Point2D projectedMyLocation = M.project(start, angle + deltaHeading, distance);
	double bulletDistance = 0;
	int estimatedBFT = (int) M.ceil(distance / bulletVelocity);
	for (int i = 0; i < estimatedBFT; i++) {
		start = start.next;
		if (start == null || start.round != currentRound)
			return null;
		bulletDistance += bulletVelocity;
	}
	distance = start.distance(projectedMyLocation);
	int newBFT = (int) M.ceil(distance / bulletVelocity);
	distance *= distance;
	if (newBFT < estimatedBFT) {
		do {
			start = start.previous;
			bulletDistance -= bulletVelocity;
			distance = start.distanceSq(projectedMyLocation);
		} while (M.sqr(bulletDistance) > distance);
		start = start.next;
		bulletDistance += bulletVelocity;
		distance = start.distanceSq(projectedMyLocation);
	} else if (newBFT > estimatedBFT) {
		do {
			start = start.next;
			if (start == null || start.round != currentRound)
				return null;
			bulletDistance += bulletVelocity;
			distance = start.distanceSq(projectedMyLocation);
		} while (M.sqr(bulletDistance) < distance);
	}
	angle = M.getAngle(projectedMyLocation,start);
	distance = M.sqrt(distance);
	Point2D resultLocation = M.project(fireLocation, angle - deltaHeading, distance);
	if (!field.contains(resultLocation)) {
		return null;
	}
	return resultLocation;
}

versus:

protected Point2D playItForwardNormal(Trace start, Trace current, Point2D fireLocation, Rectangle2D field, double bulletVelocity) {
	int currentRound = start.round;
	double distance = current.distance(fireLocation);
	double angle = M.getAngle(current, fireLocation);
	double deltaHeading = start.heading - current.heading;
	Point2D projectedMyLocation = M.project(start, angle + deltaHeading, distance);
	double bulletDistance = 0;
	do {
		start = start.next;
		if (start == null || start.round != currentRound)
			return null;
		bulletDistance += bulletVelocity;
		distance = start.distanceSq(projectedMyLocation);
	} while (M.sqr(bulletDistance) < distance);
	angle = M.getAngle(projectedMyLocation,start);
	distance = M.sqrt(distance);
	Point2D resultLocation = M.project(fireLocation, angle - deltaHeading, distance);
	if (!field.contains(resultLocation)) {
		return null;
	}
	return resultLocation;
}

Both code work fine. The first code is Skilgannon's explanation that only do estimated MEA once, and then do play it forward/backward from there. The second one is Shadow's method. --Nat Pavasant 03:30, 30 September 2009 (UTC)

And I wonder how the pure-BFT version I have in the dev version of Glacier compares as well:

    private AbsolutePoint predictSituation(AbsolutePoint origin, double bulletSpeed, EnemyRobot robot, RobotHistory situation) {
        // Constants
        double rotation = situation.getVelocity().direction - robot.getVelocity().direction;
        if (robot.getHistory().getOrientation() != situation.getOrientation()) {
            rotation += Math.PI;
        }
        long timeTillFiring = (long) Math.ceil(robots.getSelf().getGunHeat()/rules.GUN_COOLING_RATE);
        RelativePoint relativeLocation = RelativePoint.fromPP(robot.getLocation(), origin);
        AbsolutePoint projPoint = situation.getLocation().project(relativeLocation.direction + rotation, relativeLocation.magnitude);

        // Non-constants
        long t = -robot.getDataAge() - timeTillFiring;
        RobotHistory cursor = situation;
        double dist = relativeLocation.magnitude;
        long bft = (long) Math.ceil(dist / bulletSpeed);
        long lastt = t;

        // Loop while the elapsed time is not the bullet flight time
        while (bft != t && !(bft == lastt && t > bft)) {
            lastt = t;
            if (bft < t) {
                // Reverse skip
                while (cursor.prev() != null && t > bft) {
                    cursor = cursor.prev();
                    t--; // t += cursor.getTime() - cursor.next().getTime();
                }
            }
            else {
                // Forward skip
                if (cursor.next() == null) {
                    return null;
                }
                while (cursor.next() != null && t < bft) {
                    cursor = cursor.next();
                    t++; // t += cursor.getTime() - cursor.prev().getTime();
                }
            }

            // Recalculate bft
            dist = cursor.getLocation().distance(projPoint);
            bft = (long) Math.ceil(dist / bulletSpeed);
        }

        // Get the projected point
        double angle = projPoint.angleTo(cursor.getLocation());
        AbsolutePoint target = origin.project(angle - rotation, dist); 

        // Check that the projected point is within map bounds
        if (target.x < 18 || target.x > rules.BATTLEFIELD_WIDTH-36 || target.y < 18 || target.y > rules.BATTLEFIELD_HEIGHT-36) {
            return null;
        }

        return target;
    }

--Rednaxela 13:52, 30 September 2009 (UTC)

I am having problem trying to plug your pure-BFT code into my (new) robot.

=========================
Round 501 of 10000
=========================
0,000 Method 1 time: 3.5260242 seconds
0,000 Method 2 time: 2.693026591 seconds

Method 1 is ABC's method, Method 2 is skipping the first BFT and do the rest like normal method. I battled it against Shadow, my bot use HawkOnFire movement so it might have some long-distance adventage. But 500 rounds contains at least 100,000 predictions. --Nat Pavasant 14:45, 30 September 2009 (UTC)

I had to remove a couple features (timeTillFiring and 'orientation flip' support) that are important to my usage, but here's a port of my pure-BFT code to the framework that your code samples here use:

protected Point2D playItForward(Trace start, Trace current, Point2D fireLocation, Rectangle2D field, double bulletVelocity) {
    // Constants
    double rotation = start.heading - current.heading;
    double distance = current.distance(fireLocation);
    double angle = M.getAngle(current, fireLocation);
    Point2D projectedMyLocation = M.project(start, angle + rotation, distance);

    // Non-constants
    long t = -1;
    Trace cursor = start;
    long bft = (long) Math.ceil(distance / bulletVelocity);
    long lastt = t;

    // Loop while the elapsed time is not the bullet flight time
    while (bft != t && !(bft == lastt && t > bft)) {
        lastt = t;
        if (bft < t) {
            // Reverse skip
            while (cursor.previous != null && t > bft) {
                cursor = cursor.previous;
                t--;
            }
        }
        else {
            // Forward skip
            if (cursor.next == null) {
                return null;
            }
            while (cursor.next != null && t < bft) {
                cursor = cursor.next;
                t++;
            }
        }

        // Recalculate bft
        distance = start.distance(projectedMyLocation);
        bft = (long) Math.ceil(distance / bulletSpeed);
    }

    // Get the projected point
    angle = M.getAngle(projectedMyLocation,start);
    Point2D resultLocation = M.project(fireLocation, angle - rotation, distance);

    if (!field.contains(resultLocation)) {
        return null;
    }
    return resultLocation;
}

I haven't tested it, but I'm pretty sure it's right :) --Rednaxela 15:24, 30 September 2009 (UTC)

I had a similar thingie in Portia. The difference was that I skipped forward distance/(bulletSpeed+8) turns, and simulated from there. :) I dropped it because I wasn't sure it was faster, and it added complexity to the code. --Positive 16:07, 30 September 2009 (UTC)

=========================
Round 1000 of 10000
=========================
BFT-than-step-by-step time: 4.533518074 seconds
Pure BFT time: 3.49650074 seconds

I'm not sure your method is correct or not (this is codebase in Samekh, but I move it to Pallas whitch is slightly different), that 1,000 rounds I ran with your code (I run both code, but I use the result from your method) I got 100%-0% with Shadow 3.83, but with my BFT-than-step-by-step get 88%-12$ against the same robot (this time it consume 7.x seconds) Anyway, I never realize how fast this method is until I ran this test, it can run at 7-8 rps! (versus Shadow, one of the fastest top bot =)) Nat Pavasant 10:42, 1 October 2009 (UTC)

I'm not sure how it could be incorrect unless the error occured in porting between bots. It seems to work just fine in Glacier here. Anyway, I'll soon make a new Glacier release which puts this into action. --Rednaxela 13:17, 1 October 2009 (UTC)

Probably the porting, because I uses my own Point (similar to your AbsolutePoint) in Pallas and have extraTick parameter for the play-it-forward. But the result from the debugging graphics looks fine, though. Nat Pavasant 13:21, 1 October 2009 (UTC)

OK, I found the problem. In your ported code you move the cursor but you re-calc BFT using start. Well, but I found another issue with heading (it seems to be 90 degrees off). Dealing with it =) --Nat Pavasant 13:29, 1 October 2009 (UTC)

Silly me... I forgot to change start to cursor in the final projection... It work fine now =) --Nat Pavasant 13:32, 1 October 2009 (UTC)

Not sure how the old benchmark time was that, because it seems now that normal Shadow's (ABC's step-by-step) is the fastest. Running 10,000 rounds melee match, will post the time when it finished. --Nat Pavasant 13:55, 1 October 2009 (UTC)

=========================
Round 680 of 10000
=========================
0,211 Shadow's time: 6.586140695
0,211 Hybrid time: 13.745157619
0,211 Pure BFT time: 8.215406722
SYSTEM: nat.Pallas has died

Normal way seems to be faster still... --Nat Pavasant 14:31, 1 October 2009 (UTC)

Huh... that seems strange to me... the "Shadow's time" version will always take at least as many iterations as the other versions... and the main iteration part is exactly the same in the hybrid version. Are you sure you're not testing against a field of rambots? --Rednaxela 14:46, 1 October 2009 (UTC)