Алгоритм поиска пути в The Binding of Isaac

Флориан Гимсл понемногу рассказывает в своих видеодневниках о том, как он подходил к созданию разных игровых аспектов The Binding of Isaac. Истории получаются довольно интересные и позволяют узнать о том, как и почему работают многие вещи в этом культовом рогалике. Сегодня мы поговорим про алгоритм поиска пути.

Каждая комната в игре разбита на сетку из логических переменных. Если блок занят непроходимым препятствием, то это единица. В ином случае — нули. Это помогает ИИ вычислить путь. Далее, позиции игрока присваивается цифра 100, а блокам рядом с ним — значения поменьше. Чем дальше, тем ниже будет цифра.

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

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

Небольшие доработки все же были приняты: если противник «видит» игрока (между ними нет препятствий), то алгоритм просто не применяется, враг идет по прямой линии. Также противники (особенно мухи) стараются отходить друг от друга, чтобы не мешаться. Это увеличивает покрытое ими пространство и досаждает игроку.

Вспомните зомби. Они порой пытаются окружить игрока неспроста: если один из монстров блокирует путь в узком коридоре, то другие сразу ищут обходной. Более наглядно ознакомиться с работой алгоритма поиска пути в The Binding of Isaac вы можете ролике Флориана.