12
\$\begingroup\$

Currently my very basic AI framework has agents that move along a a jagged path made up of a series of points.

nav path

They do this by simply moving their position from one point to the next. When they reach the next point they move towards the next and so on. How can I change this so that they move smoothly along a curved version of the path, and how do I generate the curve?

Improve this question
\$\endgroup\$
2
  • \$\begingroup\$ how do they choose the next point? \$\endgroup\$
    – FxIII
    Nov 16, 2011 at 10:42
  • \$\begingroup\$ @FxIII sorry I didn't see this comment before - do you mean how do they chose a new search target or how do they chose the next point in the search? \$\endgroup\$
    – Dollarslice
    May 19, 2012 at 16:11

4 Answers 4

Reset to default
4
\$\begingroup\$

You're after some sort of path smoothing. Of course, as bummzack pointed out you also want to make sure that any path smoothing that you perform results in legal movements for your agents.

This article from Gamasutra explains pretty much everything you need to know, including path smoothing, legal turns and realistic, smooth turning algorithms.

Another alternative, which is slightly simpler, is to use a Seek behaviour with a small bounding circle/sphere to check whether the agent is at or close to the next point in the path.

Improve this answer
\$\endgroup\$
7
\$\begingroup\$

Since you already know your control points, you just need to update your interpolation code to use an algorithm for curvature (Hermite or Cosine, for example).

These sites offer a great explanation and sample code that should get you started:

Paul Bourke Interpolation Methods

Sol::Tutorials - Interpolation Tricks

Improve this answer
\$\endgroup\$
4
  • \$\begingroup\$ Well, what if the generated curve suddenly hits an obstacle? \$\endgroup\$
    – bummzack
    Nov 15, 2011 at 15:31
  • \$\begingroup\$ This is just for the movement of the agents, per frame. The same collision detection algo would still apply. When a collision is detected, either change the control points to avoid the object (difficult), or temporarily start using another movement algo. \$\endgroup\$
    – Doug.McFarlane
    Nov 15, 2011 at 15:44
  • \$\begingroup\$ @bummzack that's a good point, and the answer is to use a navigation mesh and smooth your curves accordingly, however for now I'm just going to get this working with a simple nav graph and so I'll just solve this by only smoothing the paths a bit. \$\endgroup\$
    – Dollarslice
    Nov 15, 2011 at 17:43
  • \$\begingroup\$ @bummzack: add some steering behaviors for obstacle avoidance on top of the curved path generating algorithm. \$\endgroup\$
    – imre
    Nov 16, 2011 at 9:46
0
\$\begingroup\$

I'm going to go against the grain here and suggest that, instead of pre-generating your curves, just handle it on a frame-by-frame basis, using (for example) the same logic you'd use to create a homing-missile.

This will be much easier, and probably more realistic because you don't need special-cases for when there are walls between two points - you just handle collision detection as usual.

The downside is the movement will look sub-optimal. The object will always take the most direct path from one waypoint to the next, meaning, unlike with a spline, he won't start turning towards waypoint 3 until he has already passed waypoint 2. Depending on your situation, this may or may not be fixable by adjusting your waypoints (if it's even a problem).

Improve this answer
\$\endgroup\$
1
  • 1
    \$\begingroup\$ This would essentially be a Seek behaviour which I suggested. \$\endgroup\$
    – Ray Dey
    Nov 15, 2011 at 21:51
0
\$\begingroup\$

The path finder should give you the path and you should not modify that. I belive that it is possible to modify your path finder algorithm to take into account that path with sharp turns are wrose than those with smooth curves as it already does with long path vs short ones.

I will post here some solution if I can find a moment to think about it deeply, but i think this is the way to go.

Improve this answer
\$\endgroup\$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .