1

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

4

2 回答 2

3

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

于 2012-04-11T09:23:06.337 回答
0

如果你的精灵有一个最大尺寸，你可以对你的数组进行排序并跳过比较屏幕上 vert+maxsize 较低的东西......

于 2012-04-16T21:28:28.437 回答