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