Darkcanuck/VelocityTest

Some code to test 1.7.1.3's updated getNewVelocity() method vs a few wiki-contributed versions.

The main class:

import robocode.Rules;


public class VelocityTest {
    
    private static Commands currentCommands = new Commands();
    private static boolean doPrint = false;
    
    public static void main(String[] args) {
        
        // init
        System.out.println("\nDarkcanuck's VelocityTest\n");
        
        if (!args[0].equals("all") && !args[0].equals("print")) {
            doPrint = true;
            double velocity = (args.length>0) ? Double.valueOf(args[0]) : 0.0;
            double distance = (args.length>1) ? Double.valueOf(args[1]) : 0.0;
            double maxvel   = (args.length>2) ? Double.valueOf(args[2]) : -1.0;
            int    exptime  = (args.length>3) ? Integer.valueOf(args[3]) : 0;
            testCase(velocity, distance, maxvel, exptime);
        } else {
            if (args[0].equals("print"))
                doPrint = true;
            
            testCase( 8.0,   22.8,  -1, 5);     // Simonton's caveat #1
            testCase( 8.0,   22.5,  -1, 5);     // Simonton's caveat #2
            testCase( 8.0, -200.0, 7.0, 39);    // Simonton's caveat #3
            
            testCase( 0.0,    6.0,  -1, 4);     // overshoot
            testCase( 0.0,   10.0,  -1, 6);     // overshoots twice
            testCase( 4.0,    0.0,  -1, 4);     // second, unnecessary overshoot
            testCase(-1.9,   10.0,  -1, 6);     // impossible decel/accel!
        }
    }
    
    public static void testCase(double velocity, double distance, double maxvel, int exptick) {
        
        StringBuffer b = new StringBuffer();
        boolean passed = true;
        
        double newvel  = velocity;
        double newdist = distance;
        double maximum = (maxvel>=0) ? maxvel : Rules.MAX_VELOCITY;
        
        int tick = 0;
        int maxtick = (exptick>0) ? exptick : (int) Math.max(Math.abs(distance), 100);
        
        b.append("Starting velocity=" + velocity + " distance=" + distance + 
                            ((maxvel>=0)? " max=" + maxvel : "") + "\n");
        
        currentCommands.setMaxVelocity(maximum);
        while ((Math.abs(newvel)>0.00001) || (Math.abs(newdist)>0.00001)) {
            // test next velocity change
            //double nextvel = orig_getNewVelocity(newvel, newdist);
            //double nextvel = void_getNewVelocity(newvel, newdist);
            //double nextvel = skil_getNewVelocity(newvel, newdist);
            //double nextvel = posi_getNewVelocity(newvel, newdist);
            double nextvel = vopo_getNewVelocity(newvel, newdist);
            passed &= checkAccel(nextvel, newvel) && checkMax(nextvel, maximum);
            
            // apply changes
            newvel = nextvel;
            newdist -= nextvel;
            tick++;
            b.append("  " + tick + " velocity=" + newvel + " remain=" + newdist + "\n");
            
            // check for infinite loops
            if (tick > 2*maxtick)
                break;
        }
        
        // check time taken
        passed &= (tick-1 <= maxtick);
        
        if (!passed)
            b.append("  FAIL\n");
        
        if (!passed || doPrint)
            System.out.println(b.toString() + "\n");
    }
    
    private static boolean checkAccel(double newvel, double oldvel) {
        double reverse = (oldvel<0) ? -1.0 : 1.0;
        double min = oldvel - reverse*Rules.DECELERATION;
        double max = oldvel + reverse*Rules.ACCELERATION;
        if (oldvel==0)
            min = oldvel - reverse*Rules.ACCELERATION;
        
        if (oldvel<0)
            return (newvel>=max) && (newvel<=min);
        else
            return (newvel<=max) && (newvel>=min);
    }
    private static boolean checkMax(double newvel, double maxvel) {
        return (Math.abs(newvel) <= Math.abs(maxvel));
    }
    
    
    /****************** ORIGINAL FROM ROBOCODE 1.7.1.3 *********************/
	private static double orig_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 -orig_getNewVelocity(-velocity, -distance);
		}

		double newVelocity;

		// Get the speed, which is always positive (because it is a scalar)
		final double speed = Math.abs(velocity); 

		// Check if we are decelerating, i.e. if the velocity is negative.
		// Note that if the speed is too high due to a new max. velocity, we must also decelerate.
		if (velocity < 0 || speed > currentCommands.getMaxVelocity()) {
			// If the velocity is negative, we are decelerating
			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(currentCommands.getMaxVelocity(),
						Math.min(Rules.DECELERATION * decelTime * decelTime + Rules.ACCELERATION * accelTime * accelTime,
						distance));

				// Note: We change the sign here due to the sign check later when returning the result
				velocity *= -1;
			}
		} else {
			// Else, we are not decelerating, but might need to start doing so due to the remaining distance

			// Deceleration time (t) is calculated by: v = a * t => t = v / a
			final double decelTime = speed / Rules.DECELERATION;

			// Deceleration time (d) is calculated by: d = 1/2 a * t^2 + v0 * t + t
			// Adding the extra 't' (in the end) is special for Robocode, and v0 is the starting velocity = 0
			final double decelDist = 0.5 * Rules.DECELERATION * decelTime * decelTime + decelTime;

			// Check if we should start decelerating
			if (distance <= decelDist) {
				// If the distance < max. deceleration distance, we must decelerate so we hit a distance = 0

				// Calculate time left for deceleration to distance = 0
				double time = distance / (decelTime + 1); // 1 is added here due to the extra 't' for Robocode

				// New velocity (v) = a * t, i.e. deceleration * time, but not greater than the current speed

				if (time <= 1) {
					// When there is only one turn left (t <= 1), we set the speed to match the remaining distance
					newVelocity = Math.max(speed - Rules.DECELERATION, distance);
				} else {
					// New velocity (v) = a * t, i.e. deceleration * time
					newVelocity = time * Rules.DECELERATION;

					if (speed < newVelocity) {
						// If the speed is less that the new velocity we just calculated, then use the old speed instead
						newVelocity = speed;
					} else if (speed - newVelocity > Rules.DECELERATION) {
						// The deceleration must not exceed the max. deceleration.
						// Hence, we limit the velocity to the speed minus the max. deceleration.
						newVelocity = speed - Rules.DECELERATION;
					}
				}
			} else {
				// Else, we need to accelerate, but only to max. velocity
				newVelocity = Math.min(speed + Rules.ACCELERATION, 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;
	}
	
	
	/************************* FROM Voidious *******************************/
	private static double void_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 -void_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 = void_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 void_decelDistance(double speed){
            double distance = 0;
            while(speed > 0){
                speed = Math.max(0,speed - Rules.DECELERATION);
                distance += speed;
            }
            return distance;
        }
    
    /**************************** FROM Skilgannon *********************************/
    private static double skil_getNewVelocity(double velocity, double distance) {

             if (distance < 0) 
                return -skil_getNewVelocity(-velocity, -distance);
          	// If the distance is negative, then change it to be positive
          	// and change the sign of the input velocity and the result

             double maxVel = currentCommands.getMaxVelocity();
             if (velocity < 0)
                return Math.min(velocity + Rules.DECELERATION, maxVel);
             //we want to go in the opposite direction, so decelerate   

             else{ 
             //we are going in the direction we want, test what happens if we accelerate

                double accel = Math.min(Rules.ACCELERATION, maxVel - velocity);
                //speed up, but not more than max velocity. decel if maxVel is less than velocity.

                accel = Math.max(accel, -Rules.DECELERATION);
                 //prevent excess deceleration due to bot lowering the maxVel while velocity is high

                if (distance > skil_decelDistance(velocity + accel))
                   return velocity + accel;
                else if(accel != 0 && distance > skil_decelDistance(velocity))
                   return velocity;
                else{
                   if(distance < Rules.DECELERATION 
                   //we'll be able to cover remaining distance in 1 tick and then decel to stop

                   && velocity - distance <= Rules.DECELERATION 
                   //and our velocity is low enough for us to get to that required velocity
                   )
                      return Math.min(distance, maxVel);
                 //choose the velocity to cover all remaining distance        

                   return Math.max(-maxVel, velocity -  Rules.DECELERATION);
                //velocity > 0 and we are close enough, so decelerate. 
                }

             }

          }
        /**
        * Returns the linear distance it would take to decelerate from a given positive velocity
        *
        * @param velocity the positive velocity from which to test
        * @return the linear distance required to decelerate to a standstill
        */
           private static final double skil_decelDistance(double velocity){
             double distance = 0;
             while(velocity > 0){
                distance += velocity;
                velocity = Math.max(0,velocity - Rules.DECELERATION);
             }
             return distance;
          }  
    
    /******************** FROM Positive ********************/
    static double posi_getNewVelocity(double velocityArg, double distanceArg) 
    	{	
    		double velocity;
    		double distance;

    		// Make sure the remaining distance is always positive or zero
    		// (we switch this back later)
    		if(distanceArg<0)
    		{
    			velocity=-velocityArg;
    			distance=-distanceArg;
    		}
    		else
    		{
    			velocity=velocityArg;
    			distance=distanceArg;
    		}

    		// Get the next most positive velocity the robot can reach for next turn
    		double mostPositiveReachableVelocity = posi_VelocityToMostPositiveVelocity(velocity);
    		// Get the next most negative velocity the robot can reach for next turn
    		double mostNegativeReachableVelocity = posi_VelocityToMostNegativeVelocity(velocity);


    		double highestWantedVelocity = Math.min(currentCommands.getMaxVelocity(), posi_maxSpeedToStopInDisp(distance));

    		// The real next velocity is limited by what is actually reachable
    		double nextVelocity = Math.min(mostPositiveReachableVelocity,Math.max(mostNegativeReachableVelocity,highestWantedVelocity ));

    		// Switch return value back if needed
    		if(distanceArg<0)
    			nextVelocity = -nextVelocity;

    		return nextVelocity;
    	}


    	static public double posi_VelocityToMostPositiveVelocity(double velocity)
    	{
    		// Returns the most positive reachable velocity from the
    		// specified velocity in one turn
    		if(velocity>0)
    		{
    			double returnVelocity = velocity+Rules.ACCELERATION;
    			if(returnVelocity>Rules.MAX_VELOCITY)
    				return Rules.MAX_VELOCITY;
    			else
    				return returnVelocity;
    		}
    		else
    		{
    			double returnVelocity = velocity+Rules.DECELERATION;
    			if(returnVelocity>Rules.ACCELERATION)
    				return Rules.ACCELERATION;
    			else
    				return returnVelocity;
    		}
    	}
    	static public double posi_VelocityToMostNegativeVelocity(double velocity)
    	{
    		// Returns the most negative reachable velocity from the
    		// specified velocity in one turn
    		if(velocity<0)
    		{
    			double returnVelocity = velocity-Rules.ACCELERATION;
    			if(returnVelocity<-Rules.MAX_VELOCITY)
    				return -Rules.MAX_VELOCITY;
    			else
    				return returnVelocity;
    		}
    		else
    		{
    			double returnVelocity = velocity-Rules.DECELERATION;
    			if(returnVelocity<-Rules.ACCELERATION)
    				return -Rules.ACCELERATION;
    			else
    				return returnVelocity;
    		}
    	}

    	static private final double[] dispStopArray = 
    		{0.0000,1.0000,2.0000,2.5000,3.0000,
    		3.5000,4.0000,4.3333,4.6666,5.0000,
    		5.3333,5.6666,6.0000,6.2500,6.5000,
    		6.7500,7.0000,7.2500,7.5000,7.7500};
    	static public double posi_maxSpeedToStopInDisp(double displacement)
    	{
    		// Returns the biggest velocity the robot could go to this turn,
    		// still being able to stop without overshooting. (Or if 
    		// remaining displacement is less than 2, returns that)
                    // This routine could be improved to match up with robocode's
                    // older velocity selecting rules.
    		if(displacement>=0)
    		{
    			if(displacement>=20)
    				return 8.0;
    			else if(displacement<=2)
    				return displacement;
    			else
    				return dispStopArray[(int)Math.floor(displacement)];
    		}
    		else
    		{
    			return 0;
    		}
    	}
    
    
    /****************** FROM Voidious + Positive ***********************/
    public static double vopo_getNewVelocity(double velocity, double distance) {
        	 if(distance<0)
        	  return -vopo_getNewVelocity(-velocity,-distance);
        	  double highestVelocity = vopo_getMaxVelocity(distance); // highest velocity without overshooting
        	  double wantedVelocity = Math.min(highestVelocity,8.0);
        	      // the actually wanted velocity by the robot is the highest possible,
        	      // limited by what the robot set by the setMaxVelocity command
        	  return vopo_getClosestReachableVelocityToVelocity(velocity, wantedVelocity);
        	      // return whatever is closest to that velocity
    }
    
    public static double vopo_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 -vopo_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;
      }
     }
    } 

    public static double vopo_getMaxVelocity(double distance)
    {
        long decelTime = vopo_decelTime(distance);
        double decelDist = (decelTime / 2.0) * (decelTime-1) // sum of 0..(decelTime-1)
            * Rules.DECELERATION;

        return ((decelTime - 1) * Rules.DECELERATION) +
            ((distance - decelDist) / decelTime);
    }

    public static long vopo_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);
    }

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

}

And a support class for setting the max velocity:

import robocode.Rules;

public class Commands {
    private static double maxVelocity = Rules.MAX_VELOCITY;

    public static double getMaxVelocity() { return maxVelocity; }
    public static void setMaxVelocity(double maxVel) { maxVelocity = maxVel; }
}