Как стать автором
Обновить
  • по релевантности
  • по времени
  • по рейтингу

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

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

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


Всего голосов 23: ↑22 и ↓1 +21
Просмотры 17K
Комментарии 3

Введение в алгоритм A*

Разработка игр *Алгоритмы *
Перевод
При разработке игр нам часто нужно находить пути из одной точки в другую. Мы не просто стремимся найти кратчайшее расстояние, нам также нужно учесть и длительность движения. Передвигайте звёздочку (начальную точку) и крестик (конечную точку), чтобы увидеть кратчайший путь. [Прим. пер.: в статьях этого автора всегда много интерактивных вставок, рекомендую сходить в оригинал статьи.]


Для поиска этого пути можно использовать алгоритм поиска по графу, который применим, если карта представляет собой граф. A* часто используется в качестве алгоритма поиска по графу. Поиск в ширину — это простейший из алгоритмов поиска по графу, поэтому давайте начнём с него и постепенно перейдём к A*.
Всего голосов 70: ↑69 и ↓1 +68
Просмотры 125K
Комментарии 20

Реализация алгоритма A*

Разработка игр *Алгоритмы *
Перевод


Эта статья является продолжением моего введения в алгоритм A*. В ней я показал, как реализуются поиск в ширину, алгоритм Дейкстры, жадный поиск по наилучшему первому совпадению и A*. Я стремился как можно больше упростить объяснение.

Поиск по графам — это семейство схожих алгоритмов. Существует множество вариаций алгоритов и их реализаций. Относитесь к коду этой статьи как к отправной точке, а не окончательной версии алгоритма, подходящей ко всем ситуациям.
Читать дальше →
Всего голосов 29: ↑28 и ↓1 +27
Просмотры 58K
Комментарии 4

Генератор подземелий на основе узлов графа

Разработка игр *Алгоритмы *Unity *
Перевод
image

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

Введение


Алгоритм был написан как часть работы на получение степени бакалавра и основан на статье Ma et al (2014). Целью работы было ускорение алгоритма и дополнение его новыми функциями. Я вполне доволен результатом, потому что мы сделали алгоритм достаточно быстрым, чтобы использовать его во время выполнения игры. После завершения бакалаврской работы мы решили превратить её в статью и отправить на конференцию Game-ON 2018.

Алгоритм


Для создания уровня игры алгоритм получает в качестве входных данных набор полигональных строительных блоков и граф связности уровня (топологию уровня). Узлы графа обозначают комнаты, а рёбра определяют связи между ними. Цель алгоритма — назначить каждому узлу графа форму и расположение комнаты таким образом, чтобы никакие две формы комнат не пересекались, и каждая пара соседних комнат могла соединяться дверьми.
Всего голосов 51: ↑51 и ↓0 +51
Просмотры 25K
Комментарии 9

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

Разработка игр *Алгоритмы *C# *Unity *
Перевод

Поле


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

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

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


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

Игра жанра Tower Defense


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

Оптимизация поиска в ширину: как обработать граф с 10 миллиардами состояний

Поисковые технологии *Программирование *Алгоритмы *Игры и игровые приставки
Перевод
image

Пару месяцев назад мне наконец пришлось признать, что я недостаточно умён, чтобы пройти некоторые уровни головоломки Snakebird. Единственным способом вернуть себе часть самоуважения было написание солвера. Так я мог бы притвориться, что создать программу для решения головоломки — это почти то же самое, что и решить её самому. Код получившейся программы на C++ выложен на Github. Основная часть рассматриваемого в статье кода реализована в search.h и compress.h. В этом посте я в основном буду рассказывать об оптимизации поиска в ширину, который бы потребовал 50-100 ГБ памяти, чтобы он уместился в 4 ГБ.

Позже я напишу ещё один пост, в котором будет описана специфика игры. В этом посте вам нужно знать, что мне не удалось найти никаких хороших альтернатив грубому перебору (brute force), потому что ни один из привычных трюков не сработал. В игре множество состояний, потому что есть куча подвижных или толкаемых объектов, при этом важна форма некоторых из них, которая может меняться со временем. Не было никакой пригодной консервативной эвристики для алгоритмов наподобие A*, позволяющих сузить пространство поиска. Граф поиска был ориентированным и заданным неявно, поэтому одновременный поиск в прямом и обратном направлении оказался невозможным. Единственный ход мог изменить состояние множеством несвязанных друг с другом способов, поэтому не могло пригодиться ничего наподобие хеширования Зобриста.

Приблизительные подсчёты показали, что в самой большой головоломке после устранения всех симметричных положений будет порядка 10 миллиардов состояний. Даже после упаковки описания состояний с максимальной плотностью размер состояния составлял 8-10 байт. При 100 ГБ памяти задача оказалась бы тривиальной, но не для моей домашней машины с 16 ГБ памяти. А поскольку Chrome нужно из них 12 ГБ, мой настоящий запас памяти ближе к 4 ГБ. Всё, что будет превышать этот объём, придётся сохранять на диск (старый и ржавый винчестер).
Читать дальше →
Всего голосов 27: ↑26 и ↓1 +25
Просмотры 8.6K
Комментарии 1

Разбор задачи с собеседования Google: поиск соотношения

Занимательные задачки Программирование *Алгоритмы *
Перевод


Добро пожаловать в очередную из серии статей с разбором задачек, которые я задавал на собеседованиях в Google, прежде чем их запретили после утечки. С тех пор я оставил работу инженера-программиста в Google и перешёл на должность менеджера по разработке в Reddit, но у меня всё ещё осталось несколько замечательных тем. К настоящему моменту мы разобрали динамическое программирование, возведение матриц в степень и синонимичность запросов. На этот раз совершенно новый вопрос.
Читать дальше →
Всего голосов 47: ↑41 и ↓6 +35
Просмотры 38K
Комментарии 73

Реалистичный боевой ИИ для 2D-игры

Разработка игр *Искусственный интеллект
Перевод
image

Хотя Close Quarters преимущественно является многопользовательской игрой, в ней всё равно должны присутствовать сложные ИИ-боты, чтобы игроки продолжали играть при плохом Интернет-соединении или отсутствии других онлайн-игроков. Кроме того, боты играют важную вспомогательную роль в некоторых режимах игры. Поэтому они должны вести себя правдоподобно и демонстрировать набор сложных поведений, в том числе использование укрытий, применение предметов в подходящее время, обход с флангов, бросание гранат и убегание от них.

Окружение и ограничения


Игровое окружение состоит из полигонов. Большинство полигонов блокирует движение, область видимости и стрельбу, однако есть и «низкие» полигоны, только блокирующие движение. Окружение плотно заставлено препятствиями и укрытиями.

ИИ тоже ограничен несколькими техническими факторами. Самый важный из них: сервер, на котором выполняются боты, когда онлайн находится мало игроков, должен быстро работать на недорогом VPS как минимум при десяти ботах. Кроме того, нагрузка на ЦП должна оставаться достаточно низкой, чтобы можно было выполнять несколько инстансов сервера на одном VPS без превышения лимита ЦП, и не при этом вызвать санкций со стороны поставщика услуг VPS.
Всего голосов 40: ↑40 и ↓0 +40
Просмотры 11K
Комментарии 2

Обход графа: поиск в глубину и поиск в ширину простыми словами на примере JavaScript

Разработка веб-сайтов *JavaScript *Программирование *.NET *
Перевод
Доброго времени суток.

Представляю вашему вниманию перевод статьи «Algorithms on Graphs: Let’s talk Depth-First Search (DFS) and Breadth-First Search (BFS)» автора Try Khov.

Что такое обход графа?


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

Двумя основными алгоритмами обхода графа являются поиск в глубину (Depth-First Search, DFS) и поиск в ширину (Breadth-First Search, BFS).

Несмотря на то, что оба алгоритма используются для обхода графа, они имеют некоторые отличия. Начнем с DFS.
Читать дальше →
Всего голосов 12: ↑11 и ↓1 +10
Просмотры 58K
Комментарии 1

Выпуск#40: ITренировка — актуальные вопросы и задачи от ведущих компаний

Блог компании Spice IT Recruitment Занимательные задачки Программирование *
Привет-привет! С вами (не)регулярная рубрика ITренировка. Соскучились? Мы тоже!



Вернёмся к вам на еженедельной основе осенью, а пока же ловите от нас подборку задачек с собеседований в норвежскую компанию Opera Software!
Рубрика выходит при поддержке рекрутингового агентства Spice IT.
Читать дальше →
Всего голосов 3: ↑3 и ↓0 +3
Просмотры 1.4K
Комментарии 1