优化穿透子弹瞄准

发表于 更新于 本文字数： 3.2k 阅读时长 ≈ 12 分钟

背景

某些穿透型子弹弹道较粗，如果索敌模式选择最近的敌人，就会“耿直”地以最近的敌人为目标发射子弹，导致索敌看起来很呆，只命中很少的敌人。其实很多时候，目标周围有很多敌人，由于弹道较粗，只要稍微调整下发射角度就可以命中一堆敌人。

问题定义

穿透型宽弹道的子弹，可以看作一个矩形弹道，子弹起点 start （取 XZ 平面的二维坐标），初始方向 dir ，子弹射程 length ，子弹半宽 halfWidth ，给定主目标 targetEntity ，在保证主目标包含在这个矩形区域内，调整弹道角度，期望以覆盖更多敌人。

一开始会想针目标计算左右边界角度 [targetMinAngle, targetMaxAngle] ，然后以子弹起点为圆心，射程为半径进行怪物查询，查询后对每个目标依次求得 [monsterMinAngle, monsterMaxAngle] 边界，最后求得最大重叠区域的角度。但是这其中的关键点是角度，处理过程中会频繁进行角度、三角函数、反三角函数的转换，这在定点数游戏里一方面性能开销较大，另一方面多次转换后误差也会叠加。

问题转换

首先为了简单起见，其他怪物的度量区间是以主目标方向为主的相对度量区间。考虑到对局中子弹只会向前发射，发射角度是半平面，也就是180°。希望在这个限制条件下，用三角函数的某个中间表达来表征角度区间，需要它能够和角度正相关，同时可以和正余弦方便进行转换。 tan(θ) 看起来是一个比较理想的表达，它在 [-π/2, π/2] 是单调递增的函数。但是在这个区间，它是无界函数，如果用它来表征区间，那么数值会极端发散，不利于后处理。那如果是 tan(θ/2) 呢？在给定的定义域情况下，它的值域是 [-1, 1] ，看起来非常的理想，此外我们还可以用半角公式方便地和 sin(θ) 、 cos(θ) 进行转换：

$$
sin(θ) = \cfrac{2tan(\cfrac{θ}{2})}{1+tan^2(\cfrac{θ}{2})}
$$

$$
cos(θ) = \cfrac{1 - tan^2(\cfrac{θ}{2})}{1 + tan^2(\cfrac{θ}{2})}
$$

$$
tan(\cfrac{θ}{2}) = \cfrac{sin(θ)}{1 + cos(θ)} = \cfrac{1 - cos(θ)}{sin(θ)}
$$

因此，本问题的解决思路里最重要的一点是，将怪物形成的角度区间，改为基于主目标方向相对角度的 tan(θ/2) 区间。下文中所述的“区间”中的“值”，皆指代以主目标为基准的相对角度 θ 的半角正切 tan(θ/2)

实现

主目标最终允许偏转的区间

计算主目标偏转区间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static Fix FindBestParameter(...)
{
    var targetHalFixarameter = GetHalfAngleParameter(targetDistance, halfWidth);
    var targetMin = -targetHalFixarameter;
    var targetMax = targetHalFixarameter;
    // ...
}

private static Fix GetHalfAngleParameter(Fix distance, Fix halfWidth)
{
    if (distance <= halfWidth)
        return Fix.One;

    var adjacent = FixMath.Sqrt(distance * distance - halfWidth * halfWidth);
    return halfWidth / (distance + adjacent);
}

扫描候选区怪物

处理怪物候选区间

代码中先构建垂直三角形，其中有效半宽取弹道半宽和与怪物距离的最小值，意味着距离小于半宽的敌人，其所产生区间是整个半平面。

随后通过点积求得主目标方向的投影距离，而叉积则求得与主目标方向垂直的投影距离，注意叉积顺序，这里怪物在主目标方向左侧时，叉积结果是正的，反之为负。需要再次强调，这里求得的 localForward 和 localSide 可以理解为，在主目标所张成的坐标系 (F, L) 里的坐标，其中 F 代表主目标方向， L 代表主目标向左旋转 90° 的方向。之所以是向左因为我们叉积顺序是 Cross(F, offset) offset 在主目标方向左侧为正。

上图中下排的左侧是计算瞄准怪物时，最大偏转区间所形成的三角函数；下排右侧是计算怪物方向与主目标方向夹角所形成的三角函数。

处理怪物候选区间

随后通过三角函数和差角公式，将怪物区间偏移转换到主目标方向的局部坐标里，公式解释如上图。再通过 AddBoundaryParameter 调用半角公式求得对应角度的半角正切值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
private static void AddCandidateIntervals(...)
{
    if (distanceSqr <= Fix.Zero)
    {
        AddInterval(targetMin, targetMax);
        return;
    }

    // 构造命中边界需要的直角三角形
    var distance = FixMath.Sqrt(distanceSqr);
    var effectiveWidth = FixMath.Min(halfWidth, distance);
    var adjacent = FixMath.Sqrt(FixMath.Max(distanceSqr - effectiveWidth * effectiveWidth, Fix.Zero));
    var localForward = Fix2.Dot(baseDirection, offset);
    var localSide = Fix2.Cross(baseDirection, offset);
    var inverseDistanceSqr = Fix.One / distanceSqr;

    // [0]: 主目标最小参数
    // [1]: 主目标最大参数
    // [2]: 怪物命中区间左边界
    // [3]: 怪物命中区间右边界
    Span<Fix> points = stackalloc Fix[4];
    points[0] = targetMin;
    points[1] = targetMax;
    var pointCount = 2;

    // 把怪物坐标转换到主瞄准方向的局部坐标系（和差角公式）
    // cos(θ - α) = cos(θ)cos(α) + sin(θ)sin(α)
    // sin(θ - α) = sin(θ)cos(α) - cos(θ)sin(α)
    var minCos = (localForward * adjacent + localSide * effectiveWidth) * inverseDistanceSqr;
    var minSin = (localSide * adjacent - localForward * effectiveWidth) * inverseDistanceSqr;
    pointCount = AddBoundaryParameter(points, pointCount, minCos, minSin, targetMin, targetMax);

    // cos(θ + α) = cos(θ)cos(α) - sin(θ)sin(α)
    // sin(θ + α) = sin(θ)cos(α) + cos(θ)sin(α)
    var maxCos = (localForward * adjacent - localSide * effectiveWidth) * inverseDistanceSqr;
    var maxSin = (localSide * adjacent + localForward * effectiveWidth) * inverseDistanceSqr;
    pointCount = AddBoundaryParameter(points, pointCount, maxCos, maxSin, targetMin, targetMax);

    // 以实际偏转角度计算怪物是否命中，产出命中区间
    SortAndCompact(points, ref pointCount);
    Span<bool> segmentHits = stackalloc bool[3];
    for (var i = 0; i + 1 < pointCount; i++)
    {
        var midpoint = (points[i] + points[i + 1]) * Fix.Half;
        segmentHits[i] = ContainsAtParameter(localForward, localSide, midpoint, halfWidth);
    }

    var inRun = false;
    var runStart = Fix.Zero;
    for (var i = 0; i + 1 < pointCount; i++)
    {
        if (segmentHits[i])
        {
            if (!inRun)
            {
                inRun = true;
                runStart = points[i];
            }
        }
        else if (inRun)
        {
            AddInterval(runStart, points[i]);
            inRun = false;
        }
    }

    if (inRun)
        AddInterval(runStart, points[pointCount - 1]);
}

private static int AddBoundaryParameter(Span<Fix> points, int count, Fix cosine, Fix sine, Fix targetMin, Fix targetMax)
{
    if (cosine < Fix.Zero)
        return count;

    // tan(θ/2) = sin(θ) / (1 + cos(θ))
    var parameter = sine / (Fix.One + cosine);
    if (parameter >= targetMin && parameter <= targetMax)
        points[count++] = parameter;
    return count;
}

private static bool ContainsAtParameter(Fix localForward, Fix localSide, Fix parameter, Fix halfWidth)
{
    // 公式组成独立计算
    var parameterSqr = parameter * parameter;
    var oneMinusParameterSqr = Fix.One - parameterSqr;
    var twiceParameter = 2 * parameter;
    var denominator = Fix.One + parameterSqr;

    var forwardNumerator = localForward * oneMinusParameterSqr + localSide * twiceParameter;
    var sideNumerator = FixMath.Abs(localSide * oneMinusParameterSqr - localForward * twiceParameter);
    return forwardNumerator >= Fix.Zero && sideNumerator <= halfWidth * denominator;
}

上方代码中 ContainsAtParameter 是判断“使用某个半角参数 parameter 对应的方向发射时，当前怪物中心是否位于矩形弹道内。”，本质是向量二维旋转，但是由于坐标轴里X是左为正，所以和标准旋转矩阵还是有些差异的，可以从不同角度来理解这个过程。下图给出五种不同的理解角度：

判断目标位于相对旋转下的矩形框内

上图的推导殊途同归，总结起来有如下两个视角：

  • 弹道坐标旋转 θ 角度
    • 怪物世界坐标不变
    • 求怪物在新的坐标轴下的局部坐标

这叫被动坐标变换：向量没变，观察它的坐标系变了

  • 怪物向量旋转 -θ 角度
    • 原弹道坐标轴不变
    • 求旋转后向量在原坐标轴下的坐标

这叫主动向量变化：坐标系没变，向量变了。两者是对同一问题的不同观察。

在得到用正弦余弦的转换关系后，再用正切的半角公式，将 tan(θ/2) 带入进去，就会得到代码里的形式了，此处不再赘述。

扫线求最优偏转

取区间中点作为稳定代表。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
private static Fix ScanBestParameter()
{
    var activeCount = 0;
    var bestCount = -1;
    var bestParameter = Fix.Zero;

    for (var i = 0; i < _eventCache.Count;)
    {
        var parameter = _eventCache[i].Parameter;
        var starts = 0;
        var ends = 0;
        do
        {
            if (_eventCache[i].Delta > 0)
                starts++;
            else if (_eventCache[i].Delta < 0)
                ends++;
            i++;
        } while (i < _eventCache.Count && _eventCache[i].Parameter == parameter);

        activeCount += starts;
        // 不偏转方向可以精确表示，单独参与比较。
        if (parameter == Fix.Zero && IsBetter(activeCount, parameter, bestCount, bestParameter))
        {
            bestCount = activeCount;
            bestParameter = parameter;
        }
        activeCount -= ends;

        // 开区间内命中集合不变，取中点作为稳定的代表方向。
        if (i < _eventCache.Count && parameter < _eventCache[i].Parameter)
        {
            var interiorParameter = (parameter + _eventCache[i].Parameter) * Fix.Half;
            if (IsBetter(...))
            {
                bestCount = activeCount;
                bestParameter = interiorParameter;
            }
        }
    }

    return bestParameter;
}

还原最优命中偏转角

最后利用求得的 parameter 也就是半角正切值还原到正余弦，然后再利用标准的二维旋转矩阵，求得最终的发射方向。

1
2
3
4
5
6
7
8
9
private static Fix2 DirectionFromParameter(...)
{
    var parameterSqr = parameter * parameter;
    var inverse = Fix.One / (Fix.One + parameterSqr);
    var cosine = (Fix.One - parameterSqr) * inverse;
    var sine = 2 * parameter * inverse;
    return new Fix2(baseDirection.x * cosine - baseDirection.y * sine,
        baseDirection.x * sine + baseDirection.y * cosine).normalized;
}

拓展

sin(θ)

前面说到，度量选择 tan(θ) 一方面是它作为中间表达，在定义域里是递增的，且在计算过程中不需要和真实角度打交道。其实在这个定义域里 sin(θ) 也是完全满足的。之所以不采用它，是因为在计算过程中，它需要开平方求 cos(θ)，对性能有一定影响。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
/// <summary>
/// 主目标边界满足 sin(θ) = w / d。
/// 偏转范围限制在 -90°~90°，sin(θ) 在该范围内单调且值域为 -1~1。
/// </summary>
private static FP GetHalfAngleParameter(FP distance, FP halfWidth)
{
    if (distance <= halfWidth)
        return FP.One;

    return halfWidth / distance;
}

private static int AddBoundaryParameter(Span<FP> points, int count, FP cosine, FP sine,
    FP targetMin, FP targetMax)
{
    // sin(θ) 只在 -90°~90° 内能唯一表示方向。
    if (cosine < FP.Zero)
        return count;

    if (sine >= targetMin && sine <= targetMax)
        points[count++] = sine;
    return count;
}


/// <summary>
/// 使用某个 sin(θ) 对应的方向发射时，当前怪物中心是否位于矩形弹道内。
/// 在以 baseDirection 为朝上的局部坐标系中：
///     localForward ≈ 局部 Y
///     localSide    ≈ 局部 X（叉积，正左负右）
/// </summary>
private static bool ContainsAtParameter(FP localForward, FP localSide, FP sine, FP halfWidth)
{
    // 当前角度限制在 -90°~90°，因此 cos(θ) 始终取非负根。
    var cosine = TSMath.Sqrt(TSMath.Max(FP.One - sine * sine, FP.Zero));

    // forward = localForward x cos(θ) + localSide x sin(θ)
    var forward = localForward * cosine + localSide * sine;
    // side = abs(localSide x cos(θ) - localForward x sin(θ))
    var side = TSMath.Abs(localSide * cosine - localForward * sine);
    return forward >= FP.Zero && side <= halfWidth;
}


private static TSVector2 DirectionFromParameter(TSVector2 baseDirection, FP sine)
{
    var cosine = TSMath.Sqrt(TSMath.Max(FP.One - sine * sine, FP.Zero));
    return new TSVector2(baseDirection.x * cosine - baseDirection.y * sine,
        baseDirection.x * sine + baseDirection.y * cosine).normalized;
}

改为右侧为正

调整下求 localSide 的叉积顺序，可以变为右侧为正，将右侧改为第一个轴，就完全等同于标准二维坐标系了，以 (R, F) 为坐标系的情况下 ContainsAtParameter 里可以直接用标准二位旋转矩阵。（再次赘述：前面左侧为正的时候，也可以 (F, L) 坐标系下直接用标准二维旋转矩阵）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
private static void AddCandidateIntervals(TSVector2 baseDirection, TSVector2 offset, FP distanceSqr,
            FP halfWidth, FP targetMin, FP targetMax)
{
    if (distanceSqr <= FP.Zero)
    {
        AddInterval(targetMin, targetMax);
        return;
    }

    // 构造命中边界需要的直角三角形
    var distance = TSMath.Sqrt(distanceSqr);
    var effectiveWidth = TSMath.Min(halfWidth, distance);
    var adjacent = TSMath.Sqrt(TSMath.Max(distanceSqr - effectiveWidth * effectiveWidth, FP.Zero));
    var localForward = TSVector2.Dot(baseDirection, offset);
    // 局部 X 轴向右为正，局部 Y 轴沿主目标方向向前为正。
    var localRight = TSVector2.Cross(offset, baseDirection);
    var inverseDistanceSqr = FP.One / distanceSqr;

    // [0]: 主目标最小参数
    // [1]: 主目标最大参数
    // [2]: 怪物命中区间左边界
    // [3]: 怪物命中区间右边界
    Span<FP> points = stackalloc FP[4];
    points[0] = targetMin;
    points[1] = targetMax;
    var pointCount = 2;

    // 偏转角使用经典二维约定：逆时针为正，即从前方向左偏转。
    // 因此怪物方位角 θ 满足：cos(θ) = localForward / distance，sin(θ) = -localRight / distance。
    // cos(θ - α) = cos(θ)cos(α) + sin(θ)sin(α)
    // sin(θ - α) = sin(θ)cos(α) - cos(θ)sin(α)
    var minCos = (localForward * adjacent - localRight * effectiveWidth) * inverseDistanceSqr;
    var minSin = (-localRight * adjacent - localForward * effectiveWidth) * inverseDistanceSqr;
    pointCount = AddBoundaryParameter(points, pointCount, minCos, minSin, targetMin, targetMax);

    // cos(θ + α) = cos(θ)cos(α) - sin(θ)sin(α)
    // sin(θ + α) = sin(θ)cos(α) + cos(θ)sin(α)
    var maxCos = (localForward * adjacent + localRight * effectiveWidth) * inverseDistanceSqr;
    var maxSin = (-localRight * adjacent + localForward * effectiveWidth) * inverseDistanceSqr;
    pointCount = AddBoundaryParameter(points, pointCount, maxCos, maxSin, targetMin, targetMax);

    SortAndCompact(points, ref pointCount);
    Span<bool> segmentHits = stackalloc bool[3];
    for (var i = 0; i + 1 < pointCount; i++)
    {
        var midpoint = (points[i] + points[i + 1]) * FP.Half;
        segmentHits[i] = ContainsAtParameter(localForward, localRight, midpoint, halfWidth);
    }

    var inRun = false;
    var runStart = FP.Zero;
    for (var i = 0; i + 1 < pointCount; i++)
    {
        if (segmentHits[i])
        {
            if (!inRun)
            {
                inRun = true;
                runStart = points[i];
            }
        }
        else if (inRun)
        {
            AddInterval(runStart, points[i]);
            inRun = false;
        }
    }

    if (inRun)
        AddInterval(runStart, points[pointCount - 1]);
}

/// <summary>
/// 使用某个半角参数 parameter 对应的方向发射时，当前怪物中心是否位于矩形弹道内。
/// 在以 baseDirection 为朝上的局部坐标系中：
///     localForward ≈ 局部 Y
///     localRight   ≈ 局部 X（右正左负）
/// parameter 对应的角度使用逆时针为正，即正值向左偏转。
/// </summary>
private static bool ContainsAtParameter(FP localForward, FP localRight, FP parameter, FP halfWidth)
{
    // 公式组成独立计算
    var parameterSqr = parameter * parameter;
    var oneMinusParameterSqr = FP.One - parameterSqr;
    var twiceParameter = 2 * parameter;
    var denominator = FP.One + parameterSqr;

    // forward = localForward x cos(θ) - localRight x sin(θ)
    //         = (localForward x (1 - t²) - localRight x 2t) / (1 + t²)
    var forwardNumerator = localForward * oneMinusParameterSqr - localRight * twiceParameter;
    // right = localRight x cos(θ) + localForward x sin(θ)
    //       = (localRight x (1 - t²) + localForward x 2t) / (1 + t²)
    var rightNumerator = TSMath.Abs(localRight * oneMinusParameterSqr + localForward * twiceParameter);
    // 第一个条件：因为分母 1 + t² 一定大于零，所以下面第一个条件判断分子大小即可
    // 第二个条件：abs(局部 X) <= 弹道半宽
    return forwardNumerator >= FP.Zero && rightNumerator <= halfWidth * denominator;
}

之前采用的左侧为正，所以 localSide > 0 代表左侧，怪物偏转角 φ > 0 也是逆时针的，向左 两者方向一致，所以：

1
2
cosφ = localForward / distance
sinφ = localSide / distance

而现在改为右侧为正，两者就是反向的，所以:

1
2
cosφ = localForward / distance
sinφ = -localSide / distance

所以上面的和差角公式里符号有些差异。