Hi guys,

Given an autonomous agent, and a path made up of 2D vertices (and some kind of seek behaviour) how does one "smooth" the path to make the agent's movement look more natural and graceful?

For example, instead of taking a hard right turn, i would like the agent to follow a smooth curve.

Could someone please point me in the right direction?

Thanks,

Mike

You might want to check out Catmull-Rom splines (a sub-set of Hermite splines).

Catmull Rom can work, but there is no guarantee it won't send the object into an obstacle

This is an interesting article about path smoothing:

http://aigamedev.com/open/tutorials/theta-star-any-angle-paths/

You may also try String-Pulling, the first google search turned up a post on this forum actually:

http://www.gamedev.net/topic/539575-string-pulling-explained/

Oh, and the old classic:

http://www.gamasutra.com/view/feature/131505/toward_more_realistic_pathfinding.php

If you're just concerned about the appearance of the motion then you could just have the agent use steering behaviors to move between nodes and avoid brushing against corners.

Thanks for the great reply guys, I will have a look at all your suggestions.

Mike

To clarify a little, what I mean is, you tesselate the map and set node coords at the barycenter of the tesselated regions, then just have agents steer toward the node in the next region until they're in the region of their target (or alternatively when they have LoS on the target you can abandon pathing and switch to a more direct chase). Instead of moving directly from node to node you just approach a node until you enter its region, then start steering toward the next one.

[attachment=28101:steering.png]

In that image, the black is walls, S and F are start and finish, the blue is the tesselation boundaries and the node positions. The sickly lime green is the path that the agent will follow. Note that it moves toward the node in the next region, then when it enters the region it turns toward the next node without reaching the one it was just seeking. Upon entering the region containing the target it just goes straight for the target.

I had a similar issue with working out a racing line for user generated racing tracks.

In the end I integrated the curve until I got an acceptable minimum distance.

I'll see if I still have the code knocking around, and post it for your pleasure.

The simplest way to do this is when you're making the path. If you have a weight map of some kind just increase the weight value near objects you don't want to walk near. Like walls. Think of it like a density or gradient function. This works better with some games/techniques than others.

Here's another easy but very natural looking solution. The trick is to not smooth the path but to follow it in a smooth manner.

1.) Get the position on the (unsmoothed) path that is closest to your character.

2.) Starting from that position move along the path towards the goal by a small distance to get the target position. (1m works well for humans)

3.) Let your character approach that target position.

4.) Next frame when the characters position has changed repeat with step 1.

The smoothness of the resulting path depends on your agents agilty and the ahead distance but it's usually very natural and easy to tweak.

Here's another easy but very natural looking solution. The trick is to not smooth the path but to follow it in a smooth manner.

1.) Get the position on the (unsmoothed) path that is closest to your character.

2.) Starting from that position move along the path towards the goal by a small distance to get the target position. (1m works well for humans)

3.) Let your character approach that target position.

4.) Next frame when the characters position has changed repeat with step 1.

The smoothness of the resulting path depends on your agents agilty and the ahead distance but it's usually very natural and easy to tweak.

That's basically a simple steering behavior. Nothing wrong with it, just wanted to point out what it is, the nice part about it is that it's easy to then add enemy avoidance to a system like that. One does have to be careful with objects that are very slow to turn or decelerate/accelerate though.