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)