algorithm
A * Алгоритм поиска пути

Вступление

Простой пример A * Pathfinding: лабиринт без препятствий

Предположим, у нас есть следующая сетка 4 на 4:

Предположим, что это лабиринт . Однако никаких препятствий нет. У нас есть только начальная точка (зеленый квадрат) и конечная точка (красный квадрат). Предположим также, что для перехода от зеленого к красному мы не можем двигаться по диагонали. Итак, начиная с зеленой площади, давайте посмотрим, на какие квадраты мы можем переместиться, и выделим их синим цветом:

Чтобы выбрать квадрат для перехода к следующему, нам нужно учитывать 2 эвристики:

1. Значение «g» - это то, как далеко этот узел находится от зеленого квадрата.
2. Значение «h» - это то, как далеко этот узел находится от красного квадрата.
3. Значение «f» - это сумма значения «g» и «h». Это окончательное число, которое указывает нам, к какому узлу нужно перейти.

Чтобы вычислить эти эвристики, это формула, которую мы будем использовать: distance = abs(from.x - to.x) + abs(from.y - to.y)

Это называется формулой «Манхэттен Дистанция» .

Вычислим значение «g» для синего квадрата сразу слева от зеленого квадрата: abs(3 - 2) + abs(2 - 2) = 1

Большой! У нас есть значение: 1. Теперь давайте попробуем вычислить значение «h»: abs(2 - 0) + abs(2 - 0) = 4

Отлично. Теперь давайте получим значение «f»: 1 + 4 = 5

Итак, окончательное значение для этого узла равно «5».

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

Мы вычислили значения g, h и f для всех синих узлов. Теперь, что мы выбираем?

Какое бы ни было наименьшее значение f.

Однако в этом случае мы имеем 2 узла с одинаковым значением f, 5. Как мы можем выбрать между ними?

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

Один из узлов с значением f 5 принимает нас в направлении «Вниз», а другой берет нас «влево». Поскольку Down имеет более высокий приоритет, чем Left, мы выбираем квадрат, который берет нас «вниз».

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

Хорошо, теперь давайте рассчитаем ту же эвристику для узлов вокруг голубого узла:

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

Давайте вычислим эвристику для единственного соседа, который имеет голубой узел:

Хорошо, поскольку мы будем следовать той же схеме, которую мы придерживаемся:

Еще раз, давайте вычислим эвристику для соседа узла:

Перейдем туда:

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