Всем привет.

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

Странно, что мне не помог ни гугл ни stackoverflow.

Есть множество объектов в трехмерном пространстве. У каждого объекта целочисленные координаты, хранятся в Vector3(x,y,z).
Множество объектов мы получаем постепенно, т.е. сначала 0 объектов, потом 1, потом еще 1...

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

Иногда массив нужно будет ресайзить. Но увеличиваться он будет до определенного размера.

Элемент с определенным индексом в массиве имеет координаты зависящие от индекса и сохраненных Min Max векторов.

И теперь, самое сложное. Множество объектов "скроллится". Т.е. данные, например по -x,-y,z становятся неактуальными их нужно удалить, сместив все элементы внутри массива по этим осям на 1.
А в x,y,-z тут же будут записаны новые, актуальные элементы. И Min Max векторы нужно будет пересчитывать.


И наконец, ожидается огромное количество итераций, значит, ради экономии времени, хранить всё будем в одномерном массиве.

Начал писать класс, но уже есть проблемы. Несколько элементов, занесенных в массив в самом начале методом AddOrReplace когда еще Size == (1,1,1), после самого первого ресайза, "теряются".
Кроме того, иногда вылетает OutOfBounds на T val = oldArr[(...

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

public class Arr3D<T> {

private T[] arr;
private Vector3 min, max;
private Vector3 size;

public Arr3D() 
{
    arr = new T[0];
}

public void AddOrReplace(T obj, Vector3 pos) 
{
    Vector3 newMin = Vector3.Min(min, pos); // ( Min(x1,x2), Min(y1,y2), ...
    Vector3 newMax = Vector3.Max(max, pos+Vector3.one); // +(1,1,1)

    if(newMin != min || newMax != max) 
    {
        Resize(newMin, newMax);
    }

    Set(obj, pos);
}

public void Set(T obj, Vector3 pos) 
{
    Set(obj, pos.x, pos.y, pos.z);
}

public void Set(T obj, int x, int y, int z) 
{
    arr[ (y-min.y)*size.x*size.y  +  (z-min.z)*size.x + (x-min.x) ] = obj;
}

private void Resize(Vector3 newMin, Vector3 newMax) 
{
    Vector3 oldMin = min;
    Vector3 oldMax = max;
    T[] oldArr = arr;
    Vector3 oldSize = size;

    min = newMin;
    max = newMax;
    size = newMax - newMin;
    arr = new T[size.z*size.y*size.x];

    for(int x=oldMin.x; x<oldMax.x; x++) 
    {
        for(int y=oldMin.y; y<oldMax.y; y++) 
        {
            for(int z=oldMin.z; z<oldMax.z; z++) 
            {
                T val = oldArr[(y-oldMin.y)*oldSize.x*oldSize.y  +  (z-oldMin.z)*oldSize.x + (x-oldMin.x)];
                Set(val, x, y, z);
            }
        }
    }

}

public T Get(int x, int y, int z) 
{
    return arr[(y-min.y)*size.x*size.y  +  (z-min.z)*size.x + (x-min.x)];
}
}

Здравствуйте, Javaec, Вы писали:

J>Есть множество объектов в трехмерном пространстве. У каждого объекта целочисленные координаты, хранятся в Vector3(x,y,z).
J>Множество объектов мы получаем постепенно, т.е. сначала 0 объектов, потом 1, потом еще 1...

J>Допустим, все объекты будем хранить в трехмерном массиве.
А зачем в трехмерном? Почему-бы не сделать простой массив строк, с возможностью фильтрации/сортировки по значению одного или нескольких полей? Сколько объектов будет существовать одновременно?

Здравствуйте, Nikolay_Ch, Вы писали:

N_C>А зачем в трехмерном? Почему-бы не сделать простой массив строк, с возможностью фильтрации/сортировки по значению одного или нескольких полей? Сколько объектов будет существовать одновременно?

Размер пространства примерно 15x15x15 (3375). Но добавление новых элементов и "скроллинг" с удалением выходящих за границу — операции очень частые.
Не думаю, что есть смысл сортировать, если можно обращаться прямо к элементу по индексу. Производительность очень важна тут.

Здравствуйте, Javaec, Вы писали:
J>Очень прошу помощи, любой, от кода до совета.

Есть противоречие. При скроллинге теряется смысл доступа к элементу по индексу (координатам) и наоборот. Можно реальную задачу?

Здравствуйте, Ромашка, Вы писали:

Р>Есть противоречие. При скроллинге теряется смысл доступа к элементу по индексу (координатам) и наоборот. Можно реальную задачу?

Задача в рамках разработки компьютерной игры. Игрок двигается — пространство скроллится.

Скорость одного обращения приоритетна. Никаких ссылочных типов. Никаких произвольных обращений к памяти.

А по индексу можно же обращаться, т.к. мы храним min и max векторы и благодаря им можем вызвать Get(-4, 3, 7) и взять его по какому-нибудь, 27му индексу в одномерном массиве.
Всякая математика по вычислению индекса выполняется на порядок быстрее, чем само обращение к памяти.

Здравствуйте, Javaec, Вы писали:

Одномерный массив из компоненнтов с тремя координатами эмулирующий трёхмерный строил так:
float* mass=(float*)malloc(sizeof(float)*size1*size2*size3*3);
int a=size2*size3*3;
int b=size3*3;
for(x1=0;x1<size1;x1++){
for(x2=0;x2<size2;x2++){
for(x3=0;x3<size3*3;x3+=3){
mass[x1*a+x2*b+x3]=value_x
mass[x1*a+x2*b+x3+1]=value_y
mass[x1*a+x2*b+x3+2]=value_z

Правда доступ вида mass[a1][a2][a3][a4] превращается в mass[a1*size2*size3*3+a2*size3*3+a3*3+a4]
но в C++ это можно обернуть в объекты и методы класса так, что доступ будет в стиле Vector(a1,a2,a3).a4
И ещё у меня прокатывало весь mass скидывать glDrawArrays(GL_POINTS,0,size1*size2*size3);
и потом в геометрическом шейдере каждую вершину генерировать в полигон.

Здравствуйте, Javaec, Вы писали:

J>Здравствуйте, Nikolay_Ch, Вы писали:

N_C>>А зачем в трехмерном? Почему-бы не сделать простой массив строк, с возможностью фильтрации/сортировки по значению одного или нескольких полей? Сколько объектов будет существовать одновременно?

J>Размер пространства примерно 15x15x15 (3375). Но добавление новых элементов и "скроллинг" с удалением выходящих за границу — операции очень частые.
J>Не думаю, что есть смысл сортировать, если можно обращаться прямо к элементу по индексу. Производительность очень важна тут.
Меня слабо интересует размер пространства. Меня интересует количество объектов в этом пространстве. Не в каждой-же точке пространства висит по объекту? Если не в каждой — Вам все равно надо пробегать во всему списку объектов, чтобы определить, какие надо скрыть. Если в каждой, то я-бы подумал про списки, индексированные по одной из координат (три словаря на каждую плоскость). Тогда для отсечения нужных, Вам просто нужно будет фильтровать нужную плоскость. Объекты будут присутствовать одновременно во всех трех списках.

Здравствуйте, smeeld, Вы писали:

S>Здравствуйте, Javaec, Вы писали:

S>Одномерный массив из компоненнтов с тремя координатами эмулирующий трёхмерный строил так:
S>float* mass=(float*)malloc(sizeof(float)*size1*size2*size3*3);

Но это же массив для хранения точек. У вас каждая координата — отдельный элемент массива.

Мне не нужно хранить точки, т.к. координаты целочисленные. В моем случае, набор из трех координат — аргумент для обращения к элементу массива.
Элементом массива может быть int, если я буду хранить, например, температуру или радиоактивность.

Здравствуйте, Nikolay_Ch, Вы писали:

N_C>Меня слабо интересует размер пространства. Меня интересует количество объектов в этом пространстве. Не в каждой-же точке пространства висит по объекту? Если не в каждой — Вам все равно надо пробегать во всему списку объектов, чтобы определить, какие надо скрыть. Если в каждой, то я-бы подумал про списки, индексированные по одной из координат (три словаря на каждую плоскость). Тогда для отсечения нужных, Вам просто нужно будет фильтровать нужную плоскость. Объекты будут присутствовать одновременно во всех трех списках.

Не обязательно пробегать по всему списку объектов. Игрок переместился на (2,0,3) — передаем этот вектор массиву в метод скролла. И каждый элемент массива нужно сдвинуть на 2 по X и на 3 по Z. В отрицательную сторону.
Все, что не поместились — отбрасываем, т.к. не актуальны.

Здравствуйте, Javaec, Вы писали:


J>И теперь, самое сложное. Множество объектов "скроллится". Т.е. данные, например по -x,-y,z становятся неактуальными их нужно удалить, сместив все элементы внутри массива по этим осям на 1.
J>А в x,y,-z тут же будут записаны новые, актуальные элементы. И Min Max векторы нужно будет пересчитывать.

Насколько я понимаю тебе нужен "зацикленный массив". Поясню для линейного. Пусть в нем N элементов. Введем понятие логического номера элемента — это номер в твоей модели, не в массиве как таковом. Например, нулевой элемент модели при скроллинге влево должен исчезнуть, первый — стать нулевым и т.д. Правильно я понял ?


Изначально

логический 0-й хранится в a[0]
логический 1-й хранится в a[1]
...
логический N-1 хранится в a[N-1]

то есть логические и физические номера совпадают.


Когда делается скроллинг влево, полагаем, что

логический 0-й хранится в a[1] // т.е. бывший логический 0-й исчез, а бывший логический 1-й стал нулевым

логический 1-й хранится в a[2]
...
логический N-1 хранится в a[0]

Еще один скроллинг вправо и имеем

логический 0-й хранится в a[2]
логический 1-й хранится в a[3]
...
логический N-2 хранится в a[0]
логический N-1 хранится в a[1]

и т.д.

При этом подходе ничего вообще сдвигать не надо.

PD>Еще один скроллинг вправо и имеем

Влево, конечно.

Здравствуйте, Pavel Dvorkin, Вы писали:


PD>Насколько я понимаю тебе нужен "зацикленный массив". Поясню для линейного. Пусть в нем N элементов. Введем понятие логического номера элемента — это номер в твоей модели, не в массиве как таковом. Например, нулевой элемент модели при скроллинге влево должен исчезнуть, первый — стать нулевым и т.д. Правильно я понял ?
PD>...
PD>Когда делается скроллинг влево, полагаем, что
PD>логический 0-й хранится в a[1] // т.е. бывший логический 0-й исчез, а бывший логический 1-й стал нулевым

Всё верно. Только вот последние элементы на место первых в моей задаче ставить не нужно.
За вариант формулировки спасибо, теперь будет проще описывать задачу.

Не понятно только, почему в интернете так мало материала по вопросу представления многомерного массива одномерным.
У меня, например, обращение к элементу одномерного массива выполняется в 2-4 раза быстрее (в зависимости от кол-ва итераций), чем к элементу "развернутого" трехмерного.

Здравствуйте, Javaec, Вы писали:

J>Не понятно только, почему в интернете так мало материала по вопросу представления многомерного массива одномерным.
J>У меня, например, обращение к элементу одномерного массива выполняется в 2-4 раза быстрее (в зависимости от кол-ва итераций), чем к элементу "развернутого" трехмерного.

А что тут писать-то ? Элемент a[i][j][k] при размерах N,M,L есть

b[i*M*L + j*M + k]

Здравствуйте, Pavel Dvorkin, Вы писали:

PD>А что тут писать-то ? Элемент a[i][j][k] при размерах N,M,L есть

PD>b[i*M*L + j*M + k]

Это и так понятно. Написал уже, вот в resize есть баг. Отладкой найти пока не получается, выглядит код годно.
Где же проблема

А потом скроллинг как писать, чтобы шустренько работал? Nikolay_Ch предлагал использовать списки. Это конечно огромное расточительство по времени обращения к одному элементу.
Но для скроллинга быстрее работать со ссылками, чем поэлементно переписывать данные в массиве.

Здравствуйте, Javaec, Вы писали:


J>А потом скроллинг как писать, чтобы шустренько работал?

Еще раз прочти, что я написал. Там весь алгоритм скроллинга изложен. Грубо говоря, весь скроллинг сводится к операции ++ или -- — переносим логическое начало в массиве.


>Nikolay_Ch предлагал использовать списки. Это конечно огромное расточительство по времени обращения к одному элементу.

Списки — смотря какие. Если на базе массива — этот то же массив, в общем-то. Если на базе ссылочной реализации — это чудовищно.

J>Но для скроллинга быстрее работать со ссылками, чем поэлементно переписывать данные в массиве.

Ничего вообще переписывать не надо. Скроллинг — смещение логического начала в массиве, и ничего больше.

Здравствуйте, Pavel Dvorkin, Вы писали:

PD>Ничего вообще переписывать не надо. Скроллинг — смещение логического начала в массиве, и ничего больше.


Вот например одномерный массив температур:
{15,16,16,17}
чтобы его заскроллить нужно пройтись по всей его длине и переприсваивать элементы.

Получим:
{16,16,17,0}

Может есть какой-то другой способ, который быстрее? Буду благодарен, если опишите.

Здравствуйте, Pavel Dvorkin, Вы писали:

>>Nikolay_Ch предлагал использовать списки. Это конечно огромное расточительство по времени обращения к одному элементу.
PD>Списки — смотря какие. Если на базе массива — этот то же массив, в общем-то. Если на базе ссылочной реализации — это чудовищно.
Пока мне вообще непонятно, что автор топика хранит внутри массива, более того, я не понял, заполнен ли массив целиком или только частично.
Ссылочные типы не всегда чудовищны, особенно, когда надо делать кластеризацию. Или в случае, если массив слабо заполнен.

Здравствуйте, Javaec, Вы писали:

J>Вот например одномерный массив температур:
J>{15,16,16,17}
J>чтобы его заскроллить нужно пройтись по всей его длине и переприсваивать элементы.
А не лучше ли Вам подумать насчет использования "скользящего окна", которое определяет, что отображается в данный момент на экране? Тогда скроллирование сведется к изменению начала координат, как написал Павел? Никаких переприсваиваний не нужно будет.

Здравствуйте, Nikolay_Ch, Вы писали:

N_C>А не лучше ли Вам подумать насчет использования "скользящего окна", которое определяет, что отображается в данный момент на экране? Тогда скроллирование сведется к изменению начала координат, как написал Павел? Никаких переприсваиваний не нужно будет.

Да, но тогда нужно будет сразу выделять память под всё.
Т.е. делать массив, размер которого будет полностью соответствовать количеству зон в игровом мире.
Надо подумать, сколько потребуется памяти.

Здравствуйте, Javaec, Вы писали:


J>Вот например одномерный массив температур:
J>{15,16,16,17}
J>чтобы его заскроллить нужно пройтись по всей его длине и переприсваивать элементы.

J>Получим:
J>{16,16,17,0}

J>Может есть какой-то другой способ, который быстрее? Буду благодарен, если опишите.

Да зачем его надо скроллить заменой элементов?
Есть два указателя — голова и хвост. В терминах C# — два индекса. Для трёхмерного массива будет 6 индексов. Дальше манипуляции с ними: скроллинг — это инкремент/декремент индексов голов. И отсечение по индексу хвостов, если надо нули выдавать или некое значение-по-молчанию. Сам массив будет фиксированного размера, элементы значениями переписывать дорого и только по исключительной необходимости.

Здравствуйте, Javaec, Вы писали:

J>Надо подумать, сколько потребуется памяти.
Интересно... А для какой платформы Вы пишете, что накладывает жесткие ограничения по памяти?

Здравствуйте, Javaec, Вы писали:


J>Вот например одномерный массив температур:
J>{15,16,16,17}
J>чтобы его заскроллить нужно пройтись по всей его длине и переприсваивать элементы.

Нет, не нужно. Нужно ввести переменную xOrigin и присвоить ей сначала 0. Элементы берем от xOrigin до конца массива, а потом от 0 до xOrigin-1, всего N штук. То есть вначале

a[xOrigin] = 15
a[xOrigin+1] = 16
a[xOrigin+2] = 16
a[xOrigin+3]=17

А теперь нужно сделать скроллинг. Выполняем xOrigin++, xOrigin становится равным 1, и это все. Теперь элементы берем в следующем порядке

a[xOrigin] = 16
a[xOrigin+1] = 16
a[xOrigin+2] = 17
а следующий элемент a[0] изменяем, ставим 0



J>Получим:
J>{16,16,17,0}

Именно это и получим

Массив закольцован — за последним (N-1) элементом следует 0-й. Логическое начало массива не в 0-м элементе, а в элементе с номером xOrigin.

Здравствуйте, Nikolay_Ch, Вы писали:

N_C>Пока мне вообще непонятно, что автор топика хранит внутри массива, более того, я не понял, заполнен ли массив целиком или только частично.

Мне тоже не совсем ясно, но он хочет трехмерный массив, по-видимому, не слишком большой, и с возможностью скроллинга. ИМХО в этом случае не стоит заводить что-то иное, кроме массива, а скроллинг сделать с помощью wrap index.

N_C>Ссылочные типы не всегда чудовищны, особенно, когда надо делать кластеризацию. Или в случае, если массив слабо заполнен.

Истина конкретна, да, есть, конечно, случаи, когда стоит хранить в виде списка или хеш-таблицы. Но мне как-то претит превращать O(1) во что бы то ни было еще.

Здравствуйте, Javaec, Вы писали:
J>Задача в рамках разработки компьютерной игры. Игрок двигается — пространство скроллится.

То есть никакого рандомного доступа к элементам массива? Нафиг массивы, делать списками.

J>А по индексу можно же обращаться, т.к. мы храним min и max векторы и благодаря им можем вызвать Get(-4, 3, 7) и взять его по какому-нибудь, 27му индексу в одномерном массиве.

Кому может понадобиться элемент [-4, 3, 7] без [-4, 3, 6] и [-4, 3, 8]?

J>Всякая математика по вычислению индекса выполняется на порядок быстрее, чем само обращение к памяти.

Да не нужно вообще математики.

Здравствуйте, Javaec, Вы писали:

J>Размер пространства примерно 15x15x15 (3375). Но добавление новых элементов и "скроллинг" с удалением выходящих за границу — операции очень частые.

Не знаю, конечно, всех имеющихся ограничений, но по идее если даже делать тупо трёхмерным массивом со скроллингом 60 раз в секунду, то 15х15х15 ― это не тот объём данных, на котором что-то может тормозить. Мне кажется, с этим справится даже ZX-Spectrum со своим CPU Z80 3,5МГц, не говоря о мобилках и тем более PC.

Я писал свой воксельный движок под Unity (https://vimeo.com/album/1836529). Много экспериментировал с разными способами хранения данных и в конечном итоге пришёл к такому варианту:
1. Весь окружающий игрока трёхмерный мир (1024х128х1024 = 128Мб) хранится в единой закольцованной в горизонтальных направлениях структуре данных, реализованной одномерным массивом. Можно сказать, что это закольцованный одномерный массив, но это несколько двусмысленная формулировка.
2. Так как структура закольцована, по мере перемещения игрока по миру скроллировать её не надо. Достаточно только скинуть на диск области, которые вышли из поля зрения, и после этого записать в массив данные для областей, которые вошли в поле зрения.

Вот так примерно выглядит устройство массива:

internal class World
{
    public const int WORLD_WIDTH_SHIFT = 10; // 10 -> the world is 1024 blocks wide
    public const int WORLD_WIDTH = 1 << WORLD_WIDTH_SHIFT;
    public const int WORLD_WIDTH_MASK = WORLD_WIDTH - 1;

    public const int WORLD_HEIGHT_SHIFT = 7; // 7 -> the world is 128 blocks high
    public const int WORLD_HEIGHT = 1 << WORLD_HEIGHT_SHIFT;
    public const int WORLD_HEIGHT_MASK = WORLD_HEIGHT - 1;

    private const int WORLD_ARRAY_SIZE = WORLD_WIDTH * WORLD_HEIGHT * WORLD_WIDTH;
    private const int WORLD_ARRAY_MASK = WORLD_ARRAY_SIZE - 1;

    public readonly Block[] blocks = new Block[WORLD_ARRAY_SIZE];

    public static int CalculatePointer(int wx, int wy, int wz)
    {
        wx &= WORLD_WIDTH_MASK;
        wz &= WORLD_WIDTH_MASK;

        return (((wx << WORLD_WIDTH_SHIFT) + wz) << WORLD_HEIGHT_SHIFT) + wy;
    }

    public Block GetBlock(int wx, int wy, int wz)
    {
        int pointer = CalculatePointer(wx, wy, wz);
        return blocks[pointer];
    }

    public void SetBlock(int wx, int wy, int wz, Block value)
    {
        int pointer = CalculatePointer(wx, wy, wz);
        blocks[pointer] = value;
    }
}

Также прелесть в том, что все обращения к такой структуре можно проводить прямо в мировых координатах. Например, если изначально в массиве хранятся данные начиная с x=0 по x=1023 включительно, то при перемещении игрока вправо все ячейки с координатами x=0 выходят из поля зрения, а ячейки с x=1024 появляются. Мы должны ячейки с x=0 прочитать и скинуть куда-нибудь на диск:

var oldValue = world.GetBlock(wx: 0, wy: ..., wz: ...);

а потом ячейки с x=1024 подгрузить с диска и записать в массив:

world.SetBlock(wx: 1024, wy: ..., wz: ..., value: newValue);

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