找到最接近某个位置的非碰撞矩形的有效方法是什么
对于我正在开发的 2D 游戏，我在简单的基于矩形的碰撞检测中使用 y 轴排序。这工作正常，现在我想高效地找到给定位置处给定尺寸的最近空矩形。我该怎么做？有算法吗？
我可以想到一个简单的强力网格测试（每个网格的大小都是我们正在寻找的空白空间的大小），但显然这很慢，甚至不是一个完整的测试。
For a 2D game I am working on, I am using y axis sorting in a simple rectangle-based collision detection. This is working fine, and now I want to find the nearest empty rectangle at a given location with a given size, efficiently. How can I do this? Is there an algorithm?
I could think of a simple brute force grid test (with each grid the size of the empty space we're looking for) but obviously this is slow and not even a complete test.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
考虑使用四叉树来存储矩形。
请参阅 http://en.wikipedia.org/wiki/Quadtree 了解更多信息。
Consider using quad-trees to store your rectangles.
See http://en.wikipedia.org/wiki/Quadtree for more information.
如果您已经在使用轴排序，那么您可能已经计算了按位置排序的矩形列表。
也许我误解了，但是你能不能只看一下所讨论的矩形之前和之后的两个矩形，然后决定哪个更接近？如果您正在谈论找到距离任意点最近的矩形，那么您可以简单地遍历列表，直到找到位置比任意点更大的第一个矩形，然后使用该矩形和它之前的矩形作为两个矩形进行比较。
If you're already using axis sorting, then presumably you've computed a list of your rectangles sorted by their positions.
Perhaps I am misunderstanding, but could you not just look at the two rectangles before and after the rectangle in question, and decide which one is closer? If you're talking about finding the closest rectangle to an arbitrary point, then you could simply walk through the list until you find the first rectangle with a greater position than your arbitrary point, and use that rectangle and the one before it as the two to compare.