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

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

collision-detection language-agnostic algorithm

Morrowless · 技术社区 · 14 年前

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

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

2 回复 | 直到 14 年前

Patrick 14 年前

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

Jordan Lewis 14 年前

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

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

推荐文章

John V · 是否存在单元测试无法发现的逻辑/流错误类型?

7 年前

Beefster · 为什么ANSI颜色转义以“m”而不是“]”结尾?

7 年前

Guillermo Gutiérrez · STR转换是如何工作的?

7 年前

RudziankoÅ · 合并排序数组算法

7 年前

user8852560 · 构造函数中的验证和构造函数冲突

7 年前

SuperHeroY · 在大于8x8的棋盘上进行象棋移动验证?[已关闭]

7 年前

jav974 · 订购产品时寻找最佳价格组合的算法

7 年前

hippietrail · 确定浮点数中前导零的数量

7 年前

Will Da Silva Alex Martelli · 如何确定具有s边的多边形的数字是否为多边形

7 年前

LaoJiu · 为什么在文本编辑器的查找函数中选择“BM算法”而不是“周日算法”?

7 年前