2D 游戏：快速（最快）找到另一个实体的 x 个最接近实体的方法 - 大量实体，高度动态
我正在开发一款具有大量动态实体的 2D 游戏。 为了好玩，我们就称他们为士兵吧，假设有 50000 人（我只是随机想到的，可能多了也可能少了:)）。
所有这些士兵都按照规则移动每一帧——想想群体/聚集/转向行为。 对于每个士兵，为了更新其运动，我需要与我正在处理的士兵最接近的 X 个士兵。
存储它们以促进这样的计算而不需要太多开销的最佳空间层次结构是什么？ （所有实体每帧都会更新/移动，因此它必须很好地处理动态实体）
I'm working on a 2D game that has a huge amount of dynamic entities.
For fun's sake, let's call them soldiers, and let's say there are 50000 of them (which I just randomly thought up, it might be much more or much less :)).
All these soldiers are moving every frame according to rules - think boids / flocking / steering behaviour.
For each soldier, to update it's movement I need the X soldiers that are closest to the one I'm processing.
What would be the best spatial hierarchy to store them to facilitate calculations like this without too much overhead ?
(All entities are updated/moved every frame, so it has to handle dynamic entities very well)
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
对于宽相碰撞检测，空间索引，如四叉树（因为它是二维的）或者一个网格就可以了。 我之前链接过 Metanet Software 的教程； 它概述了一个基于网格的方案。 当然，您的游戏甚至不需要如此广泛地使用网格。 只需将每个角色存储在隐藏的网格中，然后将其与相同和相邻单元格中的对象进行碰撞即可。
For broad-phase collision detection, a spatial index like a quad-tree (since it's 2D) or a grid will do. I've linked to Metanet Software's tutorial before; it outlines a grid-based scheme. Of course, your game doesn't even need to use grids so extensively. Just store each actor in a hidden grid and collide it with objects in the same and neighboring cells.
最简单的方法是使用网格。 它有几个优点：
另外，请确保不要为每次距离检查都进行平方根。 由于您仅比较距离，因此还可以比较距离的平方。
The simplest approach is to use a grid. It has several advantages:
Also, make sure you don't do a squareroot for every distance check. Since you are only comparing the distances, you can also compare the distance squared.
选择良好的空间层次结构的全部目的是能够快速仅选择需要测试的对象。
（一旦你发现了这个小子集，平方根可能不会再造成太大的伤害）
我也对高度动态对象的二维空间索引的最佳/最优方法感兴趣。
四叉树/kd-树看起来不错，但它们对于动态插入不太好。
KD 树可能会变得不平衡。
只是一个随机的想法，如果您的实体是点，则可以尝试将双插入排序结构（通过 X 和 Y）与二分搜索相结合..？
The whole point of selecting a good spatial hierarchy is to be able to quickly select only the objects that need testing.
(Once you've found out that small subset, the square-root is probably not going to hurt that much anymore)
I'm also interested in what the best / most optimal method is for 2d spatial indexing of highly dynamic objects.
Quadtree / kd-tree seem nice, but they're not too good with dynamic insertions.
KD-trees can become unbalanced.
Just a random thought, if your entities are points a double insertion-sorted structure (by X and Y) in combination with a binary search might be something to try..?