4 replies to this topic

[Xcrypt]

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?

[Reedbeta]

You could try using Catmull-Rom splines for the path following. These generate a smooth curve that passes through a list of waypoints, and you can use the second derivative of the spline for the acceleration.

With an force/acceleration-based approach, I expect you'll have to implement some sort of negative-feedback "steering" to keep the agent from going off course due to integration error buildup, etc. Fortunately you can use the spline position and first derivative as desired position and velocity at any given time, to implement a steering system.

The other problem you might run into is that the splines don't stay on the straight line between the waypoint - they swing out a little bit to keep the curves smooth. This can cause problems since A* will often put waypoints right next an obstacle, so you might find that the spline ends up clipping through the obstacle. You might have to dilate the obstacles a bit when running A* to avoid this, although that can cause its own set of problems - e.g. a narrow gap between two obstacles becomes impassable. Alternatively, maybe there's a way to take the A*-generated path and fix it up afterward to resolve any clipping issues.

[fireside]

It seems like, if you have the force locally pushing the character forward from behind, then all you have to do is steer the character by rotation. Adding friction may help if there is some sliding. Generally, using forces for character motion doesn't work very well, but it does simplify collision response. What I found to work the best was a cylinder. Some people use a ball, I think, with a cylinder above. If you are using someone else's physics system, it really takes some playing around.

[Stainless]

But having a force instead of just following the path can lead to really nice game play artifacts.

Like nudging the inside of a vehicle and seeing it plough into an obstacle.

Or the effect of changing friction along the path.

I wrote a robot racer type of game a long time ago, and watching the cars trying to handle ice patches and oil slicks was amazing fun.

(probably incredibly nerdy as well )

[Xcrypt]

Fun, yes, but very error prone. I wish there were some phd thesis or something on this subject.