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

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

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

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

    Как обычно перед тем как изобретать велосипед, я ищу готовые решения проблемы. Но либо я плохо гуглил, либо единственное что удовлетворяло требованием это 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
    Поделиться публикацией

    Похожие публикации

    Комментарии 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/

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

                        Самое читаемое