Какую структуру данных лучше всего использовать для запросов на основе типов? - PullRequest
Новая
       13

Какую структуру данных лучше всего использовать для запросов на основе типов?

0 голосов
/ 29 декабря 2011

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

У меня много различных типов игровых элементов.Все они имеют тип Entity.

. Существует много типов сущностей, в том числе видимых, которые необходимо нарисовать на экране.Эти сущности имеют тип VisibleEntity, который расширяет Entity.

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

Мой вопрос такой:

Какая структура данных имеет наилучшую сложность во время выполнения при выдаче запросов следующих типов?

1) получить объекты типа Entity

2) получить объекты типа VisibleEntity

3) получить объекты типа SomeSpecificGameObject

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

Очевидно, что это невозможно, когда вычисления выполняются в каждом кадре для определенных элементов на экране.

Каков наилучший способ отслеживатьвсего этого?

Я ценю любой ответ!

Ответы [ 3 ]

4 голосов
/ 29 декабря 2011

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

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

class MyEntityList {
    List<Entity> entityList = new ArrayList();
    List<MyEntityList> subclassLists = new ArrayList();
}

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

1 голос
/ 29 декабря 2011

Очевидно, что это невозможно, когда вычисления выполняются в каждом кадре для определенных элементов на экране.

Это действительно зависит от количества объектов. Современный процессор работает несколько миллиардов раз в секунду. Предполагая, что проверка и добавление в список занимает 10 циклов, а вы выполняете 100 кадров в секунду, повторение списка из 1000 элементов для каждого кадра приведет к загрузке процессора на уровне 0,1%. Таким образом, наоборот, наивное решение очень выполнимо, если у вас нет тысяч игровых объектов или вам не нужно делать запросы по типу много раз за кадр. Как обычно, рекомендация состоит в том, чтобы реализовать простейшую вещь, которая могла бы работать, измерить влияние на производительность и оптимизировать только в том случае, если это влияние является значительным.

Тем не менее, следующая простейшая вещь - сделать: 

abstract class Entity {
    private static Map<Class<?>, Set<? extends Entity>> byType = new HashMap<>();

    public static <E extends Entity> Set<E> allOfType(Class<E> clazz) {
        @SuppressWarnings("unchecked")
        Set<E> set = (Set<E>) byType.get(clazz);
        if (set == null) {
            set = new LinkedHashSet<E>();
            byType.put(clazz, set);
        }
        return set;
    }

    @SuppressWarnings({ "rawtypes", "unchecked" })
    protected Entity() {
        for (Class c = getClass(); c != Object.class; c = c.getSuperclass()) {
            allOfType(c).add(this);
        }
    }

    @SuppressWarnings({ "rawtypes", "unchecked" })
    protected void destroy() {
        for (Class c = getClass(); c != Object.class; c = c.getSuperclass()) {
            allOfType(c).remove(this);
        }
    }
}

который вы бы использовали как 

for (VisibleEntity ve : Entity.allOfType(VisibleEntity.class)) {
    ve.render();
}

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

1 голос
/ 29 декабря 2011

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

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

Что касается других произвольных атрибутов, вы можете представлять их обобщенно, а затем поддерживать индексы для быстрого поиска, или, как высказал, держать их в списках и иметь простую функцию фильтра, которая может вернуть вам подмножество объектов, которые соответствуют определенным критериям.Если объектов не так много, второй подход должен работать нормально.Пороговое значение для «too many» - это значение, которое вам, вероятно, придется выяснить при некотором тестировании.

...