I am looking for some input on how to realize a feature I would like to build into my game. (Not technical implementation, just what kind of mathematical models or algorithms would fit my situation best.)

I am making a top down space strategy game in which you command every ship individually. Ships have a position and a rotation for their current position. I want to be able to give a new position and rotation for the ship to move to. Usually a trivial task. However I have additional constraints:

  1. Ships move with a constant forward velocity. So stopping, turning towards the target and flying strait to the target position is not possible. Ships can change their speed by small increments with the next move command after a cooldown, but during a move the forward velocity can not be changed.
  2. Ships have a maximum turn rate. This combined with the set forward velocity means ships can't take turns with turn radii smaller than a certain value. Meaning there will be many target positions (+ orientations) that can not be reached with a single turn and ships will have to take a detour to reach them. A very rough and quick illustration: Say we have a ship at a current position with some rotation and we are given a destination location(+ orientation) that is too close to reach with a simple turn using the ships maximum turn rate:

enter image description here

I now want to find the shortest path that does reach the target position and orientation. Which might look something like this:

enter image description here

Some position may require even more turning where recognizing / finding the shortest path is no longer trivial.

So I have two problems to solve that I would like help with:

  1. what kind of mathematical model, that can also be calculated well by computers, can I use to represent those kind of flight paths. My first thinking was, some kind of splines. But which splines would allow me to limit the turn radius and how would I do that? It's been a while since my last math class, but I was thinking that what I am thinking of as the "turn rate" of a flight path is just the paths derivative in each direction, or is that wrong? So if I am to use splines I am wondering, what kind of spline allows me to limit the maximum value of its derivatives for the entire curve.
  2. How do I find the shortest flight path to a given position(+rotation) in a fast manner? Since a direct path is not always possible a search for the shortest legal path is necessary.


You must log in to answer this question.

Browse other questions tagged .