Когда я создал сцену с лесом и добавил туда персонажа (которого, кстати, взял на Mixamo), я подумал, что этот персонаж не может просто стоять на карте, как истукан, а должен уметь по ней передвигаться. Но не просто из точки А в точку Б, а с учетом препятствий. Раз уж наш пока что лирический герой находится в лесу, то должен уметь обходить деревья. Для меня это совершенно новый опыт и, возможно, люди, которые больше меня подкованы в теме разработки игр и алгоритмах, найдут этот текст дилетантским, но мне было интересно разбираться в том, как работает один из молотов, кующих разработчика, А*.
A*
Если представить поверхность, по которой нужно перемещаться персонажу, сеткой, то поиск пути от одной клетки до другой - это задача поиска в графе. Один из самых оптимальных способов это сделать - применить алгоритм, которому уже 62 года. Представим, что у каждой клетки есть некоторая проходимость - чем сложнее по ней передвигаться, тем выше стоимость передвижения. Некоторые клетки (те, на которых есть деревья), вообще непроходмы. Задача А* - найти такой путь, который будет иметь минимальную стоимость, то есть будет самым быстрым. Для этого для каждой клетки дополнительно еще используется эвристическая оценка, которая показывает, насколько перспективным решением будет пойти в ту или иную сторону.
Раз уж так получилось, что я занимаюсь фронтендом и мне интересны возможности веб-платформы, самым логичным шагом было начать с javascript-имплементации. Существует отличная библиотека PathFinding.js, в которой собран десяток различных вариантов этого алгоритма и несколько видов эвристик. По ссылке можно посмотреть на статистику: сколько проходит итераций поиска, сколько он занимает времени. Самым оптимальным, на мой взгляд, был двунаправленный Best First Search с эвристикой Octile. Дополнительно он может свернуть путь до небольшого количества ключевых точек, определяющих, где находятся повороты. Ссылка на код
Профиль производительности js-версии
А можно мощнее?
Javascript - штука однопоточная, и если иметь дело с большой или запутанной картой, вычисления могут повлиять на отзывчивость интерфейса. Браузер и без того занят тем, что выполняет кучу работы по визуализации сцены каждые 16 миллисекунд, и правильным решением было бы ему помочь. Например, вынеся задачу поиска пути в отдельный поток, в воркер. По идее, это должно освободить основной поток для выполнения и планирования более важной работы. Ссылка на тот же самый код, что и в предыдущем примере, но уже перенесенный внурть работника (Github).
Профиль производительности worker-версии
А еще мощнее?
JS-версия, я уверен, использует все возможности движка по оптимизации, как например, hidden classes и кеширование, и при использовании TypeScript можно быть в той или иной степени уверенным в том, что параметры, передающиеся в методы PathFinding.js, будут всегда одного и того же типа. Это, в свою очередь, не будет приводить к их деоптимизации. Но еще интересней попробовать запустить этот процесс в WebAssembly с near-native скоростью. С точки зрения веб-технологий это еще более любопытно, потому что, несмотря на 10 лет своего существования, WebAssembly не используется так уж широко.
WebAssembly можно скомпилировать из десятка языков, включая C++, Go и Rust. Так как я не умею писать ни на одном из них, то можно просто найти готовое решение и скомпилировать его под свои нужды. Я выбрал Go, потому что... не знаю, просто попробовать. Благодаря отличному разбору Aaron Powell, все оказалось не так уж и сложно и заняло буквально один день. Штука в том (и об этом есть упоминание в статье), что Wasm, скомпилированный из Go, ведет себя как отдельная подпрограмма. В ней можно использовать состояние и не инициализировать граф с препятствиями при каждом вызове. Учитывая, что в конкретно этой моей WebGL-сцене поиск пути выполняется при движении мыши над плоскостью, это может сэкономить некоторое количество ресурсов. Хотя этот же факт может привести к нежелательным последствиям:
- исключение, выброшенное внутри Wasm-модуля, означает, что поток, который не дает Go-скрипту завершиться, закрывается и повторная попытка вызвать какие-то из его функций будет неудачной;
- Go не экспортирует никаких функций, он регистрирует обработчики в глобальной области видимости. Это может привести к конфликту имен;
- то, что через все ту же глобальную область видимости он может манипулировать DOM, на мой взгляд, делает Go потенциально небезопасной штукой.
Профиль производительности go-версии
Еще!
Чтобы совсем упороться не пренебрегать возможностями Wasm по управлению памятью, я решил пойти на эксперимент и написать рализацию А* самому на AssmeblyScript. Это версия TypeScript с чуть более строгими ограничениями и разницей в поведении базовых типов (к примеру, Map.keys() возвращает не итератор, а массив ключей). В случае чего, AssmeblyScript-код можно довольно быстро преобразовать в TypeScript. Увидеть результат можно тут.
Профиль производительности AssembyScript-версии
Как теперь с этим жить?
Я надеялся, что простая миграция миграция кода с уровня браузера на уровен WebAssembly даст прирость производительности и избавит от головной боли по оптимизации. Но, как видно из скриншотов профилировщика, большой разницы нет. Wasm-версии работают даже немного хуже в периоды интенсивной деятельности. FPS снижается иногда до 1-2 кадров в секунду, и в это время сильно нагружен GPU. Эксперимент завершился, самый правильный выбор - полагаться на браузерный движок.
Update
Простые оптимизации сборки могут ускорить WebAssembly-версию в 4 раза. ¯\_(ツ)_/¯
P.S.
Да, я знаю, он никуда не идет. Но ведь они никуда и не спешит :)
13 июля 2020