Talk:Robocode/Game Physics

Robot hitbox

I need to know percisely, which might involve rotating a rectangle, I don't know, if a point intersects my bot, given its X and Y location. Remeber that in Robocode, Y is reversed. While I'm at it, I might just ask: What your opinion is on whether I should do surfing or anti-gravity movement to dodge predicted bullets my robot simulates? --Awesomeness 21:52, 3 May 2009 (UTC)

The 'hitbox' of a robot is always a non-rotated square at the bot's location, so the former check is very very simple. As for your second question: It depends. Surfing is going to be stronger almost surely, however anti-gravity movement is considerably simpler. My suggestion would be to do anti-gravity for now, and at a later date try surfing once you feel comfortable with exactly how it works. --Rednaxela 22:01, 3 May 2009 (UTC)

Oh, is it a 40 pixel long sqare? that's what it looks like. --Awesomeness 22:43, 3 May 2009 (UTC)

No, it is 36px non-rotating square. » Nat | Talk » 23:42, 3 May 2009 (UTC)

Gun turn and fire execution order

When, in the execution order, are bullets fired, and when is the gun turned? Thanks! --Mageek 02:44, 28 May 2009 (UTC)

I believe that's part of #2 in the "Robocode Processing Loop" section. I can tell you for sure, though, that if you do setFire and setTurnGunRight in the same turn, the bullet will fire at the bearing of your gun before that gun turn happens. Both of them happen on the next tick, but the bullet is fired as if it were fired on the same tick as setFire (the location is from that tick, and it has advanced by its velocity once). Does that answer your question? --Voidious 02:53, 28 May 2009 (UTC)

Thank-you, that is exactly what I was trying to figure out. --Mageek 03:39, 28 May 2009 (UTC)

Accel/decel rules

(Conversation began on Talk:Darkcanuck/RRServer...)

I've almost finished my first robot to enter to the melee rumble :), but I'm wondering: does the (melee)server use the old accel/decel rules (where you can go from -1 to 1) or the new (where you can't)? --Positive 23:22, 11 Jul 2009

The RoboRumble currently only allows clients using versions 1.5.4, 1.6.0, and 1.6.1.4, so it should only be the old rule (where you can). I actually didn't realize that was changed -- I really don't like that. =( Lots of legacy bots are programmed to believe you can. --Voidious 21:24, 11 July 2009 (UTC)

Woah, what a quick response! Thanks for the info. :) I don't really like the change either (I have a cool -1, +1 strategy and a nice move simulator), but alas. --Positive 23:36, 11 Jul 2009

Are you sure the rules have changed? I thought the only changes to movement in later versions of Robocode (still unsupported in the rumble, btw) were to fix the movement quirks that Simonton had found. I don't remember decelerating through 0 being one of them. --Darkcanuck 22:26, 11 July 2009 (UTC)

Here is the discussion at the bug tracker. Fnl explains that if for example your robot is at -1.0 velocity, it can only reach 0.75 velocity the next turn (as of version 1.7.1.2). --Positive 02:45, 12 Jul 2009

Errr.... 0.75 is not 'accurate'... It's what robocode as of 1.7.1.2 does, but it's just as incorrect as before the change... Fnl says it uses a formula of (Rules.DECELERATION * decelTime * decelTime + Rules.ACCELERATION * accelTime * accelTime), when the correct formula should be (Rules.DECELERATION * decelTime + Rules.ACCELERATION * accelTime). Change in velocity, is always equal to acceleration multiplied by time, not time squared... It looks like Fnl got his physics mixed up and looked at a formula to get distance from acceleration (d = a*t*t) instead of getting velocity change from acceleration (v = a*t) :-( --Rednaxela 01:47, 12 July 2009 (UTC)

Ooh, I see this now... Do some tests and file a bug for Fnl? --Darkcanuck 02:48, 12 July 2009 (UTC)

Robocode Developer Google Groups, I think. So Flemming can re-open that tracker instead of creating new one. I always wonder why it go from 1 to -0.75, not 0.5 since it have only half turns left, I always think that I don't have enough physics knowledge. » Nat | Talk » 02:59, 12 July 2009 (UTC)

Voidious, do you subscribe to Robocode Developer Google Groups? I think we have reached the conclusion that we worth this change, unless there are too many effects. After we changed it, Flemming and I did run a lot of test (well, mostly Flemming run, I'd run only one test). I've test Dookious with DrussGT, on both 1.6.1.4 and 1.7.1.x with new updateMovement(), and the difference is around 1-2%, which is acceptable in margin of error. I chose Dookious and DrussGT because I know that Dookious use FuturePosition library, which is the internal copy of old movement engine. And DrussGT use Skilgannon's special movement predictor which I believe should be the loosely implementation of the 'correct' movement engine.

Positive, I believe that if you create a good movement under 1.6.1.4, it will be good in 1.7.1.x version too. » Nat | Talk » 06:20, 12 July 2009 (UTC)

- - -

Hi guys, to you mind I join the discussion? I did the change in "update movement" for many reasons. The issue(s) were raised a long time ago on the old RoboWiki (the 3 caveats raised by Simonton - http://old.robowiki.net/cgi-bin/robowiki?GamePhysics/BotSpeed), and later discussed within the Robocode Developer Group (even Mathew Nelson joined the discussion). That is, if we would make the change or not. Especially with you guys in mind. The conclusion in the groups was to fix the bugs so Robocode would follow its own rules, and because lot's of robots out there counts on the rules as explained, not to the way Robocode was actually behaving. Not everybody replicates the internal code of Robocode to get the formulas correct.

The old closed bug tracker on SF created is available here: https://sourceforge.net/tracker/?func=detail&atid=419486&aid=2077512&group_id=37202

Another goal with the change was to make the internal code easier less messy and easier to understand. Regarding the impact of the change, the results are not very different (unless you can prove me wrong here). I ran lots of lots of test with RoboRumble (also Melee and TeamRumble) on my local machines (different single-code, quad-core, Linux, Windows, 32 and 64 bit etc.), and I couldn't tell the difference in rankings or score with or without the change. There was a difference, but it was in average less than 1 percent. Is it really that much of a problem? Really?

I would really love if people could try out the Betas on RoboRumble and put issues on SF as soon as they are discovered. Then the issues can be fixed or discussed before we do the real release. This way, we could avoid such issues as this one long time after the change was made and released.

Btw. I am very familiar with physics, even tough the physics in Robocode does not really follow the real physics laws. I might not have explained the details about the fix well enough.

Instead of shifting between old and new code (like you propose?), I should like you guys to tell me where the problem is in the code instead, since you are obviously the experts. The code is Open Source, so everybody is free to come with suggestions to what and where to correct things.

Here we go:

	private void updateMovement() {
		double distance = currentCommands.getDistanceRemaining();

		if (Double.isNaN(distance)) {
			distance = 0;
		}

		velocity = getNewVelocity(velocity, distance);

		double dx = velocity * sin(bodyHeading);
		double dy = velocity * cos(bodyHeading);

		x += dx;
		y += dy;

		if (dx != 0 || dy != 0) {
			updateBoundingBox();
		}

		if (distance != 0) {
			currentCommands.setDistanceRemaining(distance - velocity);
		}
	}

	/**
	 * Returns the new velocity based on the current velocity and distance to move.
	 *
	 * @param velocity the current velocity
	 * @param distance the distance to move
	 * @return the new velocity based on the current velocity and distance to move
	 */
	private double getNewVelocity(double velocity, double distance) {
		// If the distance is negative, then change it to be positive and change the sign of the input velocity and the result
		if (distance < 0) {
			return -getNewVelocity(-velocity, -distance);
		}

		double newVelocity;

		// Get the speed, which is always positive (because it is a scalar)
		final double speed = Math.abs(velocity); 

		// Check if we are decelerating, i.e. if the velocity is negative.
		// Note that if the speed is too high due to a new max. velocity, we must also decelerate.
		if (velocity < 0 || speed > currentCommands.getMaxVelocity()) {
			// If the velocity is negative, we are decelerating
			newVelocity = speed - Rules.DECELERATION;

			// Check if we are going from deceleration into acceleration
			if (newVelocity < 0) {
				// If we have decelerated to velocity = 0, then the remaining time must be used for acceleration
				double decelTime = speed / Rules.DECELERATION;
				double accelTime = (1 - decelTime);

				// New velocity (v) = d / t, where time = 1 (i.e. 1 turn). Hence, v = d / 1 => v = d
				// However, the new velocity must be limited by the max. velocity
				newVelocity = Math.min(currentCommands.getMaxVelocity(),
						Math.min(Rules.DECELERATION * decelTime * decelTime + Rules.ACCELERATION * accelTime * accelTime,
						distance));

				// Note: We change the sign here due to the sign check later when returning the result
				velocity *= -1;
			}
		} else {
			// Else, we are not decelerating, but might need to start doing so due to the remaining distance

			// Deceleration time (t) is calculated by: v = a * t => t = v / a
			final double decelTime = speed / Rules.DECELERATION;

			// Deceleration time (d) is calculated by: d = 1/2 a * t^2 + v0 * t + t
			// Adding the extra 't' (in the end) is special for Robocode, and v0 is the starting velocity = 0
			final double decelDist = 0.5 * Rules.DECELERATION * decelTime * decelTime + decelTime;

			// Check if we should start decelerating
			if (distance <= decelDist) {
				// If the distance < max. deceleration distance, we must decelerate so we hit a distance = 0

				// Calculate time left for deceleration to distance = 0
				double time = distance / (decelTime + 1); // 1 is added here due to the extra 't' for Robocode

				// New velocity (v) = a * t, i.e. deceleration * time, but not greater than the current speed

				if (time <= 1) {
					// When there is only one turn left (t <= 1), we set the speed to match the remaining distance
					newVelocity = Math.max(speed - Rules.DECELERATION, distance);
				} else {
					// New velocity (v) = a * t, i.e. deceleration * time
					newVelocity = time * Rules.DECELERATION;

					if (speed < newVelocity) {
						// If the speed is less that the new velocity we just calculated, then use the old speed instead
						newVelocity = speed;
					} else if (speed - newVelocity > Rules.DECELERATION) {
						// The deceleration must not exceed the max. deceleration.
						// Hence, we limit the velocity to the speed minus the max. deceleration.
						newVelocity = speed - Rules.DECELERATION;
					}
				}
			} else {
				// Else, we need to accelerate, but only to max. velocity
				newVelocity = Math.min(speed + Rules.ACCELERATION, currentCommands.getMaxVelocity());
			}
		}

		// Return the new velocity with the correct sign. We have been working with the speed, which is always positive
		return (velocity < 0) ? -newVelocity : newVelocity;
	}

What must be corrected in order to make everybody happy, following the "physic laws" and rules of Robocode? --Fnl 22:59, 12 July 2009 (UTC)

Fnl, it will take me some time to look over the code and discussions before I can give more constructive feedback. But some things I can comment on for now:

• Fixing the issues Simonton brought up seems very reasonable to me. One is a bug that I doubt anyone depends on (the setMaxVelocity / decel). For the others, I'd guess DrussGT and SilverSurfer are the only bots that might simulate the quirks (being Go-To surfers). Some Wave Surfing Challenge tests with SS (I will run some) and feedback from Skilgannon could shed some light on potential impact.
• I'm not clear on what has happened with this, but I believe changing the ability to go from velocity 1 to -1 could adversely impact a lot of bots. Even a bot as old as PrairieWolf (2002) has a movement mode that depends on it ("buzzing" between 1 and -1), and I'd guess nearly every modern wave surfer also simulates this aspect of the physics.
• One percent is a lot -- see the "huge" 1% APS gap between DrussGT and Dookious =). That said, it takes hundreds or thousands of battles to get a result accurate enough to see that 1% difference.
• I do not envy your position in these types of matters, and as always, I appreciate the effort you put into developing Robocode. Robocode's impact goes far beyond the "hardcore" Robocoders on this wiki, and I fully understand that you want to polish Robocode as best as you can for the benefit of everyone that uses it. Cheers,

--Voidious 00:01, 13 July 2009 (UTC)

1 percent is not a lot with this major change in physics, especially when it makes the game follows its own rule better. 1% is 'huge' in APS, I agree. But if you look at each battle closely, the results can swing up to 10% » Nat | Talk » 16:14, 13 July 2009 (UTC)

1% is 1% and it is a lot. You're right that individual battles have a large variance, that's why you need to run hundreds of battles to get a meaningful result. If you run enough battles to get a statistically accurate result, 1% is a lot. If you don't run enough battles, you can't draw any real conclusion from the results.

I'm not claiming there is a 1% difference in results. I'm only saying that if tests only narrowed it down to "1% or less", that's not really enough to satisfy my need for accuracy and consistency. No ill will here, I should get involved and run some tests if I care so much. And I do. And I will. =)

--Voidious 17:40, 13 July 2009 (UTC)

While I wat to argue that 1% is not a lot for this major physics change, I don't think that is an issue anymore. I think you already accept the changes now =) » Nat | Talk » 12:37, 14 July 2009 (UTC)

I've read the mailing list and bug report concerning the issue. Does the -1, +1 thing really need to be changed to fix the bugs? This is how I would code it, and I believe it should fix the bugs. I haven't actually compiled it into robocode, but the velocity routines themselves have been tested and are working. And excuse me, I'm a bad commenter :):

	private void updateMovement() {
		double distance = currentCommands.getDistanceRemaining();

		if (Double.isNaN(distance)) {
			distance = 0;
		}

		velocity = getNewVelocity(velocity, distance);

                // small tweak from original version
		if(velocity!=0)
		{
			x+=velocity * sin(bodyHeading);
			y+=velocity * cos(bodyHeading);
			updateBoundingBox();
		}

		if (distance != 0) {
			currentCommands.setDistanceRemaining(distance - velocity);
		}
	}

	static double getNewVelocity(double velocityArg, double distanceArg) 
	{	
		double velocity;
		double distance;

		// Make sure the remaining distance is always positive or zero
		// (we switch this back later)
		if(distanceArg<0)
		{
			velocity=-velocityArg;
			distance=-distanceArg;
		}
		else
		{
			velocity=velocityArg;
			distance=distanceArg;
		}

		// Get the next most positive velocity the robot can reach for next turn
		double mostPositiveReachableVelocity = VelocityToMostPositiveVelocity(velocity);
		// Get the next most negative velocity the robot can reach for next turn
		double mostNegativeReachableVelocity = VelocityToMostNegativeVelocity(velocity);


		double highestWantedVelocity = Math.min(currentCommands.getMaxVelocity(), maxSpeedToStopInDisp(distance));

		// The real next velocity is limited by what is actually reachable
		double nextVelocity = Math.min(mostPositiveReachableVelocity,Math.max(mostNegativeReachableVelocity,highestWantedVelocity ));

		// Switch return value back if needed
		if(distanceArg<0)
			nextVelocity = -nextVelocity;
	
		return nextVelocity;
	}


	static public double VelocityToMostPositiveVelocity(double velocity)
	{
		// Returns the most positive reachable velocity from the
		// specified velocity in one turn
		if(velocity>0)
		{
			double returnVelocity = velocity+Rules.ACCELERATION;
			if(returnVelocity>Rules.MAX_VELOCITY)
				return Rules.MAX_VELOCITY;
			else
				return returnVelocity;
		}
		else
		{
			double returnVelocity = velocity+Rules.DECELERATION;
			if(returnVelocity>Rules.ACCELERATION)
				return Rules.ACCELERATION;
			else
				return returnVelocity;
		}
	}
	static public double VelocityToMostNegativeVelocity(double velocity)
	{
		// Returns the most negative reachable velocity from the
		// specified velocity in one turn
		if(velocity<0)
		{
			double returnVelocity = velocity-Rules.ACCELERATION;
			if(returnVelocity<-Rules.MAX_VELOCITY)
				return -Rules.MAX_VELOCITY;
			else
				return returnVelocity;
		}
		else
		{
			double returnVelocity = velocity-Rules.DECELERATION;
			if(returnVelocity<-Rules.ACCELERATION)
				return -Rules.ACCELERATION;
			else
				return returnVelocity;
		}
	}

	static private final double[] dispStopArray = 
		{0.0000,1.0000,2.0000,2.5000,3.0000,
		3.5000,4.0000,4.3333,4.6666,5.0000,
		5.3333,5.6666,6.0000,6.2500,6.5000,
		6.7500,7.0000,7.2500,7.5000,7.7500};
	static public double maxSpeedToStopInDisp(double displacement)
	{
		// Returns the biggest velocity the robot could go to this turn,
		// still being able to stop without overshooting. (Or if 
		// remaining displacement is less than 2, returns that)
                // This routine could be improved to match up with robocode's
                // older velocity selecting rules.
		if(displacement>=0)
		{
			if(displacement>=20)
				return 8.0;
			else if(displacement<=2)
				return displacement;
			else
				return dispStopArray[(int)Math.floor(displacement)];
		}
		else
		{
			return 0;
		}
	}

I also appreciate your effort, Fnl. :) --Positive 01:48, 13 July 2009 (UTC)

Ok, I'm up to speed with the discussions and the code. I think, for how it was decided, this line:

    newVelocity = Math.min(currentCommands.getMaxVelocity(),
        Math.min(Rules.DECELERATION * decelTime * decelTime + Rules.ACCELERATION * accelTime * accelTime,
        distance));

...should be changed to:

    newVelocity = Math.min(currentCommands.getMaxVelocity(),
        Math.min(Rules.ACCELERATION * accelTime, distance));

• The deceleration already takes you to zero, so we just need to use the remaining time for acceleration, right?
• Don't need to square the accelTime (v = at).

So, as I understand it, your velocities should be, for example: -1, +0.5, -0.75, +0.625? "Legacy" issues aside, I like this solution a lot. It makes sense. I've been considering this issue a bit now, and here's how I'd lay out the impact to affected bots:

• A bot like PrairieWolf that oscillates between 1 and -1 will now oscillate between roughly 0.7 and -0.7. I'm guessing this has very minimal impact on performance (though I am curious to test / confirm).
• When Wave Surfers predict a change of direction, their predictions could be off. I believe most surfers are dealing with whole number velocities the great majority of the time. Changing direction from even velocities will not be impacted. Changing direction from odd velocities, their predictions could be off by as much as 4 pixels -- predicting a velocity 0.5 too high for 8 ticks (until they reach max velocity). Some might disagree, and of course I advocate ultimate precision in surfing, but I believe the impact here is negligible. (How many of us even do precise bot width? And I never found much to be gained there, anyway.)
• I'm still not crazy about changing Robocode's physics, and I might've opposed it if put to a vote, but I think the impact is negligible and the new solution is a good one.

Also, I've started running those SilverSurfer WSC tests on 1.6.1.4 and 1.7.3 to compare. I'll have the results today or tomorrow.

--Voidious 15:31, 13 July 2009 (UTC)

The information in Robocode (mostly the floating point value) isn't digital, means that only 0.5 change isn't impact much. If you can dodge bullets well, the missed 2 ticks with the most of 2 pixels won't make the bullet hit you. If you can't dodge it, the slippage of 2 pixels may make you dodged it, but only by luck. » Nat | Talk » 16:14, 13 July 2009 (UTC)

<Edit conflict> Thanks for taking a look Fnl. I personally think that the current code is more complicated than necessary, and as such, harder to understand. Here's a few things that should be addressed:

• The decelDist. Because robocode follows a discrete time base, it cannot be approximated with calculus. For example, say your speed is 3, your formula gives 3.75 as decelDist. However, 3 + 1 + 0 = 4, so your code would not want to decelerate in the right places. This would be the correct implementation:

       private static final double decelDistance(double velocity){
         double distance = 0;
         while(velocity > 0){
            distance += velocity;
            velocity = Math.max(0,velocity - Rules.DECELERATION);
         }
         return distance;
      }

• One of the ideas of robocode is that your bot has a continuous acceleration/deceleration over a single tick. I see what you have done is, when a bot is decelerating over 0 velocity, it takes 1/2 of the tick to decelerate and then 1/2 of the tick is left to accelerate in the other direction (the split may depend on the amount of time taken to decelerate to 0 first). But many older bots rely on being able to decelerate over the entire tick, using the 2 deceleration value instead of the 1 acceleration value, so that they can 'vibrate' from 1 to -1 back to 1 etc. While I agree that it is not correct, these are the physics of robocode, not real life =) Because of this, you can essentially remove the majority of the inside of that 'if' block, just leaving velocity *= -1;.
• I have re-written this method, and if people want I'll post it, but it seems that with a few quick fixes this one should be up to scratch =), so I don't really think that's necessary.

As an answer to Voidious, I haven't taken any of the 'quirks' into account while writing DrussGT. It is coded with the rules, as they are described on the Robocode/Game_Physics page, in mind. --Skilgannon 16:00, 13 July 2009 (UTC)

(edit conflict) In my tests, DrussGT usually performs worse. But just around 0.2% or somethings. I'm not sure since I ran only 3 35-rounds tests.

While I agree with you that this isn't real life, it still isn't correct under its own Rules. The major reason we have this fix is that we want Robocode to follows its own rule batter. Otherwise we should have the bullet velocity affected by robot velocity, the curved bullet, better bullet-bullet collision checking etc. » Nat | Talk » 16:14, 13 July 2009 (UTC)

Sorry, but 3 battles simply cannot produce a result within 0.2% accuracy. In my experience, you'd need 100 or more before the overall result stays within 0.2%. --Voidious 17:40, 13 July 2009 (UTC)

Hi guys. Thank you for the constructive feedback. I appreciate that. I see many of you have some really good pointer of what to change, and where to make the changes. Currently, I have my house full of guests and is just checking what is going on in this forum. Tomorrow evening, I will take a closer look at all the comments, and I agree that the new implementation for "update movevement" is buggy too. I intend to create some variants that you can download and test for yourselves. Afterwards, you can choose which one is the better one for the next version of Robocode. Compared to 1.6.x.x, the code has become much simpler than it was before. I am not sure that the code could be any simpler than it is now as we will brake something else (because something is missing) - even though I hope it is possible. So, tomorrow I will review all comment on this page and take action. =) --Fnl 17:43, 13 July 2009 (UTC)

I really agree that the code is a lot more simple and adaptable than 1.6 and before. When I was adapting the internal Robocode's movement engine for my movement predictor, I can't adapt the <1.6 code. I get my head mess when I'm trying to understand it. However, I can adapt the current code really easy (in fact, I did copy almost whole getNewVelocity() method) » Nat | Talk » 12:37, 14 July 2009 (UTC)

I have examined all the comments here, and is trying to figure out how to modify the existing code for getNewVelocity(). I think you are on the right track Voidious, and hence I want to implement your modifications so we could all try them out. However, I have a hard time figuring out how the modified version of getNewVelocity() will look like. If a change the part for the newVelocity, it must be in the two places in the code, where it is assigned. You have only written how you want the first one. Voidious, could you give the full version of your version of getNewVelocity() as you think it should be? This way we all will be able to follow (and discuss) the changes/ideas, and I will be able to implement it straight away. :-) --Fnl 22:28, 14 July 2009 (UTC)

Sorry, I was only closely examining the decelerating through zero issue before. I agree with Skilgannon's assessment that decelDist doesn't seem right, though I'm not sure I'm understanding this fully. Skilgannon, you say that decelDist(3) should be 4, but shouldn't it be 1, since we can update the speed before we move? In either case, I don't understand why it would be 3.75, but I'm curious if there is some voodoo at work in this code that I'm not getting yet. I'll study some more and try to figure it out. =)

And Skilgannon, no harm in posting your rewritten version, I wouldn't mind seeing it. I'll also check out Positive's version. And I'll have some 1.6.1.4 vs 1.7.1.3 WSC2K6 scores ready to examine tomorrow. Only about 180 more seasons to run. =)

--Voidious 00:23, 15 July 2009 (UTC)

• My understanding (and subsequently, DrussGT's movement simulator, which uses a decelDistance based method of deciding when to decelerate) is if we go with the velocity of 3 this tick, how far will we travel in total if we decide it's necessary to decelerate next tick. Basically, do we have freedom with to do as we please with our velocity this tick, and still be able to decelerate sufficiently in the future. If the answer is "no", then we need to decelerate or maintain velocity this tick. My statements about 4 and 3.75 assumed the DECELERATION is 2. Fnl gets 3.75 from this little bit of code:

final double decelTime = speed / Rules.DECELERATION;
final double decelDist = 0.5 * Rules.DECELERATION * decelTime * decelTime + decelTime;

ie. 3/2 = 1.5 --> 0.5*2*1.5*1.5 + 1.5 = 3.75 whereas it should be 3 + (3-2) = 4. I'll be very interested to see what the scores look like =) --Skilgannon 08:59, 15 July 2009 (UTC)

Wow, this problem really is not trivial. Here's what I came up with, I think it works and is pretty minimal:

    private void updateMovement() {
        double distance = currentCommands.getDistanceRemaining();

        if (Double.isNaN(distance)) {
            distance = 0;
        }

        velocity = getNewVelocity(velocity, distance);

        double dx = velocity * sin(bodyHeading);
        double dy = velocity * cos(bodyHeading);

        x += dx;
        y += dy;

        if (dx != 0 || dy != 0) {
            updateBoundingBox();
        }

        if (distance != 0) {
            currentCommands.setDistanceRemaining(distance - velocity);
        }
    }

    /**
     * Returns the new velocity based on the current velocity and distance to move.
     *
     * @param velocity the current velocity
     * @param distance the distance to move
     * @return the new velocity based on the current velocity and distance to move
     */
    private double getNewVelocity(double velocity, double distance) {
        // If the distance is negative, then change it to be positive and change the sign of the input velocity and the result
        if (distance < 0) {
            return -getNewVelocity(-velocity, -distance);
        }

        double newVelocity;

        // Get the speed, which is always positive (because it is a scalar)
        final double speed = Math.abs(velocity); 

        if (velocity < 0) {
            // Check if we are decelerating, i.e. if the velocity is negative.
            newVelocity = speed - Rules.DECELERATION;

            // Check if we are going from deceleration into acceleration
            if (newVelocity < 0) {
                // If we have decelerated to velocity = 0, then the remaining time must be used for acceleration
                double decelTime = speed / Rules.DECELERATION;
                double accelTime = (1 - decelTime);

                // New velocity (v) = d / t, where time = 1 (i.e. 1 turn). Hence, v = d / 1 => v = d
                // However, the new velocity must be limited by the max. velocity
                newVelocity = Math.min(Rules.ACCELERATION * accelTime, distance));

                // Note: We change the sign here due to the sign check later when returning the result
                velocity *= -1;
            }
        } else {
            // Deceleration distance (d) is calculated iteratively due to Robocode's
            // discrete time system.
            final double decelDist = decelDistance(speed);

            // Deceleration ticks is the number of ticks it will take to get to
            // zero velocity. 
            final long decelTime = Math.round( // VOIDIOUS: for rounding errors? maybe unnecessary
                Math.ceil((speed - Rules.DECELERATION) / Rules.DECELERATION));

            // The maximum distance coverable with an equivalent decelTime
            final double decelTimeMaxDist = ((decelTime + 1) / 2.0) * decelTime // sum of 1..decelTime
                * Rules.DECELERATION;
                
            if (distance <= Rules.DECELERATION) {
                // If we can cover remaining distance and then completely stop,
                // set speed = distance
                newVelocity = Math.max(speed - Rules.DECELERATION, distance);
            } else if (distance <= decelTimeMaxDist) {
                // If we can cover distance in decelTime, split any extra
                // distance (between decelDist and distance) over decelTime
                // ticks
                newVelocity = speed - Rules.DECELERATION + 
                    ((distance - decelDist) / decelTime);
            } else {
                // If we need more than decelTime ticks, try to spread the
                // extra distance over (decelTime + 1) ticks. This will just max 
                // the acceleration if it needs to (ie, if we need more ticks).
                // VOIDIOUS: I think this part would break if Rules.ACCELERATION
                //           were set above Rules.DECELERATION; we might need an 
                //           extra case or something. Doh. =(
                newVelocity = Math.min(speed + Rules.ACCELERATION,
                    (decelTime * Rules.DECELERATION) +
                        ((distance - decelTimeMaxDist) / (decelTime + 1)));
            }
        }

        // VOIDIOUS: I think it makes more sense to do this here; no need to decelerate maximally
        //           if you don't need to to accomodate a new setMaxVelocity.
        newVelocity = Math.max(speed - Rules.DECELERATION, 
            Math.min(newVelocity, currentCommands.getMaxVelocity()));
            
        // Return the new velocity with the correct sign. We have been working with the speed, which is always positive
        return (velocity < 0) ? -newVelocity : newVelocity;
    }

    private static final double decelDistance(double speed){
        double distance = 0;
        while(speed > 0){
            speed = Math.max(0,speed - Rules.DECELERATION);
            distance += speed;
        }
        return distance;
    }

Velocity is updated before the bot moves, right? =) This is a serious brain teaser! Wanted to post what I had before bed, but I'm still not satisfied with the part that would break with different accel/decel values. --Voidious 05:06, 15 July 2009 (UTC)

(maybe we should move this lengthy discussion to another page?) I've been going through the new velocity formula and have similar concerns as Skilgannon. Just running some test cases using my VelocityTest class and have found cases where the bot overshoots the requested distance (e.g. try starting velocity 0, distance 6 -- the bot ramps up to velocity 3 and will thus overshoot badly). I'll put together some tests and then maybe make a fixed version of the routine.

Regarding deceleration through 0, I have to sympathize with Fnl et al. There's nothing in the rules that says a bot can decelerate through 0 and gain some free acceleration. Deceleration takes you towards 0, acceleration takes you away from it. It's a quirk -- often called a "bug" -- that was perhaps first publicized here (near bottom) and has been exploited since. Its not a huge quirk, the advantage is minimal so fixing it should also be minimal but only tests can really confirm this.

--Darkcanuck 05:09, 15 July 2009 (UTC)

Hey Fellas. Great you're doing more research into this! I think the -1, +1 thing is not a major issue, but if the incorrect movement handling bugs can be fixed in a way that the -1, +1 thing stays valid, is there any harm? I think the version I posted is simpler to understand, and it should work effectively. The only thing that you might not agree with is the working of the maxSpeedToStopInDisp function, but that should at least centralize the problem. :) --Positive 05:53, 15 July 2009 (UTC)

I'm sorry I haven't examined yours more. There are two reasons, really:

• It does look like you're solving the problem efficiently (and I assume correctly), but I think it depends on fixing one or all of Rules.DECELERATION, Rules.ACCELERATION, and maximum velocity=8. I think we want a solution independent of those values.
• I find this quite an enjoyable brain teaser, and just wanted to figure out an answer myself. =)

--Voidious 13:26, 15 July 2009 (UTC)

I did test your solution and it passes all the same tests that Voidious' version 2 does. But as he pointed out, the hardcoded values are problematic. --Darkcanuck 17:48, 15 July 2009 (UTC)

The reason I don't like breaking the +-1 thing is because it makes the precise prediction significantly more complicated, and what's more it assumes that the acceleration has more than one value between 2 ticks, which to me seems to break the whole concept of a discrete time interval. For interests sake, here's the one I wrote:

    private void updateMovement() {
         double distance = currentCommands.getDistanceRemaining();
      
         if (Double.isNaN(distance)) {
            distance = 0;
         }
      
         velocity = getNewVelocity(velocity, distance);
      
         double dx = velocity * sin(bodyHeading);
         double dy = velocity * cos(bodyHeading);
      
         x += dx;
         y += dy;
      
         if (velocity != 0 ) {
            updateBoundingBox();
         }
      
         if (distance != 0) {
            currentCommands.setDistanceRemaining(distance - velocity);
         }
      }
   
   /**
    * Returns the new velocity based on the current velocity and distance to move.
    *
    * @param velocity the current velocity
    * @param distance the distance to move
    * @return the new velocity based on the current velocity and distance to move
    */
       private double getNewVelocity(double velocity, double distance) {
      
         if (distance < 0) 
            return -getNewVelocity(-velocity, -distance);
      	// If the distance is negative, then change it to be positive
      	// and change the sign of the input velocity and the result
         
         double maxVel = currentCommands.getMaxVelocity();
         if (velocity < 0)
            return Math.min(velocity + Rules.DECELERATION, maxVel);
         //we want to go in the opposite direction, so decelerate   
         	
         else{ 
         //we are going in the direction we want, test what happens if we accelerate
         
            double accel = Math.min(Rules.ACCELERATION, maxVel - velocity);
            //speed up, but not more than max velocity. decel if maxVel is less than velocity.
         	
            accel = Math.max(accel, -Rules.DECELERATION);
             //prevent excess deceleration due to bot lowering the maxVel while velocity is high
            
            if (distance > decelDistance(velocity + accel))
               return velocity + accel;
            else if(accel != 0 && distance > decelDistance(velocity))
               return velocity;
            else{
               if(distance < Rules.DECELERATION 
               //we'll be able to cover remaining distance in 1 tick and then decel to stop
               
               && velocity - distance <= Rules.DECELERATION 
               //and our velocity is low enough for us to get to that required velocity
               )
                  return Math.min(distance, maxVel);
             //choose the velocity to cover all remaining distance        
            			
               return Math.max(-maxVel, velocity -  Rules.DECELERATION);
            //velocity > 0 and we are close enough, so decelerate. 
            }
         
         }
      
      }
    /**
    * Returns the linear distance it would take to decelerate from a given positive velocity
    *
    * @param velocity the positive velocity from which to test
    * @return the linear distance required to decelerate to a standstill
    */
       private static final double decelDistance(double velocity){
         double distance = 0;
         while(velocity > 0){
            distance += velocity;
            velocity = Math.max(0,velocity - Rules.DECELERATION);
         }
         return distance;
      }  

I'm fairly sure this fixes the 0,6 test Darkcanuck is doing. Voidious, one of the problems with your decelDistance() implementation is that your decel distance assumes you decelerate before adding the distance, whereas mine checks if we can still accelerate this tick and be able to decelerate sufficiently in the future. Also, mine considers the case of continuing at the current velocity, which may be a better option, as in the 0,6 test. --Skilgannon 08:27, 15 July 2009 (UTC)

I agree that the new formulas do break the simplicity of the discrete time period. One simple solution would be simply to apply deceleration until 0 velocity is reached -- the extra time for acceleration would be lost. That would both follow the rules and keep the accel/decel values simple. But Fnl's solution does compromise by giving back the extra time for some acceleration, which should help bots that rely on this quirk. --Darkcanuck 16:29, 15 July 2009 (UTC)

(I agree about moving this to a different or its own page. Anyone can feel free, or I'll do it in a bit.) Ah, I'm just imagining a different significance to decelDist: I imagine it as the minimum distance we would cover if we slam on the brakes. The problem with the (0, 6) case (more specifically the (2, 3) case) in mine is similar to the problem I theorize about when Rules.accel is greater than Rules.decel: I assume that if you can't cover distance in decelTime ticks, you can split the extra distance over (decelTime + 1) ticks, which of course is 1 tick and you go to speed 3. Maybe I should force decelTime to a min of 1, since if it's 0 and distance <= Rules.decel, we hit the first case and don't use it, otherwise we hit the 3rd case and need 2 ticks.

Mine would also remain at constant velocity if needed, or even speed up a bit, despite lack of a special case. I'll have to investigate that 0 to -2 acceleration... hopefully that's a simple fix.

I forgot that you'd already be familiar with this kinda stuff, since you are the Lord of Go-To. =) But I still see a problem with yours in that you restrict your decisions to max accel, constant, or max decel. Take the v=6.1, d=15 case: you want to do it in 4 ticks, and mine will (I think =)) go 6.75, 4.75, 2.75, 0.75. I think yours would go 6.1, 4.1, then be presented with (4.1, 4.8) and fail to do it in 4 ticks.

I swear there must be a known Dynamic Programming problem that reduces to this. Maybe my effort would be better spent finding it and copying the established solution. =) To be clear, we are trying to do this in the optimal number of ticks, right?

--Voidious 13:26, 15 July 2009 (UTC)

I updated my method and posted it to User:Voidious/Optimal Velocity. I think this fixes both the (2, 3) case and the (0, 2) case, though I feel like the (2, 3) case should go 2/1 instead of 1.5/1.5. Can we agree that Rules.DECELERATION will never be less than Rules.ACCELERATION? Or just accept that caveat in our solutions? I believe changing that would seriously complicate things. --Voidious 14:28, 15 July 2009 (UTC)

Ok, I really need to stop thinking about this and get some work done =), but I found some topics maybe worth checking out:

• Wikipedia: Bellman equation
• Wikipedia: Backward induction (found linked here)

--Voidious 14:43, 15 July 2009 (UTC)

I understand your point Voidious. But I think in any case, the whole concept is complex in such a way, it's good to break it up into different functions (like Darkcanuck has already done partially). How about you guys make the following functions for your versions:

double getMaxVelocity(double distance)
{
 // returns the largest possible velocity for the robot to be set to,
 // that, if next turn it had to start decelerating, it would still be
 // able to stop without overshooting
}

Basically, that would refine the problem. Because in that function you don't have to care about the current velocity. :) After this function returns, you only need to check if the returned velocity "wantedVelocity" is actually reachable from the current velocity by the accelerating/deceleration laws of robocode. And if not try to get closest to it (that won't cause any problems, because any speed returned lower than the max velocity won't overshoot either) :)

So basically, the other function needed is:

double getClosestReachableVelocityToVelocity(double currentVelocity,double wantedVelocity)
{
 // with this function you can basically assume setAhead(Infinity) or setAhead(-Infinity)
 // was called, and you determine the next velocity based on the max velocity
 // set by the robot. For example, if the current velocity is 0 and the max velocity
 // set was 4.0, it would return 1.0. If the current velocity was 8.0, it would return 6.0.
} 

Finally, the getNewVelocities final version would be (independant of the workings of the other functions):

double getNewVelocity(double velocity, double distance) 
{
 if(distance<0)
  return -getNewVelocity(-velocity,-distance);
  double highestVelocity = getMaxVelocity(distance); // highest velocity without overshooting
  double wantedVelocity = Math.min(highestVelocity,currentCommands.getMaxVelocity());
      // the actually wanted velocity by the robot is the highest possible,
      // limited by what the robot set by the setMaxVelocity command
  return getClosestReachableVelocityToVelocity(velocity, wantedVelocity);
      // return whatever is closest to that velocity
}

--Positive 16:50, 15 July 2009 (UTC)

I didn't break anything up, just plugged the getNewVelocity functions into a simple (well, the latest version is no longer so simple) testing framework. The best solution is the one that gets the job done in the least code, while still remaining understandable. =) --Darkcanuck 17:48, 15 July 2009 (UTC)

I really like how you frame the problem here. I think I have a solution to getMaxVelocity at User:Voidious/Optimal Velocity. This seems like a much cooler and cleaner way to deal with this. --Voidious 18:14, 15 July 2009 (UTC)

Okay Darkcanuck, I understand. I just finished creating an implementation of the getClosestReachableVelocityToVelocity here: Positive/Optimal Velocity. I'll try to combine Voidious's getMaxVelocity routine with it and the code above, and post the results. --Positive 19:11, 15 July 2009 (UTC)

It seems like it's working. I posted the results here Positive/Optimal Velocity. Great job Voidious with your getMaxVelocity function! --Positive 19:37, 15 July 2009 (UTC)

You guys are truely amazing. Good job! I knew the "update movement" was non-trivial and could be complex when I tried to simplify things and get rid of the "bugs". But now it seems even much more complex. The rules are simple, but the code behind it complex?! I will put take all the code from the Positive/Optimal Velocity page and put into Robocode. Then I will make a new Alpha version, which everybody could try out to see if this is what we want in the next version of Robococe (1.7.1.4). And yes Positive, the your version of updateMovement is better. --Fnl 21:41, 15 July 2009 (UTC)