javascript - 如何只访问数组中的一对元素一次？

Question

我正在为一个小型 2D 游戏编写物理程序，我需要对照屏幕上的每个其他对象检查屏幕上的每个对象。那是 O(N^2)，我不太喜欢这样。

我的想法是:

for (var i = 0; i < objects.length; i ++)
    for (var j = 0; j < objects.length; j ++)
        if (collide(objects[i], objects[j])) doStuff(objects[i], objects[j]);

这是不必要的，我会多次检查相同的对象。我怎样才能避免这种情况？我想到了一个矩阵，它是 n*n(假定 n 是对象的数量)，然后每次我访问一对对象时，我都会这样做:

visited[i][j] = 1;
visited[j][i] = 1;

然后，我将始终知道我访问了哪一对对象。

这会起作用，但是，我再次需要设置所有这些单元格，n*n 次，只是为了在开始时将它们全部设置为 0 !也许，我可以将所有内容都设置为 []，但这对我来说仍然不是一个可行的解决方案。还有更好的吗？

很明显，我选择的语言是 Javascript，但我对 C、C++ 和 Python 比较流利，所以你可以用它们来回答(尽管 Javascript、C 和 C++ 的语法几乎相同)。

Answer 1

你不会避免 O(n^2)，但你可以将它减少一半:

for (var i = 0; i < objects.length; i ++)
    for (var j = i; j < objects.length; j ++)
        if (collide(objects[i], objects[j])) doStuff(objects[i], objects[j]);

假设碰撞是对称的。如果它也是自反的，并且碰撞测试很昂贵，您可以将 doStuff(object[i], object[i]) 移出内循环以避免碰撞测试并从开始内循环i+1