Структура для иерархического хранения компонентов

Question

Я уже несколько дней бьюсь над этой проблемой и не пришел к каким-либо удовлетворительным выводам, поэтому решил, что я бы попросил команду SO за их мнение. Для игры, над которой я работаю, я использую объектную модель компонентов, как описано здесь и здесь . На самом деле все идет довольно хорошо, но мое текущее решение для хранения данных оказывается ограниченным (я могу запрашивать компоненты только по имени класса или по произвольному имени «семейства»). Что мне хотелось бы, так это возможность запрашивать данный тип и выполнять итерацию по всем компонентам этого типа или любого производного от него типа.

При рассмотрении этого вопроса я впервые реализовал простую схему RTTI, в которой тип базового класса хранится через производный тип в указанном порядке. Это означает, что RTTI для, скажем, спрайта будет: component :: renderable :: sprite. Это позволяет мне легко сравнивать типы, чтобы увидеть, является ли тип A производным от типа B, просто сравнивая все элементы B: то есть component :: renderable :: sprite получен из component :: renderable, но не component :: timer. Просто, эффективно и уже реализовано.

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

       component
       /       \
  timer         renderable
  /              /      \
shotTimer   sprite      particle

На каждом узле я буду хранить список всех компонентов этого типа. Таким образом, запрос узла "component :: renderable" даст мне доступ ко всем компонентам визуализации, независимо от производного типа. Проблема в том, что я хочу иметь доступ к этим компонентам с помощью итератора, чтобы я мог сделать что-то вроде этого:

for_each(renderable.begin(), renderable.end(), renderFunc);

и переберите все дерево от рендеринга вниз. У меня довольно много работы с использованием действительно уродливой структуры узлов карты / вектора / дерева и специального прямого итератора, который отслеживает стек узлов, где я был. Хотя все время я реализовывал, я чувствовал, что должен быть лучший, более ясный путь ... Я просто не могу думать об одном: (

Итак, вопрос в том, чрезмерно ли я это усложняю? Есть ли какое-то очевидное упрощение, которое я упускаю, или уже существующая структура, которую я должен использовать? Или это просто унаследованная сложная проблема, и я, наверное, уже хорошо справляюсь?

Спасибо за ваш вклад!

Answer 1

Вам следует подумать о том, как часто вам нужно делать следующее:

• пройти по дереву
• добавить / удалить элементы из дерева
• сколько объектов нужно отслеживать

Что чаще всего поможет определить оптимальное решение

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

map<string,set<componenet *>>  myTypeList

Тогда для объекта, который имеет тип component :: renderable :: sprite

myTypeList["component"].insert(&object);
myTypeList["renderable"].insert(&object);
myTypeList["sprite"].insert(&object);

Регистрируя каждый объект в нескольких списках, становится легко что-то делать со всеми объектами данного типа и подтипов

for_each(myTypeList["renderable"].begin(),myTypeList["renderable"].end(),renderFunc);

Обратите внимание, что std :: set и моя конструкция std :: map не могут быть оптимальным выбором, в зависимости от того, как вы будете их использовать.

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

map<string, set<string> > myTypeList;
map<string, set<component *> myObjectList;

myTypeList["component"].insert("component");
myTypeList["component"].insert("renderable");
myTypeList["component"].insert("sprite");
myTypeList["renderable"].insert("renderable");
myTypeList["renderable"].insert("sprite");
myTypeList["sprite"].insert("sprite");

// this isn't quite right, but you get the idea
struct doForList {
    UnaryFunction f;
    doForList(UnaryFunction f): func(f) {};
    operator ()(string typename) { 
       for_each(myTypeList[typename].begin();myTypeList[typename].end(), func);
   }
}

for_each(myTypeList["renderable"].begin(),myTypeList["renderable"].end(), doForList(myFunc))

Answer 2

Если вы хотите увидеть код для существующей реализации, статья Game Programming Gems 5, на которую ссылается страница Cowboy Programming, поставляется с несколько урезанной версией кода, который мы использовали для нашей системы компонентов (я сделал довольно много разработка и внедрение системы, описанной в этой статье).

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

Итак, в вашем примере Sprite и Particle объявили бы, что они реализовали интерфейс RENDERABLE, и если бы мы хотели сделать что-то для всех визуализируемых объектов, мы бы просто просмотрели список активных компонентов и проверили каждый. На первый взгляд это не очень эффективно, но на практике это было прекрасно. Основная причина, по которой это не было проблемой, заключалась в том, что на самом деле это не очень распространенная операция. Такие вещи, как рендеринг, например, добавляются в сцену рендеринга при создании, поэтому глобальный менеджер сцены поддерживает свой собственный список рендерируемых объектов, и ему никогда не требуется запрашивать систему компонентов для них. Аналогично с физикой, компонентами столкновений и тому подобными вещами.

Answer 3

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

Теперь, если вы немного ограничите проблему, существует ряд старомодных алгоритмов для хранения деревьев произвольных данных в виде массивов. Мы использовали их много в дни Фортрана. У одного из них был ключевой трюк, состоящий в том, чтобы хранить дочерние элементы A, скажем, A2 и A3, по индексу (A) * 2, индексу (A) * 2 + 1. Проблема в том, что если ваше дерево редкое, вы теряете пространство, а размер вашего дерева ограничен размером массива. Но, если я правильно помню, вы получаете элементы в порядке широты, используя простой цикл DO.

Взгляните на том 3 Кнута, там есть тонна этого материала.