live13 (live13) wrote,
live13
live13

Categories:

Шаблоны игрового программирования. Локальность данных (2-я часть главы)

Локальность данных( Data Locality)



Первая часть главы
Оглавление


Архитектурные решения



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

    Знаменитая статья Ноэля Ллописа заставила многих людей задуматься об архитектуре игры с точки зрения использования кэша и получила название "ориентированная на данные архитектура (data-oriented design)".


Самый главный вопрос, на который вам придется ответить - это где и когда вам стоит применять этот шаблон. А вот еще несколько вопросов, о которых тоже стоит вспомнить.

Что вы будете делать с полиморфизмом



До сих пор мы избегали подклассов и виртуальных методов. Предположим у нас есть хорошо упакованный массив гомогенных объектов. При этом мы знаем что все они одного размера. Но ведь полиморфизм и динамическая диспетчеризация тоже хорошие инструменты. Как же согласовать эти два противоречия?


  • Не используйте:

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

      Одним из способов использовать гибкость полиморфизма без использования подклассов является шаблон Объект тип( Type Object).



    • Это просто и безопасно. Вы всегда знаете с каким классом работают все ваши объекты одного размера.

    • Это быстро. Динамическая диспетчеризация подразумевает поиск метода в виртуальной таблице методов и переход по указателю к самому методу. Несмотря на то что стоимость этой операции на различном оборудовании серьезно варьируется, вам все равно придется платить за динамическую диспетчеризацию.
        Как обычно с абсолютной уверенностью можно утверждать только о том что ничего абсолютного нет. В большинстве случаев компилятор C++ требует косвенности для вызова виртуального метода. Но в некоторых случаях компилятор может выполнить развиртуализацию (devirtualization) и вызвать нужный метод статически, если знает конкретный тип получателя. Развиртуализация встречается еще чаще в языках с компиляцией на лету, таких как Java или JavaScript.

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



  • Используйте отдельный массив для каждого типа:

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

    Но в таком случае сразу возникает вопрос - зачем складывать все в один мешок? Почему не организовать вместо этого отдельные гомогенные коллекции для каждого типа?


    • Наши объекты будут плотно упакованы. Так как все объекты в массиве одного типа - у нас не будет подбивки(padding) и других странностей.

    • Мы можем применять статическую диспетчеризацию. Как только ваши объекты будут разделены по типу, полиморфизм вам больше не понадобится. Вы можете использовать простые невиртуальные вызовы методов.

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

    • Вам нужно заботиться о каждом из типов. Так как у вас для каждого типа имеется отдельная коллекция, вы не сможете убрать связность от набора классов. Часть магии полиморфизма заключается в открытости: код, работающий с наследниками может быть полностью несвязан с потенциально большим набором типов, реализующих данный интерфейс.



  • Используйте коллекцию указателей:

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


    • Это гибкое решение. Работающий с коллекцией код может работать с объектами любого типа, пока они поддерживают нужный вам интерфейс. Полная свобода.

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





Как определять игровые сущности?



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

Вопрос здесь в том - как представлять сущность? Как она будет следить за своими компонентами?


  • Если игровые сущности - это классы с указателями на свои компоненты:

    Именно так выглядел наш первый пример. Это самое традиционное ООП решение. У вас есть класс для GameEntity и у него есть указатели на свои компоненты. Так как все это просто указатели - остается только догадываться где и как на самом деле размещаются эти компоненты в памяти.


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

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

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



  • Если игровые сущности - это классы с ID своих компонентов:

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

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


    • Это сложно. Конечно ваша система ID не сравнится по сложности с ракетостроением, но работы явно больше чем при использовании обычных указателей. Вам нужно будет ее реализовать и отладить. А еще у вас появятся накладные расходы на бухгалтерию.

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

    • Вам потребуется доступ к "менеджеру" компонентов. Основная идея заключается в том что у вас есть абстрактный ID, идентифицирующий компонент. И вы можете использовать его чтобы получить указатель на сам компонент. Но чтобы это сделать вам нужен кто-то, кто может найти компонент по его ID. Это будет класс - обертка над сырым последовательным массивом компонентов наших объектов.

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

        Вы можете подумать" Так я применю синглтон! И проблема решена!" Ну как бы да. Только советую сначала заглянуть в эту главу.




  • Если игровые сущности представляют из себя всего лишь ID.

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

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

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

    Ваши классы сущностей полностью исчезают, заменяемые удобной оболочкой над числами.


    • Сущности занимают мало места. Если вам нужно передать ссылку на игровую сущность - вы просто передаете число.

    • Сущности пустые. Логично что недостатком такого решения является, то что вам придется убрать из сущностей все. У вас больше нет места для хранения не компонентно-специфического состояния или поведения. Эти функции тоже возлагаются на шаблон компонентов.

    • Вам не нужно управлять временем жизни. Так как сущности - это значения простых типов, их не нужно явно создавать или удалять. Сущность "умирает", когда уничтожаются все ее компоненты.

    • Поиск компонентов сущности может быть достаточно медленным. Это та же самая проблема как и в предыдущем решении, но немного с другой точки зрения. Чтобы найти компонент какой-либо сущности, вам нужно найти объект по ID. Этот процесс может быть достаточно затратным.

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

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

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





Смотрите также




  • Большая часть этой главы вращается вокруг шаблона Компонент ( Component) и это определенно одна из наиболее часто используемых структур данных для оптимизации работы с кэшем. И действительно, применение компонентов этому способствует. Так как сущности обновляются по одной "области" (AI, физика и т.д.) за раз, разбиение их на компоненты позволяет поделить сущности на более удобные в плане работы с кэшем кусочки.

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

  • "Ловушки объектно-ориентированного программирования( Pitfalls of Object-Oriented Programming)" Тони Альбрехта - это наверное самое лучшее чтиво на тему организации структур данных в игре в максимально кэш-дружественном виде. Я встречал много людей (включая меня самого), кому эта книга помогла с улучшением производительности.

  • Примерно в то же время Ноэль Ллопис написал хороший пост в своем блоге на ту же тему.

  • Этот шаблон практически полностью основан на использовании последовательного массива гомогенных объектов. Время от времени вам наверняка придется добавлять или удалять из него объекты. Шаблон Пул объектов ( Object Pool) как раз этому и посвящен.

  • Игровой движок Artemis - один из первых и наверное самый известный из фреймворков, использующих ID в качестве игровой сущности.


Tags: c++, design patterns, game programming, programming, игры, книги, перевод, программирование, шаблоны, шаблоны проектирования
Subscribe

  • Fargo не так прост!

    Я уже писал что 4-й сезон вызвал у меня несколько смешанные чувства. С одной стороны это все так же стройная история, крайне достойно…

  • Про Некромунду

    Тут на подходе книга про Орлоков ожидается. А еще занимательный аванпост в пластике выпускают. Стоит даже несколько штук взять. Жаль пока не…

  • О том что случается когда фабрики стоят

    Примерно лет 12 назад (ну или оклол) качественные цифровые фотокамеры стали доступны даже фотолюбителям. И тогда очень был популярен мем про…

promo live13 may 11, 2014 17:58 46
Buy for 50 tokens
Примерно неделю назад я писал, что заинтересовался этой online-книжкой http://gameprogrammingpatterns.com/ и решил сделать ее перевод. Сам я мог бы ограничиться и английским вариантом, но думаю многим перевод пригодится. В прошлом я уже занимался переводом книг. Не как основной работой. Так,…
  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 2 comments