Как спроектировать систему воспроизведения

Итак, как бы я спроектировал систему воспроизведения?

Вы можете знать это по определенным играм, таким как Warcraft 3 или Starcraft, где вы можете снова посмотреть игру после того, как она уже сыграна.

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

• Как сохранить данные? (пользовательский формат?) (небольшой размер файла)
• Что должно быть сохранено?
• Как сделать его универсальным, чтобы его можно было использовать в других играх для записи периода времени (а не полного совпадения, например)?
• Сделать возможным перемотку и перемотку назад (WC3 не смог перемотать, насколько я помню)

Эта превосходная статья охватывает множество вопросов: http://www.gamasutra.com/view/feature/2029/developing_your_own_replay_system.php

Несколько вещей, которые статья упоминает и делает хорошо:

• ваша игра должна быть детерминированной.
• он записывает начальное состояние игровых систем в первом кадре и вводит только игрока во время игры.
• квантовать входы, чтобы уменьшить количество битов. То есть. представляют значения с плавающей точкой в ​​различных диапазонах (например, диапазон [0, 1] или [-1, 1] в пределах меньших битов). Квантованные входные данные также должны быть получены во время реального игрового процесса.
• используйте один бит, чтобы определить, есть ли во входном потоке новые данные. Поскольку некоторые потоки не будут часто меняться, это использует временную согласованность входных данных.

Одним из способов дальнейшего повышения степени сжатия в большинстве случаев является разделение всех ваших входных потоков и независимое кодирование их по всей длине прогона. Это будет победой над техникой дельта-кодирования, если вы кодируете свой цикл в 8 битов, а сам цикл превышает 8 кадров (очень вероятно, если ваша игра не является настоящим кнопочным мастером). Я использовал эту технику в гоночной игре, чтобы сжать 8 минут входных данных от двух игроков, гоняясь по трассе, до нескольких сотен байтов.

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

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

Помимо решения «убедитесь, что нажатия клавиш воспроизводимы», что может быть на удивление сложным, вы можете просто записать полное состояние игры в каждом кадре. С небольшим умным сжатием вы можете значительно сжать его. Вот как Braid обрабатывает код перемотки времени, и он работает довольно хорошо.

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

Вы можете просматривать вашу систему так, как если бы она была составлена ​​из ряда состояний и функций, где функция f[j]с вводом x[j]изменяет состояние системы s[j]в состояние s[j+1], например так:

s[j+1] = f[j](s[j], x[j])

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

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

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

Ради этого объяснения я сделаю следующие предположения:

Предположение 1:

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

Предположение 2:

Пространственная стоимость (память, диск) хранения одного состояния намного больше, чем стоимость хранения функции и ее ввода.

Предположение 3:

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

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

Способ 1:

Магазин s[0]...s[n]. Это очень просто, очень просто. Из-за предположения 2 пространственная стоимость этого довольно высока.

Для шахмат это можно сделать, рисуя всю доску за каждый ход.

Способ 2:

Если вам нужно только прямое воспроизведение, вы можете просто сохранить s[0], а затем сохранить f[0]...f[n-1](помните, это только имя идентификатора функции) и x[0]...x[n-1](что было введено для каждой из этих функций). Чтобы воспроизвести, вы просто начинаете с s[0]и рассчитываете

s[1] = f[0](s[0], x[0])
s[2] = f[1](s[1], x[1])

и так далее...

Я хочу сделать небольшую аннотацию здесь. Несколько других комментаторов заявили, что игра «должна быть детерминированной». Любой, кто говорит, что должен снова принять Computer Science 101, потому что, если ваша игра не предназначена для работы на квантовых компьютерах, ВСЕ КОМПЬЮТЕРНЫЕ ПРОГРАММЫ ДЕТЕРМИНИСТИЧЕСКИ ». Вот что делает компьютеры такими классными.

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

Если вы используете псевдослучайные числа, вы можете либо сохранить сгенерированные числа как часть вашего ввода x, либо сохранить состояние функции prng как часть вашего состояния s, а ее реализацию как часть функции f.

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

Способ 3:

Теперь вы, скорее всего, хотите иметь возможность искать свой повтор. То есть рассчитать s[n]на произвольную n. Используя метод 2, вам нужно рассчитать, s[0]...s[n-1]прежде чем вы сможете рассчитать s[n], который, согласно предположению 2, может быть довольно медленным.

Для реализации этого метод 3 является обобщением методов 1 и 2: хранить f[0]...f[n-1]и x[0]...x[n-1]точно так же, как метод 2, но также хранить s[j]для всех j % Q == 0для данной константы Q. Проще говоря, это означает, что вы храните закладку в каждом из Qштатов. Например, для Q == 100, вы хранитеs[0], s[100], s[200]...

Для того, чтобы вычислить s[n]произвольно n, вы сначала загружаете ранее сохраненные s[floor(n/Q)], а затем вычисляете все функции от floor(n/Q)до n. Самое большее, вы будете вычислять Qфункции. Меньшие значения Qвычисляются быстрее Q, но занимают гораздо больше места, в то время как большие значения занимают меньше места, но вычисляются дольше.

Метод 3 с Q==1такой же, как метод 1, а метод 3 с Q==infтакой же, как метод 2.

В шахматах это можно сделать, разыгрывая каждый ход, а также каждую десятую доску (для Q==10).

Способ 4:

Если вы хотите отменить воспроизведение, вы можете сделать небольшое изменение метода 3. Предположим Q==100, и вы хотите , чтобы вычислить s[150]через s[90]в обратном направлении. При неизмененном методе 3 вам нужно будет сделать 50 вычислений, чтобы получить, s[150]а затем еще 49 вычислений, чтобы получить s[149]и так далее. Но так как вы уже рассчитали, s[149]чтобы получить s[150], вы можете создать кеш, s[100]...s[150]когда вы рассчитываете s[150]в первый раз, а затем вы уже s[149]в кеше, когда вам нужно отобразить его.

Вам нужно только восстанавливать кэш каждый раз, когда вам нужно рассчитать s[j], j==(k*Q)-1для любого данного k. На этот раз увеличение Qприведет к уменьшению размера (только для кеша), но к более длительному времени (только для воссоздания кеша). Оптимальное значение для Qможет быть рассчитано, если вы знаете размеры и время, необходимые для вычисления состояний и функций.

Для шахмат это можно сделать, рисуя каждый ход, а также одну на каждые 10 досок (для Q==10), но также потребуется нарисовать на отдельном листе бумаги последние 10 досок, которые вы вычислили.

Способ 5:

Если состояния просто занимают слишком много места, или функции занимают слишком много времени, вы можете создать решение, которое фактически реализует (не подделывает) обратное воспроизведение. Для этого вы должны создать обратные функции для каждой из ваших функций. Однако для этого необходимо, чтобы каждая из ваших функций была инъекцией. Если это выполнимо, то для f'обозначения обратной функции fвычисление s[j-1]так же просто, как

s[j-1] = f'[j-1](s[j], x[j-1])

Обратите внимание, что здесь и функция, и вход - j-1нет j. Эта же функция и входные данные были бы теми, которые вы использовали бы, если бы вычисляли

s[j] = f[j-1](s[j-1], x[j-1])

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

Этот метод, как есть, может обратный расчет s[j-1], но только если у вас есть s[j]. Это означает, что вы можете смотреть реплей только в обратном направлении, начиная с того момента, когда вы решили переиграть в обратном направлении. Если вы хотите воспроизвести в обратном направлении с произвольной точки, вы должны смешать это с методом 4.

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

Способ 6:

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

s[j+1], r[j] = f[j](s[j], x[j])

Где r[j]находятся сброшенные данные. А затем создайте свои обратные функции, чтобы они принимали отброшенные данные, например так:

s[j] = f'[j](s[j+1], x[j], r[j])

В дополнение к f[j]и x[j], вы также должны хранить r[j]для каждой функции. Еще раз, если вы хотите иметь возможность искать, вы должны хранить закладки, например, с помощью метода 4.

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

Реализация:

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

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

Я видел, как это реализовано в некоторых крупных играх, в основном для мгновенного воспроизведения последних данных, когда происходит событие (фрагмент в кадрах в секунду или счет в спортивных играх).

Надеюсь, это объяснение не было слишком скучным.

¹ Это не означает, что некоторые программы действуют как недетерминированные (например, MS Windows ^^). Если серьезно, если вы можете создать недетерминированную программу на детерминированном компьютере, вы можете быть уверены, что одновременно выиграете медаль Филдса, премию Тьюринга и, возможно, даже Оскара и Грэмми за все, что стоит.

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

Используя float, вы можете иметь полностью детерминированную систему, но только если:

• Используя точно такой же двоичный файл
• Используя точно такой же процессор

Это связано с тем, что внутреннее представление чисел с плавающей запятой варьируется от одного процессора к другому - наиболее резко между процессорами AMD и Intel. Пока значения находятся в регистрах FPU, они более точны, чем выглядят со стороны C, поэтому любые промежуточные вычисления выполняются с большей точностью.

Совершенно очевидно, как это повлияет на бит AMD против Intel - скажем, один использует 80-битные числа с плавающей запятой, а другой 64, например - но почему такое же двоичное требование?

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

Вы можете помочь в этом, установив флаги _control87 () / _ controlfp () для использования наименьшей возможной точности. Тем не менее, некоторые библиотеки могут также коснуться этого (по крайней мере, некоторые версии d3d сделали).

Сохраните исходное состояние ваших генераторов случайных чисел. Затем сохраните, отметив время, каждый вход (мышь, клавиатура, сеть, что угодно). Если у вас есть сетевая игра, вы, вероятно, уже все это на месте.

Переустановите ГСЧ и воспроизведите вход. Вот и все.

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

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

Я бы проголосовал против детерминированного воспроизведения. FAR проще и FAR менее подвержен ошибкам, чтобы сохранять состояние каждого объекта каждую 1 / N-ю секунды.

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

Настройте кодировку. Используйте как можно меньше битов для всего. Повтор не должен быть идеальным, если он выглядит достаточно хорошо. Даже если вы используете float, скажем, для заголовка, вы можете сохранить его в байте и получить 256 возможных значений (точность 1.4º). Это может быть достаточно или даже слишком много для вашей конкретной проблемы.

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

Если вы хотите легкую перемотку, добавьте ключевые кадры (полные данные, без дельт) каждые N кадров. Таким образом, вы можете получить меньшую точность для дельт и других значений, ошибки округления не будут такими проблемными, если вы периодически будете сбрасывать в «истинные» значения.

Наконец, GZIP все это :)

Это сложно. Прежде всего прочитайте ответы Яри Комппа.

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

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

Чтобы перемещаться по файлам (что гораздо сложнее), вам нужно сбросить ПАМЯТЬ. Мол, где каждая единица, деньги, отрезок времени, все состояние игры. Затем ускоренная перемотка вперед, но воспроизведение всего, кроме пропуска рендеринга, звука и т. Д., Пока вы не доберетесь до нужного вам времени. Это может происходить каждую минуту или 5 минут в зависимости от скорости пересылки.

Основные моменты - Работа со случайными числами - Копирование ввода (проигрыватель (и) и удаленный проигрыватель (и)) - Состояние сброса при перемещении по файлам и ... - ПЛАВАНИЕ, НЕ ПРЕРЫВАНИЕ ВЕЩЕЙ (да, мне пришлось кричать)

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

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

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

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

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

Скорее всего, вам понадобится игровой логический RNG и все остальное RNG для таких вещей, как GUI, эффекты частиц, звуки. Как только вы это сделаете, вам нужно записать начальное состояние игровой логики ГСЧ, а затем игровые команды всех игроков в каждом кадре.

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

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

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

Возможно, наиболее важной частью написания системы воспроизведения, основанной на детерминизме, является запись потока данных отладки. Этот поток отладки содержит снимок как можно большего количества информации о каждом кадре (начальные значения ГСЧ, преобразования сущностей, анимации и т. Д.) И может тестировать этот записанный поток отладки в зависимости от состояния игры во время повторов. Это позволит вам быстро сообщить о несоответствиях в конце любого данного кадра. Это сэкономит бесчисленные часы желания вырвать ваши волосы из неизвестных недетерминированных ошибок. Такая простая вещь, как неинициализированная переменная, испортит все на 11-м часу.

ПРИМЕЧАНИЕ. Если ваша игра предполагает динамическую потоковую передачу контента или у вас игровая логика в нескольких потоках или в разных ядрах ... удачи.

Чтобы включить как запись, так и перемотку, запишите все события (сгенерированные пользователем, сгенерированные по таймеру, сгенерированные сообщения, ...).

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

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

Сохраненные данные - это список изменений.
Изменения могут быть сохранены в различных форматах (двоичный, XML, ...).
Изменение состоит из идентификатора объекта, имени свойства, старого значения, нового значения.

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

Пример:

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

Если вам нужны идеи о том, как реализовать свою систему воспроизведения, поищите в Google, как реализовать отмену / повтор в приложении. Для некоторых может быть очевидно, но, возможно, не для всех, что отмена / повторение концептуально аналогична воспроизведению для игр. Это просто особый случай, в котором вы можете перематывать и, в зависимости от приложения, искать в определенный момент времени.

Вы увидите, что никто, реализующий отмену / повтор, не жалуется на детерминированные / недетерминированные, плавающие переменные или конкретные процессоры.