Умная структура данных для представления многоуровневого круга

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

У вас будет два набора узлов, один из которых будет центральным кругом, а другой - вымышленным самым внешним кругом.

Затем вы можете легко перемещаться между уровнями, от соседей до соседей в любом направлении. Чтобы найти все срезы, которые находятся «в воздухе», вы можете начать с внутреннего или внешнего узла и найти любой срез, у которого нет родителя или потомка.

Единственное, что не обрабатывается, это случай, когда в вашем многослойном круге есть две несвязанные части, т.е. с полностью отсутствующим слоем. Он может поддержать это, добавив веса по краям, чтобы представить расстояние.

Answer 2

Подумайте о проекции Меркатора для карты Северного (или, если вы предпочитаете Южное) полушария. Нарисуйте несколько линий долготы и широты. Теперь, имея в виду, что стандартная проекция Меркатора не может показывать +/- 90 лат, думайте о самой верхней полосе широты как о круге вокруг полюса вашей карты. Нарисуйте сетку, достаточную для ваших целей. Теперь у вас есть хороший планарный 2D-массив, в котором вы можете представить свои данные с помощью свойства смежности, которое вы хотите (не забывая обернуть в основной анти-меридиан). Вам нужно будет представить пустые фрагменты, присвоив им какое-либо нулевое значение.

Надеюсь, этого довольно поспешного объяснения достаточно, и я извиняюсь, если 2D-массив не достаточно умен для структуры данных.

Answer 3

Просто быстрая идея, без обид, если это глупо - уже поздно: P

• Создайте вектор слоев для запуска.
• Каждый слой содержит Вектор кусочков.
• Каждая пьеса хранит значение коэффициента (0-1) и цвет, который в качестве альтернативы может быть равен NULL
• Сумма отношения всех частей всегда равна 1.

В начале каждый слой может содержать один кусок (с соотношением 1).

Если теперь вы решите добавить синий кусок с коэффициентом .5 (180º) к пустому слою со смещением .25, это заменит пустое создание: 3 элемента:

• [NULL .25] [синий .5] [NULL .25]

... и так рекурсивно, так что в итоге вы получите что-то вроде:

• [NULL .25] [синий .2] [NULL 0] [красный .1] [NULL .2] [черный .25]

Предположим, вы хотите сделать что-то интерактивное с этим ... Это может быть удобно, если вы хотите, чтобы некоторые пробелы были статичными, в то время как другие корректируются, или если вы хотите, чтобы смежный цветовой фрагмент был магнитным, вам просто нужно проверить, имеет ли фигура между ними нулевое соотношение / или достаточно, чтобы привлечь другой без необходимость делать какие-либо дополнительные расчеты. В принципе, хорошо то, что вычисления будут сделаны, когда часть будет изменена. Остальное было бы просто логикой. Скажем, если кусок перемещен, вам нужно знать только о левом / правом значении пустого пространства и не нужно итерировать остальные расчетные углы. Как-то очень похоже на то, как настраиваются эластичные интерфейсы.

Answer 4

Почему бы не использовать граф (из теории графов). Просто добавьте ребра (связи между цветными пространствами) для каждой вершины (каждого цветного пространства на игровой доске). Графики спроектированы так, чтобы было легко получить список соседних вершин (цветные пробелы в вашем случае).

Answer 5

Вы ничего не сказали о поведении срезов и слоев, что было бы важно для разработки структуры данных, которая представляла бы нечто большее, чем чисто геометрическую структуру вашего игрового поля.

Составьте список слоев. Слои [0] это ваш самый внутренний слой.

Каждый слой представляет собой список фрагментов. Каждый срез определяется своим начальным углом и цветом. Если в слое есть один срез, он обходит весь слой. Если имеется больше срезов, каждый начинается с начального угла и заканчивается там, где начинается следующий, без избыточного хранения данных. Отверстие - это особый цвет. Срез висит в воздухе, если слой под ним окрашен «пустым» по его начальному и конечному углу. Соседние срезы на том же слое являются следующими индексами в списке срезов или последним и первым в списке. Соседние срезы в других слоях снова находятся над начальными конечными углами конца среза.

Answer 6

Просто мысли вслух и не полное решение, но для каждой полосы есть 360 пустых слотов, которые можно заполнить (соответствует количеству градусов). Если подумать, зачем ограничивать его целым числом в 360 градусов. Но в любом случае вы могли определить, касались ли сегменты на соседних уровнях, просто проверив диапазон, который они занимали на каждом уровне. Таким образом, если сегмент x на уровне n занимал 120-240, а сегмент z занимал 80-300 на уровне n + 1, то они смежные.

Если подумать, как ваше приложение зависит от атрибутов концентрических кругов или даже от круга. Кажется, вы могли бы изобразить группу колец, сложенных друг на друге, чтобы сформировать трубу, или даже группу линейных рядов, сложенных друг на друге, чтобы сформировать стену, и структура данных была бы одинаковой во всех этих случаях учитывая то, что я могу почерпнуть из вашего описания проблемы.) Тогда это просто вопрос наиболее эффективной реализации связанных списков или что-то в этом роде.

Answer 7

Это интересный вопрос. Я нахожусь на работе, поэтому в данный момент мне придется дать быстрый ответ, но я проверю это сегодня вечером.

Интересно, будет ли работать массив / список циклических связанных списков? Вы можете пометить каждый элемент в списке некоторым идентификатором, чтобы показать, что он находится в срезе. Чем больше элементов вы добавляете во внешний массив, тем больше у вас слоев. Это не слишком интересно, но это просто. Таким образом вы сможете легко находить соседние предметы.