聪明的数据结构来表示分层圆形

Question

我正在制作一个游戏，需要用一种巧妙的数据结构来表示“分层”圆形。

圆形可以有任意数量的层。每个层都有若干个“片段”，它们的长度可以不同，其中的一些部分可能缺失。最内层始终是一个完整的圆。每个片段都有一种颜色，相同颜色的多个片段可以挨在一起。 圆形带层 实际上，一个圆形不会有超过40层或大约1500个单独的片段。

我需要能够轻松找到特定片段的相邻片段，查看一个片段是否“悬空”（想象向中心的重力），并移除留下空洞的片段。

我已经有了一些存储这个数据结构的想法，但我认为这是一个有趣的问题，所以我决定在这里发布它。我将使用Actionscript 3.0编写代码，但请随意在任何语言中发布想法。

- grapefrukt

Answer 1

仔细思考一下，我可以想象出一个带有不同边的有向图。 可能是这样的：

Node:
 + List<Node *> ParentLevel: a list of nodes at the level above (ie. more external)
 + List<Node *> ChildrenLevel: a list of nodes at the level below (ie. more internal)
 + Node * ClockwiseNeighbourgh
 + Node * AntiClockwiseNeighbourg

您将拥有两个设置节点，一个是中心圆，另一个代表虚构的最外层圆。您可以轻松地在任何方向上从邻居到邻居之间导航到不同层级。要查找所有“悬空”的部分，您可以从内部或外部节点开始查找没有父节点或子节点的任何部分。唯一无法处理的情况是分层圆中存在两个不连通的部分，即完全缺失一层。但是，通过在边缘上添加权重来表示距离，它也可以支持这种情况。

- Locksfree

---

很好，我在当前的实现中正在标记切片为“死亡”以将它们删除，因此遍历到“岛屿”不会成为问题。 - grapefrukt

Answer 2

想象一下用Mercator投影制作一个北半球（或南半球）地图。画出一些经纬线。现在，请记住标准的Mercator投影无法显示+/-90度纬度，将最上面的纬度带看作是你的地图极点周围的圆。为了达到你的目的，请绘制网格。现在，你有了一个漂亮的平面二维数组，可以在其中表示你想要的邻接属性的数据（请记住，在主子午线处要进行跨越表述）。你必须通过为它们分配一些空值来表示空片。

我希望这个匆忙的解释足够清楚，如果一个二维数组不是一个聪明的数据结构，我很抱歉。

- High Performance Mark

---

这很好而且简单，但如果我理解正确的话，我会在中心获得更密集的分辨率？ - grapefrukt

是的，您会在“极点”周围获得更密集的分辨率。如果不了解您的要求更详细，我会坚信数据结构的简单性以及对其进行的操作将弥补一些“浪费”的空间。 - High Performance Mark

Answer 3

这是一个有趣的问题。我现在正在工作，所以暂时只能给出一个快速答案，但今晚会测试一下。

我想知道一个循环链表数组/列表是否可行？您可以使用一些标识符为列表中的每个元素标记，以显示它在一个片段中。你添加到外部数组中的元素越多，你就有更多的层次。这不是太有趣，但很简单。您应该能够轻松地找到相邻的片段。

- Wix

Answer 4

只是随意的想法，不是完整的解决方案，但对于每个带宽，都有360个可以填充的空槽（对应于角度数）。仔细想一想，为什么要将其限制在360个整数度内。但无论如何，你可以通过仅检查它们在每个级别上所占据的范围来确定相邻级别的段是否相接。

仔细一想，你的应用程序甚至是否真正依赖同心圆的属性，甚至是否依赖圆。看起来你可以设想堆叠在一起形成管子的一堆环，或者是堆叠在一起形成墙的一堆线性行，这些情况下数据结构都是相同的（根据我从问题描述中了解到的内容）。然后只需要最有效的链表实现或其他操作即可。

- Mark

---

但是如果每个层级的360度足够了，那么就不要使用链表，而是在每个层级上使用一个简单的数组。每个层级都是一个包含360个元素的数组，其中每个元素都是一个简单的数据结构，由颜色和唯一的段标识符组成。 因此，360 * 40 * ~10字节，整个东西大约75000字节。 - Mark

但是，仅仅对应用程序有一个模糊的概念，我可以进一步补充说，您必须知道哪个操作最常见 - 插入新段或访问现有段。并且对于每一行，您可以维护一个单独的指向段起始位置的排序列表，并且每次从行中添加或删除段时都会重新排序该列表。然后访问特定段的起始位置将是log2n，插入新段为n * log2n。或者，如果插入/删除比简单访问更常见，则应想出其他方法。 - Mark

Answer 5

你没有提到切片和层的行为，这对于开发一个能够表示你的游戏场地的纯几何结构以上更多的数据结构是很重要的。

制作一个层列表。Layers[0] 是最内层。

每个层都是一个切片列表。每个切片由其起始角度和颜色定义。如果一层中只有一个切片，则它绕整个层旋转。如果有多个切片，则每个切片从起始角度开始，直到下一个切片开始，而不会存储冗余数据。空洞是一种特殊的颜色。如果下面的层在其起始和结束角度上被涂成“空”，则该切片悬浮在空中。同一层上相邻的切片是切片列表中的下一个索引，或者是列表中的最后一个和第一个。其他层上的相邻切片再次通过切片的起始和结束角度找到。

- Ozan

Answer 6

为什么不使用图形（来自图论）。只需为每个顶点（游戏板上的每个彩色空间）添加边缘（连接性链接），即可在图形中添加边缘。图形被设计成易于检索相邻顶点（在您的情况下是彩色空间）的列表。

- Jared Updike

Answer 7

只是一个快速的想法，如果它很愚蠢，不要介意 - 现在很晚了 ：P

• 创建一个起始层的向量。
• 每个层包含一个片段的向量。
• 每个片段存储一个比例值（0-1）和一种可以为空的颜色。
• 所有片段的比例之和总是等于1。

初始时，每个层可以包含一个单独的片段（比例为1）。

如果现在决定将比例为.5（180º）的蓝色片段添加到偏移量为.25的空白层中，这将替换掉空白并创建3个片段：

• [NULL .25][blue .5][NULL .25]

...然后递归进行，所以最后你会得到类似于：

• [NULL .25][blue .2][NULL 0][red .1][NULL .2][black .25]

假设您想要与此进行交互式操作... 如果您希望某些空间保持静态，而其他空间调整，则可以很方便地使用它。或者，如果您希望相邻的颜色块具有磁性，则只需检查中间的块是否具有零比率/足够吸引其他块，而无需进行任何额外的计算。 基本上，好处在于当一个块被改变时，计算会自动完成。其余部分只是逻辑。例如，如果移动了一个块，您只需要注意左/右空白空间比值，而不需要迭代其余部分来计算角度。这种方式与弹性UI调整的方式非常相似。

- Theo.T

---

这非常接近我最终实现的内容。我想我不会再太多地移动片段，但我可以看出来这很方便。我还添加了一个图层偏移量，因此我可以旋转整个图层而不影响零件的偏移量。 - grapefrukt