Умная структура данных для представления разделенного на уровни круга
Я делаю игру, и я должен представить "многоуровневый" круг в некотором умном datastructure.
Круг может иметь любое количество слоев. Каждый слой имеет много "частей", они могут иметь различные длины, и части могут отсутствовать. Самый внутренний слой всегда является полным кругом. Каждый сегмент имеет цвет, несколько сегментов с тем же цветом могут быть друг рядом с другом.
круг с уровнями http://webbfarbror.se/dump/datastructure.gif
Реалистично круговая привычка имеет больше, чем приблизительно 40 слоев или приблизительно 1 500 отдельных частей.
Я должен буду смочь легко найти смежные части к определенной части, видеть, "зависает ли часть в атмосферном воздуху" (вообразите силу тяжести к центру), и удалить части, покидая дыру в их месте.
Я уже получил несколько идей для того, как сохранить это, но я думал, что это был интересный вопрос, таким образом, я полагал, что отправлю его здесь для ударов.
Я буду кодировать это в Actionscript 3.0, но не стесняться отправлять идеи на любом языке.
7 ответов
Просто подумав об этом, я смог увидеть какой-то ориентированный граф с разными типами ребер. Вероятно, что-то вроде этого
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
У вас будет два установленных узла, один из которых является центральным кругом, а другой представляет фиктивный самый дальний круг.
Затем вы можете легко перемещаться между уровнями, от соседнего до соседнего в любом направлении. Чтобы найти все срезы, которые находятся «в воздухе», вы можете начать с внутреннего или внешнего узла и найти любой срез, у которого нет родительского или дочернего элемента.
Единственное, что здесь не работает, - это случай, когда есть две дизъюнктивные части многослойного круга, т. Е. с полностью отсутствующим слоем. Он мог бы поддержать это, добавив веса по краям, чтобы обозначить расстояние.
Подумайте о проекции Меркатора для карты северного (или, если вы предпочитаете, южного) полушария. Нарисуйте линии долготы и широты. Теперь, имея в виду, что стандартная проекция Меркатора не может отображать +/- 90 широты, подумайте о самом верхнем диапазоне широт как о круге вокруг полюса вашей карты. Нарисуйте сетку, достаточную для ваших целей. Теперь у вас есть хороший плоский 2D-массив, на котором можно представить ваши данные со свойством смежности, которое вы хотите (не забывая обернуть по первому антимеридиану). Вам нужно будет представить пустые срезы, присвоив им какое-то нулевое значение.
Я надеюсь, что этого довольно поспешного объяснения будет достаточно, и мне очень жаль, если 2D-массив не является достаточно умной структурой данных.
Это интересный вопрос. Я на работе, поэтому сейчас мне нужно дать быстрый ответ, но я проверим его сегодня вечером.
Интересно, будет ли работать массив / список круговых связанных списков? Вы можете пометить каждый элемент в списке каким-либо идентификатором, чтобы показать, что он находится в срезе. Чем больше элементов вы добавляете во внешний массив, тем больше у вас слоев. Это не слишком интересно, но очень просто. Таким образом вы сможете легко находить соседние части.
Просто мысли вслух и не полное решение, но для каждой полосы есть 360 пустых слотов, которые могут заполняться (соответствует количеству градусов). Если задуматься, зачем ограничивать это 360 целыми градусами. Но в любом случае вы можете определить, соприкасаются ли сегменты на соседних уровнях, просто проверив диапазон, который они занимали на каждом уровне. Итак, если сегмент x на уровне n занимает 120–240, а сегмент z занимает 80–300 на уровне n + 1, то они смежные.
Если задуматься, как ваше приложение действительно зависит от атрибутов концентрических окружностей или даже от окружности? Кажется, вы могли бы изобразить связку колец, уложенных друг на друга, чтобы сформировать трубу, или даже связку линейных рядов, уложенных друг на друга, чтобы сформировать стену, и структура данных будет одинаковой во всех этих случаях ( учитывая то, что я могу почерпнуть из вашего описания проблемы.) Тогда это просто вопрос наиболее эффективной реализации связанных списков или чего-то подобного.
Вы ничего не сказали о поведении срезов и слоев, что было бы важно для разработки структуры данных, которая будет представлять больше, чем чисто геометрические структура вашего игрового поля.
Составьте список слоев. Layers [0] - ваш самый внутренний слой.
Каждый слой представляет собой список фрагментов. Каждый срез определяется своим начальным углом и цветом. Если в слое один кусочек, он обходит весь слой. Если есть несколько срезов, каждый из них начинается с начального угла и заканчивается там, где начинается следующий, без избыточного хранения данных. Дырка - особого цвета. Срез висит в воздухе, если слой под ним окрашен в «пустой» цвет по его начальному и конечному углам. Соседние срезы на том же слое являются следующими индексами в списке срезов или последним и первым в списке. Соседние срезы в других слоях снова находятся над углами начального конца среза среза.
Почему бы не использовать граф (из теории графов). Просто добавьте края (связи между цветными местами) для каждой вершины (каждое цветное пространство на игровой доске). Графики предназначены для простого извлечения списка соседних вершин (цветных мест в вашем случае).
Просто быстрая идея, не обижайтесь, если она глупая - здесь уже поздно :P
- Создайте вектор Слоев для начала.
- Каждый слой содержит вектор частей.
- Каждый Piece хранит значение отношения (0-1) и цвет, который в качестве альтернативы может быть NULL
- Сумма отношений всех Pieces всегда равна 1.
В начале каждый слой мог содержать один Piece (с отношением 1).
Если теперь вы решите добавить синий кусок с отношением .5 (180º) к пустому Слою со смещением .25, это заменит пустой слой, создав 3 куска :
- [NULL .25][синий .5][NULL .25]
... и так рекурсивно, так что в итоге получится что-то вроде :
- [NULL .25][синий .2][NULL 0][красный .1][NULL .2][черный .25]
Предположим, вы хотите сделать что-то интерактивное с этим... Это может быть удобно, если вы хотите, чтобы некоторые пространства были статичными, в то время как другие изменяются, или если вы хотите, чтобы соседние цветные части были магнитными, вам просто нужно проверить, имеет ли часть между ними отношение ноль / или достаточно, чтобы притянуть другую без необходимости делать дополнительные вычисления. В принципе, хорошо то, что вычисления будут производиться, когда деталь изменяется. Остальное - просто логика. Скажем, если фигура перемещается, вам нужно знать только значения соотношения левого и правого пустого пространства, и не нужно итерационно вычислять остальные углы. Это было бы очень похоже на то, как настраиваются эластичные пользовательские интерфейсы.