## AI optimal rotation of a rigid body

I'm trying to write AI code for a program, in which a spaceship has to rotate to face a target. I've somewhat idealised the situation - the ship can yaw, pitch and roll with a maximum angular acceleration along each axis.

I'm representing the rotation of the ship relative to the world reference frame, as well as its angular velocity and acceleration as quaternions - so my code to update the ship is essentially:

Code:
d2rot = get_d2rot_somehow()
drot = d2rot * drot
rot = drot * rot
executed at each timestep. The question is essentially what value do I need for d2rot (the second differential of the ship's rotation, if that wasn't clear i.e. angular acceleration) in order for the ship to end up pointing in the right direction fairly quickly?

I've found a couple of papers:

http://citeseerx.ist.psu.edu/viewdoc...=rep1&type=pdf seems to be doing what I want, but the maths is above my head and from what I understand of the opening page, the authors are working with matrices, not quaternions.

http://ntrs.nasa.gov/archive/nasa/ca...1974020927.pdf which is a translation of a Russian paper made in the 1970s, and I'm not completely convinced it's trying to solve the same problem.

Thanks for any help / pointers! :)
 PhysOrg.com science news on PhysOrg.com >> Ants and carnivorous plants conspire for mutualistic feeding>> Forecast for Titan: Wild weather could be ahead>> Researchers stitch defects into the world's thinnest semiconductor
 Hey Snark1994 and welcome to the forums. A recommendation I have for the general situation which involves completely dynamic situations from occuring (i.e. aiming when everything is continually moving) is based on an inverse kinematics approach with the search of minimal paths. If you are making a 3D game where everything is moving, then this approach will in general be a lot better to handle situations of great complexity, especially if you have multiple enemies in a scene. IK is basically an inverse solver where you have a current bone configuration, an ideal target configuration (i.e. the bone structure) and you need a way to get there through an interpolation (i.e. determine the path entirely in-between the two points). You could simplify the approach a lot of the degrees of freedom are known and small and use a kind of dampening effect to make the AI approach a lot more fluid and realistic, but if you have complex ship structures or ship structures with their own turrets that can move, I recommend at least looking into IK. The other thing is if you have multiple turrets on a single mother ship and you want to co-ordinate all of them to have a really cool attack AI, then you can solve a simultaneous IK problem that aligns all of the turrets in the best configuration for the attack phase. The IK will generate the actual kinematic actions for you to follow so it will calculate at each time-step the bone positions at that step and then you can take those and use them to update your internal world and do whatever else needs to be done.
 AI Game Engine Programming - Brian Schwab That book has a full implementation of "AI Asteroids" (the old game) implemented with various different forms of vector manipulation and AI types, in order to teach them all. He starts off with a naive FSM that points directly and shoots, and by end of the book there's predictive stuff algos like genetic algorithms and neural nets. The main thing to remember these days is that players expect an AI to play like a human. It's not going to be good if it obviously cheats or auto-aims with robot-like precision.

## AI optimal rotation of a rigid body

Thanks for the replies. I've worked through the first paper with some help, and it turns out to not really be what I'm after anyway.

I've had a look at IK, but it seems to be more tailored to rotating joints etc. and doesn't seem to be able to cope with something that preserves its angular velocity perfectly over time.

I'll have a look at AI Game Engine Programming, it sounds good. RE: cheating, one of my main design goals for the game was that the AI was to operate exactly under the constraints that the player operates under - so while highly precise shooting might be acceptable, depending on difficulty, cheating certainly isn't...
(Before I buy the book, does it cover 3D rotations? It mentions OpenGL in the introduction which suggests it does, but I can't preview the chapters about asteroids...)

EDIT: http://my.safaribooksonline.com/book...gwM2xldjFzZWMz seems to suggest that it is in fact the 'classic' 2D for the asteroids game at least, as he only has turnLeft() and turnRight() routines, not roll/pitch/yaw...
 You can add constraints that various rotation properties be maintained in IK if you wish. This is more of a solution for say if you had a huge mothership with a dozen turrets being co-ordinated across the board for various situations. Also, you can use this in conjunction with quaternion interpolation to get a smoother transition between rotational transformations. Again it depends on the complexity and requirements of your game, but the IK provides a general solution to a much more general situation.
 Vector matrix is more common in games than quarternions. Quaternions are faster and don't need trig, but is that a problem on a modern system? Yes, the book is indeed 2D vectors but that's the same code as 3D vectors, just one less dimension in each matrix. It's mainly a book on AI but I believe it's relevant because 1) 2d to 3d with vectors isn't crazy hard, and 2) when you say how to do you work out which direction to point, that's more than picking the direct line to the target. In an FSM you will be in one several possible states (attack, evade etc), and that state has full control over the ship. In blackboard there are several competing modules, each of which inputs a vector and a priority, and the final vector will a weighted combination of all inputs. In a self-learning GA you might never calculate it directly, the system will learn it over time as it plays. Edit: if you go to vectors, wikipedia actually explains all the math you need for 3d line graphics. http://en.wikipedia.org/wiki/Rotatio...ree_dimensions I can do it, but I can't do N-body collision resolution (see my other thread) :-)
 Vector matrix is fine, I just have a more intuitive understanding of quaternions, and as far as I'm aware the two are isomorphic so it shouldn't matter which one you use. Ah, sorry, I must have explained myself badly. I know which direction I need to point - that's relatively trivial, as you noted. That's like picking the position I need the ship to be in - the harder part is manipulating the acceleration of the ship so that it arrives at the desired position. Similarly, for rotations, I know which direction I need to face, but I need to manipulate my angular acceleration so that I end up pointing in the right direction. This is just the nuts-n'-bolts, before I get to the higher level decisions of what the ship is actually going to do, like attack or evade ;) One idea I had was some sort of approximation to critically damped SHM, so having two components to guide the angular acceleration: one towards the desired position, and one against the desired velocity
 Is this a maths question (how do i add vectors?) or a programming question (how do i increment the position of the ship each frame of animation, so that it arrives at its destination?) I suspect the latter In this case, you will probably have a loop in the game that executes once for each frame of animation, e.g. 60 iterations per second for 60 FPS (frames/sec) graphics. At the start of loop you clear the screen, then you check for inputs from your player or AI, then you update the positions of the items & check for collisions, then repaint the screen. A mathematician would probably work out the vector addition required to get to the destination, then divide it by 60 and add it to the current position. I might just add an arbitary amount and have the computer turn round and punt the other way if it overshoots, in much the same manner as a human would do it. Actually if that was what your question was, the book I mentioned has the full code for it but it is only 2d vectors. edit: Actually if this is the question, what you face is a game design decision or gameplay decision based on how you want the AI to play and if it drives like robocop or a human. There's no set rule for it.

Aha, we're getting closer... It is a maths question, but I suspected it might be difficult to solve the problem analytically - so I suspect a more crude programming solution is probably the best way to solve the problem for the purposes of the game.

My problem is not how to animate the motion of the spaceship between two positions. For example, when you said:

 In this case, you will probably have a loop in the game that executes once for each frame of animation, e.g. 60 iterations per second for 60 FPS (frames/sec) graphics. At the start of loop you clear the screen, then you check for inputs from your player or AI, then you update the positions of the items & check for collisions, then repaint the screen. A mathematician would probably work out the vector addition required to get to the destination, then divide it by 60 and add it to the current position. I might just add an arbitary amount and have the computer turn round and punt the other way if it overshoots, in much the same manner as a human would do it. Actually if that was what your question was, the book I mentioned has the full code for it but it is only 2d vectors.
this suggests that either the ship has got unlimited velocity (if it travels to any position in the 60 frames) or that you've chosen the position so it corresponds to the points reachable by the spaceship's current speed (i.e. an animation).

My problem is more along the lines of "In this frame, my ship is at r0 with velocity v and needs to get to r1 as soon as possible, so what should my acceleration a be in order to achieve this as quickly as possible?"

My solution to this is as follows:
Code:
//pos = ship position
//dpos = ship speed
//d2pos = ship acceleration
Vector target = player->getPos();
Vector goal = target - pos;
if(dpos.getMagnitude() < 0.0005 && goal.getMagnitude() < 0.0005){
//stop AI ship jittering
pos = target;
dpos = Vector(0,0,0);
} else {
Vector goal_n = goal.normalise();
Vector desired_vel;
if(dpos.dot(goal_n) <= 0){
//Accelerate towards goal, we're moving away from it
desired_vel = goal_n*20;
} else if(goal.getMagnitude() < (dpos.dot(goal_n) * dpos.dot(goal_n)) / (2 * lin_thrust)) {
//according to v[SUP]2[/SUP = u2+2as
//we're not gonna make it if we start decelerating, so let's stop
desired_vel = 0;
} else {
//go faster towards goal
desired_vel = goal_n*20;
}
Vector d2pos;
if(dpos == desired_vel) {
d2pos = Vector(0,0,0);
} else {
//lin_thrust is a constant, the maximum linear acceleration the ship is allowed
d2pos = (desired_vel - dpos).normalise() * lin_thrust;
}
dpos += d2pos;
}
pos += dpos;
This has a couple of naïveties, but it generally works okay.

What I am trying to do is the same for rotations - so my code isn't allowed to manipulate the ship's rotation or angular velocity, only its angular acceleration. I have a similar implementation as above for my rotation, but my problem is that the angular equivalents of the SUVAT equations don't work so well for determining when the ship should start to slow its speed of rotation.

Is that a clearer statement of my problem? Sorry for any confusion.
 I think understand the question now. Your ship facing is (0,0,0) degrees and you need to turn to (60, 40, -90) degrees (e.g. 60 yaw, 40 pitch, -90 roll), and you want to model this turning by "newtonian" rockets that obey F=ma, so the ship's facing will start small, increase constantly, then presumumably you fire rockets on the other side to stop it, and it gradualyl stops spinning. If angular SUVAT is not working for you, do you really need them? What if you break the angle into its 3 components, treat each as a distance (call 60 degrees a distance of 60 arbitary units), work out what is needed in each component using the same code you have provided as if you had to move 60 units in a straight line with SUVAT, and then recombine them. From memory (advise you to check it) i think Code: z_rot_matrix = [ [1, 0, 0, 0], [0, cos(xa), sin(xa),0], [0,-sin(xa),cos(xa),0], [0,0,0,1] ] is rotation of a degrees about Z axis. Multiply all 3 them all together, apply scaling matrix and combine with ship. (Really advise you to double check!) I apologise if I am missing something. I can 3d but I don't know the formal technical words to express it, as from a programming POV you don't really learn it in the same way a mathematician does (well I didn't anyway).
 Aha, yeah, you've got it! (I don't think your approach would quite work, because Euler angles aren't independent of each other - if you roll right 45° and then yaw left 90°, that's the same as yawing left 90° and then pitching up 45° - but it seems to work alright with quaternions) Now, that works fine if the ship starts off not rotating relative to the target. However, if it has an initial angular velocity, and that's not in the same direction that it wants to rotate in, then it tends to gyrate about the desired direction (i.e. it can't quite cope with the existing angular velocity). Would it help if I uploaded a video of what it's doing?
 Actually you've taught me why we do it with 3x4 matrices... hadn't realised angles weren't independent. Is there any reason you are not using matrices?
 Not really, I just find quaternions more intuitive... I can visualise what's going on with quaternions better than with matrices, and as the two are isomorphic (i.e. if you can implement something with matrices, then you can implement it with no changes to the fundamental algorithm with quaternions, as far as I know) it didn't really make any difference which one I picked in terms of how difficult the problem is.
 How about using a SLERP with quaternions?
 SLERP would still be going down the animation route, wouldn't it? It's just a smooth interpolation between the two quaternions, not an acceleration/deceleration...

 Quote by Snark1994 SLERP would still be going down the animation route, wouldn't it? It's just a smooth interpolation between the two quaternions, not an acceleration/deceleration...
Yes but the parameterization does not have to be linear: you can create a transformation corresponding to the behaviour that is intended that is not necessarily linear.

 Quote by chiro Yes but the parameterization does not have to be linear: you can create a transformation corresponding to the behaviour that is intended that is not necessarily linear.
Sorry, could you give me a pseudo-code example? I'm pretty sure that it doesn't work your way, but I might be wrong. Just to make sure, you're creating a SLERP_magic function that satisfies:

Code:
function SLERP_magic(current_rot,current_drot,target_rot){
//do stuff, return a value for d2pos
}

while game_is_active {
d2rot = SLERP_magic(current_rot,target_rot,current_drot);
current_drot = d2rot * current_drot; //i.e. update drot from d2rot
current_rot = current_drot * current_rot; //i.e. update rot from the new drot
}
which will (in a reasonably efficient manner) make current_rot equal to target_rot