User talk:Positive/Optimal Velocity

Your version passes all of my tests (so far) except that it doesn't take into account the maximum velocity set by the bot. Nice catch on the updateMovement() routine, that should get fixed too (my tests assume that behaviour already). --Darkcanuck 20:21, 15 July 2009 (UTC)

Great! Please replace 8.0 in the getNewVelocity function with currentCommands.getMaxVelocity(), and it should work I believe (I temporarily set it to 8.0, because I am not using the currentCommands class). :) --Positive 20:26, 15 July 2009 (UTC)

ok, that fixed it. Nice work! --Darkcanuck 20:33, 15 July 2009 (UTC)

I just noticed that this does allow some free acceleration, although it's capped at 1. Replacing this with the time-based calc in Voidious' second version should work. --Darkcanuck 20:41, 15 July 2009 (UTC)

I did, unfortunately, find one small problem with the code: decelTime(Double.POSITIVE_INFINITY). It takes a lot of time to process. So i guess at arguments around > 1000 it could simply return Rules.MAXVELOCITY (or a more elegant solution). Personally, I think the free acceleration provides no problem, and people not liking that particular change was the start of the discussion. --Positive 20:52, 15 July 2009 (UTC)

Yeah, I was going to suggest that we add an "if (distance > SOME_MAX_DISTANCE)", just accelerate freely, for sake of execution speed. That would be 20 if you assume max velocity is 8, but Fnl might prefer to have it calculated based on a MAX_VELOCITY constant...

The free acceleration is really a separate issue from the optimal velocity. Originally, you could go from -0.1 to 1.9, so even capping velocity at 1.0 would be a change. I sort of feel like if we're going to change it, we should do it the way Fnl envisioned, which is how I had it in that "Version 2". But that's an easy change, whatever is decided.

Oh, and nice work. =) This solution definitely feels right.

--Voidious 21:02, 15 July 2009 (UTC)

You're welcome. :) Hmm, I guess you are right. Fnl's change is more logical. I remember when I started with studying the movement rules I had expected something more like what he suggested. However, staying able to easily move at integer (whole) speeds is nice too. (I guess I'm a little biased, because Portia uses integer speed lookup tables). By the way, if it can't be >=20, I'm thinking something like "static private final double MAX_CALC_DISTANCE = Rules.MAXVELOCITY + Rules.MAXVELOCITY/Rules.DECELERATION * Rules.MAXVELOCITY/2;". --Positive 21:44, 15 July 2009 (UTC)

Hijack =)

I don't mean to hijack your work, but here's what I feel is a much simpler version of both your and Voidious's ideas =) Or at least, I find it easier to read:

         private static double getNewVelocity(double velocity, double distance) {
      
         if (distance < 0) 
            return -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
      
         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 +  Rules.DECELERATION));
      }
       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);
      }

--Skilgannon 11:20, 16 July 2009 (UTC)

Very nice. Your formula replacing the decelTime function is voodoo to me right now, but I've thrown enough numbers at it that I trust it works. =) I'd like to test this (I don't trust my own logic that it's equivalent :-P), then switch to this code, and also implement the new decel-through-zero rules. Also, I added one set of parens in there for clarity, hope you don't mind. --Voidious 13:47, 16 July 2009 (UTC)

Nice simplification. It passes all my tests, except for a new one I just added: starting vel=0, distance=+INF (returns NaN). --Darkcanuck 14:36, 16 July 2009 (UTC)

Ok, I fixed the infinity case, although I hate adding more if statements. As an explanation for the voodoo in there read on: =)

From the old decelTime method: distance <= (square(x) + x) / 2) * Rules.DECELERATION
lets solve for the case where they're equal, ie.
distance = (square(x) + x) / 2) * Rules.DECELERATION
distance/Rules.DECELERATION*2 = x*x + x
0 = x^2 + x - distance/Rules.DECELERATION*2
which is in the form 0 = ax^2 + bx + c
so we can use the quadratic formula x = (-b +-sqrt(b^2 - 4*a*c))/(2*a)
which gives us:
x = (-1 +-sqrt(1 - 4*(1)*(-distance/Rules.DECELERATION*2)))/2
because we need a positive answer (time) we need the + of the +-sqrt
so, simplified: x = (sqrt(4*2/Rules.DECELERATION*distance + 1) - 1)/2
and then take the ceil, because any partial tick used means a whole tick got used.

And I really need to start packing for my holiday to Mozambique... --Skilgannon 15:09, 16 July 2009 (UTC)

Thanks for the explanation, it's clear now. Enjoy your holiday. =) --Voidious 15:17, 16 July 2009 (UTC)

Okay, I finally analyzed your code. Great work! Although your version is not the same as the one I posted. Your version's getNewVelocity(-0.1,1000000000) == 1.9 while the old one == 1.0. So considering Fnl used your version, the alpha-2 version is exactly like the 1.6.1.4 version except for the "bugs". :)

Here's the modified function that makes them equal (for if it's decided we want that):

    private static double getNewVelocity(double velocity, double distance) {
        
        if (distance < 0) 
           return -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
     
        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
        // changed here:
        return Math.min(Rules.ACCELERATION,
        	Math.min(goalVel, velocity + Rules.DECELERATION));
        // we don't need a Math.max, because the goalVel can never
        // be below zero (because distance is always positive)
     }

--Positive 01:00, 19 July 2009 (UTC)

Oh my! I didn't realize "getNewVelocity(-0.1,1000000000) == 1.9" about the version in Alpha2 before... to me that seems like a really really bad thing, because of this scenario:

getNewVelocity(-1.0,1000000000) == 1.0
getNewVelocity(-0.5,1000000000) == 1.5
getNewVelocity(-0.1,1000000000) == 1.9
getNewVelocity(0.0,1000000000) == 1.0
getNewVelocity(0.5,1000000000) == 1.5
getNewVelocity(0.9,1000000000) == 1.9

The sudden jump in output between -0.1 and 0.0 doesn't make any intuitive sense at all I think. It really should be limited to 1.0 like in the old code, unless more accurate handling is done (as in Alpha3) --Rednaxela 05:03, 20 July 2009 (UTC)

Actually, Alpha2-style is also how the old code does it. You can go from -0.1 to 1.9 in Robocode 1.6.1.4. Positive, I noticed Skilgannon changed that, but I think the old way and Fnl's new way were the two main choices up for consideration. --Voidious 05:12, 20 July 2009 (UTC)