hrxdev№2 Мир, сохранения, повторы и баг, спрятавшийся в формате сохранений
· Nick
После первой записи у ядра появился мир, в который можно что-то помещать, файлы, в которых его можно хранить, и способ доказать, что два прогона совпадают. Графики и персонажей по-прежнему нет. Большая часть записи – инфраструктура, а одна её часть – баг, который оказался достоин отдельной истории.
Мир из клеток
Мир – это сетка клеток 1×1 м на дискретных уровнях, пронумерованных от нуля. Стена или дверь – это клетка; лестница будет особой связью между двумя уровнями, но лестниц пока нет. Внутри мир представляет собой набор плоских слоёв (пол, конструкция, флаги конструкции) на всю карту плюс производный слой проходимости. Карта отслеживается чанками 16×16 со счётчиками версий, чтобы рендерер или поиск пути могли спросить «изменилась ли эта область?», не сравнивая клетки.
Размер мира выбирается при создании. Строительство выполняется командами, принимающими прямоугольник: положить пол, стену или дверь на область либо убрать их. Если часть прямоугольника занята, остальное всё равно строится, а команда сообщает, что пропустила. Пока есть три встроенных типа клеток: пол, стена, дверь. С этого момента карта входит в хеш мира и в сохранения. Она сверяется с медленной, заведомо правильной эталонной моделью на тысячах случайных команд.
Сохранения и повторы
Сохранение и повтор используют один файловый контейнер. Он разбит на именованные секции, у каждой есть тип и версия, поэтому новые части мира (персонажи, потребности, отношения) позже смогут стать новыми секциями, не ломая старые файлы. Есть контрольные суммы заголовка и тела, тело сжато, а каждый размер проверяется на соответствие лимиту до выделения памяти, так что повреждённый или злонамеренный файл не заставит игру съесть всю вашу память. Типы клеток хранятся по имени, а не по номеру, поэтому сохранение продолжит работать, если список типов изменится.
Повтор – это то, чего я хотел с самого начала: сид плюс журнал команд. При записи ядро ещё и пишет контрольный хеш каждые 100 тиков. При воспроизведении оно сравнивает результат каждой команды и каждый контрольный хеш и останавливается на первом тике, где они расходятся. Повтор также запоминает, какая сборка ядра его записала, поэтому повтор из другой сборки отклоняется, а не тихо расходится.
Само ядро никогда не трогает файлы: оно читает и пишет потоки, а где лежат сохранения, решает игра. Эта граница обеспечивается тем же механизмом запрещённых API, что и раньше.
Пока не сделано: утилита командной строки, воспроизводящая файл повтора, и игровая сторона сохранения (папка сохранений, автосохранения, безопасная запись).
Доказываем, что два прогона совпадают
Тест детерминизма теперь запускает один сценарий в двух отдельных процессах: сид, скрипт команд строительства (часть из них намеренно некорректна) и тестовая система, берущая числа из каждого случайного потока. Каждый процесс проходит его тремя способами – напрямую, через сохранение и восстановление и через повтор записанных байтов – и сравнивает хеши на каждом тике. Затем два процесса сверяют свои хеши друг с другом каждый 10-й тик.
Я нарочно его ломал, чтобы убедиться, что он умеет падать. Незасеянный Random, протащенный в тик, сделал тест красным. Рандомизированный хеш строки, который .NET засевает по-разному в каждом процессе, внутри одного процесса остался незамеченным и был пойман только при сравнении двух. Именно ради этого и нужны два процесса.
Правило, которое я записал: одна сборка ядра должна давать одинаковые хеши на процессорах x64 и arm64, так что повтор, записанный на Mac с чипом Apple, должен проигрываться на Windows-ПК. Закреплённые эталонные хеши и примеры файлов сохранений и повторов существуют именно для этой проверки. Тригонометрия и экспоненты с плавающей точкой на разных платформах дают разные результаты, поэтому в том, что влияет на мир, они под запретом; когда какой-нибудь системе они понадобятся впервые, мне понадобится детерминированная замена. Эти эталонные файлы меняются только намеренно: если хеш уплыл, изменение нужно объяснить, прежде чем его принять.
Бенчмарк, который умеет сказать «нет»
Теперь есть безголовый запускатель, который берёт сценарий, сид и число тиков и печатает отчёт в JSON: медианное и 99-процентильное время на тик, число агентов, хеш мира и сколько байт выделено за тик. Первый сценарий строит карту 512×512 на 16 уровнях примерно с 52 000 команд строительства.
Базовая линия хранится для каждой машины отдельно, потому что замеры с ноутбука ничего не значат на настольном компьютере. Регрессией считается медиана более чем на 10% выше базовой линии или 99-й процентиль более чем на 35% выше, и только если рост превышает 0,05 мс, поскольку почти пустой тик лежит на пределе разрешения таймера. На каждой машине действует один порог: ноль выделенных байт за тик. Стоит честно сказать, что это измеряет сегодня. Без систем и без персонажей тик занимает около 35 наносекунд, так что порог по времени в основном спит до тех пор, пока на этапе движения не появятся первые настоящие системы. Сейчас работает порог по выделениям памяти.
Нестабильный тест, который не был нестабильным
Пока я делал бенчмарк, тест формата сохранений начал падать на некоторых сборках, хотя ядро не менялось. Тест по очереди переворачивает каждый байт сжатого повтора и требует, чтобы загрузчик отклонял каждый вариант. В одной сборке байт ближе к концу файла был принят. В предыдущей сборке тот же тест проходил.
Почему это то появлялось, то исчезало: повтор несёт идентификатор сборки, которая его записала, так что сжатые байты отличаются от сборки к сборке, а вместе с ними и переворачиваемый байт. Дыра была всегда; тест замечал её, только когда кости ложились именно так.
Сама дыра: контрольная сумма покрывала данные после распаковки, а распаковщик .NET оказался снисходительным. Он принимает поток, который так и не сообщает о своём конце, и игнорирует всё после конца. Переворот бита-заполнителя в последнем байте даёт другой, по-прежнему допустимый поток, который распаковывается в те же данные, так что контрольная сумма совпадала, и повреждённый файл загружался как хороший.
Исправление – новая версия контейнера. Контрольная сумма теперь покрывает байты в том виде, как они хранятся в файле, и проверяется до распаковки, а распаковка должна заканчиваться ровно там, где сказано в заголовке. Пустое тело хранится без сжатия, поскольку компрессор для пустого входа ничего не пишет. Проверки теперь используют фиксированные сжатые потоки, не зависящие от сборки, плюс фаззинг повреждённых файлов. Примеры файлов пересозданы для новой версии; хеши мира не изменились.
Попутно
На сайте, который вы читаете, на главной странице теперь два счётчика посетителей: уникальные за всё время и за последние 24 часа. Они считаются по журналу страниц веб-сервера, без JavaScript, cookie и сторонних сервисов. Адрес хранится только в виде хеша с солью, боты отфильтровываются по user agent, а числа отстают на несколько минут. Несколько человек за одной сетью считаются как один.
Что дальше
Первый этап, каркас ядра, завершён. Дальше M1, режим строительства на Godot: стены, двери и комнаты по модели мира, срез этажей, камера с поворотом шагами по 90° и простые кубы вместо графики. Работа над ним ещё не началась. См. дорожную карту.