27 декабря 2012 в 01:18

Разработка патчера к игре

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

  • Поддержка юнити игр
  • Дружелюбность к пользователю
  • Отображение игровых новостей
  • Универсальность для всех игр разработанных нашей студией
  • Гибкость настройки
  • И самое важное: умение делать небольшие патчи для больших файлов

Ссылка на исходники патчера в конце статьи.

Как обычно перед тем как изобретать велосипед, я ищу готовые решения проблемы. Но либо я плохо гуглил, либо единственное что удовлетворяло требованием это M2H Patcher с Unity Asset Store.
На внедрение мы потратили несколько дней, и пропользовались им около месяца (до первой и одновременно последней поломки). В один прекрасный день патчер отказался делать патч. Потратив несколько часов на разбирательство я выяснил причину.
Дело в том что этот патчер использовал для работы утилиты bsdiff & bspatch. Для работы утилиты bsdiff нужно max(17*n,9*n+m)+O(1) памяти. Так уж получилось что на самой лучшей машине в офисе было всего 4 Гб оперативки, а файл с ресурсами был уже более 600 Мб. Вообщем bsdiff отказывался с ним работать (до этого время создания патча составляло непотребные 30+ минут).

Тогда то я решил все-таки собрать велосипед.

Алгоритм


Теперь предстояло нагуглить алгоритм сравнения больших бинарных файлов. Достойных кандидатов оказалось два. Это Rsync и алгоритм сортировки суффиксов из bsdiff.
Так как со вторым уже были проблемы, то я остановился на первом.
Его суть заключается в следующем. Разбиваем исходный файл на куски равного размера (далее чанки от англ. chunk).
Для каждого чанка считаем два хэша: сильный и слабый. Сильный хэш — это обычный MD5. Слабый хэш — это кольцевой хэш. Его особенность в том, что если хэш от n до n+S-1 равняется R, то последовательность байт от n+1 до n+S может быть посчитана исходя из R, байта n и байта n+S без необходимости учитывать байты, лежащие внутри этого интервала.
Точно так же нужно посчитать результирующий файл. На выходе у нас должно получится две последовательности хешированных чанков.
Далее мы начинаем сравнивать слабые хэши в файлах в поисках одинаковых чанков. Если хэши совпали, то сравниваем сильные хэши. Ключом алгоритма является создание двух сигнатур — быстрой и стойкой. Быстрая используется как фильтр. Стойкая используется для более точной проверки.
На выходе мы имеем список отличающихся чанков, которые и записываем в патч.

Создание патча



Для наших игр хорошо подходит система, где номер версии обозначается целым числом. Таким образом обычно мы имеем кучу папок с разными версиями текущего проекта: 1, 2, 3, и т.д.



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

string[] files1 = Directory.GetFiles(folder1, "*.*", SearchOption.AllDirectories);
string[] files2 = Directory.GetFiles(folder2, "*.*", SearchOption.AllDirectories);

и ведем список изменений. Если файл добавился, то считаем md5. Если изменился, то считаем новый и старый md5. Эти хэши нужны будут для того, чтобы определить можно ли применить патч и корректно ли он установился.
Эти данные собираются в архив с максимальным сжатием через SharpZipLib. В конце мы дописываем туда файлик patch_info.txt в котором хранятся данные о размере чанка, список файлов с их хэшами и действиями.
Пример:
1024
R	star-draft_Data\level1
M	settings.xml	5e54da0d0c1dfca2bbc623979b7bceef	7a64fb8bc102b9d6bc0862ca63cdbb8d
A	star-draft_Data\level0	a3d14f5ed8d05164d59025cc910226ea
M	star-draft_Data\resources.assets	02466b9218cbf482d562570d8c0c90c8	20f1f88b5036a168bdd26fe7f4f9dadd
M	patcher\version.txt	c81e728d9d4c2f636f067f89cc14862c	c4ca4238a0b923820dcc509a6f75849b

* R — removed, A — added, M — modified
В зависимости от действия там лежит либо сам файл, либо патч к старой версии.
Теперь этот патч можно выложить на любой веб хостинг. Я тестил на дропбоксе.

Важно заметить что для нормальной работоспособности системы в папке с игрой должен лежать файл .\patcher\version.txt. В нем хранится информация о текущей версии игры. Ее считывает патчер и сам же меняет в результате процесса применения патча. Патч билдер старается следить чтобы вы не ошиблись, и версия в файле совпадала с версией указанной в имени папки.

Патчер


Скриншот

Слева должны быть логотипы игры и издателя, а справа новости

При старте патчер считывает файл настроек по пути ./patcher/configuration.xml и проверяет на валидность.
Пример файла с комментариями:
<?xml version="1.0"?>
<root>
        <!-- Используется в заголовке окна -->
        <game_name>TestGame</game_name>
        <!-- Запускается при нажатии кнопки "Играть" -->
        <game_exe>Test.exe</game_exe>
        <!-- Открывается в браузере по умолчанию при нажатии на логотип игры-->
        <game_url>http://coolgame.com</game_url>
        <!-- URL файла с последней версией игры -->
        <check_version_url>http://coolgame.com/version.txt</check_version_url>
        <!-- URL каталога с патчами -->
        <patches_directory>http://coolgame.com/patches/</patches_directory>
        <!-- URL новостей игры -->
        <news_url>http://coolgame.com/news_for_patcher.html</news_url>
        <!-- Открывается в браузере по умолчанию при нажатии на логотип издателя-->
        <publisher_url>http://coolpublisher.com</publisher_url>
</root>


Первым делом патчер проверит свою версию из файла ./patcher/version.txt. Потом он проверит последнюю версию игры по ссылке из настроек. Если последняя версия больше то запускается процесс обновления по схеме:

for (int i = current_version; i < last_version; i++)
{
    DownloadPatch(URL + string.Format("{0}_{1}", i, i+1));
    ApplyDownloadedPatch();
}


Чтобы применить патч, сначала нужно получить список измененных файлов. Поэтому первым делом достаем из скачанного архива patch_info.txt, парсим его и пробегаем циклом по файлам.
Если файл подлежит удалению, то удаляем. Если добавлен, то распаковываем из архива. Если изменен то применяем патч если хэши совпадают (чтобы не испортить его).
В конце не забываем проверить новый md5 хэш.

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

Статистика


Для проверки я сразу же засунул в него клиент нашей игры на Unity3D, с которым отказался работать bsdiff.
Клиент версия 1 — 1669 Mb
Клиент версия 2 — 1692 Mb (мы добавили модельку с пачкой текстур)
Размер патча при размере чанка 1 Кб и максимальном сжатии архива — 11.8 Mb, что очень похоже на результаты работы патчера с bsdiff'ом
Время создания патча на моей машине меньше минуты, а применения около 10 секунд.

Source: https://github.com/Agasper/GamePatcher
Alexandr @agasper
карма
26,0
рейтинг 0,0
Похожие публикации
Самое читаемое Разработка

Комментарии (28)

  • НЛО прилетело и опубликовало эту надпись здесь
    • +1
      по поводу обновления с версии до версии, такой вариант — с поочередным накатываение всех патчей — адекватно оптимален с точки зрения разработки vs удобства применения. Да, в лоб, но зато меньше вероятности где-нибудь накосячить, плюс нет необходимости хранить (n * n -1)/2 патчей.
      • 0
        ИМХО проще хранить на сервере копию последней версии + список общих хешей для файла + список хешей по чанкам.
        При обновлении соответственно:
        * получаем список хешей с сервера
        * строим список хешей локального клиента
        * если хеши не совпали — качаем хеши чанков, дальше через range запрос получаем конкретный кусок

        Ещё вариант не делать велосипед и прикрутить ко всему этому торрент — получаем сразу чанки по всему клиенту + частичное снижение нагрузки на сервер, соответственно:
        * новая версия — делаем торрент для неё, выкладываем на свой сервер по http
        * апдейтер забирает торрент, качает всё что изменилось

        P.S. мы в своё время через торренты бэкапы так рассылали по нескольким серверам
      • +1
        «Чтобы меньше накосячить» — нужно вначале отладить «внутреннюю» инфраструктуру;
        «Нет необходимости хранить гору патчей» — а нынче это не сложно, зато пользователю становится в n-раз удобнее / проще. И, да, с оценкой сложности вы ошиблись, как мне кажется, ибо достаточно иметь патч от каждой выпущенной версии до последней, да и в продакшен такая схема вписывается проще.

        У меня иногда интересуются, может грохнем наши апдейт-файлы с того года? Они уже весят почти столько же, сколько оригинальный дистриб. Но нет, стою на своем, «все равно меньше» и так удобнее будет пользователям.
    • 0
      1. На самом деле так оно и происходит
      2. Если принудительно пропишете свежую сборку, то ничего страшного не произойдет, патчер просто не обновит вам клиент. Для нас это не принципиально, т.к. клиент игры дополнительно сверяет с сервером версию протокола, и если клиент устарел, то его не пустит в игру.
      3. У всех вариантов есть минусы. Мы выбрали этот, чтобы не увеличивать нагрузку на сервер. Учитывая малый размер патчей не вижу проблемы.
    • 0
      Честно говоря не только Blizzard так работают — EA/DICE также через Origin.
      • НЛО прилетело и опубликовало эту надпись здесь
        • 0
          Для BF3 например — ОЧЕНЬ много дополнений идут, а если у Вас Premium Edition или Premium — то еще и все платные дополнения. Однако вот последний патч (исправление сингла) был небольшим — 36MB. (diff)
          • НЛО прилетело и опубликовало эту надпись здесь
            • 0
              у них просто все ресурсы сделаны в виде фрагментов ФС — поэтому им нужно пересылать все блоки из-за этого, хотя могли бы и разностное сжатие использовать. По поводу Steam к сожалению не смотрел на эту тему — ничего не могу сказать.
  • +1
    Ваш процесс загрузки и установки патчей:
    for (int i = current_version; i < last_version; i++)
    {
    DownloadPatch(URL + string.Format("{0}_{1}", i, i+1));
    ApplyDownloadedPatch();
    }

    То есть загрузка патчей и их установка происходит синхронно. Почему бы не качать следующий патч (если он есть) в то время, когда устанавливается текущий?!

    PS в исходники не смотрел, код взят из поста.
    • 0
      Да, я думал так сделать. Планирую позже добавить и эту фичу.
  • 0
    Вполне годная идея: мы делали что-то подобное для одного из наших проектов. Только у нас основной exe'шник запускался только по команде патчера, т.е. пользователь сперва в любом случае запускал патчер, которые проверял обновления. Причём мы принудительно качали архив с XML со списком файлов и их md5 и проверяли по нему md5 всех локальных ресурсов. Если не находили нужный файл или находили несовпадение md5 — то перекачивали этот файл заново с сервера.
    • +1
      все преимущества courgette проявляются только при работе с PE файлами
      • +1
        а еще он основан на bsdiff
  • 0
    Достойных кандидатов оказалось два.

    Чем VCDIFF не подошёл?
    • 0
      Я смотрел в его сторону, но по нему меньше документации и готовых реализаций.
      • +2
        Есть Xdelta3, OpenVCDIFF.
        Наложение патча реализуется за пол часа посматривая одним глазом в RFC 3284.
        Да и есть на C# реализация наложения патча готовая
        • 0
          Значит подходящая реализация RSync была выше в выдаче
  • +3
    В Windows есть готовый API для разностного сжатия, который используется, например, в процедуре установки хотфиксов Windows Update. Правда на больших файлах я его использовать не пробовал…
    • 0
      разве это не только для PE?
      т.е. для данных нужно тогда их оборачивать в вид DLL RESOURCE.
      • 0
        API без проблем обрабатывает файлы любого типа, ничего оборачивать не нужно (когда-то успешно экспериментировал на bmp скриншотах при помощи утилит mpatch и apatch под Windows XP). Просто, как я понимаю, технология сжатия оптимизирована под PE файлы с учётом особенностей этого формата.
        • 0
          Я пробовал. У меня они так и не заработали. Окно просто закрывалось и ничего не происходило
          • 0
            Эти утилиты — консольные, их необходимо запускать из комадной строки и передавать 3 параметра — имена файлов:
            mpatch.exe «c:\original_file» «c:\new_file» «c:\patch_file»
            apatch.exe «c:\patch_file» «c:\old_file» «c:\new_patched_file»

            Если так и делали, но ничего не работало, то ещё вопрос — библиотеку mspatchc.dll в папку к утилитам (или в system32) подкладывали? Её по умолчанию нет в системе Windows XP, а в этой библиотеке как раз находятся функции по созданию патчей. По умолчанию в системе есть только mspatcha.dll в которой только функции применения патчей.
            • 0
              Я все сделал как в документации. Поставил Windows SDK и запускал именно так.
              P.S. Я не особо разбирался почему не заработало. Забил и пошел гуглить дальше.
  • 0
    Меня, вот, всегда такой вопрос мучал: а что если изменится небольшой участок близко к началу файла и размер изменившегося куска не будет кратен размеру чанка? Патч в результате будет размером на весь файл?
    • +1
      Нет патч, будет небольшим. Если вас детально интересует алгоритм посмотрите тут: citforum.ru/nets/articles/rsync/

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