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

Поиск пути — всему голова. Без него наши боты даже с места не сдвинутся и не доберутся до нужной точки на карте. Алгоритмов поиска пути существует множество, но для Tankolini Napierdolki мы выбрали HPA* (Hierarchical Pathfinding A*).

Под катом — много картинок, примеров и визуализаций. Погнали!

Этап 1. Находим препятствия

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

Здесь мы загружаем карту в память. Основная суть в том, что у нас есть только непроходимые блоки. В отличие от других игр, таких как Starcraft, где может быть много разных типов преград, у нас всё просто и понятно.

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

Этап 2. Строим карту проходимости

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

Меньше элементов — меньше нужно считать, быстрее и короче становится поиск пути. Вот ещё один пример.

Для проходимости мы берём размеры нашего объекта, который двигается, и добавляем их к препятствиям. В нашем случае танки занимают 3×3 клетки, поэтому мы добавляем по 3 точки вправо и вниз для каждого препятствия. Получается что-то вроде «тени».

Как видно, справа и снизу карты у нас по 2 квадрата залито. В теории, можно было уже на этом этапе остановиться, применить обычный A* — и всё бы работало. Но мы идём дальше.

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

Этап 3. Делим карту на сектора

В нашем случае карты 64×64 отлично делятся на сектора размером 8×8. Это хорошо подходит для того, чтобы хранить карту в бинарном виде, где 0 — проход есть, а 1 — нет.

Конечно, можно взять и другой размер ячейки, но 8×8 — это вполне разумный компромисс: данные хранить удобно, и при этом поиск пути внутри каждого сегмента остаётся максимально простым.

Этап 4. Находим порталы

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

Для простоты лучше объединять несколько соседних пикселей в одну группу. Например, у нас может быть пара пикселей [23, 45] и [24, 45], в то же время существуют более крупные группы, например [0-7, 7] и [0-7, 8].

Этап 5. Находим пути между порталами

Так как вариантов порталов очень много, я рисовал тонкие линии, но при достаточном увеличении можно чётко проследить, как между ними пролегают пути.

Наша задача — взять каждый отдельный сектор и найти маршруты между всеми порталами внутри него. Например, для сектора [0-7, 0-7] у нас есть две группы порталов: 3 пикселя по высоте справа [7, 0-2] и 7 пикселей снизу [0-6, 7]. Между этими группами будет только один маршрут, потому что мы считаем каждую группу порталов одной точкой.

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

Этап 5-1. Алгоритм A*

Но как мы прокладывали маршрут между этими точками? Здесь мы как раз и применяем алгоритм A*. На Хабре достаточно статей про его работу, поэтому сильно углубляться не будем. Например, эта: Введение в алгоритм A*.

Основная идея A* такая: мы берём какую-то начальную точку и начинаем двигаться в сторону, которая ближе к финишу. Чтобы понимать, где финиш, мы используем эвристическую функцию (в нашем случае достаточно расстояния Манхэттена: |dx| + |dy|). При этом мы запоминаем количество шагов, которое уже прошли от старта.

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

Важный момент: в алгоритме A* очень важно точно задать эвристическую функцию. Чем точнее она будет, тем естественнее бот будет искать путь. В нашем случае мы учли, что поворот танка — это отдельное действие, и лишние повороты нежелательны (иначе маршрут превращается в лесенку). Чтобы избежать этого, мы добавляем +1 к стоимости, если на пути требуется поворот. В результате маршрут получается чуть менее оптимальным по расстоянию, но гораздо больше похож на действия реального игрока.

Этап 6. Поиск пути на карте

Здесь уже дело техники. Мы применяем тот же алгоритм A*, но только для прохода между порталами. Так как мы заранее посчитали все маршруты между всеми порталами внутри каждого сектора, нам остаётся только брать готовые маршруты между двумя порталами и соединять их в полноценный путь.

Есть только один нюанс: начальная и конечная точки обычно не лежат точно на уже построенных маршрутах. Поэтому решаем задачу в лоб — для стартовой и финальной точек строим самый короткий путь до ближайшего портала с помощью того же A*.

В итоге весь конечный путь состоит из трёх этапов:

1. Построить путь от начальной точки до ближайшего портала (A')

2. Построить путь от ближайшего портала до финальной точки (B')

3. Построить путь между порталами (A' → B')

4. Склеить всё это в единый маршрут.

Завершение

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

Посмотреть, как всё это работает вживую, можно у нас в Tankolini Napierdolki. При регистрации через Telegram вы получаете бонусные 1000 баллов, которые можно обменять на билеты для платных турниров.

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

Также заходите в наш Телеграм канал и следите за новостями по розыграшах