Готовый перевод Game Programming Patterns / Паттерны программирования в играх: 1.2. Flyweight

Поднимается туман, открывая взору старый величественный лес.

Древние болиголовы бесчисленным числом возвышаются над вами, образуя собор из зелени.

Витражный навес из листьев преломляет солнечный свет, превращая его в золотые лучи тумана.

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

О подобном другом мире мы мечтаем, будучи разработчиками игр, и такие сцены часто возможны благодаря паттерну со скромнейшим названием "Приспособленец" (Flyweight).

Засадим деревьями лес.

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

Когда экран заполняет целый лес отдельных деревьев, всё, что видит программист графики - это миллионы полигонов, которые ему как-то нужно передавать видеокарте каждую шестидесятую часть секунды.

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

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

Каждое дерево имеет кучу связанных с ним данных:

Сетка из полигонов, которые определяют форму ствола, ветвей и зелени.

Текстуры для коры и листьев.

Его положение и ориентация в лесу.

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

Если придется написать быстрый код, то получится что-то вроде этого:

class Tree

{

private:

Mesh mesh_;

Texture bark_;

Texture leaves_;

Vector position_;

double height_;

double thickness_;

Color barkTint_;

Color leafTint_;

};

Тут много данных, особенно для сетки и текстур.

Загрузить видеокарту целым лесом этих объектов в одном кадре - это слишком.

К счастью, есть проверенный временем приём для обработки такой ситуации.

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

Скорее всего, все они используют одну и ту же сетку и текстуры.

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

Вы должны быть сумасшедшим или миллиардером с соответствующим бюджетом для художников, чтобы индивидуально моделировать каждое дерево в целом лесу.

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

Мы можем смоделировать это явно, разбив объект наполовину.

Сперва возьмем данные, общие для всех деревьев, и переместим их в отдельный класс:

class TreeModel

{

private:

Mesh mesh_;

Texture bark_;

Texture leaves_;

};

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

Затем каждый экземпляр дерева получает ссылку на общий класс TreeModel.

Что остаётся в классе Tree, так это состояние, которое индивидуально для каждого экземпляра:

class Tree

{

private:

TreeModel* model_;

Vector position_;

double height_;

double thickness_;

Color barkTint_;

Color leafTint_;

};

Можно представить это так:

Это выглядит очень похожим на паттерн "тип объекта" (Type Object).

Оба включают делегирование части состояния объекта некоему другому объекту, совместно используемому несколькими экземплярами.

Как бы то ни было, цели паттернов отличаются.

Цель паттерна "Тип объекта" (Type Object) - минимизировать количество определяемых классов, загрузив "типы" в собственную модель объекта.

Любое совместное использование памяти, получаемое при этом, всего лишь бонус.

Паттерн "приспособленец" (Flyweight) полностью нацелен на эффективность.

Это всё хорошо для хранения объектов в основной памяти, но никак не помогает при отрисовке.

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

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

Тысяча экземпляров

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

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

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

К счастью, сегодняшние графические API и видеокарты поддерживают именно то, что мы хотим.

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

В обоих API вы предоставляете два потока данных.

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

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

С помощью единственного вызова метода отрисовки появляется целый лес.

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

Паттерн "приспособленец" (Flyweight)

Теперь, когда у нас в кобуре есть конкретное оружие в виде примера, можно рассмотреть весь паттерн.

"Приспособленец" ("Flyweight" по англ. - игра слов "fly" - лететь, "weight" - вес) вступает в игру, когда есть объекты, требующие большей "легковесности", в основном потому что их слишком много.

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

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

"Банда четырех" называет это свойственным состоянием, но мне нравится термин "контекстно-свободные" характеристики.

В примере это геометрия и текстуры дерева.

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

Здесь это позиция, масштаб и цвет каждого дерева.

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

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

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

Этот паттерн менее очевидный (и потому более хитрый)

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

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

Позвольте мне продемонстрировать другой пример.

Где бы пустить корни

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

На земле может быть трава, грязь, холмы, озера, реки и любой другой ландшафт по желанию.

Мы сделаем землю мозаичной: поверхность в виде огромной сетки крошечных плиток.

Каждая плитка покрыта одним видом ландшафта.

Каждый тип ландшафта имеет несколько свойств, влияющих на геймплей:

Стоимость передвижения, определяющая, насколько быстро игроки смогут двигаться по ландшафту.

Флаг, является ли ландшафт водным, чтобы его можно было пересекать на лодках.

Текстура, используемая для визуализации.

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

Вместо этого, обычный подход - использовать перечисление для типов ландшафта:

В конце концов, мы уже усвоили урок с теми деревьями.

enum Terrain

{

TERRAIN_GRASS,

TERRAIN_HILL,

TERRAIN_RIVER

// Другие виды ландшафта...

};

Далее, мир поддерживает огромную сетку этого:

class World

{

private:

Terrain tiles_[WIDTH][HEIGHT];

};

Здесь я использую вложенный массив для хранения двумерной сетки.

Это эффективно в C/C++, поскольку упакует все элементы вместе.

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

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

Здесь я делаю так только для упрощения примера.

Чтобы получить полезные данные о плитке, делаем что-то вроде этого:

int World::getMovementCost(int x, int y)

{

switch (tiles_[x][y])

{

case TERRAIN_GRASS: return 1;

case TERRAIN_HILL: return 3;

case TERRAIN_RIVER: return 2;

// Другие виды ландшафта...

}

}

bool World::isWater(int x, int y)

{

switch (tiles_[x][y])

{

case TERRAIN_GRASS: return false;

case TERRAIN_HILL: return false;

case TERRAIN_RIVER: return true;

// Другие виды ландшафта...

}

}

Ну, вы поняли.

Работает, но код некрасивый.

Цена хода и влажность - это данные о ландшафте, но здесь они встроены в код.

Хуже того, данные об одном типе местности размазаны по куче методов.

Надо собрать все инкапсулированное в одном месте.

В конце концов, вот для чего предназначены объекты.

Было бы здорово завести класс ландшафта, например:

class Terrain

{

public:

Terrain(int movementCost,

bool isWater,

Texture texture)

: movementCost_(movementCost)

,

isWater_(isWater)

,

texture_(texture)

{}

int getMovementCost() const { return movementCost_; }

bool isWater() const { return isWater_; }

const Texture& getTexture() const { return texture_; }

private:

int movementCost_;

bool isWater_;

Texture texture_;

};

Вы заметите, что все методы здесь - константы.

Это не совпадение.

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

Возможно, вы этого не хотите.

Совместное использование объектов для экономии памяти должно быть оптимизацией, не влияющей на видимое поведение приложения.

Из-за этого объекты-"приспособленцы" почти всегда неизменяемые.

Но мы не хотим платить за содержание экземпляра для каждой плитки.

Если посмотреть на класс, то можно заметить, что в нем нет ничего определяющего, где находится плитка.

В терминах "приспособленца" все состояние ландшафта "свойственное" или "контекстно-свободное".

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

Каждая плитка с травой идентична любой другой.

Вместо того, чтобы мир был сеткой из перечислений или объектов Terrain, он будет сеткой указателей на объекты Terrain:

class World

{

private:

Terrain* tiles_[WIDTH][HEIGHT];

// Другие характеристики...

};

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

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

Вместо этого просто будем хранить их прямо в мире:

class World

{

public:

World()

: grassTerrain_(1, false, GRASS_TEXTURE)

,

hillTerrain_(3, false, HILL_TEXTURE)

,

riverTerrain_(2, true, RIVER_TEXTURE)

{}

private:

Terrain grassTerrain_;

Terrain hillTerrain_;

Terrain riverTerrain_;

// Другие характеристики...

};

Далее используем это, чтобы нарисовать землю:

void World::generateTerrain()

{

// Заполняем землю травой.

for (int x = 0; x < WIDTH; x++)

{

for (int y = 0; y < HEIGHT; y++)

{

// Возводим холмы.

if (random(10) == 0)

{

tiles_[x][y] = &hillTerrain_;

}

else

{

tiles_[x][y] = &grassTerrain_;

}

}

}

// Рисуем реку.

int x = random(WIDTH)

;

for (int y = 0; y < HEIGHT; y++) {

tiles_[x][y] = &riverTerrain_;

}

}

Признаюсь, это не величайший алгоритм процедурной генерации ландшафта в мире.

Теперь вместо применения методов к World для доступа к свойствам ландшафта, можем воздействовать на объект Terrain напрямую:

const Terrain& World::getTile(int x, int y)

const

{

return *tiles_[x][y];

}

Итак, World более не связан со всяческими деталями ландшафтов.

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

int cost = world.

getTile(2, 3).getMovementCost();

Мы вернулись к приятному API работы с реальными объектами и сделали это практически без накладных расходов: размер указателя часто не больше размера перечисления.

Что насчёт производительности?

Я сказал «практически», потому что при подсчете производительности правомерно захочется увидеть сравнительную характеристику указателя и перечисления.

Ссылка на ландшафт по указателю предполагает косвенный поиск.

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

Следование по указателю может вызвать промах кэша, что приведет к замедлению работы.

Для дополнительной информации о переходах по указателю и промахах кэша см. главу о паттерне "Местоположение данных" (Data Locality).

Как всегда, золотое правило оптимизации - сначала профилируй.

Современное аппаратное обеспечение слишком комплексное, поэтому производительность больше не является единственным фактором.

Я провел тесты для данной главы и не обнаружил потерь при использовании "приспособленца" по сравнению с перечислением.

Фактически, приспособленец оказался заметно быстрее.

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

Я уверен в том, что объекты "приспособленца" не следует сразу отклонять.

Они дают преимущества объектно-ориентированного стиля без издержек на тонны объектов.

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

Если волнуетесь о производительности, по крайней мере, профилируйте перед тем, как привести код к менее поддерживаемому стилю.

См. также

В примере с плитками мы просто создали по экземпляру каждого типа ландшафта и сохранили их в World.

Это позволило нам легко находить и использовать общие экземпляры.

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

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

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

Если да, просто возвращайте этот экземпляр.

Обычно это означает, что нужно инкапсулировать конструкцию за каким-то интерфейсом, который сначала ищет существующий объект.

Скрытие конструктора подобным образом - это пример паттерна "фабричный метод" (Factory Method).

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

Как подразумевает название, паттерн "объектный пул" (Object Pool) может быть полезным местом для их хранения.

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

Сущность и методы состояния - все, что нам пригодится.

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

Переведено на Нотабеноиде
http://notabenoid.org/book/51192/215211

Переводчики: Mingun, IngaJolly, Deo, Qeruim