User:Voidious/Optimal Velocity

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.

---

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)