Определение пути (часть I): общий алгоритм поиска

• Эта публикация - перевод статьи. Ее автор - Gabriel Gambetta. Оригинал доступен по ссылке ниже:

  Pathfinding Demystified (Part I): Generic Search Algorithm

Вступление

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

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

Обратите внимание, что основное внимание уделяется поиску путей для игр; в отличие от более академического подхода, мы пропустим алгоритмы поиска, такие как глубина-первая или ширина-первая. Вместо этого постараемся перейти от нуля к A* как можно быстрее.

Эта первая статья объясняет самые основные концепции поиска пути. Как только вы получите эти основные понятия, A* будет казаться вам на удивление простым.

Простая настройка

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

Простая сетка.

Первое, что мы делаем, – это представляем среду в виде графика. Я не буду вдаваться в детали того, что такое граф (набор пузырьков, соединенных стрелками). Пузыри называются «узлами», а стрелки называются «ребрами».

Каждый узел представляет «состояние», в котором может находиться ваш персонаж. В этом случае состояние вашего персонажа - это его позиция, поэтому мы создаем один узел для каждого квадрата сетки:

Узлы, представляющие квадраты сетки.

Теперь давайте добавим края. Они представляют, какие состояния вы можете «достичь» из любого другого данного состояния; в этом случае вы можете пройти от любого квадрата до соседнего квадрата, кроме заблокированных:

Дуги, представляющие действительные шаги между квадратами сетки.

Если вы можете получить от A до B, мы говорим B является «смежным» к А.

Обратите внимание, что края являются направленными; нам нужно как ребро из А в В, и край от B к A. Это может выглядеть излишним, но это не так, когда вы рассматриваете более сложные «состояния». Например, вы можете упасть с крыши на пол, но вы не можете спрыгнуть с пола на крышу. Вы можете перейти от «живого» к «мертвому», но не наоборот. И так далее.

Пример

Скажем, мы хотим перейти от А до Т. Мы начинаем в А. Мы можем сделать одну из двух вещей точно: пройти к B или дойти до F.

Предположим, что мы идем к B. Теперь мы можем сделать два действия: вернуться к А, или ходить C. Мы помним, что мы уже были в А, и мы рассмотрели наши варианты там, поэтому бессмысленно делать это снова (иначе мы могли бы потратить весь день на A → B → A → B …). Таким образом, мы идем в C.

Теперь на С нам некуда идти. Возвращаться к B – бессмысленно. Так что это тупик. Выбор B, когда мы были в A, не был хорошей идеей; может нам стоит попробовать F вместо этого?

Мы просто повторять этот процесс, пока мы не окажемся в T. В этот момент мы просто восстанавливаем путь из А, повторяя наши шаги. Мы в T ; как ты сюда попал? О ? Таким образом, в конце пути является O → Т. Как мы добрались до O? И так далее.

Имейте в виду, что мы вообще не двигались; все это было мысленным упражнением. Мы все еще стоим на А, и мы вообще не будем двигаться, пока не выясним весь путь. Когда я говорю «переехать в B», я на самом деле говорю «представьте, что мы переехали в B».

Общий алгоритм

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

Этот раздел также очень прост.

Давайте попробуем формализовать приведенный выше пример в немного псевдокода.

Нам нужно отслеживать узлы, которые мы знаем, как добраться от начального узла. В начале это только начальный узел, но по мере того, как мы «исследуем» сетку, мы выясним, как добраться до других узлов. Давайте назовем этот список reachable:

reachable = [start_node]

Нам также необходимо отслеживать узлы, которые мы уже рассмотрели, поэтому мы не рассматриваем их снова. Давайте назовем это explored:

explored = []

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

Звучит неутешительно просто? Это. Но это все, что нужно сделать. Давайте напишем это шаг за шагом в псевдокоде.

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

while reachable is not empty:

Мы выбираем один из узлов, которые знаем, как добраться, и еще не исследовали:

node = choose_node(reachable)

Если мы только что выяснили, как добраться до целевого узла, мы закончили! Нам просто нужно построить путь, следуя ссылкам previous на начальный узел:

if node == goal_node: path = [] while node != None: path.add(node) node = node.previous

return path

Нет смысла рассматривать узел более одного раза, поэтому мы отслеживаем:

reachable.remove(node) explored.add(node)

Мы выясним, какие узлы мы можем достичь отсюда. Мы начнем со списка узлов, смежных с этим, и удалим те, которые мы уже исследовали:

new_reachable = get_adjacent_nodes(node) - explored

Мы берем каждый из них:

for adjacent in new_reachable:

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

if adjacent not in reachable: adjacent.previous = node # Remember how we got there. reachable.add(adjacent)

Поиск узла цели является одним из способов выхода из цикла. Другой случай, когда reachable становится пустым: если у нас заканчиваются узлы для проверки, и мы ни разу не достигли целевого узла, это означает, что нет пути от начального узла к целевому узлу:

return None

Вот и все. Вот и все, с кодом для построения пути, выделенным в отдельный метод:

    function find_path (start_node, end_node):
        reachable = [start_node]
        explored = []
    
        while reachable is not empty:
            # Choose some node we know how to reach.
            node = choose_node(reachable)
    
            # If we just got to the goal node, build and return the path.
            if node == goal_node:
                return build_path(goal_node)
    
            # Don't repeat ourselves.
            reachable.remove(node)
            explored.add(node)
    
            # Where can we get from here?
            new_reachable = get_adjacent_nodes(node) - explored
            for adjacent in new_reachable:
                if adjacent not in reachable
                    adjacent.previous = node  # Remember how we got there.
                    reachable.add(adjacent)
    
        # If we get here, no path was found :(
        return None

Вот функция, которая строит путь по previous ссылкам обратно на начальный узел:

    function build_path (to_node):
        path = []
        while to_node != None:
            path.add(to_node)
            to_node = to_node.previous
        return path

Это –  псевдокод каждого алгоритма поиска пути, включая A*.

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

Живое демо

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

Демо см. здесь: https://gabrielgambetta.com/generic-search.html

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

Вывод

Алгоритм, представленный выше, является общим алгоритмом для каждого алгоритма поиска пути.

Итак... вы выяснили, что отличает каждый алгоритм от других - почему A* – это A* ?

Вот подсказка: если вы запустите демонстрационный поиск выше много раз, вы увидите, что алгоритм не всегда находит один и тот же путь. Он находит какой-то путь, не обязательно самый короткий путь. Почему?