Curved AI pathfinding

Author

100

October 02, 2007 09:52 PM

We all know that in AI, a path can be found between two points by simply subtracting/adding to get to the point:


if(X<xPath1)
{
X+=1;
}
else if(X>xPath1)
{
X-=1;
}

if(Y<yPath1)
{
Y+=1;
}
else if(Y>yPath1)
{
Y-=1;
}

This process, however, results in a straight line. Now it is possible to add several points in between the destinate point to simulate a slight 'curve' but this would be sloppy. To have a curve, you can have just have 2 points, you'll need three. Sow how then, would you find a curved path between three points?

Though the third model symbols a slightly curved 'V', it would be better for that 'V' to have been a 'U' type curve if you undertsand. Thank you

Holy crap, you can read!

KulSeran

3,272

October 02, 2007 10:01 PM

Bezier Curves(wikipedia) would probably do what you want. It just means
you need to calculate a couple control points perpendicular to each path segment so that you can create your curve.

Steadtler

220

October 02, 2007 10:16 PM

Bezier curves are a good idea, eazy to implement with de Casteljau. However, you will not pass exactly by the point you provided, which can cause problems. You will find this problem with any form of geometric smoothing, as smoothing a corner always makes you will always pass "inside" the corner.

I find it much easier to solve this in locomotion rather than in pathfinding, as it is a locomotion problem, not a pathfinding one. Simply navigate the path to arrive at your destination with an orientation corresponding to the tangent of the corner (if it was smooth), and with a speed invertly proportional to the sharpness of the corner.

Alrecenk

400

October 03, 2007 07:19 AM

Quote: Original post by Steadtler
Simply navigate the path to arrive at your destination with an orientation corresponding to the tangent of the corner (if it was smooth), and with a speed inversely proportional to the sharpness of the corner.

This can be done fairly easily using a hermite spline, which allows you to specify points and their derivatives along the curve:

Maverick Programmer

Author

100

October 03, 2007 07:42 AM

Quote:
I find it much easier to solve this in locomotion rather than in pathfinding, as it is a locomotion problem, not a pathfinding one. Simply navigate the path to arrive at your destination with an orientation corresponding to the tangent of the corner (if it was smooth), and with a speed invertly proportional to the sharpness of the corner.

Locomotion problem, eh? Thanks for the term. I'm not very experienced in this field.

Thanks for the info guys, that really helped. Now to implement that...

Holy crap, you can read!

Steadtler

220

October 03, 2007 11:57 AM

Quote: Original post by PCN
Quote:
I find it much easier to solve this in locomotion rather than in pathfinding, as it is a locomotion problem, not a pathfinding one. Simply navigate the path to arrive at your destination with an orientation corresponding to the tangent of the corner (if it was smooth), and with a speed invertly proportional to the sharpness of the corner.

Locomotion problem, eh? Thanks for the term. I'm not very experienced in this field.

Thanks for the info guys, that really helped. Now to implement that...

Most people will use navigation, I think. Ive always been bad with terminology.

Extrarius

1,412

October 03, 2007 05:09 PM

Be aware that if you're searching an actual spatial graph, simply modifying the path between nodes is not guaranteed to work. You character could end up walking off a cliff, for example, when you nudge the path off of the straight line. You'll need to store extra information in your nodes and edges in order to accomidate differing paths between nodes.

"Walk not the trodden path, for it has borne it's burden." -John, Flying Monk

Stoic

368

October 03, 2007 05:21 PM

Hello,

Just to throw my hat in the ring, I'd also recommend looking at Catmull-Rom Splines, especially if you're following a path with several waypoints. Catmull Rom splines are guaranteed to connect all their points without any additional parameters, except additional points at the beginning and end of the path.

Link

Bezier curves have one advantage over Catmull Rom splines in that the curve is guaranteed to be within the control polygon between the points. (This could be useful on say, a polygon based navigation mesh). Catmull Rom splines don't make this guarantee, but they are a little simpler to use.

Anyhow, hope this helps!

...