Darkcanuck/VelocityTest
< Darkcanuck
Jump to navigation
Jump to search
Revision as of 21:18, 15 July 2009 by Darkcanuck (talk | contribs) (updated for expanded testing, includes versions tested so far)
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; }
}
