How are you guys resolving NPC positions in your games? Right now in our game the steering and formation code is determining an optimal position for each NPC as they move through the world, which largely works on the x-z plane. However, we need to resolve the y component of an NPCs position, as well as have external forces modify the position of NPCs (ie gravity). So given a desired direction and magnitude, I see two options:
 
1. Assume the NPC stepped however much it wanted to that frame, then add a constant artificial value to the y component, and let the NPC "fall" for a given distance. An example would be, move the NPC up by .25m, then fall for .5m. If the NPC doesn't hit anything on his instantaneous "fall", then it can be assumed the NPC stepped off the edge of a cliff or something equally foolish, and then they switch to a state in which gravity takes over.
 
2. Use a rigid body physics package to resolve positions. Use the direction vector for where we want the NPC to go and apply this as a momentum to the NPC's physics object. Right now I'm thinking the ideal geometry for this would be an inverted cone, where the point of the cone represents the tip of the characters feet. The height of the cone would dictate the maximum vertical height the NPC could climb (ie, stairs). This is nice because external forces are now implicitly solved by the physics simulator.
 
Problems:
 
1. If your step-up value is too low, you may enter a state of improper falling. For instance, if you attempt to climb a large slope and for the given step at that frame, you needed to move up by .3m, in our example, we would start falling until we found something solid under-foot. Also, we want our step-up value to be constant, and not dependent on time, otherwise if we had a dip in framerate, we might allow the character to warp up to the next level in a multfloor building; this implies that we have to have a sufficiently large step-up (and fall down), yet one that isn't too big such as to cause the character to jump up cliffs.
 
2. NPC movement code because much more complicated. Steering and formation code now no longer have the ultimate say on where NPCs are positioned, and have to be told where they are (this currently breaks our formation code, but if this is a workable solution, I'm willing to accept that). How about sliding on gentle slopes? If our cone is axis locked (which it would be) the tip of the cone is going to be the only contact point with a near-level terrain, however gravity would probably be constantly pulling it down -- can this be fixed by offering very high friction coefficients?
 
Both of these techniques offer some ugly problems, and neither one is really looking all that good to me (although I prefer the second, simply because I haven't done it yet :). What's the third option, or how have you gotten around the problems that I have? Better yet, what problems are there with the second approach that I haven't hit yet?