网页游戏的稀疏（伪）无限网格数据结构
我正在考虑尝试制作一款在本质上无限的网格上进行的游戏。
- 网格非常稀疏。某些密度相对较高的小区域。孤立的非空单元相对较少。
- 正在使用的网格量太大，无法天真地实现，但按照“大数据”标准可能很小（我不是试图映射互联网或类似的东西）
- 这需要很容易坚持。
以下是我可能想要在此网格上执行（相当有效）的操作：
- 请求一些单元格的小矩形区域及其所有内容（玩家当前的邻居）
- 设置单个单元格或位块传输小区域（玩家正在移动）
- 询问一些较大矩形区域的粗略形状或轮廓/轮廓（世界地图或区域预览）
- 找到一些具有大约给定密度的区域（玩家产卵位置）
- 通过每跳至多一些小的恒定空白空间的间隙的近似最短路径（经常出现不好的近似是可以的，但继续朝错误的方向搜索就不行了）
- 区域的近似凸包
这里有一个问题：我想在网络应用程序中执行此操作。也就是说，我更愿意使用现有的数据存储（可能以关系数据库的形式）和相对较少的外部依赖（最好避免对持久过程的需要）。
伙计们，关于实际实施这个问题，你能给我什么建议吗？如果没有网络应用程序限制，您会如何执行此操作？如果是的话你会如何修改？
非常感谢大家！
I'm considering trying to make a game that takes place on an essentially infinite grid.
- The grid is very sparse. Certain small regions of relatively high density. Relatively few isolated nonempty cells.
- The amount of the grid in use is too large to implement naively but probably smallish by "big data" standards (I'm not trying to map the Internet or anything like that)
- This needs to be easy to persist.
Here are the operations I may want to perform (reasonably efficiently) on this grid:
- Ask for some small rectangular region of cells and all their contents (a player's current neighborhood)
- Set individual cells or blit small regions (the player is making a move)
- Ask for the rough shape or outline/silhouette of some larger rectangular regions (a world map or region preview)
- Find some regions with approximately a given density (player spawning location)
- Approximate shortest path through gaps of at most some small constant empty spaces per hop (it's OK to be a bad approximation often, but not OK to keep heading the wrong direction searching)
- Approximate convex hull for a region
Here's the catch: I want to do this in a web app. That is, I would prefer to use existing data storage (perhaps in the form of a relational database) and relatively little external dependency (preferably avoiding the need for a persistent process).
Guys, what advice can you give me on actually implementing this? How would you do this if the web-app restrictions weren't in place? How would you modify that if they were?
Thanks a lot, everyone!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
我认为您可以使用四叉树完成所有操作，正如其他人所建议的那样，也许还可以使用一些其他数据结构。这里有更多细节：
具有大约给定密度的区域：如果您正在寻找的密度很高，那么我会维护地图中所有对象的单独索引。取一个随机对象并检查四叉树中该对象周围的密度。大多数物体都会靠近高密度区域，因为高密度区域有很多物体。如果您选取的对象附近的密度不是您要查找的密度，请选取另一个对象。
如果您正在寻找低密度点，那么只需在地图上随机选择位置 - 鉴于它是一张稀疏地图，通常应该为您提供低密度点。再次强调，如果它不起作用，请重试。
近似最短路径：如果这是一个不太频繁的操作，则创建起点 A 和终点 B“之间”的区域的粗略图，以对之间进行一些适当的定义（可能是包含以 AB 的中点为圆心，以 1.5*AB 为直径的圆，除非该直径小于某个最小值，在这种情况下......实验）。制作与粗略形状/轮廓相同类型的网格，然后创建（例如）黑点的 Delaunay 三角剖分。在此图上绘制一条最短路径，然后将其覆盖在实际地图上，并将路径细化为在给定实际地图的情况下有意义的路径。您可能需要在几个不同的细化级别上重做此操作 - 从一个非常粗略的图表开始，然后“放大”将从更高级别获得的两个点作为起点和终点，然后进行迭代。
如果您需要非常频繁地执行此操作，您将需要为整个地图维护这种类型的图表，而不是每次都重新构建它。不过，这可能会很昂贵。
近似凸包：再次从粗略形状开始，然后取其中黑点的凸包。
我不确定这是否很容易放入关系数据库中；基于文件的存储可以工作，但让写入操作与其他任何操作同时进行是不切实际的，如果您想让它增长到合理的玩家数量（每个世界/地图，如果有的话），您可能会希望这样做是多个世界/地图）。我认为在这种情况下，你可能最好保持一个单独的进程处于活动状态......即使这样，正确地尊重多线程也会是一个令人头痛的问题。
I think you can do everything using quadtrees, as others have suggested, and maybe a few additional data structures. Here's a bit more detail:
Region with approximately given density: if the density you're looking for is high, then I would maintain a separate index of all objects in your map. Take a random object and check the density around that object in the quadtree. Most objects will be near high density areas, simply because high-density areas have many objects. If the density near the object you picked is not the one you were looking for, pick another one.
If you're looking for low-density, then just pick random locations on the map - given that it's a sparse map, that should typically give you low density spots. Again, if it doesn't work right try again.
Approximate shortest path: if this is a not-too-frequent operation, then create a rough graph of the area "between" the starting point A and end point B, for some suitable definition of between (maybe the square containing the circle with the midpoint of AB as center and 1.5*AB as diameter, except if that diameter is less than a certain minimum, in which case... experiment). Make the same type of grid that you would use for the rough shape / outline, then create (say) a Delaunay triangulation of the black points. Do a shortest path on this graph, then overlay that on the actual map and refine the path to one that makes sense given the actual map. You may have to redo this at a few different levels of refinement - start with a very rough graph, then "zoom in" taking two points that you got from the higher level as start and end point, and iterate.
If you need to do this very frequently, you'll want to maintain this type of graph for the entire map instead of reconstructing it every time. This could be expensive, though.
Approx convex hull: again start from something like the rough shape, then take the convex hull of the black points in that.
I'm not sure if this would be easy to put into a relational database; a file-based storage could work but it would be impractical to have a write operation be concurrent with anything else, which you would probably want if you want to allow this to grow to a reasonable number of players (per world / map, if there are multiple worlds / maps). I think in that case you are probably best off keeping a separate process alive... and even then making this properly respect multithreading is going to be a headache.
kd 树或四叉树是解决您的问题的良好数据结构。尤其是后者，这是一种解决网格问题并将二维复杂性降低到一维复杂性的巧妙方法。四叉树还用于许多地图应用程序，如 bing 和谷歌地图。这是一个好的开始：Nick 四叉树空间索引希尔伯特曲线博客。
A kd tree or a quadtree is a good data structure to solve your problem. Especially the latter it's a clever way to address the grid and to reduce the 2d complexity to a 1d complexity. Quadtrees is also used in many maps application like bing and google maps. Here is a good start: Nick quadtree spatial index hilbert curve blog.