NPC Spaceship Navigation System

[paulscode]

I am trying to come up with a navigation system for NPC spaceships.  Basically, I want them to have a target position anywhere in 3D space and rotate/translate smoothly toward it (no sharp un-realistic turns).  I also want to specify a maximum value the ship can rotate around its z-axis and x-axis (so the ship doesn't flip upside-down when moving to a target position behind where it started out).  I'm sure I can eventually work out a system to do this, but I thought I would check first if anyone has done something like this before, and could give me some ideas (no reason to re-invent the wheel if I don't have to).

[C3R14L.K1L4]

Hi,

you may want to check my AI project (Goal Game Simulation), where I use some of those techniques (smooth path following) but in my case things may be a 'little' different than yours. In the SoldierAgent's code there's a function where I set a upper limit for the rotation of the agents (bots), 'calculateRotationStep'. This function is used to set a new direction vector (rotated using the maximum allowed angle step) for the agent.

In my program this is only done on a plane (xOz) but I think you can adapt it to tri-dimensional space.

Heres the site:
http://student.dei.uc.pt/~jcgonc/productions.htm

[EgonOlsen]

For smooth transitions, i'm usually using matrix interpolation. That works fine as long the matrices aren't too different.

[C3R14L.K1L4]

Yep, one I've used before is an interpolation titled Catmull–Rom spline. Here's the code:

Code Select Expand

float catmullRomSpline (float p1, float p2, float p3, float p4, float t) {
return(0.5*((-p1 + 3*p2 -3*p3 + p4)*t*t*t
+ (2*p1 -5*p2 + 4*p3 - p4)*t*t
+ (-p1+p3)*t
+ 2*p2));
}

Because it is a cubic interpolation, it requires 4 positions, interpolating between the 2 middle ones (t=0.0 gives p2, t=1.0 gives p3).
But to use maximum rotation angles I suggest the other option.

[paulscode]

Thanks for the suggestions.  I've only had a little time to work on this, but I'm thinking that I will probably go with a modified version of C3R14.K1L4's idea eventually.  I haven't gotten to the point of setting rotation upper limits yet, but I have got the thing working on a 2D plane so far.  The first thing I did is create a constant forward thrust (distance per millisecond).  I can reduce this if desired as the ship approaches the target point if I want it to stop close to there, or I can just keep the thrust constant so the ship orbits the target point.  The second thing I did is set a radians-per-millisecond variable which determines the maximum speed that the ship will rotate over time (so it looks the same on any speed of computer).  Increasing this number causes the ship to more tightly orbit the target point, and decreasing it causes the ship to turn more smoothly.  The final thing I did is check if the ship is flying in the general direction of the target (by checking if the front of the ship is closer to the target than the back).  In that case, I cast the target point onto the ship's x/z plane, and use law of cosines to determine the difference in angle.  If that difference in angle is smaller than the maximum angle it is allowed to turn in the number of milliseconds that have past, then it only rotates the smaller amount (this lines the ship up horizontally with the target point).

Here is the source code so far (probably easier to follow than my poor attempt at an explanation  )

Code Select Expand

        SimpleVector com = centerOfMass.getTransformedCenter();
        SimpleVector fdir = flightDirection.getTransformedCenter();
        float pointDistance = targetPoint.calcSub( fdir ).length();
        float centerDistance = targetPoint.calcSub( com ).length();

        float turnAngleY = yrpm * (float) milisPast;

        if( centerDistance < pointDistance )
        {
            ship.rotateAxis( ship.getYAxis(), turnAngleY );
        }
        else
        {
            SimpleVector initialVector = new SimpleVector( fdir );
            initialVector.y = com.y;
            SimpleVector directionI = initialVector.calcSub( com )
                                                               .normalize();
            SimpleVector finalVector = new SimpleVector( targetPoint );
            finalVector.y = com.y;
            SimpleVector directionD = finalVector.calcSub( com )
                                                               .normalize();
            // Length of the triangle's third side:
            float distC = directionD.calcSub( directionI ).length();

            // Y-angle (unsigned):
            float angle = (float) Math.acos( (2.0f - (distC * distC))
                                                                   / 2.0f );
            if( angle > turnAngleY )
                angle = turnAngleY;

            // Sign the angle:
            if( directionD.x > directionI.x )
                angle = -angle;

            ship.rotateAxis( ship.getYAxis(), angle );
        }
        com = centerOfMass.getTransformedCenter();
        fdir = flightDirection.getTransformedCenter();

        SimpleVector trans = fdir.calcSub( com ).normalize();
        trans.scalarMul( dpm * milisPast );
        ship.translate( trans );

-- EDIT --
I made a simple applet demonstrating this method:
http://www.paulscode.com/source/AutoNavigation/    (Source Code)

As you can see, the ship has a bias to turn counterclockwise, which could be fixed with a little bit more logic on my part if I so desired.

The next thing I am going to add in is verticle navigation.  This will be a bit more tricky, since I don't want the ship to be able to flip upside down.  I'm going to take a look at that AI project code and the rotation upper-limit idea, and see if I can modify it for my purposes.

The final thing I want to add in is a tilt to the ship in whatever horizontal direction it is rotating toward (again, this needs to happen smoothly and have an upper-limit).  Of course this won't have a positive effect on the ship's flight direction, but it should look more realistic, which is what I'm after.  There are a couple of work-arounds I could use to fix this potential problem area.  The first option would be to compensate for the verticle drift this causes by choosing a higher upper-limit for verticle rotations around the ship's x-axis.  The second option would be to make the ship a child of a dummy object, and tilt the child object but not the parent.  That way I could use the parent's "untilted" axis' for vertical and horizontal navigation.  I'm not sure which method will look better, so I'll probably try both and see.

--EDIT #2--
Here's something interesting I just noticed.  The plane always seems to line up with the target point when flying more-or-less into the screen but never when flying toward the camera.  I believe this is due to a small logic error in my code:

Code Select Expand

            if( directionD.x > directionI.x )
                angle = -angle;
I forgot to change these vectors into object-space first, so the angle is being signed incorrectly unless the ship is flying in a net +z direction.   I'm kind of glad I made this mistake, though, because I could actually use this in my game if I wanted the NPC enemy ships to always align with the user when flying toward the camera (I'd only have to convert the vectors into camera space and reverse the angle's sign for the ships to have that behavior).

[C3R14L.K1L4]

Humm, I have been thinking, if you want the 'bodies' to show all those behaviours and more, perhaps the best would be to implement a physics engine (you already have a simple one), and then using some little reactive functions for the ships like:

Code Select Expand

get my destination();
pos = get my position();
apply me my thrust(pos);
//--physics
apply me external forces();
compute coordinates using inertial mass and forces();
//etc...

I.e, according to the ship's desired destination you apply it's thrust (force) and all external forces (whatever they are like friction, gravitational etc.) to the ship's body. Then you compute it's new coordinates from the resulting total force / energy. Remember, in space the ship's inertia mantains it's movement for some time...
(this is a very simplified physics engine but its more than enough for your game )

[paulscode]

I like the way you think   A physics engine might be a bit of overkill for this project, but certainly something I should consider in the future if I wanted to add more reactive capabilities to my ships than just smoothly navigating to random points in 3D (things like colliding with asteroids of various masses or reacting to forces like gravity or weapon strikes).

[C3R14L.K1L4]

LOL!
Glad to help

[paulscode]

I did a bit more work on this today.  I was giving myself a math headache until I had the ingenious idea to convert everything into object space (Duh!  ).

Anyway... it is still only moving along the x/z plane, but I did correct the counterclockwise bias, so the ship seems a little smarter now (use the previous link to see the new demo applet).  I'm hoping to have a little more time to work on it this weekend.

I may start a new thread for this in the Projects section.

[fireside]

The plane doesn't bank when it turns, other than that it looks pretty good.

[paulscode]

Right, I have only added in rotations on the x/z plane so far.  Rotations on the x/y plane and y/z plane are what I will be adding in next.

[paulscode]

For anyone interested, I finally got around to finishing the auto navigation system (between work, school, and my new son I haven't had a lot of time to work on my game).

The math behind a complete physics system is a little beyond my ability at the moment (torque and rotational velocity specifically were giving me a major headache), so I decided to simulate some of the rotation stuff instead.

What I came up with is a root object that navigates on the x/z plane (y-axis rotations), which has a tiltable child (z-axis rotations), which has a liftable child (x-axis rotations), which has the actual plane model as its child.

The root object works exactly as before, rotating and translating along the x/z plane to navigate toward the target's 2D position.  Additionally, the root object now translates linearly along the y-axis to navigate toward the target's y position.

The tilt and lift effects are done by rotating the respective children objects mentioned above, and are merely for the visual effect - those rotations don't actually affect the plane's navigation.

I uploaded an example of the working navigation system:

Auto Navigation Demo  (Source)