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

Question

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

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

---

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

Answer 1

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

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

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

Результирующий массив будет коротким: границы массива кратны размеру вашей плитки.

Answer 2

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

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

Answer 3

Если вам могут потребоваться запросы диапазона, 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 4

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

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

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

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