Jump to content
  • Advertisement
Eternal

Motion-planning for spaceships with physics

Recommended Posts

Hi, I am currently working on a 2d strategy game/simulation involving spaceships moving around in a solar system and have hit a problem I'm not sure how to solve.

The basic idea is, I have a spaceship at some position and want to move to some other position, the ship can only accelerate along a fixed axis, with a fixed magnitude of acceleration, change of acceleration and orientation of the ship can be treated as instant. So far I've only dealt with the situation where the initial (and final) velocities were zero. Accelerate towards the target for half the distance, turn around, brake. Now I've been trying to extend this to ships already moving, without much success. I figured that I could still use the same approach of splitting the movement into two segments, first accelerating (or aligning the velocity with the vector towards the target) and then braking, as before, but I can't solve the resulting equations and I'm hoping one of you can help me or tell me that I'm stuck with numerical methods.

The equations I have are:

P=v0*t1+0.5*a1*t1^2+v1*t2+0.5*a2*t2^2 //We want to end up at our target

v0+a1*t1+a2*t2 =(0,0) //and standing still

with P being the target position, v0 initial velocity,a1, a2 and t1,t2 the direction vectors and durations of the acceleration burns and finally

v1 = v0+a1*t1 the velocity after the first burn.

And for example we can now eliminate a2 = normalize(-v1) and t2 = ||v1||, to leave only a1 and t1 as unknowns, but the result is still a mess that I can't solve. Does anyone have a suggestion?

Share this post


Link to post
Share on other sites
Advertisement
Posted (edited)

Don't quite understand what all your variables mean, so I can't comment much on your equations. Never tried to solve your problem before, but I'd say, the fastest solution is to constantly accelerate until you are at the 'middle', and then constantly decelerate until you reach the end position.

If you draw a graph with x the positiion, and y the speed forward in time from the startposition, and you draw a graph from the end position back in time, with x the position, and y the speed, then I think both graphs have to cross somewhere. At exactly that point you switch from acceleration to deceleration.

Likely you can compute it symbolically (there may exist special solve methods for quadratic functions), but with a computer nearby, it works just as well to search for the crossing point by bisection.

Edited by Alberth

Share this post


Link to post
Share on other sites

Not sure on a nice math solution, planning courses in space in complex (even more so once you add gravity, which you havn't here).

One quick solution I have used for vehicles in various contexts is to compute a "stopping distance" and use that in my vehicle AI update. This is slightly different to what you have in that it is not "planned", it would simply keep accelerating (in my case I had a velocity cap so not tried with such high speeds) until an update where "stopping_distance >= remaining_distance".33

Another hack approach, is to just have a guess of what the flight plan could be (lets say start on your accelerate half way, then flip and burn) then simulate it and see how far it ends up being off. Then add some more acceleration in that direction (change angle/thrust veector a bit if off left/right, flip and burn sooner/later if distance is off) to the flight plan to try and correct the error, until it has one that is good enough.

Another work around would be to try and burn off any "wrong" velocity early in the path so that it is heading in exactly the right direction, although certainly a less optimal plan, and then you have a simpler flip and burn in a single dimension.

Share this post


Link to post
Share on other sites

Okay, time for an update, took me a while to get back to this and make some progress.
Thanks for your suggestions, even if my description of the problem wasn't the clearest.

So here's a picture showing some examples of the trajectories I am trying to get.
Starting positions at the origin, initial velocities (-1,-1) or (0,-2) and the dots on the graphs showing where the acceleration direction changes:

sample_trajectories.thumb.png.07d0e146425309fd7070879395bc59fb.png

But finding that point to switch acceleration (or the acceleration directions / times themselves) seems more difficult than I first thought.
As for progress: I've given up on finding an explicit solution, even if it exists, as @SyncViews noted, it would probably be impossible to adapt it to any more complicated problems.
Instead I've implemented a numerical solver using Newton's method, so basically the not-so-hacky version of starting with an initial guess and then adjusting depending on how far off the result was.
So far, after fixing the initial bugs, this seems to work well, although I'm worried about stability issues. Time to write some more tests and then fix the problems if they actually exists...

Now the next step is to make this a bit more flexible... Intercepting moving targets doesn't sound too complicated, I just hope I'm not totally wrong about that again! And then there's relaxing the "always accelerating" constraint, having a speed vs fuel use trade-off would be nice, but I'm not sure how to approach that yet.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!