Пишем ботов без ботов. Нахождения пути с помощью HPA* алгоритма

В сфере искусственного интеллекта произошло заметное событие. t0rsym 1 минуту назад Пишем ботов без ботов. Нахождения пути с помощью HPA* алгоритма Средний 4 мин 0 Алгоритмы * Программирование * Разработка игр * Визуализация данных * Веб-разработка * Туториал Кто сказал, что Хабр - не торт ???? Пока все ставят капельницы с раствором нейронной сети, мы вспоминаем дедов и делаем так, как они завещали.

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

Технические детали

Алгоритмов поиска пути существует множество, но для Tankolini Napierdolki мы выбрали HPA* (Hierarchical Pathfinding A*). Под катом — много картинок, примеров и визуализаций. Находим препятствияТам мы видим оригинальную картуВ игре есть возможность самому создавать карты в небольшом редакторе, поэтому вполне логично обрабатывать карту сразу после её создания и использовать готовые маршруты для каждого бота.

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

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

Отраслевые последствия

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

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

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

Этот прогресс даёт важные сигналы о будущем отрасли, и технологический мир внимательно наблюдает.