Jump to content
  • Advertisement
Sign in to follow this  
xynapse

Simple 2D Plane Trajectory with Bezier Curve

This topic is 2530 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, and Happy New Year !

Let me begin with the strict facts instead of writing the whole scenario here.

zdj.jpeg



This is what i have:

- A plane in 2D Space (X,Y)
- A destination this plane has to fly to in 2D space (X,Y)
- A bezier curve class that generates the bezier from 4 points (A,B,C,D)


This is what i need to do:

- When user clicks on the space in X', Y' i need to generate a bezier curve
for this plane to fly there.


These are some assumptions:

- It is known that plane can't rotate in one place, it has to make some minimal turn
- It is known that when destination is in front of the plane it doesn't make any turn

- Bezier curve has to be calculated from 4 points where
- point A = actual plane position
- point B = actual plane position + actual plane direction * 2 (so it goes forward a bit ? )
- point C = needs to be calculated
- point D = plane destination


Here are few of those scenarios drawed:

0.jpg

1.jpg




2.jpg


Question:

- How do i calculate this bezier curve, i already have point A,D but i need those B,C to make this turn proper.

- How can i characterize this bezier so that let's say planeA has smaller turns than planeB ?


I almost had it, but almost is nothing in this case so i better rewrite this with your help.

Thanks for any help with this, i am scratching my head with this and found it's not that easy i was thinking... or ?

Share this post


Link to post
Share on other sites
Advertisement
I'm just wondering why it is necessary to use a bezier curve. It seems to me that this is where a lot of your difficulty is coming from. Why not just use a few simple rules to allow the plane to navigate to a location, e.g. turn at it's maximum turning speed until it is pointing at the target and then fly straight. While that particular rule does not work when the plane is too close to the destination, it seems like it meets your requirements without having to mess around with curve fitting.

-Josh

Share this post


Link to post
Share on other sites

I'm just wondering why it is necessary to use a bezier curve. It seems to me that this is where a lot of your difficulty is coming from. Why not just use a few simple rules to allow the plane to navigate to a location, e.g. turn at it's maximum turning speed until it is pointing at the target and then fly straight. While that particular rule does not work when the plane is too close to the destination, it seems like it meets your requirements without having to mess around with curve fitting.

-Josh


Well unfortunately this is the requirement - Client's requirement there is nothing i can do without having alternative option.

If there is anything else i can do without Bezier - like your rule, i would be able to speak to the client and try to force him to use it, but unfortunately your rule won't work for destinations which are close to the plane - and if there is any other method, i would love to hear it...

Share this post


Link to post
Share on other sites


Well unfortunately this is the requirement - Client's requirement there is nothing i can do without having alternative option.

If there is anything else i can do without Bezier - like your rule, i would be able to speak to the client and try to force him to use it, but unfortunately your rule won't work for destinations which are close to the plane - and if there is any other method, i would love to hear it...


Sorry, I had to leave for work so I was in a bit of a hurry when I wrote my reply. It is relatively easy to create a rule that handles the case when the plane is in a position where orienting towards the target and heading straight fails -- just fly straight until re-orienting is possible. So there is an alternative that you can present to the client. This looks like an example of a problem in differential game theory called 'the homicidal chauffeur', so at least that's something you can search for.

If your client insists on using a Bezier curve then I suspect you will end up with a minimization problem to solve. The objective function will be the 'elastic energy' of the trajectory, which you will be trying to minimize so that you do not violate the turning angle constraint. I think that will end up being a tricky approach because you probably also want to minimize the time taken getting to the target.

Another idea would be to use something like an A* search to solve the problem and then get the Bezier curve using a least squares fit.

Some ideas to consider at least :)

-Josh

Share this post


Link to post
Share on other sites
Need to elaborate a bit on this before i go to the client saying "Hey, we can't go with bezier" smile.png

Well i believe i have seen many games where you just Click to set some plane destination and it worked well,
i am just thinking - is this such a rocket science ?


Now speaking of 'flying' and turning when possible - wouldn't that require much more complicated stuff than this 'damn simple bezier' ?




Btw. Thanks for your help mate.

Share this post


Link to post
Share on other sites
Ok i see that the whole GD never made anything related to bezier curves, never did any game that was to deal with a plane, never made AI model that would fly to destination when clicked on the map?

Come one guys, it can't be that damn hard!! These are just 4 points on the curve, and simple life-assumptions, that this plane can't turn in one place, can't go backwards and so on... it is just impossible i am here, sitting alone and trying to work out something that looks like can't be done.

More, we already have A,B,D points of A,B,C,D bezier - we look for a 'good' C .. can i ask for a bit of help with this or at least somebody saying: This Can't be done
so that i'll start digging something else? I have seen many using bezier - even here:

http://devmag.org.za/2011/04/05/bzier-curves-a-tutorial/

it's nicely described, what is the problem here??


Hope for somebody to at least shed a bit of light on this approach or propose something else, this is just impossible i'm stuck here alone! Somebody had to try it before / implement solution / alternative...

Share this post


Link to post
Share on other sites
A Bezier curve really isn't the best tool for a plane trajectory. When calculating positions along the curve, you have to deal with the fact that the arc-length of a segment t time units long is going to vary across the curve; in other words, throughout the arc of the curve the plane's velocity is going to vary in a completely unrealistic fashion. That is basically what people are getting at here; you are not choosing an appropriate methodology or solution here, and trying to shoehorn in your requirements just adds complexity to an already unsuitable procedure.

Share this post


Link to post
Share on other sites
FLeBlanc - so what people use to 'fly' to a chosen destination?

Simple - "calculate angle between position and destination" and move towards that direction will not work.

Bezier - won't work,

what else then?

Share this post


Link to post
Share on other sites
I thought about something similar a few weeks ago. I in didn't use Bezier curves, but i calculated cubic curves from the endpoints and the differentials (velocity vectors) at the end points which is almost the same thing (both are cubic curves). Now the issue is that these kind of curves don't come with any guarantee when it comes to length, constraits on velocity at a given point or turning radii. The velocity issue is somewhat solvable by following the curve "piecewise" and scale the stepsize by 1/v (for v either estimate with the value from the last step or calculate it explicitly since it's only the derivative of a polynomial).

For the curvature you'd have to do something similar. Calculate the curvature at a bunch of sample points and check if they fulfill your turning radius condition or whatever and if not fiddle with the parameters cleverly and repeat until you get a satisfying curve.

The problem in both cases is that finding a "direct" solution would usually require you to find the zeros of functions that are either polynomials of too high order or not even polynomials. So I guess your best bet is to either use approximation methods like I described or come up with clever heuristics that work for the reasonable cases.

From playing with steambirds i'd assume they do something along the lines of finding a polynomial from startpoint, endpoint, start velocity and some other condition like requiring that the second derivative at the endpoint location is zero (not sure if that is enough, I didn't do the math yet).

Share this post


Link to post
Share on other sites
A simple rule:

  • always move forward at maximum speed
  • turn left or right by the amount that aligns your velocity with the vector from you to the target if you can
  • turn hard left or right if you cannot align with the target this turn

    Simple enhancements:

    • choose and adjust the target smartly (e.g. dead reckoning or aiming for the midpoint between you and a slower evading target)
    • at each speed, you have a certain steering radius; if the target is inside the circles of that radius that are tangent to your trajectory at your position, you cannot turn to face it: slow down to shrink the circles and put the target into the reachable region.

      By the way, Steambirds lets you choose the radius and length of what appear to be circular arcs (constrained by steering radius limits). If it uses splines, they are close approximations of circular arcs.

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.

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!