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

Итак, это был поиск в ширину. В играх жанра 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 при каждом поиске мала, возможно, стоит лучше использользовать хэш-таблицу.