Curved AI pathfinding

Started by
7 comments, last by Maverick Programmer 16 years, 6 months ago
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? Free Image Hosting at www.ImageShack.us 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!
Advertisement
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.
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.
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:
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!
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.
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
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!
...
Hey thanks!
Holy crap, you can read!

This topic is closed to new replies.

Advertisement