Рубрика «поиск пути»

Решение головоломки из университетского квеста с помощью Python - 1

Cat Walk — одна из интересных головоломок игры Puzzle HuntЧитать полностью »

Быстрый поиск касательных и пересечений у выпуклых многоугольников - 1

Я недавно сделал маленькую библиотеку для решения задачи поиска кратчайшего пути на 2D карте с выпуклыми препятствиями. В процессе реализации я придумал пару алгоритмов и трюков, описания которых я нигде не встречал. Поэтому делюсь этими "изобретениями" с общественностью.

Горжусь тем, что мое решение работает очень быстро. Для внушительного количества полигонов все операции можно выполнять каждый кадр. Т.е. не надо ничего запекать и вся геометрия карты может меняться в каждом кадре.

Читать полностью »

Задача движения юнитов в играх является одной из ключевых задач, стоящих перед разработчиками игр. От того, как двигаются игровые юниты, во многом зависит восприятие всего геймплея в целом.
Традиционно считается, что достаточно реализовать алгоритм поиска пути и дальше всё будет работать само собой.
На практике же мы имеем совсем другую ситуацию.
Алгоритмы поиска пути разобраны досконально.
Нужен поиск пути с весами? A*. Нужен поиск для большого количества юнитов? Flow Field или кластеризация.
По большому счету по поиску пути не осталось не разобранных вопросов.
И вот, поиск пути реализован и довольный игродел запускает свою игру… И видит, что болванчики полностью оправдывают своё название. Они конечно находят путь и едут туда, куда им сказали. Но при этом спотыкаются о препятствия… Толкаются друг с другом или проезжают насквозь… Упираются друг в друга при встречном движении…
Эти проблемы и будем сегодня решать.
Реализация маневрирования юнитов в играх (избегание столкновений) - 1

Disclaimer

Данная статья не претендует на исчерпывающее решение обозначенной проблемы.
Я лишь рассказываю о том, как конкретно мне видится решение, над которым я работал. Это решение в оттюнингованном виде попало в один из зарелизенных в этом году РТС проектов, но осталось ли там на данный момент я не знаю. Комментарии и дополнения приветствуются.

Читать полностью »

Новый алгоритм поиска пути в Factorio - 1

На прошлой неделе мы говорили в своём блоге об изменениях, которые позволят врагам (biters) не наталкиваться друг на друга, но это было не единственное обновление, связанное с biter-ами. Совпало так, что в обновления этой недели вошло то, над чем мы работали предыдущие несколько недель — обновление системы поиска пути для врагов.

Поиск пути

Когда юнит хочет куда-то переместиться, ему сначала нужно понять, как туда добраться. В самом простом случае можно двигаться прямиком к цели, но на пути иногда возникают препятствия — скалы, деревья, гнёзда врагов (spawners), юниты игрока. Чтобы проложить дорогу, мы должны сообщить функции поиска пути (pathfinder) текущую и конечную позиции, а pathfinder вернёт нам (возможно, через много тактов) путь, который просто является набором промежуточных точек (waypoints), по которым должен двигаться юнит, чтобы добраться до места назначения.

Для выполнения своей работы pathfinder использует алгоритм под названием A* (произносится «A star»). Простой пример поиска пути при помощи A* показан на видео: biter хочет найти путь в обход скал. Функция поиска пути начинает исследовать карту вокруг biter-а (исследование показано белыми точками). Сначала она пытается пойти напрямик к цели, но как только достигает скал, «разливается» в обе стороны, пытаясь найти позицию из которой снова можно будет двигаться к цели.
Читать полностью »

Quality-lab ценности

Многие компании стараются заботиться о своих сотрудниках. Кому-то даже кажется, что они в этом преуспели, но на деле не всё так просто. Как компании оценить свой HR-бренд, а соискателю выбрать работодателя по душе? Наверное, с этой целью авторитетные ресурсы вроде hh.ru и составляют рейтинги работодателей. Давайте выяснять, как попасть в его TOP и при чём тут менеджмент счастья.Читать полностью »

image

Goldeneye 007 — одна из самых важных игр в истории. Она определила дальнейшее развитие целого поколения консольных игр и проложила шутерам от первого лица дорогу на рынок консолей. Перенесёмся более чем на 20 лет назад, чтобы узнать, как одной из самых популярных на Nintendo 64 игр удалось реализовать ИИ врагов и друзей, у которого можно чему-то научиться даже сегодня.

Об игре

После своего выпуска в 1997 году GoldenEye 007 не только определил судьбу поколения, но и превзошёл все ожидания. В эту игру мало верила сама Rare, Nintendo и даже владелица прав на франшизу Бонда — компания MGM. Выпущенная спустя два года после выхода фильма и спустя год после появления консоли на рынке, она казалась обречённой на провал, но стала третьей по продажам (восемь миллионов копий) за весь срок жизни платформы, уступив только Super Mario 64 и Mario Kart 64. Не говоря уже о том, что в 1998 году она заработала компании Rare награду BAFTA и звание разработчика года.

Искусственный интеллект Goldeneye 007 - 2

Эта игра оставила нам огромное наследие: она задала стандарты того, что нужно ожидать от следующих поколений шутеров от первого лица, особенно в поведении ИИ: персонажи с паттернами патрулирования, враги, запрашивающие подкрепление, убегающие в страхе мирные жители, плавная навигация и поиск пути, богатый набор анимаций, динамические свойства, возникающие в процессе игры, и многое другое. Она не только задала стандарты поколения, но и повлияла на игры, которые её превзошли — Half Life, Crysis, Far Cry и многие другие.
Читать полностью »

Поле

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

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

Туториал создавался в Unity 2018.3.0f2.

Создание игры Tower Defense в Unity, часть 1 - 1

Поле, готовое к использованию в тайловой игре жанра tower defense.

Игра жанра Tower Defense

Tower defense — это жанр, в которой целью игрока является уничтожение толп врагов, пока они не добрались до своей конечной точки. Игрок выполняет свою цель, строя башни, которые атакуют врагов. У этого жанра очень много вариаций. Мы будем создавать игру с тайловым полем. Враги будут двигаться по полю в сторону своей конечной точки, а игрок будет создавать им препятствия.
Читать полностью »

image

Часть 1. Общий алгоритм поиска

Введение

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

Цель данной статьи — объяснить поиск пути в целом и A* в частности очень понятным и доступным образом, положив таким образом конец распространённому заблуждению о том, что эта тема сложна. При правильном объяснении всё достаточно просто.

Учтите, что в статье мы будем рассматривать поиск пути для игр; в отличие от более академических статей, мы опустим такие алгоритмы поиска, как поиск в глубину (Depth-First) или поиск в ширину (Breadth-First). Вместо этого мы постараемся как можно быстрее дойти от нуля до A*.
Читать полностью »

image

Следование по пути и управление движением

Иногда нам нужно, чтобы ИИ-персонажи бродили по игровому миру, следуя по грубо очерченному или точно заданному пути. Например в гоночной игре ИИ-противники должны ехать по дороге, а в RTS юниты должны уметь перемещаться в нужную точку, двигаясь по рельефу и учитывая положение друг друга.

Чтобы казаться умными, ИИ-агенты должны уметь определять, что они делают, и если не могут достичь нужной точки, то они должны уметь прокладывать наиболее эффективный маршрут и изменять свой путь, когда на пути появляются препятствия.

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

Технические требования

Необходима версия Unity 2017, установленная в системе с Windows 7 SP1+, 8, 10 или с Mac OS X 10.9+. Код из данной статьи не будет работать на Windows XP и Vista, а серверные версии Windows и OS X не тестировались.

Файлы кода для этого поста можно найти на GitHub.

Чтобы изучить код в действии, посмотрите это видео.
Читать полностью »

Предисловие

Если вы создаёте игру-платформер в стиле «беги и прыгай», то, возможно, уже задумывались о добавлении в неё ИИ. Он может управлять противниками, объектами, которые игрок должен преследовать, и так далее… И слишком часто ради простоты программист реализации отказывается от умного ИИ, что в результате приводит к тому, что ИИ не может справиться с хитрыми прыжками, особо умным игроком или движущимися объектами уровня.

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

Мы рассмотрим основную идею и создадим полную реализацию. Более сложные случаи, в том числе подвижные платформы/разрушаемые стены, мы рассмотрим в другой статье.

Эта техника использована в игре Nomera, см. на www.dotstarmoney.com или в Twitter.

e3iKSJ7.png

Прежде чем начать, проверьте, возможно, вы удастся реализовать более простой алгоритм, соответствующий упрощённой геометрии карты. Например, если коллизии в уровнях распознаются по сетке квадратов (как в большинстве 2D-игр). В таких случаях можно реализовать надёжный поиск путей ИИ с помощью более простых техник. Мой метод в основном подойдёт тем, кто хочет более «человечного» поведения ИИ.
Читать полностью »


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js