# Curved AI pathfinding

This topic is 3728 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

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

##### Share on other sites
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.

##### Share on other sites
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.

##### Share on other sites
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:

##### Share on other sites
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...

##### Share on other sites
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.

##### Share on other sites
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.

##### Share on other sites
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.

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!

##### Share on other sites

This topic is 3728 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.