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)