Hullo, I'm developing a space-trader game (as if there aren't enough of those) and am now forced to implement some rudimentary AI for the game to go anywhere. As I've never worked with this stuff I'm quite lost though. Basically what I want right now is a decent method to make a ship (that has a position and rotation and on which we can call thrust(), yaw(), pitch() and roll() methods) go to a specified point (and orientation). For example, the ship is somewhere in space and I want it to end up on the parking lot on a space station. Any thoughts on what I should do (or read) to get this working?

So then, it was a one dimensional space trader!? Thrilling, but I think it's a bit late for me to change change dimensions ;). Does anyone have an idea of how ta make my spacemen go where they wanna be?

If you don't take obstacles into account (which is a bad assumption to make, but a good starting point perhaps), you could look at using splines to make a smooth path to follow to get to your desired position and orientation. I don't know much about splines, but it may be possible to constrain the second derivative of the spline to account for how fast the ship can turn. At that point, it would just be a matter of calling the appropriate movement methods at the points required by the spline.

If this sort of method DID work, then you could handle obstacles by breaking your path into pieces, and re-calculating the parts of the path that overlap obstacles, with the endpoints adjusted to steer around the obstacle.

Hope all this comes through, forum has been cutting off my posts.

Also, all of these are ideas off the top of my head and have not been tested. Will probably need modifications during implementation. Last idea is probably best one.

Sparse A* Terrain Search.

Space is vast and mostly empty.

Say you have 100 objects in space.

Make each object a node in a graph.

Make the graph fully connected.

Calculate the length of every path from 1 object to another.

So 100x99 paths.

For each of the 100 objects on the left side, keep the edges for the shorted path.

Do this outside of the game. Preprocess the search space.

Now you have a graph where all 100 objects are connected by edges that are part of their shortest path to every other object in space.

When you decided that you want bob, at space station A to go to space station D, you run A* on the graph and it quickly calculates what path it should take.

If your ship starts off in the middle of space and not a spot on the map, figure out which object on the map is closest and pathfind from there. Then just remove the step where you fly to that nearest object and fly directly to the next object on the list.

The fact that the object you pathfound from was the closest to your prevents you from actually running into anything unless it is in a straight line from your ship, through the closest object to the second closest object. That special case is easy to check and handle.

If all of the objects are in motion, its fine and still works. Just recalc the weight across all the edges. So long as their relative positions doesn't change, it won't be too far wrong.

If the objects positions change significantly you can still handle it, albiet slower.

For each object, figure out the closest other object and put and edge between them. You will end up with groups of two or more objects. For each group, repeat this process but only check with members outside their group.

Now you have groups of minimum size 4. Do this until you only have 1 group. Now you are able to get anywhere from anywhere quickly.

Now pathfind that.