Easy A * (звезда) Поиск пути

Сегодня мы рассмотрим алгоритм поиска пути A *, его работу и его реализацию в псевдокоде и реальном коде на Python 🐍.

Ищете только псевдокод или исходный код? Прокрутите вниз!

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

F = G + H

Одним из важных аспектов A * является f = g + h. Переменные f, g и h находятся в нашем классе Node и вычисляются каждый раз, когда мы создаем новый узел. Я быстро рассмотрю, что означают эти переменные.

• F - общая стоимость узла.
• G - расстояние между текущим узлом и начальным узлом.
• H - эвристически оцененное расстояние от текущего узла до конечного узла.

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

Потрясающие! Допустим, node(0) - наша начальная позиция, а node(19) - наша конечная позиция. Также предположим, что наш текущий узел находится в красном квадрате node(4).

G

G - расстояние между текущим узлом и начальным узлом.

Если мы посчитаем назад, то увидим, что node(4) находится на расстоянии 4 пробелов от нашего начального узла.

Мы также можем сказать, что G на 1 больше, чем наш родительский узел (node(3)). Так что в данном случае для node(4), currentNode.g = 4.

H

H - эвристически оцененное расстояние от текущего узла до конечного узла.

Итак, давайте посчитаем расстояние. Если мы посмотрим, то увидим, что если мы пройдем более 7 пробелов и 3 пробела, мы достигли конечного узла (node(19)).

Применим теорему Пифагора! a² + b² = c². После того, как мы применим это, мы увидим, что currentNode.h = 7² + 3². Или currentNode.h = 58.

Но разве нам не нужно применять квадратный корень к 58? Неа! Мы можем пропустить это вычисление на каждом узле и при этом получить тот же результат. Умно!

С помощью эвристики нам нужно убедиться, что мы действительно можем ее вычислить. Также очень важно, чтобы эвристика всегда занижала общий путь, так как завышение приведет к тому, что A * будет искать сквозные узлы, которые могут быть не «наилучшими» с точки зрения f значения.

F

F - общая стоимость узла.

Итак, давайте сложим h и g, чтобы получить общую стоимость нашего узла. currentNode.f = currentNode.g + currentNode.h. Или currentNode.f = 4+ 58. Или currentNode.f = 62.

Время использовать f = g + h

Хорошо, это было много работы. Теперь, после всей этой работы, для чего я собираюсь использовать это значение f?

С этим новым значением f мы можем посмотреть на все наши узлы и сказать: «Эй, это лучший узел, который я могу выбрать, чтобы двигаться вперед прямо сейчас?». Вместо того, чтобы перебирать все узлы, мы можем выбрать те, которые имеют наибольшие шансы на достижение нашей цели.

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

Алгоритм Дейкстры

Итак, взглянув на алгоритм Дейкстры, мы видим, что он просто продолжает поиск. Он не знает, какой узел «лучший», поэтому рассчитывает пути для всех.

Алгоритм A *

С помощью A * мы видим, что как только мы преодолеем препятствие, алгоритм отдает приоритет узлу с наименьшим f и «наилучшим» шансом достичь конца.

Шаги метода A - от Патрика Лестера

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

1. Добавьте начальный квадрат (или узел) в открытый список.

2. Повторите следующее:

A) Найдите в открытом списке квадрат с наименьшей стоимостью F. Мы называем это текущим квадратом.

Б). Переключите его в закрытый список.

C) Для каждого из 8 квадратов, примыкающих к текущему квадрату…

• Если по нему нельзя ходить или он находится в закрытом списке, игнорируйте его. В противном случае сделайте следующее.
• Если его нет в открытом списке, добавьте его в открытый список. Сделайте текущий квадрат родительским для этого квадрата. Запишите стоимость квадрата F, G и H.
• Если он уже есть в открытом списке, проверьте, лучше ли этот путь к этому квадрату, используя стоимость G в качестве меры. Более низкая стоимость G означает, что это лучший путь. Если это так, измените родительский элемент квадрата на текущий квадрат и пересчитайте оценки G и F. Если вы сохраняете свой открытый список, отсортированный по шкале F, возможно, вам придется пересчитать список, чтобы учесть это изменение.

D) Остановитесь, когда вы:

• Добавьте целевой квадрат в закрытый список, и в этом случае путь найден, или
• Не удалось найти целевой квадрат, и открытый список пуст. В этом случае пути нет.

3. Сохраните путь. Двигаясь назад от целевого квадрата, переходите от каждого квадрата к его родительскому квадрату, пока не дойдете до начального квадрата. Это твой путь.

Псевдокод

Следуя приведенному ниже примеру, вы сможете реализовать A * на любом языке.

// A* (star) Pathfinding
// Initialize both open and closed list
let the openList equal empty list of nodes
let the closedList equal empty list of nodes
// Add the start node
put the startNode on the openList (leave it's f at zero)
// Loop until you find the end
while the openList is not empty
    // Get the current node
    let the currentNode equal the node with the least f value
    remove the currentNode from the openList
    add the currentNode to the closedList
    // Found the goal
    if currentNode is the goal
        Congratz! You've found the end! Backtrack to get path
    // Generate children
    let the children of the currentNode equal the adjacent nodes
    
    for each child in the children
        // Child is on the closedList
        if child is in the closedList
            continue to beginning of for loop
        // Create the f, g, and h values
        child.g = currentNode.g + distance between child and current
        child.h = distance from child to end
        child.f = child.g + child.h
        // Child is already in openList
        if child.position is in the openList's nodes positions
            if the child.g is higher than the openList node's g
                continue to beginning of for loop
        // Add the child to the openList
        add the child to the openList

Исходный код (на Python 🐍)

Не стесняйтесь использовать этот код в своих собственных проектах.

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

Ресурсы

Ниже приведены несколько отличных веб-сайтов, на которые стоит обратить внимание. Я особенно рекомендую A * Pathfinding для начинающих.