聪明的数据结构代表分层圈

Question

我正在制作游戏,我需要在一些聪明的数据结构中代表一个"分层"的圆圈.

圆圈可以包含任意数量的图层.每层都有许多"切片",它们可以具有不同的长度,并且可以丢失碎片.最内层始终是一个完整的圆圈.每个片段都有一个颜色,相同颜色的多个片段可以彼此相邻.

带有层的圆圈http://webbfarbror.se/dump/datastructure.gif

实际上,圆圈不会超过大约40层或大约1500个单独的切片.

我需要能够轻松地找到特定部件的相邻部件,看看是否"悬挂在自由空气中"(想象重力朝向中心),并移除在其位置留下孔的碎片.

我已经有了一些关于如何存储它的想法,但我认为这是一个有趣的问题,所以我想我会在这里发布它来踢.

我将在Actionscript 3.0中对此进行编码,但您可以随意发布任何语言的想法.

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

您将有两个集合节点，一个是中心圆，一个代表虚构的最外圆。

然后，您可以轻松地在各个级​​别之间导航，从一个邻居到另一个邻居，向任何方向移动。要查找所有“空中”切片，您可以从内部或外部节点开始，查找任何没有父节点或子节点的切片。

唯一不能处理的是分层圆有两个分离部分的情况，即。完全缺失层。不过，它可以通过在边缘上添加权重来表示距离来支持它。