Here are two suggestions.

1) Try natural cubic splines. They approximate the minimum energy curve passing through the control points, and thus could be described as the "optimal" path one would take to move through the points. No need to write code for it just yet, though. Play around with this java applet. Put a few points down, and see if the natural cubic spline passing through the points looks reasonable to you. Make sure to change the curve type from "Polynomial" to "Cubic Spline".

2) If a person were walking along and had to go through a certain set of points, he''d probably just travel in something very, very close to a straight line from point to point. The only difference is that he likely wouldn''t instantaneously change direction, as happens with linear interpolation through a set of points. Rather, he''d arc very slightly as he approached each point.

If I remember correctly, a Catmull-Rom spline is a unique curve, i.e. other than specifying the control points, you can''t modify it. So Catmull-Rom splines probably won''t get the job done here. I suggest looking into Kochanek-Bartels curves (sometimes called TCB splines). With these curves, there are four ways to control the curve: you specify the control points (which will be your path waypoints), and also specify the tension, continuity, and bias (hence TCB spline) at each point. Keep the default parameters for bias and continuity, but make the tension at each point very high. This will result in a tightening of the curve at each control point. The end result should be that the curve closely resembles linear interpolation, except that it has slightly smoothed edges at each control point, which I think is exactly what you want.

Kochanek-Bartels curves are essentially a generalization of Catmull-Rom splines, and are a weaker form of a Hermite curve (Catmull-Rom < Kochanek-Bartels < Hermite = Piecewise Cubic Bezier). This page has a useful document on Kochanek-Bartels curves (in the "Curves and Mesh Representations" section), and source code can be found at that site as well.

Good luck.

@sthomas

How can you say that splines give better curves than bezier? They are just two different types of curves with different properties, neither is better than the other.

Personally i''ve used peicewise cubic bezier curves and that works fine for my needs. In this case i would assume it would also be adequate, note that for all of these curves you will not be able to analytically calculate the length of the curves, i.e. you won''t be able to get a constant velocity if you use it directly for movement.

Here are some links for you:

http://astronomy.swin.edu.au/~pbourke/curves/bezier/
http://astronomy.swin.edu.au/~pbourke/curves/bezier/cubicbezier.html
http://astronomy.swin.edu.au/~pbourke/curves/spline/

quote:Original post by SpaceDude
@sthomas

How can you say that splines give better curves than bezier? They are just two different types of curves with different properties, neither is better than the other.

Well it really depends on the application of course. In general though, I think natural cubic splines tend to result in nicer curves than piecewise cubic Bezier curves, for two reasons:

1) Natural cubic splines approximate the minimum energy curve passing through the control points. Minimum energy = minimum curvature = good.

2) Natural cubic splines have C2 continuity at each control point, whereas piecewise cubic Bezier curves only have C1 continuity at each joint.

They''re not going to solve the original poster''s problem, though. He probably needs an AI-specific solution or something.

Thanks for all the suggestions guys, I''m gonna check out the steering behavior stuff, it looks very interesting. From what I saw in that little Java Applet it looks like the steering might provide the results I''m looking for... strange coincidence that gamedev.net was just running the poll about the OpenSteer library, I''ll have to download it.

quote:Original post by sthomas
1) Natural cubic splines approximate the minimum energy curve passing through the control points. Minimum energy = minimum curvature = good.

Curves don''t have energy, so what do you mean by minimum energy curve?

quote:Original post by SpaceDude

quote:Original post by sthomas
1) Natural cubic splines approximate the minimum energy curve passing through the control points. Minimum energy = minimum curvature = good.

Curves don''t have energy, so what do you mean by minimum energy curve?

Here, by "energy", I''m referring to what''s sometimes called the "bending energy" of the curve. It''s defined as the integral of k^2*ds over the curve, where k = curvature and ds = arc length. The lower the bending energy, the less work you have to do to move a particle along the path. Natural cubic splines approximately minimize this bending energy, under the constraint that all the control points are interpolated. Any numerical analysis text should describe this in much greater detail.