next »

[Theotherguy]

So I'm trying to make my first 3D game, and I've hit a bit of a snag.

I'm trying to make a 3D RTS with a similar sort of control style to the Homeworld series. So far I have the ability to render boxes, spheres and capsules, and apply physics to them. (exciting, I know!)

Right now, I am trying to make a simple AI routine that moves a ship from point A to point B in a somewhat believable fashion. I first tried to do this with a simple pair of PID controllers, one for position and one for orientation, and gave them control over an arbitrary force and torque vector that basically said "You want to be at this 3D point and this set of euler angles. Try to minimize the error by applying forces and torques". This seemed to work alright, but it was not very realistic to see a ship in space just sliding to its target and orientation.

What I want is a more realistic motion, something akin to what an airplane would do -- banking and making curves to get to its target.

I realize now that the problem I am trying to solve is one of non-holonomic constraints on motion in 3D space. This is a problem I've solved for robots before, but its simply giving me a headache.

So, here's the problem:

Suppose I have a vehicle in space that has two methods of control. It can:

A. Apply a thrust vector from an engine in the rear with force t.

B. Rotate to an arbitrary orientation.

Here's a diagram of the vehicle:



How do I get the vehicle from any point in space to any other point in space, given these constraints?

The most obvious solution is "turn towards the target and then fly towards it. Then stop and turn to the orientation you want to be at." But I'm having trouble with even doing this (for instance, how do you turn "towards" something in 3D space?  )

Can anyone lend some help with this?

[Gold Cray]

You can move to any fraction of the angle between the direction you're facing and the direction you want to face by taking a linear combination of the normalized vectors for each. Get the starting angle between the two using cross product, choose the fraction of that angle that you desire, and use that to create your new vector.

[muku]

The most obvious solution is "turn towards the target and then fly towards it. Then stop and turn to the orientation you want to be at." But I'm having trouble with even doing this (for instance, how do you turn "towards" something in 3D space?  )

For general 3D rotations, I'd really recommend ditching Euler angles and instead using quaternions to avoid all the well-known problems (gimbal lock, in particular). Once you have that, you can use quaternion slerp to smoothly interpolate between two orientations.

[Mikademus]

What I want is a more realistic motion, something akin to what an airplane would do -- banking and making curves to get to its target.

Just pitching in a semantic point here: That's not "realistic" in space, what you're looking for is "believable" for a current audience.

Anyway, perhaps this resource on Spacecraft Trajectories might be of some help?
http://fti.neep.wisc.edu/~jfs/neep533.lecture9.trajectories.99.html

[Pishtaco]

The most obvious solution is "turn towards the target and then fly towards it. Then stop and turn to the orientation you want to be at." But I'm having trouble with even doing this (for instance, how do you turn "towards" something in 3D space?  )

I wrote a flight simulator with a simple dogfighting and navigation AI. The navigation AI is unsatisfactory in certain ways so I'll describe the dogfighting one, and maybe it will give you some ideas.

I didn't want to have to learn the maths of quaternions or anything like that, so I decided to use an existing physics library (ODE), originally just to have something to take care of rotations for me, although I ended up using it for much more. Also, I had a working flight model, so rather than having the AI set its own rotation or thrust in a brute-force way, I was able to let it control the engine and the flight surfaces. This had the effect of making the movement more natural, and it was also much simpler conceptually to think of what the AI should do in a given situation.

Say you are aircraft A and you want to fly at aircraft B. There are basically three cases:

1 - B is directly in front of you. Then do fine tuning stuff to keep him in front of you,  rotate to stay aligned with him, and if things are just right, fire.
2 - B is above your nose. Then pull back on the stick, so you pitch up to bring him in front of you.
3 - B isn't directly in front of you or above your nose. Then roll towards him until he is above your nose.

The main trick, and the thing which tells you which case you are in, is to get the unit vector from yourself to B *in your local coordinates*. This means that you let f be a unit vector in the direction of your nose, u be a unit vector pointing up out of the top of your head, and l be a unit vector in the direction of the left wing (or possibly right wing, depending on how things are set up). You want to express a unit vector from A to B as a combination of these. You can do this by dot products, or maybe the physics library will have utility functions to convert from global vectors to ones in a body's own local coordinate system.

Once you have these, if the f component is large, B is in front of you, and you are in case 1 (where to rotate to the same plane as him, you take his up vector and look at it in your local coordinates, to decide which way to roll).

If the u component is positive and the l component has small absolute size, then he is above you and you are in case 2. You should pull back on the stick, and you can even (as a sensible first thing to try), make the amount you pull back proportional to the u component (so long as B isn't actually behind you).

Otherwise you are case 3, and B is to one side (or below you, but let's ignore that). Then if the l component is positive he is to the left and you should roll that way, and if it is negative you should roll the other way. So you just (as a first try) set the displacement of the ailerons proportionally with the l component.

The main problems with using this AI for something other than mindless dogfighting is that it knows nothing about sensible level flight, or even which way is up.

[Theotherguy]

What I want is a more realistic motion, something akin to what an airplane would do -- banking and making curves to get to its target.

Just pitching in a semantic point here: That's not "realistic" in space, what you're looking for is "believable" for a current audience.

Anyway, perhaps this resource on Spacecraft Trajectories might be of some help?
http://fti.neep.wisc.edu/~jfs/neep533.lecture9.trajectories.99.html

I meant "in 3D space" rather than "in outer space." My game's setting is in the atmosphere, and will involve airships and other aircraft.

Also, thanks to pishtaco, that might be the right direction to go in. Perhaps I can just give the AI control over a few things and then use heuristics and sensors to tell it where to go.

Also, I've heard quaternions were much better than euler angles, but I don't know much about them. I was using euler angles because it seemed like the natural extension of "angle" in 2D space, which I know how to control. Also,the physics engine I'm using only allows you to apply torques along arbitrary vectors, so it seemed natural to use pitch-yaw-roll. What I'd really like is the ability to say "I am in this orientation A, and I want to get to orientation B (where A and B are quaternions). What torques should I apply to get there?" Thanks for the suggestion though, muku. I'll do research on quaternions.

[muku]

I was using euler angles because it seemed like the natural extension of "angle" in 2D space, which I know how to control. Also,the physics engine I'm using only allows you to apply torques along arbitrary vectors, so it seemed natural to use pitch-yaw-roll.

That's not quite the same though: pitch-yaw-roll gives you three fixed axes along which you can rotate, while quaternions let you rotate along any arbitrary axis very easily. So I'd say quaternions match the model of the physics engine more closely.

What I'd really like is the ability to say "I am in this orientation A, and I want to get to orientation B (where A and B are quaternions). What torques should I apply to get there?" Thanks for the suggestion though, muku. I'll do research on quaternions.

I'm not sure if by torque you mean the physical concept, or just the axis and angle to rotate about. The latter is easy with quaternions: just compute C = A^-1 * B; this will be the quaternion representing the rotation from orientation A to orientation B. (Inverting a quaternion is a very cheap and simple operation, as opposed to inverting a 4x4 matrix.) If you want the axis and the angle, use this formula to convert the quaternion C to axis-angle representation. So basically you need three things: representing an axis-angle rotation as a quaternion, inverting a quaternion, and multiplying two quaternions. Every one of the dozens if not hundreds of quaternion tutorials on the internet will teach you about those. If you have troubles, feel free to ask here!

[Theotherguy]

I now have a simple "turn towards a point and fly to it AI" based on quaternions! Thanks for your help, muku.

[muku]

Wow, that was fast! Good job. Nice that I could help.

[Theotherguy]

XNA has a lot of neat Quaternion functions. It was as simple as doing a few conversions and lerping.:D

Now onto my next technical challenge: I want to be able to select all the units inside a box. This is easy in 2D, especially if you're using a quad tree. However, it doesn't seem so simple to me in 3D. Right now, I can select stuff by casting a ray from the mouse, but this only allows me to select one thing at a time. I'm thinking about doing the brute force method of casting a ray from each pixel inside the selection rectangle, or a subsampling of it, but this is undoubtedly too expensive. Is there a better way to do this? Maybe by intersecting things with a huge rectangle that extends out from the screen?

[muku]

Maybe by intersecting things with a huge rectangle that extends out from the screen?

Basically this, except what you're looking to intersect with is something like a rectangular cone; the technical term is frustum, so you might want to check with the XNA documentation if something like this already exists. If not, basically you need to set up four planes for the edges of this cone, with their normal vectors pointing inside; an object is inside the cone if it is inside with respect to each of the four planes. Such plane-vertex checks are very cheap, basically it's just one dot product.

EDIT: This might help: http://www.gamedev.net/community/forums/topic.asp?topic_id=435736

[Theotherguy]

Alright, I'm getting pretty close to having the selection mechanism done, but I think I'm doing it wrong. The physics library I'm using doesn't support collisions with frustums, so I'm trying to reconcile XNA's built in frustum collisions with JigLib's system. I can currently select all the units visible to the screen, but I'm having trouble selecting a sub-section of the screen. I think it has something to do with the fact that if the projection matrix of a camera changes, its view matrix ought to change as well. I'll keep at it, but I think I've nearly got it. Once I do, I should be able to select units and move them around to points in space!

[deemen]

Why not invert the problem and instead project your units into screen space. Then you can do a regular box collision.

You'll probably need to do this anyway to display HUD elements like health bars and such; might as well store the result in a quad tree or other data structure and use it for selecting units. (Not to mention your graphics hardware is doing it as well)

I can't think of a good way of creating a "subfrustum" from camera data and a rectangle :/.

[Theotherguy]

Wow, that's a great idea deemen, I did just that, and implemented a working selection model in exactly 45 seconds  Thanks a lot!

[deemen]

Cheers!