# Determine if AI can traverse a given spline

I have some AI Agents that I want to navigate along a spline. The agents have a speed and a maximum turning radius. For some splines the curvature is too tight for the AI agents to navigate around and they end up shooting of the spline and then turning, which looks weird. How can I take a given spline and find the segments that are too tightly curved for a given agent to traverse without shooting off?

I thought about just taking the angle between control points, but that alone won't account for the speed limitations that I want to impose as well. Can someone point me in the right direction?

I am using Curvy for my spline implementation but using my own agent movement system to walk along the splines. http://www.fluffyunderware.com/pages/unity-plugins/curvy.php

If I understand correctly, what you want to compute is the spline's radius of curvature at each point. Then you want to compare that value to an agent's turning radius to determine if the agent will leave the track there. 

To do this, you need to calculateR(s)as you see here: https://en.wikipedia.org/wiki/Curvature (under "Curvature of plane curves" > "Precise definition")

I don't believe Curvy offers second derivativesT'(s)(possibly because some of its spline algorithms do not have continuous second derivatives). So, I'll see if I can cook up an approximation here using Curvy's API: 

So, we haveT(s)for free, just using Curvy's CurvySplineBase.GetTangent(float)method. We can use this call to estimate T'(s). Here I am taking the average of just before and just after, but in practice it may not matter, and it does complicate the endpoint code somewhat.

public bool checkCurvature(float position, CurvySpline spline, Agent agent)
{
// This may be too small a difference for Curvy - try larger values
//   if it behaves poorly.
float epsilon = float.epsilon;

// You'll need to enhance this to account for the beginning/end
//   of the spline (s = 0.0 or 1.0)
Vector3 tanPrev = spline.GetTangent(position-epsilon);
Vector3 tanCurr = spline.GetTangent(position);
Vector3 tanNext = spline.GetTangent(position+epsilon);

Vector3 prevDiff = tanCurr-tanPrev;
Vector3 nextDiff = tanNext-tanCurr;

// average the two, hopefully a better approximation
Vector3 acceleration = (prevDiff + nextDiff) / (2.0f*epsilon); // dT / ds

float curvature = acceleration.magnitude(); // k(s)
float radius = 1.0f/curvature; // R(s)

// if the agent can turn faster than the curve at this point, return true
{
return true;
}
return false;
}


Notes:

 You may be using a different interpretation of "maximum turning radius" than I am here - perhaps yours is a diameter instead of radius, so you may need to divide by 2. (Or multiplyR(s)by 2)

 I do not have Curvy right now so I haven't compiled this or tested it. Sorry. :)

• this awesome, thanks a lot for your help, I'll give this a shot tonight – weichsem Jun 27 '15 at 18:57