Jump to content
  • Advertisement
Sign in to follow this  
Maverick Programmer

Curved AI pathfinding

This topic is 4033 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
Advertisement
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
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!