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.

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?

share|improve this question
    
how do they choose the next point? –  FxIII Nov 16 '11 at 10:42
    
@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? –  Asher Einhorn May 19 '12 at 16:11
add comment

4 Answers

up vote 4 down vote accepted

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.

share|improve this answer
add comment

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

share|improve this answer
    
Well, what if the generated curve suddenly hits an obstacle? –  bummzack Nov 15 '11 at 15:31
    
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. –  Doug.McFarlane Nov 15 '11 at 15:44
    
@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. –  Asher Einhorn Nov 15 '11 at 17:43
    
+1 Paul Bourke is my frickin' hero. –  Nick Wiggill Nov 15 '11 at 18:28
    
@bummzack: add some steering behaviors for obstacle avoidance on top of the curved path generating algorithm. –  imre Nov 16 '11 at 9:46
add comment

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).

share|improve this answer
1  
This would essentially be a Seek behaviour which I suggested. –  Ray Dey Nov 15 '11 at 21:51
add comment

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.

share|improve this answer
add comment

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.