Использование контейнеров в разработке игр.

Автор: Игорь Курилов

Ни одна игра, сложная или простая не может обойтись без контейнеров. В своих играх вы используете собственные контейнеры (возможно не подозревая как они называются:) или стандартные на основе шаблонов. Контейнерами называют объекты, способные хранить списки данных определенного типа. Контейнеры делятся по способу обращения к информации на векторы, карты (или словари) и списки. Шаблоны контейнеров входят в стандартную библиотеку C++ — STL. Целью этой серии статей является рассмотреть применение контейнеров в разработке игр. Подразумевается, что вы владеете C++ и хотя бы чуть-чуть знакомы с STL. (Впрочем, никогда не поздно ознакомиться, тем более описаний ее достаточно в интернете. MSDN также содержит полное описание STL, входящей в пакет VC++).

Быстрые списки
Карты ресурсов

Быстрые списки

Прежде всего - для чего нужны списки? Списки предоставляют последовательный доступ к данным. Очень часто программируя игры, мы сталкиваемся с необходимостью динамически создавать однообразные структуры, после чего производить с ними одинаковые действия. Это могут быть юниты в вашей стратегической игре или системы частиц для создания эффектов в вашей стрелялке. Естественно, для динамичной игрушки важна скорость. Наибольшую скорость в доступе к данным дают массивы. Но у них есть существенный недостаток - очень медленная вставка и удаление элементов, поскольку они связаны с итерационными алгоритмами. Поэтому массивы используются только для статических множеств данных. Для реализации динамических множеств придуманы списки.

Стандартная библиотека STL содержит шаблон std::list который позволяет создавать списки для различных типов данных. Например:

#include <list>   // заголовок, где описан std::list
using namespace std; // используем область имен std

typedef   list<int>  INT_LIST;    // список int-ов
typedef   list<LPVOID>  PTR_LIST;  // список из указателей
typedef   list<POINT>  POINT_LIST;    // список координат

В принципе, стандартные списки дают все, что нам нужно за одним исключением. При добавлении нового элемента std::list выделяет новый блок памяти, а при удалении - освобождает его. А это медленные операции. К тому же вставка нового элемента происходит следующим образом:

list::push_back( MyVariable );

Прежде всего, как решить проблему выделения памяти? - Выделить ее сразу столько, сколько может понадобиться. Этот путь похож на реализацию массива. Так и есть - мы создаем массив. Итак, наш шаблон будет выглядеть следующим образом:

template <class Type> class list

Объявляем указатель на данные:

typedef Type * t_ptr; // указатель на данные

Переменная для хранения указателя на массив данных:

t_ptr m_pData; // массив для данных

Код выделения m_Capacity элементов:

m_pData = new Type[m_Capacity];

Как теперь организовать список? Самый быстрый вариант списка - связной список. Он представляет собой набор элементов, каждый из которых хранит указатель на следующий и предыдущий. Конечно, элемент связного списка может иметь указатель только на следующий элемент, но тогда мы сможем перемещаться только в одну сторону (чего обычно достаточно) и второй недостаток - медленное удаление единичного элемента из списка. Т.е. такой список может накоплять элементы. Удалять же можно только все  элементы сразу. Поэтому мы будем использовать следующую структуру для элементов списка:

typedef struct { 
         void * pNext;   //  указатель на следующий элемент
         void * pPrior;   //  указатель на предыдущий элемент
         t_ptr pData;      //  указатель на данные
} t_listitem; 

Чтобы не выделять память каждый раз для нового элемента t_listitem мы выделим ее сразу для всех:

m_pCache = m_pItems = new t_listitem[m_Capacity];

Но как же нам не растерять резервные элементы? Мы их тоже соберем в список, а начало списка поместим в переменную m_pCache. Следующий фрагмент демонстрирует организацию резервного списка:

// связываем элементы списка в одну цепочку 
t_listitem *pLast = NULL; 
t_listitem *pCurrent = m_pCache; 
for(int n=0; n < m_Capacity; n++, pCurrent++){ 
      pCurrent->pPrior = (void*)pLast; 
      pCurrent->pData = m_pData + n; 
      if(pLast!=0) pLast->pNext = (void*)pCurrent; 
      pLast = pCurrent; 
} 
m_pCache[m_Capacity-1].pNext = 0; 

Теперь реализуем добавление нового элемента на примере добавления в начало списка:

Type & add_first() { 
     // перемещаем элемент из резерва в начало списка 
     t_listitem *item = m_pCache;   // первый свободный элемент
     m_pCache = (t_listitem*)item->pNext; // убираем его из резерва
     if(m_pCache!=0) m_pCache->pPrior = 0; 
     // добавляем в список
     if(m_pBegin== 0) m_pEnd= item; 
     else m_pBegin->pPrior = (void*)item; 
     item->pNext = (void*)m_pBegin; 
     m_pBegin = item; 
     // приводим в соответствие количества элементов в списке и резерве 
     m_Size++; 
     m_Capacity--; 
     return *(item->pData); 
} 

Чтобы удалить элемент из списка нужно просто связать между собой предыдущий и следующий элементы:

void remove(const iterator & i) { 
     if(i.m_pPosition->pPrior!=0) 
         ((t_listitem*)(i.m_pPosition->pPrior))->pNext = i.m_pPosition->pNext; 
     if(i.m_pPosition->pNext!=0) 
         ((t_listitem*)(i.m_pPosition->pNext))->pPrior = i.m_pPosition->pPrior; 
     if(i.m_pPosition==m_pBegin) 
         m_pBegin = (t_listitem*)(i.m_pPosition->pNext); 
     if(i.m_pPosition==m_pEnd) 
         m_pEnd = (t_listitem*)(i.m_pPosition->pPrior); 
     // приводим в соответствие количества элементов в списке и резерве 
     m_Size--; 
     m_Capacity++; 
}

Тут мы использовали класс iterator (итератор). Итератор нужен для позиционирования в списке, он выполняет роль своеобразного индекса. Итератор скрывает внутреннюю реализацию списка. Вся функциональность итератора заключена в четырех операторах:

Код класса iterator небольшой, поэтому приведу его полностью:

class iterator // класс для перебора записей 
{ 
friend class legionary::list; 
protected: 
     t_listitem * m_pPosition; // указатель на текущий элемент цепочки 
public: 
     iterator() { m_pPosition = 0; } 
     ~iterator() {} 
     Type & operator*() { // оператор для получения данных (*iter) 
          return *(m_pPosition->pData); 
     } 
     iterator& operator++() { // для движения по списку вперед 
          m_pPosition = (t_listitem*)m_pPosition->pNext; return (*this); } 
     iterator& operator--() { // для движения по списку назад 
          m_pPosition = (t_listitem*)m_pPosition->pPrior; return (*this); } 
     iterator& operator=(const iterator& iter) { // для движения присвоения 
          m_pPosition = iter.m_pPosition; return (*this); } 
     // проверка возможности перемещения 
     bool valid() { return (m_pPosition!=0); } 
     bool last() { return (m_pPosition->pNext!=0); } 
     bool first() { return (m_pPosition->pPrior!=0); } 
};

Ну, вот и все, шаблон списка готов. Полностью код legionary::list можно найти в файле baseobj.h. Хотелось бы узнать его эффективность. Для этого я написал тестовую программу test.cpp. Результаты теста показывают, что полученный список работает на порядок быстрее (до 30 раз) чем стандартный при операциях вставки и удаления элементов и до 4х раз быстрее при перемещении по списку.

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

#STL, #итераторы, #контейнеры

14 июня 2002 (Обновление: 17 сен 2009)

Комментарии [6]