c++ - 检查大网格上的放置重叠

Question

我正在开发一款游戏，您可以在该游戏中将通过连接器连接的建筑物放置在矩形网格上。什么都不能重叠。建筑物和连接器一旦在网格上就不能改变；它们可以随时被摧毁。网格的定义使得左下角为 (0,0)。

建筑物是矩形的，每条边的长度可以是 1 - 4 个单位；还有一个 5x5 的正方形。

连接器有一个起点和一个终点。它们不能重叠，并且有 1 个单位宽。他们可以走直线编辑:(左、右、上、下)并在任何地方弯曲 90 度。无限长度。

理想情况下，网格会非常大(200x200 或更大)，但这意味着可能有成千上万个这样的对象和连接器。

构建对象时，我需要检查它是否与任何对象重叠。如果我制作一个比特网格，它的大小将超过 300x300。如果我列出所有对象，我可以在一定范围内搜索，但我将如何处理连接器？

鉴于二维位数组是不可能的，我必须为所有建筑物编制索引，并按 x 坐标对它们进行排序，然后按 y 坐标对它们进行排序。我可以对连接器进行线性搜索，但这会非常乏味和痛苦。

有人有什么建议吗？附言我在 C++ 中这样做

Answer 1

除了 300x300 并不大，如果你真的想要你可以将你的 bool 值打包成一个字节的位(但出于速度原因我不建议这样做)你可以检查连接器是否与一个简单的函数相交:https://stackoverflow.com/a/565282/2436175

假设您已经检查过您的新建筑物不与任何其他建筑物相交，剩下要检查的是您的新建筑物(部分)的一侧不与您已经到位的任何连接器相交.