JavaScript "pixel"- 使用数学(可能是线性代数)旋转 Sprite 的完美碰撞检测

Question

我正在用 JavaScript 制作 2D 游戏。为此，我需要能够“完美地”检查两个 Sprite 之间的碰撞，这些 Sprite 具有 x/y 位置(对应于它们的中心)、弧度旋转，当然还有已知的宽度/高度。

经过数周的工作(是的，我什至没有夸大其词)，我终于想出了一个可行的解决方案，不幸的是，结果证明它太慢了大约 10,000 倍，并且无法以任何有意义的方式进行优化。我完全放弃了从 Canvas 上实际绘制和读取像素的想法。那只是不会削减它，但请不要让我详细解释原因。这需要通过数学和“想象的”2D 世界/网格来完成，通过与众多人交谈，基本思想变得显而易见。然而，实际实现并非如此。这是我要做的和想做的:

我已经做过的事

在程序开始时，每个 Sprite 都在其默认的垂直位置进行像素透视，并用与图像的 alpha channel 对应的数据填充一维数组:实心像素用 1 表示，透明像素表示按 0。见图 3。

这背后的想法是，那些 1 和 0 不再代表“像素”，而是“相互之间距离完美的小数学球体”，它们可以旋转而不会“丢失”或“添加”数据，就像像素一样，如果您可以一次旋转 90 度以外的任何图像。

我自然会先快速进行“边界框”检查，看看我是否应该费心进行准确计算。这个做完了。问题是罚款/“确定”检查...

我想不通的

现在我需要确定 Sprite 是否确实发生碰撞，我需要使用“线性代数”(我不知道)构建某种数学表达式，以确定这些“数据点的矩形”，定位和旋转正确地，两者在重叠位置都有一个“1”。

虽然理论很简单，但实现这一点所需的实际代码简直超出了我的能力范围。我已经盯着代码看了好几个小时，问了很多人(并且有很多问题清楚地解释了我的问题)并且真的付出了努力。现在终于想放弃了。我非常非常感谢完成这项工作。我什至不能通过使用库来放弃和“作弊”，因为我发现的任何东西都无法从我所知的范围内解决这个问题。它们对我来说都是不可能理解的，并且似乎有完全不同的假设/要求。无论我在做什么，似乎总是一些特殊情况。这很烦人。

这是程序相关部分的伪代码:

function doThisAtTheStartOfTheProgram()
{
    makeQuickVectorFromImageAlpha(sprite1);
    makeQuickVectorFromImageAlpha(sprite2);
}

function detectCollision(sprite1, sprite2)
{
    // This easy, outer check works. Please ignore it as it is unrelated to the problem.
    if (bounding_box_match)
    {
        /*

            This part is the entire problem.
            I must do a math-based check to see if they really collide.

            These are the relevant variables as I have named them:

                sprite1.x
                sprite1.y
                sprite1.rotation // in radians
                sprite1.width
                sprite1.height
                sprite1.diagonal // might not be needed, but is provided

                sprite2.x
                sprite2.y
                sprite2.rotation // in radians
                sprite2.width
                sprite2.height
                sprite2.diagonal // might not be needed, but is provided

                sprite1.vectorForCollisionDetection
                sprite2.vectorForCollisionDetection

            Can you please help me construct the math expression, or the series of math expressions, needed to do this check?
            To clarify, using the variables above, I need to check if the two sprites (which can rotate around their centre, have any position and any dimensions) are colliding. A collision happens when at least one "unit" (an imagined sphere) of BOTH sprites are on the same unit in our imaginated 2D world (starting from 0,0 in the top-left).

        */

        if (accurate_check_goes_here)
            return true;
    }

    return false;
}

换句话说，“accurate_check_goes_here”就是我想知道它应该是什么。当然，它不需要是一个单一的表达，我更愿意看到它在“步骤”中完成(带有注释!)，以便我有机会理解它，但请不要将其视为“勺子喂养”。我完全承认我数学很烂，这超出了我的能力。这只是一个事实。我想继续前进，研究我自己可以真正解决的问题。

澄清一下:由于性能原因，一维数组是一维而不是二维。事实证明，速度在 JS World 中非常重要。
虽然这是一个非盈利项目，完全是为了让私有(private)满意，但我只是没有时间和精力订购和坐下来看一些数学书，从头开始学习。我并不以缺乏对我有很大帮助的数学技能而自豪，但在这一点上，我需要完成这个游戏，否则我会发疯。这个特殊的问题使我长时间无法完成任何其他工作。

我希望我已经很好地解释了这个问题。然而，最令人沮丧的感觉之一是当人们发送善意的回复时，不幸的是，这表明帮助的人没有阅读问题。我不是在侮辱你们所有人——我只是希望这次不要发生!对不起，如果我的描述很差。我真的尽力做到完全清楚。

好的，所以我需要“声誉”才能发布我花时间创作的插图来说明我的问题。所以我改为链接到他们:

插图

(由 Stackoverflow 审查)

(由 Stackoverflow 审查)

好的。这个网站不会让我什至链接到图像。只有一个。然后我会选择最重要的一个，但如果我能链接到其他人，那会很有帮助......

Answer 1

首先，您需要了解无法使用单个/简单方程来检测此类碰撞。因为 Sprite 的形状很重要，而这些是由宽度 x 高度 = 面积位的数组描述的。所以算法的最坏情况复杂度必须至少为 O(Area)。

这是我将如何做到的:

用两种方式表示 Sprite :

1) 指示像素不透明位置的位图，

2) 不透明像素的坐标列表。 [可选，用于加速，在空心 Sprite 的情况下。]

选择像素列表最短的 Sprite 。找到将这个 Sprite 的局部坐标转换为另一个 Sprite 的局部坐标的刚性变换(平移 + 旋转)(这是线性代数发挥作用的地方 - 旋转是 Angular 差，平移是两者之间的向量左上 Angular - 见 http://planning.cs.uiuc.edu/node99.html)。

现在扫描不透明像素列表，将像素的本地坐标转换为另一个 Sprite 的本地坐标。通过查找位图表示来检查您是否落在不透明像素上。

这需要最坏的 O(不透明区域)坐标变换 + 像素测试，这是最佳的。

如果您的 Sprite 被放大(大像素)，作为第一个近似值，您可以忽略缩放。如果需要更高的精度，可以考虑对每个像素采样几个点。精确计算将涉及方形/方形碰撞相交算法(带旋转)，更复杂且成本更高。见 http://en.wikipedia.org/wiki/Sutherland%E2%80%93Hodgman_algorithm .