如何仅访问数组中的一对元素一次

How to visit a pair of elements in an array only once?

本文关键字：元素 一次 访问 数组 何仅      更新时间：2023-09-26

我正在为一个小型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++具有几乎相同的语法）。

你不会避免 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

如果你的精灵有最大大小，你可以对数组进行排序，跳过比较屏幕上 vert+maxsize 较低的内容......

相关文章：