# User:Voidious/Optimal Velocity

## First attempt

I don't want to clutter the Talk:Robocode/Game Physics page with full versions of this, but I want the updated full version somewhere... The goal is to go `distance`

in the fewest number of ticks, limited by `Rules.ACCELERATION`

, `Rules.DECELERATION`

, and `currentCommands.getMaxVelocity()`

.

```
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) / Math.max(decelTime + 1, 2)));
}
}
// 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(speed + Rules.ACCELERATION,
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;
}
```

- Version 1 posted in-line at Talk:Robocode/Game Physics.
- Version 2 bounds newVelocity by speed + Rules.ACCELERATION and sets a min of 2 for the number of ticks to split the extra distance over.

## getMaxVelocity solution

Phrasing this a different way, we might try to figure out the max velocity we can go now and still decelerate to a given distance. I think this works, and it does seem like a much more elegant solution.

```
double getMaxVelocity(double distance)
{
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;
}
```

I derived this by first mapping some things out for different distances, then dissecting it:

- [0, 2] - distance
- (2, 6] - 2 + ((distance-2)/2)
- (6, 12] - 4 + ((distance-6)/3)
- (12, 20] - 6 + ((distance-12)/4)

## Hijack 2

Ok, another hijack here. I took Skilgannon's much-reduced version of the code from Talk:Positive/Optimal Velocity, fixed up some white space formatting because I'm OCD, and added support for Fnl's new decel-through-zero rules.

```
private static double getNewVelocity(double velocity, double distance) {
if (distance < 0)
// If the distance is negative, then change it to be positive
// and change the sign of the input velocity and the result
return -getNewVelocity(-velocity, -distance);
final double goalVel;
if(distance == Double.POSITIVE_INFINITY)
goalVel = currentCommands.getMaxVelocity();
else
goalVel = Math.min(getMaxVelocity(distance),
currentCommands.getMaxVelocity());
if(velocity >= 0)
return Math.max(velocity - Rules.DECELERATION,
Math.min(goalVel, velocity + Rules.ACCELERATION));
//else
return Math.max(velocity - Rules.ACCELERATION,
Math.min(goalVel, velocity + maxDecel(-velocity)));
}
final static double getMaxVelocity(double distance) {
final double decelTime = Math.max(1,Math.ceil(
//sum of 0... decelTime, solving for decelTime using quadratic formula
(Math.sqrt((4*2/Rules.DECELERATION)*distance + 1) - 1)/2));
final double decelDist = (decelTime / 2.0) * (decelTime-1) // sum of 0..(decelTime-1)
* Rules.DECELERATION;
return ((decelTime - 1) * Rules.DECELERATION) +
((distance - decelDist) / decelTime);
}
private static double maxDecel(double speed) {
double decelTime = speed / Rules.DECELERATION;
double accelTime = (1 - decelTime);
return Math.min(1, decelTime) * Rules.DECELERATION +
Math.max(0, accelTime) * Rules.ACCELERATION;
}
```

The only functional change is replacing Rules.DECELERATION with maxDecel(-velocity) in the one spot. --Voidious 15:55, 16 July 2009 (UTC)