Хабрахабр

[Перевод] Блуждающий монстр: как избавиться от проблем на карте

image

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

Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть