飞机自动寻路
背景
最近在做自己第一款独立游戏 移动战区,其中有一种类型的炮台是以飞机为攻击载体,因此需要给飞机设计AI.需求如下:
- 需要有漂亮的飞行轨迹
- 目标点移动,轨迹需要相应变动
- 轨迹变动应该时连续的
- 飞机移动时能控制移动速度
方案
- 选择一种曲线方式,来描述飞机的轨迹
- 计算曲线长度的方式
- 通过路径长度求坐标位置的方式
- 动态且连续修改贝塞尔曲线
贝塞尔曲线
寻路使用三阶贝塞尔曲线,因为三阶贝塞尔曲线平滑,且可以同时控制飞机的起飞点,起飞方向,目标点,目标方向.
image.png
下图为三阶贝塞尔曲线表达式:
image.png
计算贝塞尔曲线长度
方案一:折线法
对贝塞尔曲线在t∈[0,1]区间进行平均采样,将采样点连起来求长度.
这种方法比较原始,效率较低
[Obsolete]
public static float Distance(Vector3 p1, Vector3 p2, Vector3 p3, Vector3 p4, int sampleCount)
{
float result = 0;
Vector3 prev = p1;
for (int i = 0; i < sampleCount; i++)
{
Vector3 cur = Bezier3Th(p1, p2, p3, p4, i * 1f / sampleCount);
result += (cur - prev).magnitude;
prev = cur;
}
return result;
}
方案二:不知名玄学方法
参考 https://stackoverflow.com/questions/29438398/cheap-way-of-calculating-cubic-bezier-length
一种比较便宜的长度计算方法
public static float Distance(Vector3 p0, Vector3 p1, Vector3 p2, Vector3 p3)
{
float chord = (p3-p0).magnitude;
float contNet = (p0 - p1).magnitude + (p2 - p1).magnitude + (p3 - p2).magnitude;
return (contNet + chord) / 2;
}
方案三: Guass-Lengendre积分(最终方案)
参考
如何得到贝塞尔曲线的曲线长度和 t 的近似关系？ - 饭后温柔的回答 - 知乎
https://www.zhihu.com/question/27715729/answer/310580409
参考答案用的是二阶贝塞尔函数,二阶比较简单是可以求导的,而三阶贝塞尔过于复杂,无法求导.
因此我采用近似法,(f(t + 0.0001f) - f(t)) / 0.0001f
/** Guass-Lengendre积分 五阶权重表 **/
private static readonly double[] GuassLengendreWn =
{
0.5688888888888889,
0.4786286704993665,
0.4786286704993665,
0.2369268850561891,
0.2369268850561891
};
private static readonly double[] GuassLengendreXn =
{
0.0000000000000000,
-0.5384693101056831,
0.5384693101056831,
-0.9061798459386640,
0.9061798459386640,
};
public static float GuassLengendreDistance(Vector3 p1, Vector3 p2, Vector3 p3, Vector3 p4,float t)
{
double r = 0f;
for (int i = 0; i < GuassLengendreWn.Length; i++)
{
double dt = t / 2 * GuassLengendreXn[i] + t / 2;
r += GuassLengendreWn[i] * Derivative(p1,p2,p3,p4,dt);
}
return (float) r * t / 2;
}
// 导数
public static float Derivative(Vector3 p1, Vector3 p2, Vector3 p3, Vector3 p4,double dt)
{
return (Bezier3Th(p1, p2, p3, p4, (float)dt + 0.0001f) - Bezier3Th(p1, p2, p3, p4, (float)dt)).magnitude * 10000;
}
通过路径长度求坐标位置的方式
同样参考
如何得到贝塞尔曲线的曲线长度和 t 的近似关系？ - 饭后温柔的回答 - 知乎
采用了牛顿迭代法
https://www.zhihu.com/question/27715729/answer/310580409
public static float GetFixedLenghtTValue(Vector3 p1, Vector3 p2, Vector3 p3, Vector3 p4,float l)
{
float l1 = GuassLengendreDistance(p1, p2, p3, p4, 1);
if (l >= l1)
{
return 1;
}
float a = l / l1;
for (int i = 0; i < 10; i++)
{
a -= (GuassLengendreDistance(p1, p2, p3, p4, a) - l) / Derivative(p1, p2, p3, p4, a);
}
return a;
}
动态且连续修改贝塞尔曲线
为什么要动态修改贝塞尔曲线,因为目标点发生了变化,按照原来的贝塞尔曲线是无法飞到想要的目的地的.
但是如果直接修改目标点,那么曲线无法连续变化,表现出来就是飞机会一直打圈.
因此最终的修改方案是,贝塞尔曲线的四个控制点,起始位置,起始方向,目标方向不变化,只变化目标位置,这样就是连续的了.
这里的方案是乱试试出来的,也不知道具体原理.
