通过 2d/3d 坐标访问内容的容器
有很多游戏通常可以被视为一堆散布在空间中的物体，一个非常常见的操作是拾取一个子区域中的所有物体。典型的例子是一个在大地图上有大量单位的游戏，并且爆炸会影响一定半径内的单位。这需要选取半径内的每个单位才能应用爆炸效果。
现在，有多种方法可以存储对象，从而可以有效地选取子区域。最简单的方法可能是将地图划分为网格；在一个区域中选取单位将涉及仅选择受影响的网格部分，并进行细粒度的坐标检查，检查不是 100% 在该区域内的网格图块。
我不喜欢这种方法的是回答“网格图块应该有多大？”太大了，效率可能会成为一个真正的问题。太小了，如果游戏世界足够大，网格就会占用大量内存（如果游戏是 3d 的话，网格会变得很荒谬）。甚至可能没有合适的中庸之道。
解决上述问题的明显方法是制作一个具有某种智能细分的大型网格，例如伪树结构。正是在这一点上，我确信我已经陷入了过早优化的境地。 （然后有适当的动态四叉树/八叉树，但是编码起来更加复杂，我什至不相信它会表现得更好。）
所以我的问题是：是否有一个标准的解决方案以上问题？在 STL 容器中，有什么东西可以存储任何具有坐标的对象，并检索特定区域内的对象列表？它不必与我上面描述的不同，只要它是经过深思熟虑并被认为“足够好”的东西即可。
如果该算法有 Python 实现，那么加分，但 C 也可以。
There are a lot of games that can generally be viewed as a bunch of objects spread out through space, and a very common operation is to pick all objects in a sub-area. The typical example would be a game with tons of units across a large map, and an explosion that affects units in a certain radius. This requires picking every unit in the radius in order to apply the effects of the explosion.
Now, there are several ways to store objects that allows efficiently picking a sub-area. The easiest method is probably to divide the map into a grid; picking units in an area would involve selecting only the parts of the grid that is affected, and do a fine-grained coordinate check grid tiles that aren't 100% inside the area.
What I don't like about this approach is answering "How large should the grid tiles be?" Too large, and efficiency may become a real problem. Too small, and the grid takes up tons of memory if the game world is large enough (and can become ridiculous if the game is 3d). There may not even be a suitable golden mean.
The obvious solution to the above is to make a large grid with some kind of intelligent subdivision, like a pseudo tree-structure. And it is at this point I know for sure I am far into premature optimization. (Then there are proper dynamic quad/octrees, but that's even more complex to code and I'm not even confident it will perform any better.)
So my question is: Is there a standard solution to the above problem? Something, in the lines of an STL container, that can just store any object with a coordinate, and retreive a list of objects within a certain area? It doesn't have to be different than what I described above, as long as it's something that has been thought out and deemed "good enough" for a start.
Bonus points if there is an implementation of the algorithm in Python, but C would also do.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
编写实用程序的第一步是接受某些常数的选择来自现实世界的考虑，而不是超越的数学真理。这尤其适用于游戏设计/世界模拟类型编码，如果您坚持尝试对现实世界进行最佳建模，您将永远不会取得任何成果。 :-)
如果您的对象都具有相当统一的大小，我只会选择与平均对象大小成正比的网格大小，然后使用它。这是最简单的 - 请记住，即使您最终搜索的对象比绝对必要的多，简单也会为您带来一些速度！
如果你的物体大小差异很大，事情就会变得更加困难 - 例如，如果你尝试使用相同的引擎来处理子弹、老鼠、人类、巨型怪物、车辆、小行星、行星等。如果是这种情况，一种常见的接受（但丑陋）的方法是根据您所处情况的类型来采用不同的游戏“模式”。除此之外，一个想法可能是使用带有网格单元的二叉树细分的大型网格当他们积累了太多的小物体之后。
一方面：如果您使用浮点坐标，则需要小心网格大小的精度和舍入问题，因为靠近原点的点比远离原点的点具有更高的精度，这可能会导致网格出现错误细胞会错过一些物体。
The first step to writing a practical program is accepting that choices for some constants come from real-world considerations and not transcendent mathematical truths. This especially applies to game design/world simulation type coding, where you'd never get anywhere if you persisted in trying to optimally model the real world. :-)
If your objects will all be of fairly uniform size, I would just choose a grid size proportional to the average object size, and go with that. It's the simplest - and keep in mind simplicity will buy you some speed even if you end up searching over a few more objects than absolutely necessary!
Things get a big harder if your objects vary greatly in size - for example if you're trying to use the same engine to deal with bullets, mice, humans, giant monsters, vehicles, asteroids, planets, etc. If that's the case, a common accepted (but ugly) approach is to have different 'modes' of play depending on the type of situation you're in. Short of that, one idea might be to use a large grid with a binary-tree subdivision of grid cells after they accumulate too many small objects.
One aside: if you're using floating point coordinates, you need to be careful with precision and rounding issues for your grid size, since points close to the origin have a lot more precision than those far away, which could lead to errors where grid cells miss some objects.
这是一本在线免费书籍，它将回答您的问题。
具体看第18章碰撞检测和交叉。
Here is a free book available online that will answer your question.
Specifically look at Chapter 18 on collision detection and intersection.
我对游戏编程一无所知，但我可以想象（基于直觉和我过去读过的内容），完整的网格对于大空间来说会变得非常低效；您将损失存储空间和时间，因为您将融化缓存。
STL 容器本质上是一维的。是的，像
set和map这样的东西允许您定义任意排序关系，但它仍然只在一维中排序。如果你想做得更好，你可能需要使用四叉树、kd 树或类似的东西。I don't know anything about games programming, but I would imagine (based on intuition and what I've read in the past) that a complete grid will get very inefficient for large spaces; you'll lose out in both storage, and also in time, because you'll melt the cache.
STL containers are fundamentally one-dimensional. Yes, things like
setandmapallow you to define arbitrary sort relationships, but it's still ordered in only one dimension. If you want to do better, you'll probably need to use a quad-tree, a kd-tree, or something like that.