Jump to content
  • Advertisement
Sign in to follow this  
Jotaf

Ooops, forgot the subject: realistic thrusters for a spaceship in 2D

This topic is 4826 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hello! I know this might be quite simple, but I've been banging my head against the wall for not figuring it out for almost a week. I hope you guys can help! What I'm trying to do can be reduced to the problem of controling a spaceship in a 2D environment. I'm trying to make it so that the ship can move towards a stationary target, given some initial velocity. The ship can rotate (at a constant rate for now), to make its main thrusters face the direction it wants, and of course engage the main thrusters, to accelerate or deccelerate in the direction it's facing. I've figured out some simple equations so that after the initial acceleration, it knows at what point it should start deccelerating (it's not supposed to crash into the target!). Anyways, the big problem here is that this does not take into account the initial velocity. This produces some really bad aiming at the target, and sometimes extremely weird behaviour. The first thing that comes to mind is to fully stop the ship and only then move towards the target; but this is terribly inefficient and doesn't look very good :) I think I came up with a solution, but it's not 100% figured out. We have a velocity vector and a vector that points towards the target. We need a vector with the desired direction of the thrusters (acceleration). Given an -arbitrary- set of 2 axis (X & Y), a vector can be broken down in 2 components (one part along the X and another along the Y). So if you align the arbitrary X axis with the vector that points towards the target, it's possible to find the component of the velocity vector along the (orthogonal) Y axis. This is the vector that must be countered using the thrusters -- if it's null, then by definition the remaining of the velocity vector is either pointing directly at the target or away from it: so now all we have to do is move directly towards the target. Do you think this is a good idea? I can explain it better if it was not clear enough. I can point out a possible flaw: by the time the ship has rotated and engaged the thrusters to counter the Y component of the velocity, this could have changed a lot. I'm hoping that the system will still converge to the solution anyway. BTW, if I'm going to try this, can someone please remind me of how do you figure out the vector I was talking about? Bad memories from 2 months of exams still haunt me so I'm trying to avoid touching my math books :P I would also like to know your opinion about this problem and how to solve it. Thanks! [Edited by - Jotaf on August 22, 2005 2:53:20 PM]

Share this post


Link to post
Share on other sites
Advertisement
Hi Jotaf,

I'm sorry but I don't have a complete solution for you. It's an interesting problem and I don't think it is entirely trivial.

I can, perhaps, refresh you exam-wearied brain a little [smile]

Your idea about decomposing a vector is correct. If you have two, orthogonal unit vectors u and v then you can always write a 2D vector, p, as

p = (p.u)u + (p.v)v

where x.y is the dot product of two vectors x and y. The dot product projects the p vector along the u or v vectors. But that's just a number, so we scale the appropriate unit vector by that number. It is easy to check from here that this decomposition of p is equivalent to the original vector.


I'll think some more about the big problem you're trying to solve. In the meantime, maybe someone else can suggest a strategy.


-Josh





Share this post


Link to post
Share on other sites
Do the ships have a maximum velocity? If not, to get there the fastest you'd want to accelerate continuously for the first half of the trip, then slam on the brakes for the entire second half. You'd be going way too fast to handle anything along the way though :P

Okay, the simplest way I can think of is a two-step approach. First, eliminate any velocity perpendicular to the target vector, then simply solve the 1D problem. For step one you get the perpendicular velocity vp, then just thrust in the opposite direction until vp is zero:

u = Unit vector pointing to target.
v = Velocity.
vp = v - dot(u,v)*u

Is that good enough?

Share this post


Link to post
Share on other sites
Jjd, I appreciate your clarification. Now that I remember it is obvious, thanks. Have you thought a bit more about this problem? Captainmikey goes one step further, that's exactly what I was talking about. Your two-step approach is the same as the one I described, and the code is elegantly simple.

Now, if it didn't take some time to rotate and engage the thrusters until the perpendicular component of the velocity is nullified, it would work perfectly (I know because I tested it), but in the real application it doesn't work that well. Maybe it's my mistake, I'll need some time to go over the code. But anyways if you think about it, as the ship moves, this component is bound to vary (in most cases, increase), because the unit vector that points from the ship to the target will vary as it moves.

Implementing this 2-step method in my specific application is a bit hard, because of the nature of the application: the target is the cursor, which is controled by the user, so it can change at any time. So everything has to be calculated on a per-frame basis, you can't keep any information like which step you're in from one frame to the other because the target's position might have changed.

This is also why it's impossible to use a simplistic approach to the problem of accelerating and then deccelerating. If the target changes its position all the time, you can't really define the "middle point" when the ship should switch from acceleration to decceleration. I also slapped in a maximum velocity, which complicates matters a lot more. But don't be baffled by all of this, I already solved this problem! The real issue is discussed in the earlier paragraphs.

Thanks for your help!

Share this post


Link to post
Share on other sites
I've thought about it a little. I was assuming that you wanted a smoother (possibly optimal) method rather than the 2-step method.

The way I would like to solve this problem is to find the best step towards some target given the crafts position and velocity, but only the best first step. This can be used to move from the ships initial position to a new position, and then you can simply apply the method again using the new position as the initial condition. If it's possible to solve the problem like this, it would fit perfectly with your application as well since each step taken would be the best step towards wherever the target currently is.

However, it's tricky [smile]

-Josh

Share this post


Link to post
Share on other sites
I think I know exactly the behavior you want, so I hope I'll save you some trouble. I've dealt with this problem before, and it's very hard the way you're approaching it.

You are constraining yourself too much at the beginning without an initial solution. You've said "I'm limiting turn speed" and "I can only use a thruster" (i.e. only apply force and directly affect the 2nd derivative). If you toss away these requirements (for the moment), your solution is simpler and looks better.

Here's some code to start.

// use a damped spring to move v0 towards target given a current velocity,
// time over which the spring would cover 90% of the distance from rest;
// and dt, the change in time.

template<typename T>
inline void damp_spring(T& v0, const T& target, T& vel, float time_90, float dt)
{
const float c0 = dt * 3.75f / time_90;

if(c0 >= 1.0f)
{
// here, constant is too small, spring too stiff. so go the whole way to prevent oscillation.
v0 = target;
vel = T(0.0f);
return;
}

const T delta = target - v0;
const T force = delta - 2.0f * vel;

v0 += vel * c0;

vel += force * c0;
}



Just pass in ship's current position, desired position, current velocity (note that current position and velocity are modified within the function, so leave them unchanged until you call the function again!) You also pass in time_90 as the amount of time until the ship reaches near the target, maybe 1 second or something, and the current time-step for the frame.

It's also templated so you just need to specialize for whatever your 2d point structure is (Point2D, vec2, etc) and overload the operators.

The idea is that given the current velocity and distance-to-target, it works out an equation so that it applies the correct force, based on the amount of time to reach the target... however, as you said, it doesn't want to hit the target, it just wants to come to a gradual stop there. The nice thing about this is that distance is totally irrelevent, the only constraint is time.

Anyway, it has some nice properties. It's completely stable for any inputs, target can change drastically from one frame to the next, it doesn't oscillate, and it's smooth across all derivatives and it's nicely compact.

Share this post


Link to post
Share on other sites
Oooh, I see what you're saying. Since the target vector is constantly changing it's a much more complex problem o_O I briefly tried thinking of things in terms of "motion curves". Thrusting perpendicular to your velocity would result in a "medium" curve, with constant speed. Thrusting with an angle less than 90 degrees (between facing and velocity) would result in a wider (widening?) curve with increasing speed. More than 90 would give a tightening curve but slow you down. But then there's the latency of having to change orientation...

I think you're looking at an AI problem here (or a simplification like ajas95 posted), because the mathematical approach seems horrifying :D I'd be interested to hear about what you come up with.

Share this post


Link to post
Share on other sites
Well, there is a mathematical solution to a similar problem. Your problem sounds like a classic problem in differential game theory called the "homocidal chauffeur problem". The spaceship is the chauffeur in a car trying to run over a person in a parking lot. The twist in your problem is that you want the spaceship to stop over the target. So simply chasing down the target is not enough.

I haven't had time to get much deeper into this problem but I'll let you know if I figure anything out. It's an interesting problem... [smile]


-Josh

Share this post


Link to post
Share on other sites
It works!! WOOHOO!!!

Damn, I never thought this would be so much work!! I'm sorry for not replying earlier, but I was on holydays (road trip ;) ). Anyways I had a couple of days to work on this now and after struggling with lots of errors related to floating point inprecisions and code with angles that got out of bounds etc, I *finally* was able to apply all the theory and see it work!

In a nutshell: What the ship does first is check if it's moving towards the target or away from it.
If it's moving away, no component of the velocity is useful for its movement, so it tries to counter the current velocity (that is, stop; this was the only bit that wasn't referenced in this discussion).
If a component of the velocity is indeed useful for the movement, it tries to counter the remaining component of the velocity (perpendicular velocity).
After one of these 2 actions, all it needs to do is move directly towards the target.

Now, it is possible that one or 2 bugs have sliped by my thorough testing, but for now it seems stable.


Quote:
Original post by jjd
...If it's possible to solve the problem like this, it would fit perfectly with your application as well since each step taken would be the best step towards wherever the target currently is.
(...)
Well, there is a mathematical solution to a similar problem. Your problem sounds like a classic problem in differential game theory called the "homocidal chauffeur problem".


You were right, I didn't even try to implement variables that are persistent from frame to frame - it's all calculated on a "best first step" basis.
Although there are 2 distinguishable "phases" to the movement (countering the velocity that doesn't contribute to the desired movement, and then moving towards the target), as suggested, the movement phase is calculated for each frame only, independently.

As to the "homocidal chauffeur problem", thanks for the reference, it seems very interesting. I'll check it out, but I'll probably not alter the current code to use the solution they found for that problem.


Quote:
Original post by ajas95
I think I know exactly the behavior you want, so I hope I'll save you some trouble. I've dealt with this problem before, and it's very hard the way you're approaching it.


You bet it's hard! :P

Your method seems great, the only downside is that it skips through the part where the thrusters are propelling the aircraft - it deals with the velocity directly.
Part of the objective of this was purely cosmetic, as I wanted to show the thrusters working to propel the aircraft, rotate, etc, in a realistic fashion.
The other part was for the challenge of programming something that in theory *would* work *if this ship was actually sent to space*! Thanks for the suggestion though, if this method ends up not being viable, I'll give yours a try.


Quote:
Original post by captainmikey
Oooh, I see what you're saying. Since the target vector is constantly changing it's a much more complex problem o_O I briefly tried thinking of things in terms of "motion curves". Thrusting perpendicular to your velocity would result in a "medium" curve, with constant speed. Thrusting with an angle less than 90 degrees (between facing and velocity) would result in a wider (widening?) curve with increasing speed. More than 90 would give a tightening curve but slow you down. But then there's the latency of having to change orientation...


Yes, that was my first thought too :)
Then I started considering how to deal with latency, and it hit me that it would probably take some mad systems of equations, because all the variables are interdependent... But this is obviously the "academic" way of doing things, and I would love to see a solution like this.


Ok guys, thanks! Any more thoughts? I'll post again if there's any development.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

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

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!