处理统一网格中的碰撞

Question

所以目前我正在尝试开发一个 2D 游戏，其中我有不同大小的不同对象。为了性能，我决定为碰撞使用统一的网格。

我了解到对于每个对象，我们将它们存储在网格的相应单元格中以检查碰撞。但是由于我们的对象不是一个点而是一个矩形，所以在某些情况下我们需要将对象存储在多个单元格中（例如当对象重叠多个单元格时）。

当我尝试使用链表实现这个数据结构时出现了问题。对于包含对象链接列表的统一网格数组，每个对象都包含一对指向同一单元格中的上一个和下一个对象的指针。这意味着如果我在单元格 1 中有对象 A、B、C，如果对象 B 重叠，我不能使对象 B 位于多个单元格中，因为对象 B 已经指向单元格 1 中的对象 A 和 C，并且它可以不再指向单元格 2 中的任何其他对象。

一个简单的解决方案就是使用向量或数组，但是有更好的解决方案吗？

Answer 1

使用元素包装器，如下所示：

class Wrapper {
public:
  Object *obj;
  Wrapper *next, *prev;
}

然后在网格中存储 Wrapper 而不是 Object。