代码之家 › 专栏 › 技术社区 › Morrowless

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

collision-detection language-agnostic algorithm

4

Morrowless · 技术社区 · 15 年前

对于我正在研究的一个二维游戏,我在一个简单的基于矩形的碰撞检测中使用Y轴排序。这个工作很好,现在我想找到 最近的 在给定位置使用给定大小的空矩形,效率很高。我该怎么做?有算法吗?

我可以想到一个简单的蛮力网格测试(每个网格的大小与我们正在寻找的空白空间相同),但显然这是一个缓慢的,甚至不是一个完整的测试。

2 回复 | 直到 15 年前

1

Patrick 15 年前

考虑使用四叉树来存储矩形。见 http://en.wikipedia.org/wiki/Quadtree 更多信息。

2

0

Jordan Lewis 15 年前

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

也许我是误解了,但你能不能看一下这个矩形前后的两个矩形,然后决定哪个更接近?如果你要找一个离任意点最近的矩形,那么你可以简单地浏览这个列表,直到你找到第一个位置比任意点大的矩形,然后用这个矩形和它前面的那个矩形作为比较。