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

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



Как это реализовать?

Для нахождения кратчайшего пути между двумя точками часто используются алгоритмы поиска на графах, например поиск A*. Можно использовать его для каждого врага, чтобы находить путь к цели. Существует множество разных алгоритмов поиска на графах, которые можно использовать в играх такого жанра. Вот классические примеры:

1. Одна начальная и одна конечная точки:
   • Поиск по первому наилучшему совпадению
   • A* — широко используется в играх
2. Одна начальная и все конечные точки или все начальные, одна конечная точки:
   • Поиск в ширину — рёбра без весов
   • Алгоритм Дейкстры — добавляет рёбрам веса
   • Алгоритм Беллмана-Форда — имеет поддержку отрицательных весов
3. Все начальные и все конечные точки:
   • Алгоритм Флойда-Уоршелла
   • Алгоритм Джонсона

В играх наподобие Desktop Tower Defense есть множество позиций врагов (начальных точек) и одна конечная точка для них всех. Поэтому они находятся в категории все начальные и одна конечная точки. Вместо выполнения A* для каждого врага, можно выполнить алгоритм один раз, и он вычислит путь для всех врагов. Более того, он вычислит кратчайший путь из любого места, поэтому когда враги обходят друг друга или создаются новые враги их пути уже будут вычислены.

Давайте изучим алгоритм поиска в ширину, который иногда называют «заливкой» (вариация FIFO). Хотя поиск по графам работает для любого графа с узлами и рёбрами, в своих примерах я использую сетку квадратов. Сетки — это особый случай графов. Каждая клетка сетки является узлом графа, а границы между клетками сетки — рёбрами графа. Я рассматривают графы без сеток в другой статье.

Поиск в ширину начинается с одного узла и последовательно проходит по всем соседним. Ключевым понятием здесь является «граница» — рубеж между исследованными и неисследованными областями. Граница расширяется наружу от исходного узла, пока не исследует граф целиком.

Очередь frontier — это граница: список/массив узлов графа (клеток сетки), которые нужно проанализировать. В начале в нём содержится только один элемент, узел start. Флаг visited каждого узла позволяет отслеживать, проверяли ли мы его. В начале он для каждого узла кроме start имеет значение False. Потяните ползунок, чтобы понаблюдать за расширением границы:


Как работает алгоритм? На каждом шаге берётся один элемент из frontier и называется current. Затем выполняется поиск каждого из соседей current, называемых next. Если они не были посещены (visited) ранее, то добавляются в очередь frontier. Вот пример кода на Python:

frontier = Queue()
frontier.put(start)
visited = {}
visited[start] = True

while not frontier.empty():
   current = frontier.get()
   for next in graph.neighbors(current):
      if next not in visited:
         frontier.put(next)
         visited[next] = True

Ознакомившись с кодом, попробуйте пошагово изучить анимацию выше. Обратите внимание на очередь frontier, узел current и на множество узлов next. На каждом этапе элемент границы становится текущим узлом, помечаются соседи, и все непосещённые соседи добавляются в границу. Некоторые соседи уже были посещены ранее, поэтому они не добавляются в границу.

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

1. Помечаю все узлы, которых можно достичь. Это полезно, если карта соединена не полностью, и вы хотите знать, каких точек можно достичь. Именно это мы и сделали выше с помощью поля visited.
2. Нахожу пути от одного узла до всех остальных, или из всех узлов к одному. Именно этот способ я использовал для анимированного демо в начале статьи.
3. Измеряю расстояния от одного узла до всех остальных. Это полезно, чтобы знать, что находится в пределах расстояния ходьбы монстра.

Если вы генерируете пути, то нужно знать, в каком направлении двигаться из каждого узла. При посещении соседа надо помнить, откуда вы пришли. Давайте переименуем таблицу visited в came_from и используем её для хранения предыдущего местоположения:

frontier = Queue()
frontier.put(start)
came_from = {}
came_from[start] = None

while not frontier.empty():
   current = frontier.get()
   for next in graph.neighbors(current):
      if next not in came_from:
         frontier.put(next)
         came_from[next] = current

Давайте посмотрим, как это выглядит:



Если вам нужны расстояния, то можно начать со счётчика, значение которого равно 0 в начальном узле, и увеличивать его при каждом посещении соседа. Давайте переименуем таблицу visited в distance и используем её для хранения счётчика:

frontier = Queue()
frontier.put(start)
distance = {}
distance[start] = 0

while not frontier.empty():
   current = frontier.get()
   for next in graph.neighbors(current):
      if next not in distance:
         frontier.put(next)
         distance[next] = 1 + distance[current]

Давайте посмотрим, что у нас получилось:



Можно оставить обе переменные, если вам нужно вычислять и пути, и расстояния.

Итак, это был поиск в ширину. В играх жанра Tower Defense я использовал его для нахождения путей из всех точек в нужную точку вместо того, чтобы последовательно применять A* для отдельного поиска пути каждого врага. Я использовал его для поиска всех точек в пределах расстояния ходьбы монстра. Я также применял его для процедурного генерирования карт. В Minecraft он используется для отсечения области видимости. Этот алгоритм стоит знать.

Следующие шаги:

• У меня есть заметки по реализации с кодом на Python и C++.
• Если вам нужно пределять пути из одной точки, а не в одну точку, то переверните указатели came_from при проходе по путям.
• Если вам нужны пути к одной из нескольких точек, а не в одну точку, можно добавить в графы рёбра из каждой конечной точки в дополнительный конечный узел. Дополнительный узел не будет виден на сетке, но в графе он будет представлять конечную точку.
• Ранний выход: если вы ищете путь в/из одной точки, то можно прервать поиск сразу после того, как эта точка найдена. Я объясняю это в статье про A*.
• Рёбра с весами: если вам нужно использовать разную стоимость прохождения точек, то поиск в ширину превращается в алгоритм Дейкстры. Я описываю это в статье про A*.
• Эвристический подход: если добавить способ направления поиска в сторону цели, то поиск в ширину превращается в поиск по первому наилучшему совпадению. Подробнее об этом в статье про A*.
• Если начать с поиска в ширину и добавить ранний выход, рёбра с весами и эвристический подход, то получится A*. Как можно догадаться, я описываю этот алгоритм в статье про A*.

Реализация

Внутреннее состояние

В этой статье используется внешнее состояние множеств visited/came_from/distance и хэш-таблиц. Можно также использовать внутреннее состояние, при котором данные хранятся внутри структуры данных узлов графа. Зачем использовать внешние, а не внутренние данные? Хотя внутренние данные чуть быстрее (в реализации не используется хэш-таблица), внешние «чище», потому что не изменяют структуру данных графа при поиске. Кроме того, они поддерживают несколько одновременных операций поиска, или многопоточных, или реализуемых через корутины. Вот пример узла с внутренним флагом visited:

class Node:
    def __init__(self, name):
        self.visited = False
        self.name = name
        self._neighbors = []

    def neighbors(self):
        return self._neighbors

А вот пример графа:

A = Node("A")
B = Node("B")
C = Node("C")
D = Node("D")
E = Node("E")
A._neighbors = [B]
B._neighbors = [A, C]
C._neighbors = [D]
D._neighbors = [E]
E._neighbors = []
start = A

Если используется внутреннее состояние, то для повторного выполнения алгоритма нужно флагу visited снова установить значение False. Мы можем сделать это перед выполнением алгоритма:

ALL_NODES = [A, B, C, D, E]
      
frontier = Queue()
frontier.put(start)
for node in ALL_NODES:
    node.visited = False
start.visited = True

while not frontier.empty():
    current = frontier.get()
    callback(current)
    for next in current.neighbors():
        if not next.visited:
            next.visited = True
            frontier.put(next)

Скачать пример программы.

Или же мы можем установить значение после выполнения алгоритма, сохраняя список всех посещённых узлов:

frontier = Queue()
frontier.put(start)
start.visited = True
visited_nodes = [start]

while not frontier.empty():
    current = frontier.get()
    for next in current.neighbors():
        if not next.visited:
            next.visited = True
            visited_nodes.append(next)
            frontier.put(next)

for node in visited_nodes:
    node.visited = False

Скачать пример программы.

Как выбрать тот или иной подход? На самом деле это не очень важно, потому что мы посещаем все узлы. Если посещаются все узлы, то первый подход немного быстрее. Однако если вы используете ранний выход, то все узлы не посещаются, и тогда второй подход будет гораздо быстрее. Первый способ каждый раз проходит через все узлы. Второй способ проходит только через узлы, которые были посещены.

Идентификаторы узлов

(Примечание: в большинстве случаев эта оптимизация не понадобится.) Чтобы подход с хэш-таблицей работал, узлы должны быть хэшируемыми. Или же можно дать каждому узлу целочисленный идентификатор. После этого можно использовать битовый массив для хранения visited и обычный массив int для хранения distance и came_from.

Если вы пишете код на C или C++, то можно оставить массивы distance и came_from неинициализированными (потенциально это большое преимущество!). Потребуется только инициализировать битовый массив, сжимающий 64 идентификатора в один (long) int. Значение в массиве distance или came_from инициализируется, только если бит установлен. Можно или поместить массивы distance/came_from в стек, если в нём достаточно места, или использовать статически размещаемые массивы, не инициализируемые повторно после каждого поиска. Аккуратно взвешивайте затраты на инициализацию битового массива visited и затраты на использование хэш-таблицы. Если часть узлов visited при каждом поиске мала, возможно, стоит лучше использользовать хэш-таблицу.