Не кинокритик. Не палеонтолог. (plakhov) wrote,
Не кинокритик. Не палеонтолог.
plakhov

Categories:

Программистское: статистическая и доказательная стратегии защиты от ошибок

Расскажу об одном интересном баге из моего геймдевелоперского прошлого.

Хотя нет, сначала будет мораль, а сама история потом.

Как всем известно, от ошибок можно защищаться runtime-тестированием, а можно - build-time проверками. К первой группе относятся monkey testing, ассерты, функциональные и регрессионные тесты, и некоторые более экзотические практики. Ко второй группе относятся проверки типов на этапе компиляции, инструменты, проводящие анализ кода (например, lint и т.п.), и unit-тесты. В геймдеве к этой группе также относятся проверки, производимые на этапе сборки ресурсов редактором в бинарное внутриигровое представление (см. на эту тему хорошую статью aruslan'а, за шесть лет не потерявшую своей актуальности).

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

Скажем, компилятор С++ или Java гарантирует нам, что объект "не того типа" не может быть передан в качестве параметра функции, а у объекта не может быть вызван несуществующий метод. В Python проверить то же самое можно с помощью юниттестов, регрессионных и функциональных тестов, а также прославленным в веках методом "несколько раз запустить и посмотреть, не упадет ли". Хотя оба подхода на практике могут обеспечивать надежность, которая всех устраивает, отличие между ними довольно резкое: никакие тесты не покроют все множество возможных ситуаций. Всегда остается крохотная возможность того, что пользователь программы сделает что-то такое экзотическое, и скрытый баг вылезет наружу.

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

Уже несколько раз в разных обсуждениях на эту тему я приводил такой вот пример. Полтора года назад, когда мы в Vogster'е доделывали Robocalypse на DS, тестировщики нашли рассинхронизацию в multiplayer'е. Это крайне неприятный тип ошибки. Многопользовательская игра у нас была организована по p2p-схеме: разные DS-ки передавали друг другу только команды пользователей, и каждая просчитывает состояние всего мира. Это идеальная для RTS схема, позволяющая организовать богатую фичами игру на основе очень узкого канала передачи данных и минимального "языка общения". Основной ее недостаток в том, что вся игровая логика должна быть абсолютно детерминированной, то есть, получая один и тот же набор команд, на выходе всегда иметь одинаковое состояние игрового мира. То есть нельзя никакого random'а, никакой зависимости от системного таймера, никаких шалостей с битами округления, никаких неинициализированных переменных и т.п. Как только рассинхронизация произошла, она уже фатальна: расхождения, даже начинающиеся с одного бита, быстро накапливаются, и скоро оба игрока видят совершенно разные картины происходящего (как правило, оба выигрывают с огромным перевесом). При помощи подсчета контрольных сумм факт рассинхронизации можно установить с точностью до такта просчета игровой логики, а вот дальше уже нужно целое расследование. Если вы можете себе позволить сериализовать все игровые данные с какими-то аннотациями, а затем сравнить два дампа с разных компьютеров/консолей, расследование того, что именно произошло, несколько упрощается. К сожалению, у нас и этой возможности не было.

Описание бага, которое я получил от тестера, выглядело так: "Иногда при невыясненных обстоятельствах происходит рассинхронизация. Что именно к ней приводит, непонятно. Reproduce: создать игру на 4 человек, и играть до посинения, активно пользуясь героями и их возможностями. Если игра закончилась, и все хорошо, повторить. Рано или поздно, сейчас или через день, она случится".

Зашибись. В попытках повторить баг я провел пару часов, но лишь убедился, что да, "оно случается". Что делать?

Хорошо, а почему вообще игра может рассинхронизироваться? Насчет неинициализированных переменных, к счастью, можно было не волноваться - у нас было собственное управление памятью, геймплейные данные всегда лежали в отдельном месте, изначально заполненном нулями, так что их состояния в отсутствие рассинхронизации совпадали бы до бита, даже если бы неинициализированные переменные встречались. На самом деле я к тому же был почти уверен, что их нет, поскольку регулярно проверял на этот счет код специальным анализатором (нивальцы, возможно, помнят, его ранний аналог Arch). Значит, кто-то совершил святотатство - позвал из игровой логики функцию, которая не обязана работать синхронно; например, обратился к интерфейсу. Строго говоря, сделать это не так-то просто: для этого нужно как минимум написать внутри игровой логики #include <../../interface/blah-blah.h> и ни о чем в этот момент не задуматься. Простой поиск регулярного выражения в коде показал, что такую глупость никто не совершал.

В этот момент я осознал, что передо мной задача проверки типизации. Не очень, правда, распространенная: меня интересовали не типы в смысле языка, а "логические типы" функций. Какой-нибудь Haskell не видит особенных различий между этими понятиями, и правильно делает, но у нас-то C++.

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

Что здесь важно:
1) в коде содержались какие-то нарушения этих правил, иначе ошибка не возникала бы
2) вовсе не любое такое нарушение будет приводить к рассинхронизации, но если их не будет, то отсутствие рассинхронизаций будет математически строго доказуемо

Отлично, оставалось поработать заместителем компилятора, и явным образом переименовать все фунции doSmth на границе между игровым миром, интерфейсом и графикой либо в doSmthSync, либо doSmthAsync, параллельно отслеживая, кто кого вызывает. Не прошло и часа, как все нарушения "типизации" были ликвидированы, а я смог восстановить цепочку событий, приводящих к рассинхронизации.

Ошибка оказалась в том месте, где интерпретировалась команда сбрасывания наковальни (это в Robocalypse такой мультяшный аналог ядерного оружия). Чтобы проверить, сброшена она куда-то в пустую точку игрового поля, или же наведена на конкретного юнита, по ошибке использовалась конструкция isVisible(getCurrentPlayer()), а не isVisible(игрок, который сбрасывает наковальню).

Вот как воспроизводился баг: одному игроку нужно было построить Скаута, сделать его невидимым, и пойти на вражескую базу. Второму нужно было построить снайпера и использовать способность "сбросить наковальню" на точку, в которой стоит (или через которую проходит) невидимый скаут (вернее, на верхнюю половину его туловища). Эта команда на одной DS-ке означала "сбросить наковальню в точку за торсом скаута", а на другой - "сбросить наковальню на этого скаута" (то есть в точку у него под ногами). Мало того, важно было при этом не подходить черезчур близко к нему, чтобы не "заметить" его и не вывести из состояния невидимости.

Я не представляю себе юнит-, да и какой угодно еще тест, который был бы способен отловить подобное фантастическое стечение обстоятельств. Чтобы в игре не было подобных ошибок, необходимы живые самоотверженные тестировщики, и крайне желательна математическая строгость кода.
Tags: gamedev, soft
Subscribe
  • Post a new comment

    Error

    default userpic

    Your reply will be screened

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