[Home]DeadlineGoto

Robo Home | Changes | Preferences | AllPages

Showing revision 15

Calling All Math Wizards

I have a problem to solve! Given a speed (s), a distance to travel (d), and the number of ticks you have to get there (t), what speed should you travel such that you will arrive at that distance at the lowest speed possible?

Here's why I ask. I want to plot a course to a given point on the battlefield, and I want to arrive there at the time a wave crashes over it, at the latest. So I have a deadline. I also want to get there as quickly as possible, and just hang out for a while if there's time. If necessary, though, I'll arrive at full speed just as the wave crashes.

I want to boil the problem down to a straight line. That is, I'll worry about turning toward that point with a different algorithm. That makes this problem strictly linear.

Here's what I have so far (mostly due to Voidious' help). Consider a function m(s, t) that gives you the minimum distance you can possibly travel. That is, the distance you would travel if you hit the brakes hard. This problem, then can be stated in terms of m. You wan to pick an s such next tick m(s, t)=d. That is, so that next tick you can hit the brakes as hard as possible and still make your deadline. So, we want to solve this equation for s:

 m(s, t-1)=d-s

Note that this requires figuring out what m is, exactly! So, who's up to the challenge??

-- Simonton


Math wizards, enter your comments here

Hmm ... m(s, t) should just be the sum from x=1 to t of s-2x. Who remembers / is learning how to solve simple summations? But this only works as long as t <= s/2. Then you have to start using sum of s-x. Or can that be handled easily with special cases? -- Simonton

using formulas: 
sum of i from 1 to n = (n/2)(n + 1)
sum of k from 1 to n = kn, where k is a constant

sum of s - 2x from 1 to t
= (sum of s from 1 to t) - 2*(sum of x from 1 to t)
= ts - 2*(t/2)(t + 1)
= ts - t*t - t
therefore 
d - s = (t - 1)s - (t - 1)^2 - (t - 1)
d - s = ts - s - t*t + 2t - 1 - t + 1
d = -t*t + t + st 
(d + t*t - t)/t = s
-- Skilgannon

I heard from Chase-san who heard from his software that the sum of x=1 to t of s-2x is -t^2+s*t-t. Let's try some scenarios to see if that's all we needed. -- Simonton

Chase-san again saves the day by avoiding all my mistake-prone algebra using his super-solver (from what I hear [Maxima] is pretty cool software). d-s=-(t-1)^2+s*(t-1)-(t-1) solved for s is s=(t*t-t+d)/t. Now to try out this function: -- Simonton

    public double getSpeed(double curSpeed, double distance, long time) {
        assert distance >= 0;
        assert time > 0;
        double min = Math.max(curSpeed-2, 0);
        double max = Math.min(curSpeed+(curSpeed<0?2:1), 8);
        double ideal = (time*time-time+distance)/time;
        return Math.min(Math.max(ideal, min), max);
    }

Ah, this is going to work well for the case that you are going to reach your deadline just on time (according to my experiments with it in a spreadsheet). But it needs a separate case for when you'll have time to spare, to sit idle at the destination until the deadline passes. I guess that will be tomorrow's project (unless someone graciously beats me to it). -- Simonton

I notice this assumes your moving in a straight line to the destination, what if your arcing (as in many surfers, and/or when wall-smoothing)? --Chase-san

I did some tests limiting the speed of my travel, and I concluded that it makes me very vulnerable to velocity segmentation. It might have just been bugs in my system, but keep that in mind =) -- Skilgannon

This can, I think, be simplified to s = d/t + t - 1 if you wanted to... --Starrynte


Robo Home | Changes | Preferences | AllPages
Edit revision 15 of this page | View other revisions | View current revision
Edited May 1, 2008 2:42 EST by Starrynte (diff)
Search: