User:Positive/Optimal Velocity

To not clutter up the Talk:Robocode/Game Physics page:

I believe this is the correct getClosestReachableVelocityToVelocity function (feel free to comment):

double getClosestReachableVelocityToVelocity(double currentVelocity,double wantedVelocity)
{
 // this function assumes wantedVelocity<=Rules.MAXVELOCITY
 // 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.
 if(wantedVelocity<0)
  return -getClosestReachableVelocityToVelocity(-currentVelocity,-wantedVelocity);
 if(currentVelocity<0)
 {
  double nextVelocity;
  // we are travelling the wrong way, decelerate
  nextVelocity = currentVelocity + Rules.DECELERATION;
  if(nextVelocity>Rules.ACCELERATION)
   // make sure we can't jump from -0.1 to 1.9 or something
   nextVelocity = Rules.ACCELERATION;
  if(nextVelocity>wantedVelocity)
   // if the wanted velocity is for example 0.5, limit the velocity to that.
   return wantedVelocity;
  else
   // else return the highest possible
   return nextVelocity;
 }
 else
 {
  if(currentVelocity>wantedVelocity)
  {
   // both velocities are positive, but we need to decelerate
   double nextVelocity = currentVelocity - Rules.DECELERATION;
   if(nextVelocity<wantedVelocity)
    // if we can decelerate more than what's wanted, return what's wanted
    return wantedVelocity;
   else
    // else return the closest to it
    return nextVelocity;
  }
  else
  {
   // the wantedVelocity is higher than current
   double nextVelocity = currentVelocity + Rules.ACCELERATION;
   if(nextVelocity>wantedVelocity)
    // if we can accelerate more than what's wanted, return what's wanted
    return wantedVelocity;
   else
    // else return the closest to it
    return nextVelocity;
  }
 }
} 

getMaxVelocity function by Voidious:

    double getMaxVelocity(double distance)
    {
        if(distance>=20)  // temporary fix, works for maxVelocity==8.0 && maxDecel==2.0
          return Rules.MAX_VELOCITY;
        long decelTime = decelTime(distance);
        double decelDist = (decelTime / 2.0) * (decelTime-1) // sum of 0..(decelTime-1)
            * Rules.DECELERATION;
            
        return ((decelTime - 1) * Rules.DECELERATION) +
            ((distance - decelDist) / decelTime);
    }

    long decelTime(double distance) {
        long x = 1;
        do {
            // (square(x) + x) / 2) = 1, 3, 6, 10, 15...
            if (distance <= ((square(x) + x) / 2) * Rules.DECELERATION) {
                return x;
            }
            x++;
        } while (true);
    }

    long square(long i) {
        return i * i;
    }

The getNewVelocity function:

    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
    }

Simulator:

    public void simulate()
    {
    	double currentVelocity = 8.0;
    	double distanceRemain = -2.0;
    	while(distanceRemain!=0.0 || currentVelocity!=0.0)
    	{
    		out.println("velocity = "+currentVelocity+"; distance="+distanceRemain);
    		currentVelocity = getNewVelocity(currentVelocity,distanceRemain);
    		distanceRemain -=currentVelocity;
    	}
    }

Results

StartVelocity = 0.0; StartDistance = 6.0;

velocity = 0.0; distance=6.0
velocity = 1.0; distance=5.0
velocity = 2.0; distance=3.0
velocity = 2.5; distance=0.5
velocity = 0.5; distance=0.0

StartVelocity = 0.0; StartDistance = 10;

velocity = 0.0; distance=10.0
velocity = 1.0; distance=9.0
velocity = 2.0; distance=7.0
velocity = 3.0; distance=4.0
velocity = 3.0; distance=1.0
velocity = 1.0; distance=0.0

StartVelocity = -1.9; StartDistance = 10;

velocity = -1.9; distance=10.0
velocity = 0.10000000000000009; distance=9.9
velocity = 1.1; distance=8.8
velocity = 2.1; distance=6.700000000000001
velocity = 3.1; distance=3.600000000000001
velocity = 2.8000000000000007; distance=0.8000000000000003
velocity = 0.8000000000000007; distance=-4.440892098500626E-16;
velocity = -4.440892098500626E-16; distance=0.0

StartVelocity = 8.0; StartDistance = -2.0;

velocity = 8.0; distance=-2.0
velocity = 6.0; distance=-8.0
velocity = 4.0; distance=-12.0
velocity = 2.0; distance=-14.0
velocity = -0.0; distance=-14.0
velocity = -1.0; distance=-13.0
velocity = -2.0; distance=-11.0
velocity = -3.0; distance=-8.0
velocity = -4.0; distance=-4.0
velocity = -3.0; distance=-1.0
velocity = -1.0; distance=0.0

StartVelocity = 5.0; StartDistance = 40.0;

velocity = 5.0; distance=40.0
velocity = 6.0; distance=34.0
velocity = 7.0; distance=27.0
velocity = 8.0; distance=19.0
velocity = 7.75; distance=11.25
velocity = 5.75; distance=5.5
velocity = 3.75; distance=1.75
velocity = 1.75; distance=0.0

Original game updateMovement code

    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);
        }
    }

Suggested updateMovement code Positive

Now I'm thinking, if the distance remaining == 0.0, and the velocity is set from 6.0 to 4.0, shouldnt the distance remaining become -4.0? Also, the updateBoundingBox is called whenever velocity!=0, because the condition dx==0 && dy==0 is only when the velocity==0, so that can be easier to check. I suggest:

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

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

        velocity = getNewVelocity(velocity, distance);

	if(velocity!=0)
	{
		x += velocity * sin(bodyHeading);
		y += velocity * cos(bodyHeading);
		updateBoundingBox();
	}

	currentCommands.setDistanceRemaining(distance - velocity);
    }

Corrected updateMovement code

When I run your suggested version against the unit test for 1.6.1.4, I get an error. After some studying and experiments, I found out that the updateMovement() method used in 1.7.1.3 (the "original" on this page) and your suggested version are both buggy. The problem is that the remaining distance is incorrect. The bugfree version compared to 1.6.1.4 is this version:

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

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

		velocity = getNewVelocity(velocity, distance);

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

			x += velocity * sin(bodyHeading);
			y += velocity * cos(bodyHeading);
			updateBoundingBox();
		}
	}

The problem was, that is the robot has a velocity of e.g. 8, and we call setAhead(0), the remaining distance would be set to 0. But this is not correct, as the robot needs to brake first, and will move at least 6 + 4 + 2 = 12 pixels more, meaining that it should end with a remaining distance of -12. My new version about take this into account and works in the 1.6.1.4 code. Unfortunately this also means that our Alpha versions are buggy, as I used this improved version for all of them. That might explain the "big" differences in score! I am affraid that we need to do new alphas and retest them all with this issue in mind. Argh! What to do? Should we make new alphas for Hijack 1 and 2 etc. and retest? We could do this + we gain benefits of all bugfixes that have been made since 1.7.1.3. --Fnl 22:04, 7 August 2009 (UTC)

Thankyou for taking the time to investigate this, could you please expand on why you added:

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

Say you are at -2 velocity, and set distance to travel=100. Wouldn't that code cause distance to travel to be incorrectly set to 0? --Positive 23:06, 7 August 2009 (UTC)

Fnl, what I think you are trying to do is prevent bots from reversing back to their original position if setAhead(0) is called? You shouldn't do that by checking if velocity == 0 but rather by checking if distance == 0 because velocity has nothing to do with what the bot passed as an arguments, distance is. So rather have the updateMovement() method as:

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

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

        velocity = getNewVelocity(velocity, distance);

	if(velocity!=0)
	{
		x += velocity * sin(bodyHeading);
		y += velocity * cos(bodyHeading);
		updateBoundingBox();
	}
        if(distance != 0)
		currentCommands.setDistanceRemaining(distance - velocity);
    }

--Skilgannon 23:21, 7 August 2009 (UTC)

Yes, I believe your version is correct, and that my newest version is buggy (too). Actually, I was using the "if(distance != 0)" in my original code for 1.7.1.3. It seems to work better. And running on the old test cases for 1.6.1.4 shows that the previous version only covers some parts of the errors I saw yesterday with the suggested updateMovement from Positive.

Doh! This means that the new alphas I made yesterday (5, 6, 7) are incorrect too! :-\

Okay, so we should wait on doing new tests, and create new Alphas again, again. I need to try out this new version too. --Fnl 13:16, 8 August 2009 (UTC)

Skilgannon, it seems your version is buggy too. The problem is that is does not take the braking scenario into account I described earlier. E.g. if the robot is moving at velocity 8, has quite some remaining distance left, and then we call setAhead(0), the robot should end with a remaining distance = -12 after the braking has stopped.

• Time n+0: Velocity = 8, remaining distance = 1000 -> Now we call setAhead(0)
• Time n+1: Velocity = 8, remaining distance = 0
• Time n+2: Velocity = 6, remaining distance = -6
• Time n+3: Velocity = 4, remaining distance = -10
• Time n+4: Velocity = 2, remaining distance = -12
• Time n+5: Velocity = 0, remaining distance = -12 -> We have finally stopped

This scenario must be taken into account in order to stay compatible with 1.6.1.4. I guess we need a seperate variable to keep track of the user's setAhead/Back(x) request. --Fnl 13:48, 8 August 2009 (UTC)

Isn't it should be

• Time n+0: Velocity = 8, remaining distance = 1000 -> Now we call setAhead(0)
• Time n+1: Velocity = 6, remaining distance = -6
• Time n+2: Velocity = 4, remaining distance = -10
• Time n+3: Velocity = 2, remaining distance = -12
• Time n+4: Velocity = 0, remaining distance = -12 -> We have finally stopped

? Because robot did move once more in each tick. » Nat | Talk » 14:59, 8 August 2009 (UTC)

Yes, you are right here. :-) --Fnl 21:28, 8 August 2009 (UTC)

Let see if this work...

boolean isOverDriving = false;

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

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

      	velocity = getNewVelocity(velocity, distance);

	if (velocity == 0 && isOverDriving) {
		currentCommands.setDistanceRemaining(0);
		isOverDriving = false;
	}

	if (Math.signum(distance * velocity) != -1) {
		if (getDistanceTraveledUntilStop(velocity) > Math.abs(distance))
			isOverDriving = true;
		else
			isOverDriving = false;
	}

	if(velocity != 0) {
		x += velocity * sin(bodyHeading);
		y += velocity * cos(bodyHeading);
		updateBoundingBox();
	}
       	
	if(distance != 0)
		currentCommands.setDistanceRemaining(distance - newVelocity);
}

private double getDistanceTraveledUntilStop(double velocity) {
	double distance = 0;
	velocity = Math.abs(velocity);
	while (velocity > 0)
		distance += (velocity = getNewVelocity(velociy, 0));
	return distance;
}

» Nat | Talk » 14:21, 8 August 2009 (UTC)

Testing using hacked Darkcanuck's VelocityTest, my version seems to work fine. » Nat | Talk » 14:59, 8 August 2009 (UTC)

Fnl, with the version I posted as suggestion to the original, it should work like you said. I really can't see why it wouldn't work. To check we are on the same page, if the robot is at 8 velocity, and setAhead(0) is set, it should move backwards after it has overshot, right? If you look at the version I posted, you see the line:

	currentCommands.setDistanceRemaining(distance - velocity);
    }

Lets say distance is set to 0, and velocity is set to 6. Then distance remaining will be set here to (0 - 6) = -6. And after that (-6 - 4) = -10. Etc. --Positive 17:27, 8 August 2009 (UTC)

Positive, I ran my test again with your version. I am sorry that I wrote that the problem with your version is the remaining distance. This is not the case, as it is perfect in your version. The problem with your version is that when the robot is braking, it does not stop at velocity = 0. It continues to velocity = -1 in the next turn, and afterward -2, where it should have stopped at velocity = 0. This can be seen with the TestBodyTurnRate (using the BodyTurnRate test robot). The additonal check if(distance != 0) by Skilgannon fixes this problem, but wrecks the remaining distance. So we need a method to take both issues into account. :-p Now I will check out Nat's version. I cross my fingers that his version works. --Fnl 21:15, 8 August 2009 (UTC)

Hrm, but what would be the use of getting a distance of -12 at velocity=0, if the robot doesn't try to get to 0 distance by going -1, -2 etc.? I'll try to test with that robot to see what you mean. --Positive 21:47, 8 August 2009 (UTC)

FNL's test robot

Okay, I guees I need to provide a sample robot + give the result I expect so you are able to follow what I am talking about. ;-) Basically, I just want us to be compatible with version 1.6.1.4, at least for the following test.

This robot will show a simple movement:

public class TestVelocityAndRemainingDist extends robocode.AdvancedRobot {
	public void run() {
		// Set far ahead
		setAhead(1000);

		// Execute for 9 turns
		for (int i = 0; i < 9; i++) {
			executeAndDump();
		}

		// Stop moving
		stopMovingAndDump();
	}

	private void executeAndDump() {
		double lastVelocity = getVelocity();
		double distanceRemaining = getDistanceRemaining();

		execute();

		out.println(getTime() + ": " + lastVelocity + ", " + distanceRemaining);
	}

	private void stopMovingAndDump() {
		setAhead(0);
		setTurnLeft(0);
		
		for (int i = 0; i < 7; i++) {
			executeAndDump();
		}
	}
}

The results (robot output) we get when running this robot in version 1.6.1.4 is:

1: 0.0, 1000.0
2: 1.0, 999.0
3: 2.0, 997.0
4: 3.0, 994.0
5: 4.0, 990.0
6: 5.0, 985.0
7: 6.0, 979.0
8: 7.0, 972.0
9: 8.0, 964.0
10: 8.0, 0.0
11: 6.0, -6.0
12: 4.0, -10.0
13: 2.0, -12.0
14: 0.0, 0.0
15: 0.0, 0.0
16: 0.0, 0.0

Here the first number is the turn, the second row is the velocity, and the third row is the remaining distance.

--Fnl 21:54, 8 August 2009 (UTC)

When I test using Positive's updateMovement, I get almost the same, but have problems with the velocity in the end:

...
13: 2.0, -12.0
14: 0.0, -12.0
15: -1.0, -11.0
16: -2.0, -10.0

That is, the velocity should end at 0. So this is bad compared to 1.6.1.4.

When I test using Skilgannon's and also Nat's version of updateMovement, I end with (in both cases):

...
10: 8.0, 0.0
11: 6.0, 0.0
12: 4.0, 0.0
13: 2.0, 0.0
14: 0.0, 0.0
15: 0.0, 0.0
16: 0.0, 0.0

Here the remaining distance is wrong compared to 1.6.1.4.

--Fnl 22:13, 8 August 2009 (UTC)

(Edit conflict) Okay, so lets say the current velocity is positive, the pseudocode would be (for your suggested behaviour):

 if remaining distance is positive:
   the next velocity is the closest possible to the max velocity without overshooting
   the next remaining distance is current remaining distance - next velocity
 if remaining distance is negative:
   the next velocity is the closest possible to 0
   if the next velocity is 0:
     the next remaining distance becomes 0
   else
     the next remaining distance becomes current remaining distance - next velocity

Is this correct? --Positive 22:16, 8 August 2009 (UTC)

Yes, this looks right to me. :-) --Fnl 22:31, 8 August 2009 (UTC)

Heh, and if I make this little tweak and run in 1.6.1.4:

	private void stopMovingAndDump() {
		setAhead(-0.01);
		setTurnLeft(0);
		
		for (int i = 0; i < 13; i++) {
			executeAndDump();
		}
	}

it gives

1: 0.0, 1000.0
2: 1.0, 999.0
3: 2.0, 997.0
4: 3.0, 994.0
5: 4.0, 990.0
6: 5.0, 985.0
7: 6.0, 979.0
8: 7.0, 972.0
9: 8.0, 964.0
10: 8.0, -0.01
11: 6.0, -6.01
12: 4.0, -10.01
13: 2.0, -12.01
14: 0.0, -12.01
15: -1.0, -11.01
16: -2.0, -9.01
17: -3.0, -6.01
18: -4.0, -2.01
19: -2.0, -0.009999999999999787
20: -0.009999999999999787, 0.0
21: 0.0, 0.0
22: 0.0, 0.0

showing how near-zero values behave. Ugh... this highly inconsistant behavior between near-zero and zero makes me tempted to suggest something like having setAhead() behave like 1.6.1.4, but make something like a setBetterAhead() with more intuitive/sane behavior. Personally, I can think of little usefulness of the old setAhead() behavior in a new bot, except to annoy the bot author. If an author wants the bot to coast to a stop, the stop() function makes much more sense. Every single movement I've personally written, or seen anyone else write, is based upon either a "goToPoint()" style method, a "setVelocity()" style method, or is a simple oscillator. For simple oscillators or "setVelocity()" method the "setAhead(0)" condition likely never occurs. For a "goToPoint()" style, "setAhead(0)" will almost always be intended to mean "go where I am now". The ONLY case in which I can see people thinking the current behavior of "setAhead(0)" makes sense, is if what they REALLY meant was "setVelocity(0)". --Rednaxela 22:28, 8 August 2009 (UTC)

I really agree with you that the setAhead() and stop is not really intuitive. It fooled me many times as I always forget how it behaves. However, I have never dared to change that as I would break the compatibility and rankings in RoboRumble. ;-) Your idea with setVelocity(0) reminds me of the new robot type in Robocode named RateControlRobot. Go have a look. :-) --Fnl 22:42, 8 August 2009 (UTC)

Just for the record, I forgot to add the test result for my updateMovement method from yesterday against the TestVelocityAndRemainingDist robot. My version seems works perfect in this specific scenario. But I am still not sure if it is 100% correct. --Fnl 22:31, 8 August 2009 (UTC)

I think like Rednaxela it seems illogical that the distance should first become -12, and then be set to 0 when velocity=0 is reached. I believe there are 2 options:

1. The overshot is added to the remaining distance (my first suggested code).
2. Nothing is added to the remaining distance and it stays the same until the robot travels in the right direction. That means that remaining distance would stay at 0 if a robot sets setAhead(0), but will eventually move backwards only by -2 if set with setAhead(-2) independant of what the initial velocity was.

Otherwise what Rednaxela posted will happen (setAhead(-0.01) being treated completely different from setAhead(0)). --Positive 22:40, 8 August 2009 (UTC)