AI to move custom-shaped spaceships (shape affecting movement behaviour)

Question

I'm designing a networked turn based 3D-6DOF space fleet combat strategy game which relies heavily on ship customization. Let me explain the game a bit, since you need to know a bit about it to set the question.

What I aim for is the ability to create your own fleet of ships with custom shapes and attached modules (propellers, tractor beams...) which would give advantages and disadvantages to each ship, so you have lots of different fleet distributions. E.g., long ship with two propellers at the side would let the ship spin around that plane easily, bigger ships would move slowly unless you place lots of propellers at the back (therefore spending more "construction" points and energy when moving, and it will only move fast towards that direction.) I plan to balance all the game around this feature.

The game would revolve around two phases: orders and combat phase. During the orders phase, you command the different ships. When all players finish the order phase, the combat phase begins and the ship orders get resolved in real-time for some time, then the action pauses and there's a new orders phase.

The problem comes when I think about player input. To move a ship, you need to turn on or off different propellers if you want to steer, travel forward, brake, rotate in place... These propellers don't have to work at their whole power, so you can achieve more movement combinations with less propellers.

I think this approach is a bit boring. The player doesn't want to fiddle with motors or anything, you just want to MOVE and KILL. The way I intend the player to give orders to these ships is by a destination and a rotation, and then the AI would calculate the correct propeller power to achive that movement and rotation. Propulsion doesn't have to be the same throught the entire turn calculation (after the orders have been given) so it would be cool if the ships reacted as they move, adjusting the power of the propellers for their needs dynamically, but it may be too hard to implement and it's not really needed for the game to work.

In both cases, how would that AI decide which propellers to activate for the best (or at least not worst) trajectory to be achieved?

I though about some approaches:

• Learning AI: The ship types would learn about their movement by trial and error, adjusting their behaviour with more uses, and finally becoming "smart". I don't want to get involved THAT far in AI coding, and I think it can be frustrating for the player (even if you can let it learn without playing.)
• Pre-calculated timestep movement: Upon ship creation, ALL possible movements are calculated for each propeller configuration and power for a given delta-time. Memory intensive, ugly, bad.
• Pre-calculated trajectories: The same as above but not for each delta-time but the whole trajectory, which would then be fitted as much as possible. Requires a fixed propeller configuration for the whole combat phase and is still memory intensive, ugly and bad.
• Continuous brute forcing: The AI continously checks ALL possible propeller configurations throughout the entire combat phase, precalculates a few time steps and decides which is the best one based on that. Con: what's good now might not be that good later, and it's too CPU intensive, ugly, and bad too.
• Single brute forcing: Same as above, but only brute forcing at the beginning of the simulation, so it needs constant propeller configuration throughout the entire combat phase.
• Coninuous angle check: This is not a full movement method, but maybe a way to discard "stupid" propeller configurations. Given the current propeller's normal vector and the final one, you can approximate the power needed for the propeller based on the angle. You must do this continuously throughout the whole combat phase. I figured this one out recently so I didn't put in too much thought. A priori, it has the "what's good now might not be that good later" drawback too, and it doesn't care about the other propellers which may act together to make a better propelling configuration.

I'm really stuck here. Any ideas?

Answer 1

Sorry haven't got a tried-and-tested solution, but can this not be solved mathmatically?

Given any propeller and its offset from the center of mass, you can compute what plane you can rotate in.

For any movement, you can use 1 or more propellers. Each propeller can be queried to see whether its plane can contribute to the target orientation, how much effort it would take from the propeller to contribute (propellers far from the CoM can use less energy to generate more turn), and how close that would get you to the target oritentation. Then you A* across that search space until you come up with a solution with low cost, which could be least total energy used or fastest movement.

Keep reevaluating that as you complete the turn and moderate power as you approach the target, maybe with a PID controller.

For forward movement, a simple solution would drive you always forwards, dropping your target speed as you approach the target. As you've got 3D space to play in you can avoid complicated 3-point turn routines. You'd need to factor the output from the propellers chosen for straight-line speed into your turning calculations, as some kind of initial state.

This is very back-of-the-envelope but I don't see any major flaws. Just lots of hard work and number tweaking. :)

Answer 2

Since you want to give up a bit of player control for playability using an AI, you might want to consider also simplifying the effect of tacking on propellers and altering ship dimensions into less, more easily manageable parameters for a computer algorithm. The player is still allowed to add propellers on any given part of the ship, but once completed this is 'compressed' into parameters.

Each propeller affects the turn rate of the ship, or, combined with a parallel placed propeller, affects the travel rate in a specific dimension. Combine these parameters for each propeller, and you get the maximum turn rate and speed for a ship. Combine these two parameters for each propeller and propeller set into the maximum turn and speed rate for the ship as a whole, for all available dimensions (up, down, left, right, forward, backward).

Using the turn rate and velocity for each dimension, you have enough information to actually allow the ship to move to a destination. The player will see the effect of his propeller configuration, but under the hood his input is vastly simplified. You could come up with more than one fly strategy based on the distance the ship has to travel, to make the flight look more natural and increase the player's sense he or she has exerted control over the ship movement. But in the end, like you said, it will not matter how the ship gets to the destination and whether its route is optimal, it just needs to be there and its arrival time is influenced by the propeller configuration.

For the ship dimensions, you could factor them in once you have the compressed velocity values for a rough effect, or use them while calculating for a more precise effect. You would probably want to test if the precise method is worth the effort, because the difference might not impact the player's sense of control.

Answer 3

In space, shape does not affect movement. No air to drag on.

It's the ship plus add-ons total mass that matters. It's a simpler mass thrust gravity problem. So you can do these calculation or since it's a turn base game, develop a movement system like RPGs like Traveller have.