AI optimal rotation of a rigid body

[Snark1994]

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:

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/download?doi=10.1.1.175.5952&rep=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/casi.ntrs.nasa.gov/19740020927_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! :)

 

[chiro]

Hey Snark1994 and welcome to the forums.

A recommendation I have for the general situation which involves completely dynamic situations from occurring (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.

 

[rorix_bw]

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.

 

[Snark1994]

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/programming/game-programming/9781584505723/finite-state-machines/ch15lev1sec3#X2ludGVybmFsX0ZsYXNoUmVhZGVyP3htbGlkPTk3ODE1ODQ1MDU3MjMvY2gwM2xldjFzZWMz 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...

 

[chiro]

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.

 

[rorix_bw]

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/Rotation_matrix#Rotations_in_three_dimensions

I can do it, but I can't do N-body collision resolution (see my other thread) :-)

 

[Snark1994]

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

 

[rorix_bw]

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.

 

[Snark1994]

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 r₀ with velocity v and needs to get to r₁ 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:

//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 = u[SUP]2[/SUP]+2as
        //we're not going to 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.

 

[rorix_bw]

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

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).

 

[Snark1994]

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?

 

[rorix_bw]

Actually you've taught me why we do it with 3x4 matrices... hadn't realized angles weren't independent. Is there any reason you are not using matrices?

 

[Snark1994]

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.

 

[chiro]

How about using a SLERP with quaternions?

 

[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...

 

[chiro]

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.

 

[Snark1994]

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:

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

 

[chiro]

What I mean is to make the parameter you pass (i.e. t between 0 and 1 inclusive) to vary non-linearly. Instead of going from 0 to 1 in incremental steps that are the same, you can make it go say faster at the start and then let it decay at the end.

Different kinds of behaviours for f(t) where f(t) is in [0,1] and t is in [0,1] give different kinds of behaviours for how the AI rotates itself to approach the target.

If you are continually updating the path every tick so that the SLERP changes in accordance with the new position, then you can base the behaviour of f(t) on things like the dot product of the direction vector of the ship and the vector of the actual ship itself: speed it up when they are not aligned (i.e. dot product < 0) and then make it slow down when they are close (dot product > .05 for example)

You can, by transforming the parameter and how its incremented, directly control how the object moves and what it looks like when it rotates.

 

[Snark1994]

Thanks, I understand that a non-linear parameter will give the appearance of an accel/decel rotation, but that's more applicable to animation. I also can't see how it would cope with the case where e.g. the ship is at (Y,P,R) = (90,0,0), wants to get to (0,90,0) and is initially rotating around the yaw axis at 10 deg/second - as the path the ship would take is no longer a linear interpolation but a curve.

I think I can get it to work using something similar to http://www.shiffman.net/itp/classes/nature/week06_s09/seekarrive/ but for rotations. I'm going off on holidays now, and it's not quite working but I suspect it's due to a bug rather than a problem with the method, so I'll see if I can get it fixed when I get back - if I do, I'll post back here with my algorithm.

Thanks for all the suggestions so far!

 

[Snark1994]

Well, I haven't got C++ working but my python seems to be working well enough - using the seek/arrive steering behaviour I posted in my last post:

#!/usr/bin/env python3

from math import sqrt,sin,cos,acos

rot_thrust = 0.01 #degrees per timestep
DEGTORAD = 0.0174532

def main():
        rot = Quaternion(1/sqrt(2),0,0,-1/sqrt(2))
        drot = Quaternion(cos(30*rot_thrust*DEGTORAD),0,sin(30*rot_thrust*DEGTORAD),0)
	d2rot = Quaternion(1,0,0,0)

	goal = Vector(0,5,0)
	step = 0

	while abs(rot.w - 1) > 0.00000001:
		step += 1
		d2rot = steer(rot,drot,goal)
		drot = d2rot * drot
		rot = drot * rot

def steer(rot,drot,goal):
	desired_drot = get_desired_drot(goal,rot,drot)
	desired_d2rot = (desired_drot * drot.inverse()).normalise()
	return get_d2rot(desired_d2rot)

def get_desired_drot(goal,rot,drot):
	slow_down_dist = 90*DEGTORAD #radians
	max_speed = 0.0146221 #radians per timestep

	dot = Vector(0,1,0).dot(goal.normalise());
	axis = goal.cross(Vector(0,1,0)).normalise()
	alpha = acos(dot)
	if axis == None and dot == 1: #parallel
		desired_rot = Quaternion(1,0,0,0)
	elif axis == None and dot == -1: #opposite
		desired_rot = Quaternion(0,1,0,0)
	else:
                desired_rot = Quaternion(cos(alpha/2),axis.x*sin(alpha/2),axis.y*sin(alpha/2),axis.z*sin(alpha/2))

        to_desired = (desired_rot * rot.inverse()).normalise()
        dist = acos(to_desired.w)*2;
        if dist > 0:
                axis = Vector(to_desired.x,to_desired.y,to_desired.z).normalise()
                if dist < slow_down_dist:
                        theta = max_speed*dist/slow_down_dist
                else:
                        theta = max_speed
                return Quaternion(cos(theta/2),axis.x*sin(theta/2),axis.y*sin(theta/2),axis.z*sin(theta/2))
        else:
                return Quaternion(1,0,0,0)

def get_d2rot(desired):
        axis = Vector(desired.x,desired.y,desired.z).normalise()
        desired_theta = acos(desired.w)*2
        assert(desired_theta >= 0)
        theta = min(desired_theta,rot_thrust*DEGTORAD)
        return Quaternion(cos(theta/2),axis.x*sin(theta/2),axis.y*sin(theta/2),axis.z*sin(theta/2))

With a sensible definition of the Quaternion and Vector classes. Hope this helps someone!