Pull to refresh
  • by relevance
  • by date
  • by rating

Вперед к новым вершинам незнания

Intel corporate blog Website development *Programming *
Translation

За время своей деятельности Intel сгенерировала и воплотила в жизнь огромное количество инновационных замыслов, начиная с пионерских технологий в процессорах и памяти 60-х – 70-х годов и заканчивая перспективными разработками сегодняшнего дня. Ключ к этим достижениям – мощная и бережно лелеемая внутри компании культура выдвижения и восприятия новых идей. Под катом – сокращенный перевод интервью со старшим архитектором подразделения Intel Software and Services Group Ylian Saint-Hilaire о нелегкой, но увлекательной жизни разработчиков-первопроходцев, перед которыми Intel ставит особую задачу — генерировать и продвигать новые идеи.
Читать дальше →
Total votes 22: ↑16 and ↓6 +10
Views 12K
Comments 4

Поиск пути через NavMesh на ActionScript – CrossBridge-порт Recast Navigation

Open source *Game development *Action Script *
Sandbox


В этой статье я расскажу об опыте переноса C++ кода на ActionScript с помощью FlasCC компилятора и покажу, как с его помощью мне удалось портировать довольно большой объем полезного кода, решающего задачу поиска пути. В конце будет демо и ссылка на репозиторий с кодом. А пока пара слов о том, с чего вообще все началось.
Читать дальше →
Total votes 20: ↑18 and ↓2 +16
Views 8.5K
Comments 2

AI монстров и поиск пути с помощью тепловых карт

Game development *
image Допустим, у нас есть плоская карта, состоящая из тайлов. На некоторых тайлах стоят монстры, а на некоторых других – всякие штуки, которые монстров интересуют: игрок, оружие, зелья, боеприпасы и прочее в том же духе. Задача состоит в том, чтобы объяснить монстрам, к каким штукам им идти и как. Путь должен быть близким к оптимальному, а время вычисления – настолько маленьким, насколько это возможно. Один из самых простых способов – использовать тепловую карту дистанций до определённой цели или целей.
Читать дальше →
Total votes 61: ↑61 and ↓0 +61
Views 24K
Comments 26

Поиск пути в играх Tower Defense

Python *Game development *Algorithms *
Translation
[Прим. пер.: в оригинале статьи есть интерактивные демо, которые я продублировал с помощью видео. Для большей наглядности рекомендую изучить примеры в оригинале.]

В играх жанра Tower Defense (TD) множество врагов стремится добраться в одну точку. Во многих играх TD существует заранее заданный путь или несколько путей. В некоторых, в том числе в классической Desktop Tower Defense можно размещать башни в произвольных местах, и они становятся препятствиями, влияющими на пути врагов. Запустите демо и нажимайте на карту, чтобы возводить или убирать стены:


Total votes 23: ↑22 and ↓1 +21
Views 17K
Comments 3

Библиотека быстрого поиска путей на графе

Website development *JavaScript *Programming *Game development *Algorithms *

Привет, Друзья!


Я написал библиотеку поисков путей на произвольных графах, и хотел бы поделиться ей с вами.


Пример использования на огромном графе:



Поиграться с демо можно здесь


В библиотеке используется мало-известный вариант A* поиска, который называется NBA*. Это двунаправленный поиск, с расслабленными требованиями к функции-эвристике, и очень агрессивным критерием завершения. Не смотря на свою малоизвестность у алгоритма отличная скорость сходимости к оптимальному решению.


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

Читать дальше →
Total votes 114: ↑112 and ↓2 +110
Views 32K
Comments 53

Обобщённый поиск путей для ИИ в платформерах

Game development *
Translation

Предисловие


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

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

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

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

e3iKSJ7.png


Прежде чем начать, проверьте, возможно, вы удастся реализовать более простой алгоритм, соответствующий упрощённой геометрии карты. Например, если коллизии в уровнях распознаются по сетке квадратов (как в большинстве 2D-игр). В таких случаях можно реализовать надёжный поиск путей ИИ с помощью более простых техник. Мой метод в основном подойдёт тем, кто хочет более «человечного» поведения ИИ.
Читать дальше →
Total votes 27: ↑26 and ↓1 +25
Views 10K
Comments 3

Гуляем по городу с умом: как я делал сервис для построения интересных пешеходных маршрутов

Algorithms *Geoinformation services *Urbanism
UPD: так как тема хорошо зашла и показала наличие спроса на такой сервис, буду развивать его дальше. Завел паблик вконтакте для сбора фидбека и публикации информации об обновлениях https://vk.com/sightsafari

Незнакомый район города, небольшое количество свободного времени и необходимость (или желание) пешком добраться до метро/отеля/вокзала – наверное, каждый хоть раз попадал в такую ситуацию. При этом с одной стороны хочется посмотреть какие-нибудь красивые и интересные места, однако с другой стороны ограниченное время не позволяет слишком сильно уклоняться от прямого маршрута.

Ситуация еще больше осложняется, если рядом нет никаких крупных достопримечательностей, о которых все знают и которые можно было бы включить в свой маршрут после короткого поиска в интернете. Что делать если вы застряли в каком-нибудь Купчино, про которое вы только и слышали, что там лучше не застревать? Приходится идти по навигатору, надеясь, что на пути встретится что-то интересное. Однако популярные навигаторы учитывают лишь расстояние и время в пути, но не принимают во внимание интересность маршрута. Мне попадались еще проекты, пытающиеся учитывать удобство пешего маршрута (ведущие в обход шумных магистралей), но хочется же пройти не только комфортно, но и увидеть какие-нибудь красоты.



Подумав немного, я решил взяться за эту задачу сам. Как всегда, общая идея алгоритма довольно проста, но дьявол кроется в мелочах. А в случае навигации, мелочи могут быть довольно существенны и с риском для здоровья, ведь вряд ли какой-нибудь турист обрадуется, когда навигатор в поисках достопримечательностей заведет его в дебри полузаброшенной промзоны ради маленькой мемориальной таблички (тру стори, один раз так и случилось).

Описание алгоритма и примеры работы под катом, ссылка в конце.
Читать дальше →
Total votes 114: ↑113 and ↓1 +112
Views 48K
Comments 212

Реализация поиска путей для ИИ-агентов с помощью NavMesh

Game development *Unity3D *
Translation
image

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


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

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

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

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


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

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

Чтобы изучить код в действии, посмотрите это видео.
Читать дальше →
Total votes 14: ↑13 and ↓1 +12
Views 29K
Comments 3

Job system и поиск пути

Game development *Unity3D *

Карта


В предыдущей статье я разобрал, что из себя представляет новая система задач Job system, как она работает, как создавать задачи, наполнять их данными и выполнять многопоточные вычисления и лишь в двух словах объяснил где можно использовать эту систему. В этой статье я попробую разобрать конкретный пример того где можно использовать эту систему, чтобы получить большую производительность.
Читать дальше →
Total votes 21: ↑20 and ↓1 +19
Views 6.4K
Comments 4

Карты из шестиугольников в Unity: поиск пути, отряды игрока, анимации

Game development *Unity3D *
Translation
Части 1-3: сетка, цвета и высоты ячеек

Части 4-7: неровности, реки и дороги

Части 8-11: вода, объекты рельефа и крепостные стены

Части 12-15: сохранение и загрузка, текстуры, расстояния

Части 16-19: поиск пути, отряды игрока, анимации

Части 20-23: туман войны, исследование карты, процедурная генерация

Части 24-27: круговорот воды, эрозия, биомы, цилиндрическая карта

Часть 16: поиск пути


  • Подсвечиваем ячейки
  • Выбираем целевую точку поиска
  • Находим кратчайший путь
  • Создаём очередь с приоритетом

Вычислив расстояния между ячейками, мы перешли к нахождению путей между ними.

Начиная с этой части, туториалы по картам из шестиугольников будут создаваться в Unity 5.6.0. Нужно учесть, что в 5.6 есть баг, разрушающий массивы текстур в сборках для нескольких платформ. Обойти его можно, включив в инспекторе массива текстур Is Readable.


Планируем путешествие
Total votes 24: ↑24 and ↓0 +24
Views 8.5K
Comments 0

Простое объяснение алгоритмов поиска пути и A*

Game development *Algorithms *Game design *
Translation
image

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


Введение


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

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

Учтите, что в статье мы будем рассматривать поиск пути для игр; в отличие от более академических статей, мы опустим такие алгоритмы поиска, как поиск в глубину (Depth-First) или поиск в ширину (Breadth-First). Вместо этого мы постараемся как можно быстрее дойти от нуля до A*.
Читать дальше →
Total votes 29: ↑29 and ↓0 +29
Views 32K
Comments 11

Гуляем по городу с умом — 2: ходим по городу кругами с помощью генетического алгоритма

Algorithms *Geoinformation services *

В прошлой статье я описал алгоритм, позволяющий строить более интересные (в противовес более коротким, как делают всякие яндексы-гуглы) пешеходные маршруты между двумя точками. Алгоритм загружал достопримечательности, парки и прочие приятные и интересные для пешеходов объекты из Open Street Map и прокладывал маршрут через них. В итоге путь мог оказаться на 10-20% длиннее, но гораздо живописнее и интереснее.



Фото города — Alex 'Florstein' Fedorov


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


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

Читать дальше →
Total votes 56: ↑55 and ↓1 +54
Views 12K
Comments 71

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

Game development *Algorithms *C# *Unity3D *
Translation

Поле


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

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

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


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

Игра жанра Tower Defense


Tower defense — это жанр, в которой целью игрока является уничтожение толп врагов, пока они не добрались до своей конечной точки. Игрок выполняет свою цель, строя башни, которые атакуют врагов. У этого жанра очень много вариаций. Мы будем создавать игру с тайловым полем. Враги будут двигаться по полю в сторону своей конечной точки, а игрок будет создавать им препятствия.
Читать дальше →
Total votes 23: ↑22 and ↓1 +21
Views 15K
Comments 0

Опыт разработки ассета Unity для поиска пути в 3D пространстве

Unity3D *Start-up development
Sandbox
Вас приветствует команда «Graceful Algorithms»!

В качестве эксперимента нами было принято решение вести «дневники» разработчиков, в которых мы будем делиться опытом и освещать некоторые интересные результаты проводимых нами экспериментов. Это наша дебютная статья по проекту «Pathfinder 3D» — ассету для игрового движка Unity, который позволяет производить поиск пути в трёхмерном пространстве. В ней мы расскажем о пути от зарождения идеи до полноценного продукта и о некоторых проблемах, с которыми мы встретились. Данный материал будет полезен для людей, которые хотят начать свой проект и поддерживать его в дальнейшем, а также для желающих реализовать поиск пути в пространстве.
Читать дальше →
Total votes 21: ↑20 and ↓1 +19
Views 3.9K
Comments 4

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

Game development *Algorithms *Games and game consoles
Translation

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

Поиск пути


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

Для выполнения своей работы pathfinder использует алгоритм под названием A* (произносится «A star»). Простой пример поиска пути при помощи A* показан на видео: biter хочет найти путь в обход скал. Функция поиска пути начинает исследовать карту вокруг biter-а (исследование показано белыми точками). Сначала она пытается пойти напрямик к цели, но как только достигает скал, «разливается» в обе стороны, пытаясь найти позицию из которой снова можно будет двигаться к цели.
Total votes 58: ↑57 and ↓1 +56
Views 20K
Comments 29

Унификация поиска пути вместо различной логики ИИ

Programming *Game development *Unity3D *
Sandbox

ИИ нужно бегать по разным навигационным картам, каждая из которых требует свои входные и выходные данные, но прописывать дополнительную логику не хочется? Отлично, в этом вопросе нам поможет унификация поиска пути!

Объяснение и реализация
Total votes 9: ↑8 and ↓1 +7
Views 1.5K
Comments 2

Добавляем ботов в мультиплеерный шутер на Unity

Lightmap corporate blog Game development *Unity3D *Game design *Artificial Intelligence

С ростом проекта в него приходит постоянно приходит новая аудитория: как матерые игроки, так и новички в жанре. Закинуть всех в один матч можно, но первым будет скучно, а вторым — сложно. В итоге всех можно потерять уже на старте.

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

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

Читать далее
Total votes 47: ↑46 and ↓1 +45
Views 5.2K
Comments 2