重叠空间区域的有效数据结构
我正在编写一个游戏，其中大量对象将在平铺的 2D 地图区域上产生“区域效果”。
所需功能：
- 其中几个区域效果可能会重叠并影响同一个图块
- 必须能够非常有效地访问任何给定图块的效果列表
- 区域效果可以具有任意形状，但通常采用“最多 X 个图块”的形式距引起效果的对象的距离”，其中 X 是一个小整数，通常为 1-10
- 区域效果会频繁变化，例如，当对象移动到地图上的不同位置时
- 地图可能会很大（例如 1000*1000 块
）数据结构最适合这个？
I'm writing a game where a large number of objects will have "area effects" over a region of a tiled 2D map.
Required features:
- Several of these area effects may overlap and affect the same tile
- It must be possible to very efficiently access the list of effects for any given tile
- The area effects can have arbitrary shapes but will usually be of the form "up to X tiles distance from the object causing the effect" where X is a small integer, typically 1-10
- The area effects will change frequently, e.g. as objects are moved to different locations on the map
- Maps could be potentially large (e.g. 1000*1000 tiles)
What data structure would work best for this?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
如果你确实有很多区域效果同时发生，并且它们将具有任意形状，我会这样做：
存储在全局效果列表中
（不一定是全局变量，
只是适用于
整个游戏或当前游戏地图）
它会影响并存储这些图块的列表，以对抗
通知新的影响，并且
将对其的引用存储在
每个图块列表（在 C++ 中我会使用
std::vector 为此，与
连续存储，而不是链接存储
列表）
感兴趣的图块并删除对其的引用，然后在销毁它、
如上所述的参考文献，执行变化计算，
然后在现在受影响的图块中重新附加引用，
整个地图并验证效果中的图块列表
与地图中引用它的图块完全匹配。
Providing you really do have a lot of area effects happening simultaneously, and that they will have arbitrary shapes, I'd do it this way:
stored in a global list of effects
(not necessarily a global variable,
just something that applies to the
whole game or the current game-map)
it affects, and stores a list of those tiles against the effect
notified of the new effect, and
stores a reference back to it in a
per-tile list (in C++ I'd use a
std::vector for this, something with
contiguous storage, not a linked
list)
the interested tiles and removing references to it, before destroying it
the references as above, performing the change calculations,
then re-attaching references in the tiles now affected
your entire map and verifies that the list of tiles in the effect
exactly matches the tiles in the map that reference it.
通常这取决于地图的密度。
如果您知道每个图块（或图块的主要部分）至少包含一种效果，您应该使用常规网格 - 简单的二维图块数组。
如果您的地图填充得很弱并且有很多空图块，那么使用一些空间索引 如四叉树、R 树或 BSP 树。
Usually it depends on density of your map.
If you know that every tile (or major part of tiles) contains at least one effect you should use regular grid – simple 2D array of tiles.
If your map is feebly filled and there are a lot of empty tiles it make sense to use some spatial indexes like quad-tree or R-tree or BSP-trees.
通常 BSP 树（或 四叉树 或 八叉树） 。
Usually BSP-Trees (or quadtrees or octrees).
一些不依赖于复杂计算机科学的强力解决方案：
1000 x 1000 并不算太大 - 只是一兆。计算机有演出。你可以有一个二维数组。字节中的每一位都可以是一种“区域类型”。更大的“受影响区域”可能会更大一些。如果您有合理数量的不同类型的区域，您仍然可以使用多字节位掩码。如果这变得荒谬，您可以将数组元素指针指向重叠区域类型对象的列表。但这样你就会失去效率。
您还可以实现稀疏数组 - 使用散列表键（例如，key = 1000*x+y） - 但这要慢很多倍。
当然，如果您不介意用奇特的计算机科学方法进行编码，它们通常会工作得更好！
Some brute force solutions that don't rely on fancy computer science:
1000 x 1000 isn't too large - just a meg. Computers have Gigs. You could have an 2d array. Each bit in the bytes could be a 'type of area'. The 'effected area' that's bigger could be another bit. If you have a reasonable amount of different types of areas you can still use a multi-byte bit mask. If that gets ridiculous you can make the array elements pointers to lists of overlapping area type objects. But then you lose efficiency.
You could also implement a sparse array - using a hashtable key'd off of the coords (e.g., key = 1000*x+y) - but this is many times slower.
If course if you don't mind coding the fancy computer science ways, they usually work much better!
如果您知道每个区域效果的最大范围，则可以使用您选择的数据结构并存储实际源，仅针对正常的 2D 碰撞测试进行了优化。
然后，在检查图块上的效果时，只需检查（碰撞检测样式，针对您的数据结构进行优化）最大范围内的所有效果源，然后应用定义的测试函数（例如，如果该区域是圆形，则检查如果距离小于常数；如果是正方形，则检查 x 和 y 距离是否均在常数内）。
如果您有少量（<10）效果“场”形状，您甚至可以在其预先计算的最大范围内为每种效果场类型执行独特的碰撞检测。
If you have a known maximum range of each area effect, you could use a data structure of your choosing and store the actual sources, only, that's optimized for normal 2D Collision Testing.
Then, when checking for effects on a tile, simply check (collision detection style, optimized for your data structure) for all effect sources within the maximum range and then applying a defined test function (for example, if the area is a circle, check if the distance is less than a constant; if it's a square, check if the x and y distances are each within a constant).
If you have a small (<10) amount of effect "field" shapes, you can even do a unique collision detection for each effect field type, within their pre-computed maximum range.