Вопросы о структуре данных итерации игрового цикла - PullRequest
Новая
       30

Вопросы о структуре данных итерации игрового цикла

1 голос
/ 02 марта 2011

Итак, я пишу 2D-движок Java на основе LWJGL. (Это будет с открытым исходным кодом, но когда это будет немного более отточено.: P) Я довольно далеко вперед, но, пытаясь пройти еще одну полировку, я решил, что мне нужно какое-то внешнее мнение о структуре данных. Я пользуюсь.

Структура называется UpdateList <(generic)> . По сути, я хочу, чтобы полностью динамический список объектов представлял все объекты в игре, и в то же время имел возможность проходить через него со скоростью массива, поскольку предположительно можно ссылаться на сотни + объектов.

Для этого в классе есть 3 члена данных: ArrayList <(generic)> , массив того же типа и логическая отметка, изменившаяся список или нет (озаглавленный изменен ).

Класс работает довольно просто - объекты добавляются и удаляются из ArrayList, как вы можете себе представить, и при этом задает , изменяющее на true .

Тогда есть два метода, которые включают доступ к массиву - updateList (T []) и getUpdateList () .

updateList передает массив в ArrayList для его метода toArray (generic []); для массива установлено это новое значение (если изменено - истинно - если список не изменился, ничего не происходит).

getUpdateList возвращает массив.

Таким образом, для использования updateList вызывается всякий раз, когда разработчик хочет обновить массив, а getUpdateList используется для итерации. Это не только немного быстрее, чем просто использование ArrayList, но и позволяет избежать ConcurrentModificationErrors, а UpdateList можно редактировать во время итерации.

Итак, два вопроса:

1 :) Это хороший способ получения нужного мне типа структуры данных? С точки зрения использования / API это очень просто, но меня беспокоит метод ArrayList toArray. Сколько времени это займет при большем количестве записей? Если это громоздко, есть ли лучший динамический класс, который я могу использовать?

2 :) Во-вторых, мне не нравится вызывать updateLists (T [0]). Есть ли хороший способ управлять копией ArrayList в массив без необходимости в этом?

Ответы [ 2 ]

4 голосов
/ 02 марта 2011

1 :) Это хороший способ получения нужного мне типа структуры данных?

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

С точки зрения использования / API, это очень просто, но я обеспокоен методом ArrayList toArray.Сколько времени это займет при большем количестве записей?Если это громоздко, есть ли лучший динамический класс, который я могу использовать?

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

  1. Один поток отслеживает изменения и записывает ссылки на отдельные объекты в ChangedSet структура данных (с блокировкой записи вокруг записи).Это заменит ваш логический changed набором измененных объектов.Также обратите внимание, что Sets имеет свойство уникальности, поэтому вам не нужно беспокоиться о добавлении одного и того же объекта несколько раз.

  2. Другой поток ожидает сигнала для обновления экрана, чтение блокирует ChangedSet, копирует содержимое как ArrayList (или UpdateList, если вы его так называете), а затем очищает ChangedSet (снятие блокировки чтения).

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

EDIT : ответ на вопрос в комментарии

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

HOWEVER , вы должны помнить, что Java всегда многопоточная, независимо от того, понимаете вы это или нет.Поток Swing (AKA AWT Event Queue) отделен от ваших вычислений. SwingUtilities.invokeLater () - отличное решение для добавления кода отложенного рендеринга в однопоточное решение.

Просто помните, очень важно создать такое разъединение между кодом рендеринга и даннымиуправление.Вы можете сделать это либо с отдельными структурами, либо с соответствующим параллелизмом, но если вы проигнорируете проблему, у вас будет либо тупик, либо ConcurrentModificationExceptions .

END EDIT :

1 голос
/ 02 марта 2011

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

...