Math: A good "Travel-To-Target" strategy on a universe scale level

#1

Reaching out to those who work on procedural universe generation, you math geniuses (or maybe even directly to the I-Novae magicians :wink: ), I need some advice for my prototype to implement a robust “Travel-To-Target” strategy. No matter how simple it is.

I found some time to continue on my custom double implementation of Unity3D running as a sandbox within Unity3D, and utilizing Floating Point Projection to render large “double”-distances within Unity3D, I’ve finished my custom ransform-Class Extension that allows me to define positions on a Universe scale on a detailed sub-meter level. To do so each gameobject’s Transform stores a tuple with a “meter” and a “lightyear” value (both double types). You could image the lightyear coodinate of the tupel (e.g. 0,0,5) defines a “box” for the meter tupel wherein the meter coordinate is utilized from -9460730472580800.0d/2 (half a lightyear) to +9460730472580800.0d/2 (half a lightyear) range. That allows positioning on a precise submeter level (except for the very outer meter-tupel bounds where a bit of precision is lost, so to say while crossing border of a lightyear-“box” to the next one).

After implementing the instatiation of mesh-debug-prototypes of asteroids (that instanciate across a few lightseconds distances) and stars (that instanciate on a view multiple of ~1500 lightyears) I’d now like to add a simple travel mechanism for testing and to implement instanciation on a galaxy level.

However traveling turns out to be more complex than I thought, eventually one of you mathematicians can help :slight_smile: My problem is that since I work with very large numbers for distances and velocity, I havent found a good way that prevents overshooting the target position or stopping too early, one that works with very different distances.

To find a initial working solution, for the ease of things at the begining the observer must have zero velocity.
I know the full distance from start to target once traveling is initiated.
For each physics-update in fixedupdate I know the remaining distance to the target as well as the distance already traveled, as well as the current velocity.

My current strategy is to split the overall travel-distance into phases, so an

  1. Acceleration Phase
  2. Travel Phase (constant velocity) and
  3. Deceleration phase.

Also for the ease of things I apply the same acceleration value in Phase 1) as well as for deceleration in Phase 3). Due to that I thought I could simply split the overall distance into 1/3 for each phase, calculate the velocity in Phase 2) which could e.g. be the velocity required to travel the distance in ~30 seconds, and lineary increase or decrease in Phase 1) and 3). Later my idea was to use the two point formula to check how much percentage of the distance of each phase is traveled and to smooth the acceleration using a sin.

However the condition changing between phases seems to be an issue, as the speed during traveling is at so distances that hight that even a moment too late makes the observer overshoot while too early makes the observer to stop too early. A typical travel speed to move to one of the next asteroids is approximately ~70Mm/s. So if the timing is not absolutely exact I miss the target during deceleration. So this static phase-approach might become a deadend.

So I start to think that I need a more dynamic approach, not one that simply works on the overall distance being split. But maybe one that more relies on the remaining distance to the target.

What I’ve tried also was to

  1. Add a fourth phase 4) Reach_Target that would differently try to reach the desired position once I overshooted or stopped too early. In fact that was the only approach where I managed to reach the target position, however I don’t like that approach as it feels like a workaround.
  2. Calculate the predicted brake-distance to move from Phase 2) (travel) to Phase 3) (decelerate). However again the problem with the condition occured leading to overshoot or stop too early.
  3. Use the overall- and the current distance and calculate the related value between 0 and 2 using the two point formula, and throw the result into a sin function which then defines a percentage amount of a maximum velocity - and completely skip phases. Even though the velocity was smoothed nicely I didnt reach the target, and the time traveling takes became hard to control. :expressionless:

Does anyone of you have an idea what could work better? Any advice is very much appreciated!
I feel I need a first simple robust strategy before dealing with more complex situations (shorter or very very long distances, or non-zero velocity during travel initiation).

PS: Glad to add a video of the different approaches once I get the recording tool back to work
PPS: All hands down :astonished: to those who manage to implement these problems with much more dynamics like in games like I-Novae or even real world situations (autocontrols in automotives)…

9 Likes
#2

Wow, you are still working on this.

I haven’t dealt with problems that you are facing, but from a quick read the first solution that comes to me is to put this system on rails. Because you are dealing with such extreme distances and velocities, you are loosing little fractions all over the place due to timing.

I would calculate where the ship is supposed to be at some humanly unnoticeable fraction of time, like 250ms ahead and then lerp to that position instead of applying velocity directly. It’s impossible to overshoot when lerping in 0-1 range and even if you miscalculate the position a little you just add that difference to the next lerp point, it shouldn’t be noticeable. It’s the equivalent of calculating orbits and following them instead of pushing planets around with forces.

9 Likes
#3

Are there any additional forces acting on your vehicle during travel like gravity from nearby stars? If so, constant velocity phase won’t be constant.

I think it might be beneficial to look at the problem from a controls perspective. You have position, a rate, and the ability to change that rate(acceleration, which is what you’re controlling). Your error that you’re controlling is the distance from A to B(PosDesired-PosCurrent). Essentially you want a PID controller or two. Output of Pos controller inputs into a velocity controller, and outputs of velocity controller are changes in accelerations. Currently, you’re only using a proportional(linear) velocity controller. You have some P value, and I and D are zero.

The sin example you used could be described is having a bit of D because it smooths it out, but you what you want is some I to “look forward” to see how you might want to change accelerations in the future. Could also look into a feed-forward term as well to smooth out the inputs further and prevent overshoots.

2 Likes
#4

His current solution has nothing to do with a controller/regulator. He only thought about using “remaining distance” but did only use it to smooth a fixed, predetermined acceleration. Without feedback it is no controller/regulator.

Both cybercritic or skyentists solutions would probably work for such a problem. Tuning PIDs would be required for the PID solution but that would be one/two tune per different ship characteristic either manually or with an algorithm. Another more exotic controller/regulator, besides PID could be used of course, I don’t have much experience with those though.

As I interpreted Joergs solution he tries to plan out the manoeuvre ahead of time. Problem there is, the more variable get introduced into the environment, the more things need to be accounted for in the preplaning phase. So if you plan to have all kinds of influences, like gravities from different planets and stars, different drag regions in space or similar things like that you would need to account for all this into your “Travel-To-Target” algorithm. On top of that you would need to remove that error you currently have. Have perfect control over the timing and achieve repeatable results. Which I think could be possible … but not enjoyable because it probably has a lot to do with inherent discreteness of the underlying execution of the simulation, the fixedupdate if I understood correctly. A given course correction may fall between two updates, probably resulting in the erro. Something you should not need to worry about when designing something like your are right now.

#5

Remaining distance to target is positional feedback which is why I suggesting thinking of it like a controls problem if he were to take that route. I assumed(maybe incorrectly) the end goal was to automate NPCs on these trajectories(why else would you want them) and formulating it like this may save headaches down the road especially in the case of added perturbations.

The measured output in this case is current position and desired position is your reference. The output of the position controller would be a change in velocity, which you would then enact through a acceleration velocity controller outputting accelerations.

The benefit to treating it in this way is that you never really have to pre-compute anything which may or may not be what Joerg wants. You just set the destination and the controller finds a way to get from A->B assuming everything is tuned reasonably. Though precomputing the trajectory and having a controller follow the trajectory would probably be the most “realistic” way.

It’s also possible to add in cost functions to minimize straying into gravity wells or what have you in the future, though I haven’t messed with cost functions at all so I can’t offer advice there.

I just wanted to add an alternative idea mostly because I’m a controller kick in life right now and find it to be an interesting approach :slight_smile:

6 Likes
#6

How often do your physics update? Since the update assumes fixed points in time, high speeds might lead to a problem, where on one frame breaking means you wont be able to reach the target, whereas breaking starting the next frame will make you overshoot. I’d say predict if your speed n updates ahead will lead to overshoot.

Btw, wouldn’t it be faster to get rid of the flight phase and make it purely acceleration and deceleration?

3 Likes