优化穿透子弹瞄准

发表于 本文字数： 1.8k 阅读时长 ≈ 6 分钟

背景

某些穿透型子弹弹道较粗，索敌又是以最近目标优先，因此经常“耿直”地锁定最近敌人，直接发送子弹，导致索敌看起来很呆，只命中很少的敌人。但是很多时候，目标周围有很多敌人，由于弹道较粗，只要稍微调整下发射角度就可以命中一堆敌人。

问题定义

穿透型宽弹道的子弹，可以看作一个矩形弹道，子弹起点 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(θ) 区间。下文中所述的“区间”中的“值”，皆指代以主目标为基准的相对角度 θ 的半角正切 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);
}

扫描候选区怪物

处理怪物候选区间

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

随后通过点积求得主目标方向的投影距离，而叉积则求得与主目标方向垂直的投影距离，注意叉积顺序，这里怪物在主目标方向左侧时，叉积结果是正的，反之为负。

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

处理怪物候选区间

随后通过三角函数和差角公式，将怪物区间偏移转换到主目标方向的局部坐标里，公式解释如上图。再通过 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是左为正，所以和标准旋转矩阵还是有些差异的，具体推导如下图。

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

扫线求最优偏转

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

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;
}