Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

I'm implementing A* waypoint pathfinding with some twists. One of the problems I'm encountering is because I do not change velocities of the agents directly but rather I do so through forces.

Which gives me the following problem: let's suppose the path consists of three nodes,

P0 = the starting position P1 = node 1 P2 = node 2

When the agent starts moving, it's first target position is P1. The agents moves in that direction because I let a force F act on it's velocity: F=normalized(targetPos-agentPos)*agentAccel*agentMass;

The agent reaches P1.

Now the agent's target position is P2, and upon it will act a force in the direction of (targetPos-agentPos).

However, this is a centripetal force, meaning that the agent will most likely orbit around P2 instead of popping the next node off the path (unless the angle between [P0,P1] and [P1,P2] is small) Stopping the agent at each node is not an option (would look unnatural) What should really happen is the velocity of the agent gradually shifting towards 100% the direction of [targetPos-agentPos], and the velocity should be completely 'shifted' before a certain distance(dX) is laid off, starting from the previous node position

In order to solve this problem, only one parameter is adjustable:

  • F_dir: the direction of the force acting upon the agent, that's supposed to lead the agent to the next node.

The values of the following parameters are known:

  • agentAcceleration (=the magnitude of the force vector)
  • agentVelocity
  • agentPosition
  • node positions
  • targetPosition (= the next node on the path)

I've been trying some different strategies with trial and error to prevent this, but it seemed rather messy, so my question is, what is a decent approach to this problem?

share|improve this question
    
Are you doing frictionless, Newtonian physics like in a space sim or do you have high sideways friction like a car or airplane? –  Patrick Hughes Apr 23 '12 at 19:49
    
@PatrickHughes For this problem, friction may be ignored. Although if anyone knows the answer to the problem with friction I'd be more than happy to hear it too –  xcrypt Apr 23 '12 at 19:53
2  
I think this answer is related: How to prevent homing entities from orbiting their targets –  John McDonald Apr 23 '12 at 20:25

2 Answers 2

As much as I can tell you can use beizer curves to smooth the path. I know it's not physical at all, but just create a beizer curve with order of 2, from each three points in the path. this way character will not path exactly over all the waypoints but it'll move over a path which can be an actual physical shape's path. you can also check for the collision along the way to solve issues about the object moving through the walls, since beizer curves will go through the wall.

share|improve this answer
    
Well I actually want to allow my agents to experience external forces(not due to the path) as well, eg explosions. That is why I'd prefer not to use bezier curves. –  xcrypt Apr 23 '12 at 20:22
1  
if an object is hit by an explosion you can recompute beizer curve to make it look affected. –  Ali.S Apr 23 '12 at 22:15
1  
Recomputing such Bezier curves is not even that costly, so one can do it at each time step.. if required to interact with random forces all the time. –  teodron Apr 24 '12 at 9:50

Note: know that with constant acceleration your speeds will soon become ludicrous if the path is even moderately straight.

Mode 1: Cheat. Use the path points to define a hermite spline then use velocity and acceleration to define how fast, it will look reasonable to audiences brought up on Star Wars and Battlestar Galactica physics. (this is basically faking sideways friction)

Mode 2: Cheat less. Realize that passing directly through the path points is not necessary, allowing a radius to trigger arrival will stop the orbiting behavior you are talking about.

Mode 2.5: (I think this will work) You left out current direction of movement, in physics terms "velocity" is simply a speed. Take the direction your agent is currently moving and that's vector V1, now take the direction directly to the new point and call that vector V2. Get the angle between V1 and V2 and create a vector V3 that is -angle from V1 and this will be your F_dir vector. Note that it does not point directly at the next point, but appears to over-compensate by pushing too far - but that's self correcting because over time V1 will approach a heading directly at the next point.

Mode 2.5a: Since your acceleration is constant and the agent's velocity is constantly changing the real angle to move your force's direction vector won't be as I described in 2.5 above but instead will have to over and under compensate based on relative velocity versus force, but that's beyond my math to describe beyond that. (ie. a very slow agent doesn't require as much angle to get headed the right way, while a very fast one would require extreme measures to bring into line).

share|improve this answer
1  
there is a maximum speed limit :) Also, velocity =/= speed, even in physics. At least that's what I've always been told. –  xcrypt Apr 23 '12 at 20:42
    
I have also tried something like [2.5] before, it works a little, but it's messy –  xcrypt Apr 23 '12 at 20:48
    
@xcrypt Yes, velocity is speed+direction, I had a brain meltdown there for a minute =( Don't completely discount splines, hermite works from point+tangent to control its curves and can act as a cheap approximation since you're enforcing an upper bound on speed. –  Patrick Hughes Apr 23 '12 at 21:03

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.