## [Algorithms] Resolving NPC positions

 [Algorithms] Resolving NPC positions From: Ryan Greene - 2004-04-30 06:03:10 Attachments: Message as HTML ```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?```

 [Algorithms] Resolving NPC positions From: Ryan Greene - 2004-04-30 06:03:10 Attachments: Message as HTML ```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?```