Vexal

3D Ship Arbitrary Thrust Solver

3D Ship Arbitrary Thrust Solver - Description

Overview

The goal of this project is to move one step closer to an AI system for which arbitrarily-designed agents can move with physical realism without need for manual tweaking.

TL;DR: Use linear programming to control AI vehicle and character thruster activation to achieve target linear and angular velocity in a specified direction

In my game engine, all controlled movement by an object is done through the concept of thrusters. A thruster is an object attached to an in-game object which allows the in-game object to apply a force to itself. This applied force is always in local coordinates to the owning object.

struct Thruster
{
const Vec3D offset; //attachment point in local coordinates relative to owning object
const Vec3D direction; //thrust direction in local coordinates of owning object
const float maximumMagnitude;
const float currentMagnitude; //percentage of maximum thrust magnitude currently in use
};

The problem

The difficult part of using a system like this to control all objects is allowing the AI (and to some extent, players) to correctly figure out which thrusters to activate to achieve optimal movement in a particular direction (or combination of directions and rotations). The following picture illustrates a typical thruster configuration for a spaceship.

Cube Picture

This image shows a ship and its thruster configuration. The blue arrows indicate the position and direction of each thruster object.

In the above image, a ship with 8 thrusters is shown. A human looking at this picture could easily devise a plan for which thrusters to activate to move in a particular direction (example: activate the rear left thruster at full capacity and the rear right thruster at half capacity to turn the ship right and move forward at the same time, etc). This process can be further simplified for human controllers by making these combinations of thrusters automatically activate so the result of the player moving the mouse or turning the joystick a certain magnitude and direction causes the expected action in game.

AI vs human control

For an AI, it is not so simple. Say you want the AI to follow and face towards a player character as the player moves around the world. It will need to turn itself over a combination of axises while also moving forward.

One could hack a simple solution by hardcoding the AI to apply specific thrusters to move in certain directions. It's easy enough to say "activate the two rear thrusters" to move straight. But for the AI to move and turn at the same time with only two active thrusters, it becomes more complicated. Especially when it comes to controlling exactly how fast the object moves and turns. When a human controls a vehicle, speed is adjusted by a manual feedback loop -- the human applies throttle, 'feels' the response of the vehicle, then immediately changes the amount of applied throttle. An AI is not able to easily do this.

An AI can only optimally work if, given a target acceleration (angular or linear, or both), and an arbitrary thruster configuration, some sort of interesting function can return a list of which thrusters to activate to achieve the target acceleration (as well as how much percentage of its maximum magnitude to activate each thruster).

The solution

It is possible to determine a specific set of thruster activation magnitudes necessary to achieve a given acceleration using linear programming. Linear programming is a method to optimize the output of a function given a set of constraints. In this case, we want to optimize for the minimum difference between the total force applied to the object, and the target force for the object, per dimension. If we have:

forceAppliedX = Thruster_1.xForce * Thruster_1.activationPercentage + Thruster_2.xForce * Thruster_2.activationPercentage .. Thruster_n.xForce
forceAppliedY = Thruster_1.yForce * Thruster_1.activationPercentage + .. + Thruster_n.yForce * Thruster_n.activationPercentage
forceAppliedZ = Thruster_1.zForce * Thruster_1.activationPercentage + .. + Thruster_n.zForce * Thruster_n.activationPercentage
torqueAppliedX = Thruster_1.xTorque * Thruster_1.activationPercentage .. Thruster_n.xTorque * Thruster_n.activationPercentage
torqueAppliedY = Thruster_1.yTorque * Thruster_1.activationPercentage .. Thruster_n.yTorque * Thruster_n.activationPercentage
torqueAppliedZ = Thruster_1.zTorque * Thruster_1.activationPercentage .. Thruster_n.zTorque * Thruster_n.activationPercentage
and
targetXForce = The total force we want to be applied in the x direction (summed from all movement goals this frame)
targetYForce = The total force we want to be applied in the y direction (summed from all movement goals this frame)
targetZForce = The total force we want to be applied in the z direction (summed from all movement goals this frame)
targetXTorque = The total force we want to be applied around the x axis (summed from all movement goals this frame)
targetYTorque = The total force we want to be applied around the y axis (summed from all movement goals this frame)
targetZTorque = The total force we want to be applied around the z axis (summed from all movement goals this frame)
then we want the objective function:
abs(targetXForce - forceAppliedX) +
abs(targetYForce - forceAppliedY) +
abs(targetZForce - forceAppliedZ) +
abs(targetXTorque - torqueAppliedX) +
abs(targetYTorque - torqueAppliedY) +
abs(targetZTorque - torqueAppliedZ) = 0 to be minimized
with the constraints:
Thruster_1.activationPercentage >= 0
Thruster_1.activationPercentage <= 1
Thruster_2.activationPercentage >= 0
Thruster_2.activationPercentage <= 1
..
Thruster_n.activationPercentage >= 0
Thruster_n.activationPercentage <= 1
This page goes over the basics of setting up a regular optimization problem. I used the library lpsolve in this project.

Absolute value

Because absolute value is not itself a valid function in a regular linear optimization problem, some tweaking must be done to these formulas. This page gives a better explanation on how to do this than I can.

The end result is that each force and torque absolute value term in the objective function should be replaced with respective new variables:

xF, yF, zF, xT, yT, zT
and for each of these terms, two new constraint functions be added to the system:
xF <= xF'
-xF <= xF'
yF <= yF'
-yF <= yF'
..
zT <= zT'
-zT <= zT'

Other benefits

Being able to solve for a set of thruster magnitudes given any arbitrary list of thruster structs allows for interesting effects, such as dynamically destroying parts of vehicles (and their thrusters with it), allowing the AI to automatically compensate for movement with the thrusters it has remaining. As long as there is a set of basis vectors in the vector space formed by the directions of all thrusters on an object that covers all degrees of freedom, the AI will be able to move in any direction with any set of thrusters. Desired speed as well as direction is easily encoded in the equations.

Game systems can allow players to customize the thruster layout of a vehicle or ship. As well, procedurally generated AI units can make use of randomly placed on its body or vehicle.

In addition to computing thruster activations in coordinates local to the object, it can support global coordinate computation by first transforming the desired global coordinate target forces into local coordinate space.

Current results

This is a video of it working -- the ships circle the player and compensate for being shot


This is a video of it not working -- everything crashed and explodes

Further work

While this system allows an object to move in a specific direction given a current state, it computes which thrusters to activate based solely on the current location and rotation of the object. It is best suited to computing a desired linear and angular velocity, but not well-suited for computing a desired location or rotation. This can cause problems when the goal is to do something in global coordinate space. If a ship is already facing a target (and the ship can move fastest in the direction its front is facing), then everything works fine. If the ship is facing a direction such that its thrusters are pointed in a direction that will not be able to provide as powerful of thrust in the desired direction of movement, this system will not do anything to compensate. It will only compute the solution given its current rotation and position. It is similar to asking a human to move forward when it is currently sitting, and it computing that it should crawl to the target instead of getting up first and then walking.

Therefore, the next step to increase the usefulness of this system is the implementation of a planning system. The AI should recognize how its current state in global coordinates differs from the state in global coordinates which would be optimal to be in to complete its movement goal. It should also be able to compute whether the time it takes to transition from its current state to its optimal state for goal completion is worth the time (if a human is sitting on the floor, but very near its goal, it might be faster to crawl to it when taking into account the time it takes to stand up first before walking).