Перейти вниз
Admin
Admin
Admin
Сообщения : 46
Дата регистрации : 2019-08-31

Заготовки статей Empty Заготовки статей

в Вс Окт 27, 2019 12:28 am
Заголовок статьи: "Структура данных «Дерево»"
Контент:
____________________________________________________

Статья взята с сайта https://coderdailynotes.wordpress.com/2019/10/19/структура-данных-дерево/


Структура данных «Дерево»


Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная .

Зачем нужны деревья?

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

  • автомобиль, состоящий из кузова и колес
  • танк с вращающейся башней
  • оружие в руке персонажа


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

Как известно, для анимации персонажа используется технология скелетной анимации. Так вот, скелет персонажа также можно представить в форме дерева.

Часто в играх используются одинаковые предметы, разбросанные по уровню. Это разнообразные деревья, камни, ящики, бочки и т.д. Нужно отметить, что в узел дерева сцены можно добавить какие угодно данные. Например, если добавить в узел дерева сцены указатель на объект 3D-модели, то можно будет получить возможность использовать одну 3D-модель для нескольких экземпляров игровых объектов одного типа. Например, если нужно расположить несколько одинаковых бочек на уровне, нужно будет загрузить в память всего одну 3D-модель бочки и связать с ней столько узлов дерева сцены, сколько бочек данного вида необходимо на уровне. Получаем экономию ресурсов. Конечно, это упрощенное описание, но суть оно передает.

Структура дерева

Дерево — это структура данных, состоящая из узлов, каждый из которых может иметь произвольное количество дочерних узлов. У дерева есть единственный узел, у которого нет родительского узла. Такой узел называется корнем дерева. У каждого узла дерева, кроме корня, может быть только один родительский узел. Узел также может и не иметь ни одного дочернего узла. Обычно такие узлы называют листьями. Узлы, у которых есть и родитель, и дочерние узлы, называются ветвями. Ниже представлена схема дерева, имеющая три уровня в своей иерархии:

Заготовки статей Cdn_article_tree

Как программно представить дерево?

Так как узлы связаны друг с другом, то нужно сначала создать класс узла. В общем случае у каждого узла есть:


  1. родитель;
  2. множество дочерних узлов.

Код:
class TreeNode {
public:
 TreeNode* parent_; // указатель на родительский узел
 std::list<TreeNode*> childList_; // список дочерних узлов
};
Имея указатель на родительский узел и список дочерних узлов, можно перемещаться по иерархии узлов. Необязательно, чтобы узел имел список дочерних узлов. Можно задать указатели на родственные узлы — те узлы, которые являются дочерними по отношении к родителю данного узла. Тогда вместо списка дочерних узлов можно задать указатель на первый дочерний узел в списке.

Код:
class TreeNode {
public:
 TreeNode* parent_; // указатель на родительский узел
 TreeNode* firstChild_; // указатель на первый дочерний узел

 // указатели для перебора дочерних узлов родителя данного узла
 TreeNode* next_;
 TreeNode* prev_;
};
Первый подход быстрее в реализации, поскольку вам самим не придется программировать вставку и удаление дочерних узлов в список. Также список std::list предоставляет удобный способ прохода по дочерним узлам. Но впоследствии нужно будет думать о применении оптимального аллокатора (распределителя) памяти, потому что список std::list создает копии хранимых элементов через оператор new (если вы не задали свой аллокатор), что при частой вставке и удалении дочерних узлов приведет к дефрагментации памяти.

Правила программирования вставки и удаления узлов из дерева

1. Сначала отсоедини, потом присоединяй.

Вставлять в дерево можно только свободные узлы — то есть узлы, которые не привязаны ни к какому дереву. Как не трудно догадаться, когда узел отсоединяется от дерева, то он сам становится деревом. Т.е. свободные узлы — это деревья. Пусть даже если дерево состоит из одного корня.

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

2. Связь узлов  — двусторонняя.

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

3. В дереве не может быть циклов.

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

4. Предусмотрите управление распределением памяти для узлов.

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

Поведение дерева

Паттерн «грязный бит»

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

Существующие библиотеки

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