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
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
![[Home]](/images/RoboWiki.png)
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
I just implemented something like this in DrussGT. If I need to get to a point, but I'm going to be sitting still for a while after getting there, rather sit still here for as long as possible so the enemy doesn't know where I'm headed. Although there may be some subtle changes in the movement all around, it shouldn't actually affect any of the points where I cross the waves, only what the enemy sees as I'm getting there. I don't expect it to do much, but you never know. -- Skilgannon
Actually, the new variety of TrueSurfing that I'm working with lately would do something similar to this. Due to the way the algorithm works (by simply evaluating which movement option leaves the lowest reachable danger open still), it would also be "lazy" and would move as late as possible to the new location. Of course, in actuality, I don't think this "lazy" effect does much, because I count all waves and it's rare for the lowest reachable danger of EVERY wave to still be reachable for all movement options. It may not be DeadlineGoto, but it has an equivalent property in TrueSurf-style. -- Rednaxela
Wouldn't this only be the case if you made staying still the priority, so if all are equal, staying still is the option that gets followed? Otherwise you could make it so it always moves towards GF 1 (or -1) until a 'best' option presents itself. -- Skilgannon
Well, yes, it does depend on implementation but in my implementation I do have it choose the option of staying still if all options are equal. I did at one point consider breaking such ties by evaluating which one has the lowest total (total as opposed to lowest danger point) danger, but then decided that's not worth it and that generally staying still would not be a bad thing because as you note it doesn't give the enemy much information about what I'll do next. -- Rednaxela