什么是找到距离某个位置最近的非碰撞矩形的有效方法

Question

对于我正在处理的2D游戏，我在基于矩形的简单碰撞检测中使用y轴排序。这工作正常，现在我想在给定的位置有效地找到最接近空矩形的。我怎样才能做到这一点？有算法吗？

我可以想到一个简单的强力网格测试（每个网格都是我们正在寻找的空白空间的大小），但显然这是缓慢的，甚至不是一个完整的测试。

Answer 1

考虑使用四叉树来存储矩形。 有关更多信息，请参阅http://en.wikipedia.org/wiki/Quadtree。

Answer 2

如果您已经在使用轴排序，那么您可能已经计算出了按其位置排序的矩形列表。

也许我误解了，但是你能不能只看看问题矩形前后的两个矩形，并决定哪一个更接近？如果您正在讨论寻找距离任意点最近的矩形，那么您可以简单地遍历列表，直到找到第一个矩形的位置大于任意点的位置，然后使用该矩形和前一个矩形作为两个矩形比较。