简单的效率问题C++ （内存分配）..也许一些碰撞检测有帮助？

Question

我正在用 C++ 编写一个类似街机的小游戏（多向 2d 空间射击游戏），并且正在完成碰撞检测部分。

以下是我的组织方式（我只是编造出来的，所以它可能是一个糟糕的系统）：

每艘船都由圆形组件组成 - 每艘船中的组件数量是任意的（更多组件，更多 CPU 周期）。 我有一个 maxComponent 距离，是在创建船舶时计算的，这基本上是我可以从船舶中心到最远组件边缘绘制的最长线。 我跟踪屏幕上的内容，并使用 maxComponentDistance 来查看它们是否足够接近以发生碰撞。

如果它们非常接近，我就会开始检查不同船舶的组件是否相交。 这就是我的效率问题出现的地方。

我有组件相对于船舶中心的 (x,y) 位置，但它没有考虑船舶当前如何旋转。 我保持它们是相对的，因为我不想每次船舶移动时都重新计算组件。 因此，我有一个用于旋转计算的小公式，并返回一个对应于相对于船舶中心的旋转考虑位置的二维向量。

碰撞检测位于 GameEngine 中，并且使用 2d 向量。 我的问题是关于返回类型。 我是否应该在每次调用该函数时创建并返回一个 2d 向量对象 或者 我应该给该组件对象一个额外的私有二维向量变量，在调用函数时编辑私有变量，并返回指向该对象的指针吗？

我不确定内存分配的效率与拥有永久、可编辑、私有变量的效率。 我知道还必须为私有变量分配内存，但不是每次检查冲突时都分配内存，只有在创建新组件时才分配内存。 在我的环境中，组件并不是恒定的，因为它们会在飞船被摧毁时被删除。

这是我的主要困境。 我也非常感谢任何有关我的实际碰撞检测系统设计的指示。 这是我第一次对此进行破解（也许应该阅读一下）

提前致谢。

Answer 1

您绝对应该尽量避免在每次调用 getter 函数时为组件向量分配内存。 相反，尽可能少地进行分配。 例如，您可以在船舶的组件组成发生变化时执行此操作，甚至很少发生（通过过度分配）。

当然，您也可以研究内存池，在内存池中预先分配大量此类组件并将其放入池中，以便您可以在恒定时间内分配新组件。

作为进行这种碰撞检测时的一般要点（如果太明显的话，我们深表歉意）：计算距离的平方，而不是计算平方根。 :)

Answer 2

如果你的 2D 向量只是：

 class Vector2D { double x, y; };

那么一定要返回它！ 例如：

  Vector2D function( ... );

或者通过引用传递：

  void function( Vector2D * theReturnedVector2D, ... );

不惜一切代价避免：

 vector<double> function(...);

Vector 类固有的常量堆分配/释放是一个错误！

---

从计算角度来说，复制您自己的 Vector2D 类非常便宜。 与 Vector<> 不同，您自己的 Vector2D 类可以合并您喜欢的任何方法。

我过去曾使用此功能来合并distanceToOtherPointSquared()、scanfFromCommandLineArguments()、printfNicelyFormatted() 和operator[](int) 等方法。

---

或者我应该给该组件对象一个额外的私有二维向量变量，在调用函数时编辑私有变量，并返回指向该对象的指针？

多个函数调用使先前的数据无效。 这是灾难的根源！

Answer 3

1. 您可以从返回一个向量开始，然后对其进行基准测试。 谁知道呢，它可能足够快。 使用分析器，您甚至可以查看哪些部分占用了运行时间。
2. 您可以使用内存池来重用向量并减少复制
3. 您可以尝试坐标的享元模式，以减少复制和分配（如果它们在整个引擎中重复）。
4. 将数据保留在组件中是减少分配的好方法，但会在设计中引入一些陷阱，例如谁使用向量取决于组件的生命周期。 内存池可能更好。

Answer 4

不要使用 2D 矢量。 相反，使用点的向量。 对于碰撞检测也是如此。 这里使用二维向量是错误的数据结构。

根据函数的内容，编译器将能够执行 NRVO（即 命名返回值优化）这意味着在最佳情况下，返回向量没有开销，即它永远不会被复制。 但是，只有当您使用函数的返回值来初始化新实例，并且编译器能够跟踪函数内部的执行路径并查看每个返回路径返回相同的对象时，才会发生这种情况。 请考虑以下两点：

vector<int> f(int baz) {
    vector<int> ret;
    if (baz == 42)
        ret.push_back(42);
    return ret;
}

vector<int> g(int baz) {
    if (baz == 42)
        return vector<int>(1, 42);
    else
        return vector<int>();
}

编译器可以对 f 的调用执行 NRVO，但不能对 g 的调用执行 NRVO。

Answer 5

在堆上分配内存和在堆栈上分配内存有很大区别。 在堆上分配，例如使用 new/delete 或 malloc/free 非常慢。 在堆栈上分配确实非常快。 对于堆栈，通常最慢的部分是复制对象。 因此，请注意向量等，但返回简单的结构可能是可以的。