Уже в процессе создания The Witness стала одной из самых любимых моих игр. Я начал играть в неё с того момента, когда Джонатан Блоу начал её разработку, и не мог дождаться её релиза.

В отличие от предыдущей игры Джона Braid, масштаб ресурсов и программирования The Witness был гораздо ближе к AAA-проектам, чем к инди-играм. Всем, кто работает над подобными проектами, известно, что объём работы при выборе такого пути значительно возрастает. Над The Witness работало гораздо больше людей, чем над Braid, но как и в случае с любым проектом такого уровня, в нём есть множество аспектов, которые требуют больше внимания, чем может позволить себе руководство проекта.

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

Walkmonster in Wall

В контексте The Witness, задача кода движения игрока — быть как можно более ненавязчивым. Игрок должен полностью погрузиться в альтернативную реальность, и в этом игровом опыте важна каждая деталь. Меньше всего нам хотелось, чтобы игрок заметил, что он сидит за компьютером и перемещает виртуальную камеру.

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

После нашего обсуждения я приступил к работе над этой задачей. Первым делом я решил написать интегрированные инструменты для работы с кодом движения игрока, чтобы мы могли анализировать его и наблюдать за его текущим поведением. Открыв проект, я столкнулся с уже известной мне серьёзной проблемой: как назвать первый файл исходного кода? Это всегда самая важная часть любого проекта (как однажды сказал Боб Поллард о названиях музыкальных групп и альбомов). Если вы дадите файлу исходников подходящее название, то дальнейшая работа будет чёткой и плавной. Выберете неверное — можете погубить и весь проект.

Но как назвать систему для обеспечения качества кода движения игрока? Раньше мне никогда не приходилось писать подобный код. Когда я задумался об этом, то осознал, что лично видел пример такого кода только однажды: при игре в раннюю бету Quake. В ней присутствовали баги с расположением монстров, а в окне консоли можно было видеть сообщения об ошибках, гласящие, что монстры, вместо создания на поверхности земли, создаются, частично пересекаясь с геометрией уровней. Каждое отладочное сообщение начиналось с фразы «walkmonster in wall at…»

Бинго! Сложно подобрать для файла кода лучшее название, чем «walk_monster.cpp». И я был почти уверен, что с этого момента код будет создаваться без проблем.

Движение к точке

Когда вы хотите тестировать систему, то самое важное — это на самом деле тестировать систему. Хотя это правило выглядит простым, пишущим тесты людям часто не удаётся его соблюсти.

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

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

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

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

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

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

Стоит также заметить, что этой функции не передаются физические входные данные; например, для начальной точки не указываются скорости. Так сделано потому, что The Witness — это не экшн-игра, поэтому у игрока есть мало значимых физических свойств. Игроки не могут прыгать, бегать по стенам, включать «bullet time». Поддерживать такие поведения можно с помощью систем, которые я опишу позже, но они добавляют уровни сложности, которые в нашем проекте не требовались.

Как бы то ни было, после реализации DriveTowardPoint я мог приступить к решению первой задачи системы: определению того, куда игрок может двигаться на острове The Witness.

Rapidly Exploring Random Trees

Куда могут двигаться игроки? Кажется, что это простой вопрос, но вы удивитесь, узнав, как много игр выпускалось, когда команда разработчиков не знала настоящего ответа. Если это возможно, то я хотел, чтобы The Witness была одной из тех немногих игр, в которой разработчики перед выпуском точно знали, куда может и куда не может попасть игрок — никаких сюрпризов.

Это делает постановку проблемы (но, вероятно, не её решение) очень простой: при наличии функции DriveTowardPoint, надёжно определяющей, может ли игрок двигаться по прямой линии между двумя точками, создать карту покрытия, демонстрирующую, где может оказаться игрок.

По каким-то причинам я, ещё не написав ни строки кода, почему-то считал, что лучше всего будет использовать Rapidly Exploring Random Tree. Для тех, кто незнаком с этим алгоритмом, объясню: это очень простой процесс, в котором мы записываем все точки, посещённые нами со ссылкой на точку, из которой мы пришли. Чтобы добавить в дерево точку, мы берём случайную целевую точку в любом месте мира, выбираем наиболее близкую к ней точку, уже находящуюся в дереве, и пытаемся добраться из этой точки к целевой. То место, где мы оказались в итоге, становится следующей точкой выборки.

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

После реализации этого алгоритма (к счастью, она очень проста и не потребовала много времени) я увидел, что он выполнил вполне качественную работу по исследованию пространства (белыми дорожками показаны исследованные пути, а вертикальными красными линиями обозначены места, в которых алгоритм столкнулся с препятствием):


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


Если бы я задумался об этом перед началом работы, то понял бы, что преимущество алгоритмов наподобие Rapidly Exploring Random Tree заключается в том, что они эффективно исследуют высокоразмерные пространства. На самом деле, обычно это основная причина их использования. Но в The Witness нет высокоразмерных пространств. У нас есть двухмерное пространство (да, распределённая по сложному многообразию, но это всё-таки двухмерное пространство).

В этом низкоразмерном пространстве преимущества Rapidly Exploring Random Tree проявляются слабо, а его недостаток критически важен для моей задачи: алгоритм предназначен для наиболее эффективного поиска путей к соединённым парам точек в пространстве, а не для эффективного поиска всех достижимых точек этого пространства. Если у вас такая задача, то на самом деле у Rapidly Exploring Random Tree уйдёт на её решение огромное количество времени.

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

3D Flood Filling

Когда я по-настоящему задумался о выборе алгоритма, то стало очевидным, что на самом деле мне требуется что-то наподобие старой доброй двухмерной заливки, которая используется для заполнения областей битовой карты. Для любой стартовой точки мне нужно было просто заполнить всё пространство, исчерпывающее проверяя каждый возможный путь. К сожалению, по множеству причин решение для The Witness будет гораздо сложнее, чем для двухмерной битовой карты.

Во-первых, у нас нет чёткой концепции конечной связности точки. Всё пространство непрерывно. Это для пикселя мы с лёгкостью можем перечислить 4 возможные места, в которые можно попасть из заданной точки, и проверить каждое из них по очереди.

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

В-третьих, хотя движение по пространству The Witness локально можно считать перемещением по плоскости, само пространство в действительности является глубоко взаимосвязанным и меняющимся многообразием, в котором проходимые для игрока области находятся непосредственно над другими областями (иногда может быть несколько расположенных друг над другом уровней). Кроме того, существуют соединения, изменяющиеся в зависимости от состояний мира (открытые/закрытые двери, поднимающиеся/опускающиеся лифты и т.д.).

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

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

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


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


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

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

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

Локализованное направленное сэмплирование

Вероятно, потому, что я начал с Rapidly Exploring Random Tree, мой мозг вытеснил все остальные идеи, кроме идеи близости. Все предыдущие алгоритмы для выполнения своей задачи использовали близость, например, для того, чтобы определить новую точку, которую нужно рассмотреть следующей, или для того, чтобы выбрать точку, с которой нужно начать, чтобы добраться до новой целевой точки.

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

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

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

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


Поскольку алгоритм выполняет поиск вдоль направлений, а не просто использует близость, то он защищён от граничного эхо и ограничивает излишнее сэмплирование только теми границами, которые нам необходимы:


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

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

Рудиментарная проверка рёбер

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

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

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


А вот та же область с проверкой рёбер:


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

Быстрые победы

Даже вложив всего немного времени в разработку и создав довольно простой код, я добился того, что Walk Monster уже создаёт вполне пригодные выходные данные, способные обнаруживать настоящие проблемы в игре. Вот примеры проблем, которые я нашёл в процессе разработки алгоритма:


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


The Witness должна была стать созерцательной игрой, но задаваться вопросом, почему кажется, что камень есть, хотя его нет, не было одним из её коанов. Как можно догадаться, эта проблема возникла, потому что кто-то оставил в игре объём коллизии после удаления обозначающей его геометрии. Такое может запросто случиться, и очень хорошо, что у нас есть инструмент, способный быстро распознавать такие ошибки, чтобы этого не пришлось делать людям.



Эти объекты должны были стать непроходимыми скалами, но Walk Monster обнаружил, что этого не произошло. Хуже того — Walk Monster обнаружил, что путь почему-то проходим только в одном направлении (на скриншоте — слева направо), а такого быть не должно. Я убедился, что игрок действительно может это сделать (мне удалось). Очень интересно наблюдать за возникновением таких ошибок!

Открытые вопросы

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

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

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

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

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

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