Вас приветствует команда «Graceful Algorithms»!
В качестве эксперимента нами было принято решение вести «дневники» разработчиков, в которых мы будем делиться опытом и освещать некоторые интересные результаты проводимых нами экспериментов. Это наша дебютная статья по проекту «Pathfinder 3D» — ассету для игрового движка Unity, который позволяет производить поиск пути в трёхмерном пространстве. В ней мы расскажем о пути от зарождения идеи до полноценного продукта и о некоторых проблемах, с которыми мы встретились. Данный материал будет полезен для людей, которые хотят начать свой проект и поддерживать его в дальнейшем, а также для желающих реализовать поиск пути в пространстве.
Работу над ассетом начала команда из двух человек. У первого имелись наработки, позволяющие ускорить процесс поиска кратчайшего пути на сложных графах в достаточной мере для работы в реальном времени, и желание найти им практическое применение, второй имел некоторый опыт работы с Unity и искал идею для стартапа. Так как они нередко общались друг с другом, неудивительно, что в определённый момент возникла идея о возможности создания ассета для поиска пути в трёхмерном пространстве.
При изучении каталога ассетов Unity было найдено множество решений для поиска пути на двумерном пространстве, но ни одного на трёхмерном. Стало очевидно, что это отличная возможность выхода на рынок программных надстроек для Unity, особенно учитывая наглядность и зрелищность ожидаемого результата.
Целью было поставлено реализовать непосредственно поиск пути в трёхмерном пространстве и типовые возможности существующих решений поиска пути в двумерном пространстве. Мы приступили к работе: один разрабатывал непосредственно механизм поиска пути, второй классы и методы для управления процессом поиска пути, интерфейсы для настройки, тестовые сцены, документацию, сайт проекта, а также занимался регистрацией и настройкой аккаунтов сервисов, необходимых для продажи ассета.
Вскоре после начала работы стало ясно, что необходим какой-то общий для команды ресурс для ведения заметок: списка задач и проблем, которые необходимо решить, информации о принятых решениях, интересных в перспективе идей и результатов исследований. Проанализировав существующие решения, мы остановились на Trello, из-за его функциональности, простоты, удобства и приятного внешнего вида. Как показала практика, данный сервис очень удобен для небольших команд. Если в команде больше 5 человек, мы бы посоветовали использовать полноценную систему управления проектами.
Далее опишем решения, принятые при разработке первой версии ассета, и логику, которой мы следовали при их принятии. Люди, которые имеют опыт работы с Unity и знакомы с алгоритмами поиска пути, сразу поймут, где в будущем возникнут проблемы. В этих местах мы воспользовались простым решением в угоду сокращению сроков разработки до получения первой рабочей версии ассета, чтобы не увязнуть, ведь энтузиазм штука ограниченная и непостоянная. Таким образом мы справились с одной из самых распространённых причин закрытия подобных стартапов, из-за которой многие проекты умирают так и не родившись. Все проблемные места исправлялись уже после публикации ассета.
Для поиска пути был выбран алгоритм A* (A star) из-за его высокой скорости работы на больших открытых пространствах. Большинство алгоритмов поиска пути работают на графах, представленных дискретной матрицей. Можно было бы строить данную матрицу заранее, но единоразовый процесс её построения по трехмерному пространству с препятствиями выглядел на тот момент как довольно сложная задача. К тому же было не ясно, как можно сделать это без ущерба производительности, так как на момент начала работы над ассетом опыта работы с фоновыми процессами и многопоточностью в Unity, как и с многопоточностью в целом, не было. Граф формировался в реальном времени, путем прощупывания пространства физическими лучами (Physics.BoxCast) в направлении поиска. Найденные траектории приводились к ломанным, имеющим меньшее количество промежуточных точек, а затем сглаживались сплайнами.
Основная сложность заключалась в невозможности асинхронного использования физических методов движка, так как они могут работать исключительно в основном потоке. На не слишком сложных сценах использование функции поиска одновременно не более чем двадцатью агентами не сильно влияло на частоту кадров. Чтобы избавиться от редких сильных просадок FPS, вычислительная нагрузка была разнесена во времени с помощью сопрограмм (corutines). Это замедлило поиск, но незначительно.
Перед подачей ассета на модерацию необходимо привести код в порядок и составить подробную документацию, в соответствии с требованиями, зарегистрировать и настроить почту поддержки. Желательно также создать сайт проекта, где будут в удобной форме отображаться новости разработки и демонстрационные примеры. Это будет большим плюсом как при прохождении модерации, так и при изучении вашего ассета пользователем перед покупкой. Услуги и почтового сервиса были заказаны нами у компании BeGet, так как она на тот момент предлагала наиболее выгодные предложения, и обходятся нам в 1000р/год.
Модерация ассета длилась 22 дня и прошла с первого раза, так как мы очень тщательно подошли к составлению документации и оформлению страницы ассета в магазине Unity. После публикации ассет сразу попал на первые места в категории Scripting/AI. С этого момента на почту поддержки стали приходить письма с просьбами помочь в решении тех или иных проблем. Иногда несколько за день, иногда ни одного за месяц. Если усреднить, то за месяц с вопросами обращались 2 человека, переписка с которым занимала суммарно 2-3 часа. Не так уж много, но следует учитывать, что вне зависимости от вашей текущей загруженности отвечать нужно очень оперативно, чтобы разгневанные пользователи не писали плохих отзывов о продукте, а, наоборот, восторженные качественной поддержкой, оставляли положительные. Также на почту приходит довольно много вопросов по типу «а будет ли ваш ассет работать, если…». Такие письма тоже не следует игнорировать, ведь это потенциальный покупатель, который может уйти.
По мере получения жалоб от первых покупателей, стало ясно, что многие пользователи используют ассет на сложных сценах, имеющих конфигурацию лабиринта или иной связной полости. В подобных проектах применяемая нами схема поиска пути, основанная на проверке столкновений, да еще и в главном потоке, была недостаточно эффективна. Поэтому мы приступили к реализации досрочного построения графа, чтобы стало возможным производить поиск пути в побочном потоке без использования физики и обращений к объектам сцены.
Дискретизация трехмерного пространства разбивает его на кубы. Хранение информации о всех кубах разбиения избыточно и является очень затратным по памяти. Поэтому логично хранить только координаты непроходимых клеток, что и было сделано.
Игровые препятствия являются полигональными фигурами и состоят из треугольников. Для учета препятствий в графе поиска необходимо найти все кубы разбиения, пересекающие какой-либо треугольник какого-либо препятствия. Уже на этом этапе была заложена возможность динамического удаления и добавления препятствий на сцене, и сохранялись не только координаты занятых кубов, но и идентификаторы препятствий, которые находились в них. Теперь появилась возможность строить навигационный граф до начала игрового процесса и, за счет устранения большого количества сложных расчетов во время поиска пути, более двухсот агентов могли совершать его одновременно без ущерба производительности.
Также дала о себе знать другая известная нам проблема: алгоритм A* и его модификации крайне плохо работают в замкнутых пространствах на графах большой мощности. Поскольку их алгоритм отдает предпочтение направлению маршрута в сторону сближения с целевой точкой, любой тупик, ведущий в сторону цели, сильно замедлял поиск пути, так как, прежде чем выбрать другое направление «прорастания», алгоритм сначала «заполняет» все пространство внутри тупика.
В таких ситуациях очень эффективным показывает себя волновой алгоритм поиска (Алгоритм Ли) за счёт меньшего количества операций, требуемых для «заполнения» пространства. Поэтому он был добавлен в состав ассета как альтернативный. При тестировании на сцене, являющейся лабиринтом, время поиска пути сократилось более чем в 30 раз.
Для ускорения предварительной обработки сцены и поиска пути в ассет была добавлена возможность параллельного выполнения процессов, но эффективность параллелизма была крайне низкой, из-за того, что при работе с контейнером, хранящим координаты занятых клеток, необходимо производить синхронизацию потоков, которая была выполнена с помощью мьютексов, так как конкурентные коллекции и многие другие средства для обеспечения эффективной синхронизации были реализованы только в стандарте .NET Framework 4.5, а в Unity до 2018 выпуска использовалась версия .NET Framework 3.5. Мы пытались решить данную проблему с помощью доступных средств, но они обладали очень посредственным быстродействием, и желаемый результат мы получили только после перехода на 2018 выпуск Unity. Использование конкурентных коллекций также открыло возможность реализации динамического изменения препятствий на сцене.
На определённом этапе в команде начали возникать разногласия по поводу распределения прибыли, и к команде присоединился третий человек, который ввёл систему оценки временных вложений каждого члена команды, а также стал заниматься инспекцией кода и тестированием, что заметно повысило качество продукта.
Система оценки временных затрат на данный момент выполнена в виде Excel таблицы и представляет из себя автоматизированную систему, в которую раз в месяц необходимо вводить информацию о продажах и выполненных за прошедший месяц задачах. Участникам команды необходимо оценить сколько времени им потребовалось бы на решение той или иной задачи. Таким образом при оценке временной сложности задач учитывается скорость работы каждого участника. Аномальное завышение или занижение оценки кем-либо из участников сразу же становится видно по накопленной статистике его предыдущих оценок. И, при отсутствии удовлетворительного пояснения, данный вопрос решается всем коллективом. Этот подход хорошо себя показал за полгода использования и позволил собирать интересную статистику. Готового бесплатного решения, которое бы предоставляло описанные возможности, нами найдено не было. Поэтому на данный момент для маленьких команд реализация в виде Excel таблиц видится нам оптимальной. Для относительно больших команд скорее всего придётся спроектировать свои базу данных, разработать серверную часть и клиент, либо реализовать расширение для одной из существующих систем управления проектами.
Подведём итоги. С момента начала разработки до первой версии с минимально необходимым функционалом и достаточной производительностью для использования в реальных проектах прошёл год. Ещё полгода ушло на повышение быстродействия и реализацию многопоточной работы ассета. На данный момент временные затраты на этот проект были оценены нами в 1065 человекочасов (это достаточно оптимистичная оценка), а средняя прибыль за месяц составляет 9,5тр. Несложно посчитать, что средняя стоимость часа работы составляет примерно 160р, что не так много. Однако, главное в этом мероприятии полученный каждым участником опыт. В том числе опыт работы в команде и опыт поддержки программного продукта. Проект можно считать успешным.
Теперь наша команда приступила к реализации дополнительного полезного функционала: алгоритмическая проверка достижимости; возможность назначать игровые объекты порталами; поддержка динамических препятствий; локальная навигация между агентами, для предупреждения столкновений и планирования локальных маршрутов.
Надеемся, данный материал поможет кому-нибудь довести свой проект до финишной прямой.
Автор: Samuel13
