Структура данных для расширяемого трехмерного массива?

Question

Я ищу структуру данных, похожую на T[,,] (трехмерный массив), за исключением того, что я заранее не знаю размеров (и не имею разумной верхней границы), которые со временем будут расширяться наружу.Я также хотел бы использовать отрицательные индексы.

Единственное, что приходит на ум, - это словарь с некой структурой Point3 в качестве ключа.Есть ли другие альтернативы?Я хотел бы, чтобы поиски были максимально быстрыми.Данные всегда будут сгруппированы вокруг 0,0,0.Он может расширяться в любом направлении, но между точками никогда не будет «пробелов».

---

Я думаю, что я собираюсь пойти дальше и просто использовать Dictionary<Point3, T> сейчас и посмотреть, какчто выполняет.Если это проблема с производительностью, я постараюсь создать оболочку вокруг T[,,], чтобы я мог использовать отрицательные индексы.

Answer 1

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

Я немного схожу с ума здесь, но я думаю, что ваши индексы должны быть в Сферические координаты . Это имеет смысл для меня, так как ваши данные растут наружу. Это также сделает поиск элементов в определенном диапазоне от (0, 0, 0) чрезвычайно простым.

Answer 2

Если вам могут потребоваться запросы диапазона, вам на ум приходит KD-Trees.Они представляют собой древовидные структуры, на каждом уровне разделяющие вселенную на две части вдоль одной оси.Они предлагают время поиска O (logN) (для постоянного числа измерений), которое может быть или не быть достаточно быстрым, но они также обеспечивают время O (logN + S) для запросов диапазона, где S - размер найденных элементов, который обычноочень хорошо.Они могут обрабатывать динамические данные (вставки и удаления вместе с поиском), но в результате дерево может стать неуравновешенным.Также вы можете выполнить поиск ближайших соседей из заданной точки (т.е. получить 10 ближайших объектов к точке (7,8,9)). Википедия, как всегда, является хорошей отправной точкой: http://en.wikipedia.org/wiki/Kd-tree

ЕслиВ мире огромное количество вещей, и если мир очень динамичен (вещи движутся, все время создаются / разрушаются), kd-деревья могут быть недостаточно хороши.Если большую часть времени вы будете только спрашивать «дайте мне вещь в (7,8,9)», вы можете использовать хеш, как вы упоминали в своем вопросе, или что-то вроде List<List<List<T>>>.Я просто реализовал бы то, что проще в интерфейсе, и потом беспокоился о производительности.

Answer 3

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

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

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

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

Answer 4

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

Каждая отдельная плитка может содержать, скажем, 32x32x32 вокселей. Или любую сумму, соответствующую вашим целям. Поиск вашего тайла выполняется путем деления вашего индекса координат на 32 (конечно, путем сдвига битов), а индекс в тайле вычисляется путем маскирования верхних битов.

Подобный поиск довольно дешев, возможен наравне с .net Dictionary, но он будет использовать меньше памяти, что также хорошо для производительности.

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