boat movement stratergy game
hi... this is my first post.
I'm making a strategy game with boats in it... 2d top down tile based, blah.
ship movement is not restricted to tiles at all.... they just happen to be in the background and are mostly of water (der)
the movement of the ships is controlled by mouse.
1. you click the boat
2. you click the destination, then hold and drag for the final orientation.
on release the ship will move from it's current position and rotation to it's final position and rotation
so we have something like
function calculatePath(float startRot, int startX, int startY, float goalRot, int goalX, int goalY) {
// blah
}
okay... the boat is more a big ship and doesn't have the greatest of turning circles... so the path will normally be an arc to orientate the ship to a direction and then a straight line... or a straight line with an arc on the end to orientate the direction. depending on what is more logical for the ship to do in the situation.
I hope someone is understanding me.
when the ship doesn't more very far... things get even more complex as the ship will have to drive away from the starting point and goal to do it's turning circle and then drive back to 'park'.
What I am looking for are any links about this kind of movement or path finding.... a clue to what it might be called or what i should start researching. I've never had to do anything like this before and any help to point me in the right direction would be fantastic.
thanks for your time and if anything is not clearly explained please point it out.
The ships are nonholonomic vehicles. Something is non-holonomic if its degrees of freedom are less than the degrees of freedom of the environment. You're working with ships though, and last I checked, ships also have the option of turning in place, although depending on the circumstances this could often be slower than turning while moving to the destination. In fact, a ship's turning radius would actually be smaller when it is moving slower, and would increase with speed.
In any case, the key word here is nonholonomic. Possibly with some fudging or hacks, since this is for a game and not an actual robot.
In any case, the key word here is nonholonomic. Possibly with some fudging or hacks, since this is for a game and not an actual robot.
thanks for your reply... i'm researching nonholonomic robots now.
the ships are like large naval ships... the game is a naval battle... i don't think these large ships can turn on the spot... but please correct me if i am wrong... i'm still trying to find these things out.
it is a good point that ships will have a smaller turning radius at lower speeds and i'm considering this... even a better reason for them to turn at the start or end of movement when the movement delta is at it's lowest.
thanks for your help... and i'll get back to you when i have done more research.
looking forward to more ideas :)
the ships are like large naval ships... the game is a naval battle... i don't think these large ships can turn on the spot... but please correct me if i am wrong... i'm still trying to find these things out.
it is a good point that ships will have a smaller turning radius at lower speeds and i'm considering this... even a better reason for them to turn at the start or end of movement when the movement delta is at it's lowest.
thanks for your help... and i'll get back to you when i have done more research.
looking forward to more ideas :)
The turning distance (angle/distance) of such a vessel is not constant - indeed it is dependent on the instantaneous speed. What is closer to being constant is the angular velocity (angle/time). More accurately, its angular force is near-constant, but the damping factor (from the viscous water) causes a strong enough bias in the overall acceleration sigmoid curve for the previous approximation to be pretty decent. At least on the upper-end of the curve (after the ship has picked up a little angular momentum).
Most large ships can turn on the spot, but as Vorpy pointed out, there's usually a quicker way to perform an arbitrary rotation than performing the translation and local-rotation independently.
This problem falls into the category of Variational Calculus. Unfortunately, formulation of the problem is non-trivial and solution looks to be a computational nightmare. However, there are ways to produce a convincing solution, even though it may not be optimal.
An idea that springs to mind is to use Bézier curves. It is almost trivial to produce such a curve to satisfy the initial and final conditions (leaving us with two degrees of freedom). This curve may then be traversed at the maximum speed maintainable at the given curvature. The remaining problem is to tweak the magnitudes of the directional knots so as to minimise the maximum curvature, and hence the time of travel. My intuition tells me that such a minimax problem can't be solved analytically, but I suspect that excellent results could be achieved with a little numerical iteration. I don't have time to look into the details right now, but this material may be enough to get you started.
Admiral
Most large ships can turn on the spot, but as Vorpy pointed out, there's usually a quicker way to perform an arbitrary rotation than performing the translation and local-rotation independently.
This problem falls into the category of Variational Calculus. Unfortunately, formulation of the problem is non-trivial and solution looks to be a computational nightmare. However, there are ways to produce a convincing solution, even though it may not be optimal.
An idea that springs to mind is to use Bézier curves. It is almost trivial to produce such a curve to satisfy the initial and final conditions (leaving us with two degrees of freedom). This curve may then be traversed at the maximum speed maintainable at the given curvature. The remaining problem is to tweak the magnitudes of the directional knots so as to minimise the maximum curvature, and hence the time of travel. My intuition tells me that such a minimax problem can't be solved analytically, but I suspect that excellent results could be achieved with a little numerical iteration. I don't have time to look into the details right now, but this material may be enough to get you started.
Admiral
Thanks for your excellent reply TheAdmiral.
Variational Calculus does look like a nightmare!!!
Bezier curves is a great idea and I will try to implement it as an option. It looks a little unrealistic when traversing large distances however… it is more likely that a ship would turn to the correct direction and then sail directly towards the goal rather than doing a graceful curving sweep. Still it will get the ship from A to B and that’s a good start.
At the moment I am trying a method where a curve is drawn from start and the goal at the same time… and when the angle of the curve and the angle of a line between two points is the same angle… I can find the position when the ship should stop turning and draw a straight line directly between the start and the goal. It’s very hard to illustrate without a picture. I’m getting an image uploaded now…. It doesn’t work yet but should be enough to give you the idea.
http://members.iinet.net.au/~ccondon/images/image.gif
I’m just unsure how exactly how to calculate when to stop drawing the curves and when to draw the line yet… but it seems like it will work and look realistic if I figure that out.
Thanks for your help on this topic. It seemed like a really easy problem to move the ship from A to B, but it has turned out to be far more trying than I first thought.
Variational Calculus does look like a nightmare!!!
Bezier curves is a great idea and I will try to implement it as an option. It looks a little unrealistic when traversing large distances however… it is more likely that a ship would turn to the correct direction and then sail directly towards the goal rather than doing a graceful curving sweep. Still it will get the ship from A to B and that’s a good start.
At the moment I am trying a method where a curve is drawn from start and the goal at the same time… and when the angle of the curve and the angle of a line between two points is the same angle… I can find the position when the ship should stop turning and draw a straight line directly between the start and the goal. It’s very hard to illustrate without a picture. I’m getting an image uploaded now…. It doesn’t work yet but should be enough to give you the idea.
http://members.iinet.net.au/~ccondon/images/image.gif
I’m just unsure how exactly how to calculate when to stop drawing the curves and when to draw the line yet… but it seems like it will work and look realistic if I figure that out.
Thanks for your help on this topic. It seemed like a really easy problem to move the ship from A to B, but it has turned out to be far more trying than I first thought.
Quote:Original post by narky
Bezier curves is a great idea and I will try to implement it as an option. It looks a little unrealistic when traversing large distances however… it is more likely that a ship would turn to the correct direction and then sail directly towards the goal rather than doing a graceful curving sweep. Still it will get the ship from A to B and that’s a good start.
Ah, but the large sweeping curve is only one such solution. If both knots' directional vectors have equal magnitude, proportional to the distance separating them, then this sweeping, far-from-realistic curve is exactly what you will see. On the other hand, if the initial position's directional handle is very small and the final position's very large, the resulting curve will be just the way it should be: a short forward journey along a curve that directs the vessel towards the target, then a large, nearly straight path for the remainder. It the size of these two magnitudes that makes or breaks the result. This system avoids the necessity to define the path piecewise, and results in a truly smooth trajectory.
I'm not saying you're doing it wrong. In fact, your solution is rather elegant and realistic. It looks like you have the equations of the spirals perfect. All that remains is to determine the earliest arc-length parameter that corresponds to the correct gradient (in each case). Computing the two points of discontinuity and then generating the complete path should be relatively simple.
Let us know if you have any problems, or if you get things working. It's always nice to see an elegant solution to a tricky problem in all its glory [smile].
Admiral
problems... i have plenty of them so far LOL!
you couldn't draw me a picture of where the control points might go?
i'm getting a variety of effects but none very helpful.
Judging from that picture, your problem isn't the positioning of the control-points, but the evaluation of the spline. A Bézier curve should be 1-smooth (its first derivative must be continuous on the interval). This means that you shouldn't have a kink at the half-way point, as you do, no matter where the control points are.
Could we see the code you are using?
Edit: I trust you are talking about Bézier curves here, and not the points of discontinuity on your spiral-based approach. If that image is supposed to be a piecewise spiral then you have bigger problems than I thought [razz].
Admiral
Could we see the code you are using?
Edit: I trust you are talking about Bézier curves here, and not the points of discontinuity on your spiral-based approach. If that image is supposed to be a piecewise spiral then you have bigger problems than I thought [razz].
Admiral
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement