在数据库上存储位置点阵(storing a positional lattice on a database)

在数据库上存储位置点阵(storing a positional lattice on a database)

这个问题出现在以下考虑之后：考虑像Travian或Tiberium战争这样的MMOG的巨大世界地图。 即使它们是2D地图，它们通常也有许多不同的身份，如玩家的城镇，地形特征和其他。

这些地图如何保存在数据库中？ 是否每个磁贴都有一个条目，并且该标识位于该位置的外键？ 或者反过来说：每个身份作为两个位置属性（x，y）来定义它的位置？

从更广泛的意义上讲，我的问题如下：在类似mysql的数据库中存储位置点阵（方形图块，六边形图块等）的最有效方法是什么？ 在查询数据库中的位置或位置列表时，制作此类存储的瓶颈（如果有）是什么？

This question appeared after the following consideration: consider the immense world map of a MMOG like Travian or Tiberium wars. Even if they are 2D maps, they normally have a lot of different identities like player's towns, terrain features and others.

How are those maps saved on a database? Is there an entry for every tile, with a foreign key to the identity which is at that position? Or is the other way around: each identity as two position attributes (x,y) which define its position?

In a more broad sense, my question is the following: what is the most efficient way to store a positional lattice (square tiles, hexagonal tiles, etc) on a mysql-like database? What is the bottleneck (if any) of making such a storage when querying the db for a position, or list of positions?

最满意答案

这完全取决于场景。 例如，如果地图是稀疏的，则将具有坐标的实体的位置存储在单行中可能是有意义的。 如果拓扑是不规则的（即，任何给定的tile中有任意多个路径），那么您可以将其存储为图形（即，在一对多配置中单独的“节点”和“边缘”表） 。 您可能决定对数据库中的项使用连续（例如，实际）坐标，然后将它们简单地划分为应用程序中的逻辑“切片”。

同样，瓶颈将取决于应用程序。 你经常需要问“我周围的东西是什么吗？”，或者你只是问“我可以从这里到那里吗？”。 如果您考虑到特定的用例，也许您可​​以添加更多细节，我们可以尝试提供更详细的答案。

在任何谈论绩效的事情中，假设案例中的随机猜测永远不能替代原型设计和衡量。

This is entirely dependent upon the scenario. For example, if the map is sparse, it might make sense to store the position of entities with coordinates in a single row. If the topology is irregular (i.e., there are arbitrarily many paths out of any given tile), then you might store it as a graph (i.e., separate "node" and "edge" tables, in a one-to-many configuration). You might decide to use continuous (e.g., real) coordinates for items in the database, and then simply partition those into logical "tiles" in the application.

Similarly, the bottlenecks are going to be application-dependent. Do you regularly need to ask "what is presently around me?", or are you merely asking "Can I get from here to there?". If you had particular use-cases in mind, perhaps you could add more detail and we could attempt to provide more detailed answers.

And as always in anything talking about performance, random speculation in the hypothetical case is never a substitute for prototyping and measuring.