Sign in to follow this  

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.

If you intended to correct an error in the post then please contact us.

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? 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

Share this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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.

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!

Share this post


Link to post
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.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this