Представим, что нам необходимо попасть из точки A в точку B. Прямой путь между этими двумя точками разделён стеной, как показано на рисунке 1.

Для упрощения области поиска пути, её необходимо разделить на сетку с квадратными ячейками (смотри рисунок 2). Это позволит выразить область поиска пути через двумерный массив, каждый элемент которого будет представлять одну из клеток получившейся сетки. Одним из значений каждой ячейки массива будет проходимость соответствующей ей клетки (проходима или непроходима).

Для нахождения пути необходимо определить, какие именно клетки нужны для перемещения из точки A в точку B. Как только путь будет найден, можно начинать перемещение из центра клетки A в центр следующей клетки пути, до тех пор, пока не будет достигнута конечная точка B. Замечание: Сетка не обязательно строится из квадратных ячеек. Она может быть построена из прямоугольных ячеек, из шестиугольных ячеек, из треугольных ячеек, или из любых других ячеек. При этом центральные точки ячеек называют вершинами. Вершины могут располагаться как в центре, так и вдоль граней, или ещё где-нибудь.

Поиск пути начинаем со следующих шагов:

1. Добавляем стартовую клетку, где находится точка A, в «открытый список». В данный момент в этом списке будет находиться только одна ячейка, но позже в него будут добавляться и другие ячейки. Клетки, находящиеся в открытом списке это клетки, которые необходимо проверить и решить, будут ли они являться частью искомого пути к конечной клетке.
2. Ищем проходимые клетки, граничащие со стартовой клеткой, игнорируя непроходимые клетки (со стенами, водой и прочим), и добавляем их в открытый список. Для каждой из этих клеток сохраняем клетку A как «родительскую».
3. Удаляем стартовую клетку A с открытого списка и добавляем её в «закрытый список» клеток, которые больше не нужно проверять.

После этих шагов должно получиться нечто похожее на то, что изображено на рисунке 3. На нём стартовая клетка выделена оранжевым цветом для отображения того, что она находится в закрытом списке. Все соседние клетки в данный момент находятся в открытом списке, – они выделены синим цветом. Каждая из этих клеток имеет указатель, направленный на родительскую клетку, которая в данном случае является стартовой клеткой A.

Далее необходимо выбрать одну клетку из находящихся в открытом списке клеток, и, практически, повторить вышеописанный процесс. Но следующая клетка из открытого списка, выбирается не случайно, а в зависимости от её величины F.

Величина F вычисляется по формуле 1:

F = G + H (1)

где

• G – энергия, затрачиваемая на передвижение из стартовой клетки A в текущую рассматриваемую клетку, следуя найденному пути к этой клетке;
• H – примерное количество энергии, затрачиваемое на передвижение от текущей клетки до целевой клетки B. Изначально эта величина равна предположительному значению, такому, что если бы мы шли напрямую, игнорируя препятствия (но исключив диагональные перемещения). В процессе поиска она корректируется в зависимости от встречающихся на пути преград.

Обычно, энергия, затрачиваемая на прохождение в соседнюю клетку по горизонтали, берётся равной 10 единицам, а по диагонали – 14 единицам. Для вычисления величины G текущей рассматриваемой клетки, необходимо величину G её родительской клетки сложить с 10 или 14 (в зависимости от диагонального или ортогонального расположения текущей клетки относительно родительской клетки). Величина H обычно вычисляется методом Манхэттена. Суть его заключается в том, чтобы сосчитать общее количество клеток, необходимых для достижения целевой клетки B, от текущей рассматриваемой клетки, причём игнорируя диагональные перемещения между клетками, а также любые препятствия. Затем полученное количество умножается на 10. Рассчитав величину F по формуле 1, для всех клеток в открытом списке, получим результат похожий на то, что изображено на рисунке 4.

Клетки, расположенные ортогонально к стартовой клетке, имеют значение G равное 10, а клетки, расположенные диагонально к стартовой клетке – G равное 14. Значение H равняется Манхэттенскому расстоянию от центра текущей клетки до центра целевой клетки B, умноженное на 10. Например, для клетки с индексами [2, 2], расстояние от её центра до центра целевой – 3 клетки (рисунок 5).

А для клеток с индексами [1, 0] и [3, 0], расстояние от их центра до центра целевой клетки – 6 клеток (рисунок 6).

Величина F для каждой клетки вычисляется по формуле 1, как сумма величин G и H. Для продолжения поиска кратчайшего пути выбирается ячейка, из открытого списка, с наименьшим значением F. И для этой клетки выполняются следующие действия (продолжение действий описанных выше):

1. Выбранную из открытого списка клетку удаляем из него и добавляем в закрытый список.
2. Добавляем в открытый список все соседние к ней клетки, если они еще не находятся в нём (при этом игнорируя непроходимые клетки и клетки, которые содержатся в закрытом списке). Предварительно указав, что текущая клетка является родительской для клеток, добавленных в открытый список, а также вычислив их значения G, H и F.
3. Если соседняя клетка уже находится в открытом списке, то сравниваем значение величин G у клетки в открытом списке и текущей проверяемой клетки. Если прежнее значение (в открытом списке) меньше нового, то ничего не делаем. В обратном случае, у клетки в открытом списке меняем значение G на новое, также меняем указатель на родителя, чтобы он указывал на текущую проверяемую клетку.

Рассмотрим описанные шаги. Сейчас в открытом списке находится 8 клеток, а стартовая клетка – в закрытом списке. Из открытого списка следующей клеткой для рассмотрения будет выбрана клетка с наименьшим значением F – это клетка с индексами [2, 2]. Смотри рисунок 7.

Вначале текущую клетку (с индексами [2, 2]) удаляем из открытого списка, и помещаем в закрытый список (поэтому на рисунке 7 она отмечена оранжевым цветом). Затем проверяем соседние клетки. Четыре из них, игнорируем, – это три непроходимые клетки стены и стартовая клетка, находящаяся в закрытом списке. Оставшиеся четыре клетки уже расположены в открытом списке, а значит необходимо сравнить их значения G со значением G таким, что если бы мы к ним дошли через текущую клетку. Значение G у клетки ниже текущей (с индексами [3, 2]) равно 14, а значение G, полученное при проходе через текущую клетку равно 20 (G = 10 у текущей клетки, и плюс 10 путь до клетки ниже текущей). Значение 14 меньше 20, поэтому значение G у клетки ниже текущей не нужно обновлять. У клетки слева внизу (с индексами [3, 1]) G = 10, а значение G, полученное при проходе через текущую клетку 24 (G = 10 у текущей клетки, и плюс 14 – путь от текущей до проверяемой клетки). 24 больше 10, значит обновлять значение G у этой клетки не нужно. Соответственно делаются проверки и для клетки выше текущей (с индексами [1, 2]), и для клетки слева вверху от текущей клетки (с индексами [1, 1]). После того, как все соседние клетки рассмотрены, можно двигаться далее. На данный момент в открытом списке находятся 7 клеток, две из которых имеют одинаковое наименьшее значение F равное 54. Какую клетку выбрать следующей текущей из этих двух клеток, для алгоритма не имеет значения, поэтому представим, что случайным образом выбрали клетку находящуюся справа внизу от стартовой клетки (с индексами [3, 2]), как показано на рисунке 8.

Проверяя клетки, соседние к текущей клетке, с индексами [2, 3] и [3, 3], игнорируем, так как они непроходимы. Клетку с индексами [2, 2] и стартовую клетку также игнорируем, – они находятся в закрытом списке. Клетку с индексами [4, 3] также игнорируем, по причине того, что к ней невозможно добраться без среза угла ближайшей стены. – Сначала необходимо перейти на клетку с индексами [4, 2], а потом уже переходить на клетку с индексами [4, 3]. (Правило запрещающее срезать углы у препятствий необязательно к выполнению, его применение зависит от расположения ваших вершин.) Клетка с индексами [3, 1] уже находится в открытом списке, поэтому сравниваем её значение F со значением F таким, что если бы мы пришли на неё через текущую клетку. Это значения 60 и 64, соответственно, а значит, данные проверяемой клетки не нужно обновлять. Клетки с индексами [4, 1] и [4, 2] добавляем в открытый список, предварительно вычислив их значения величин G, H и F, а также установив указатель на родительскую клетку (как проиллюстрировано на рисунке 8). Повторяем описанную выше методику поиска пути до тех пор, пока не добавим целевую клетку в открытый список. Следующая клетка в открытом списке с наименьшим значением F, равным 54, это клетка с индексами [1, 2]. Удаляем её из открытого списка, добавляем в закрытый список, и проверяем её соседей (при этом добавляем две клетки с индексами [0, 1] и [0, 2]). Итог операций проиллюстрирован на рисунке 9.

Сейчас в открытом списке находится две клетки с наименьшим значением F равным 60. Случайным образом выбираем клетку с индексами [3, 1]. Удаляем её из открытого списка, добавляем в закрытый список. Проверяем её соседей (добавляем в открытый список клетку с индексами [4, 0] и у клетки с индексами [4, 1], уже находящейся в открытом списке, обновляем значение F и меняем указатель на родителя, теперь он ссылается на текущую клетку, с индексами [3, 1]). Смотри рисунок 10.

Следующую из открытого списка обрабатываем клетку с индексами [2, 0]. Удаляем её из открытого списка и добавляем в закрытый список. При этом никакие из её соседних клеток не нуждаются в обновлении (смотри рисунок 11).

Далее обрабатываем клетку с индексами [1, 1]. Удаляем её из открытого списка, добавляем в закрытый список. При этом обновляем данные её соседней клетки с индексами [0, 1] и добавляем в открытый список клетку с индексами [0, 0]. Смотри рисунок 12.

Следующие клетки в открытом списке имеют наименьшее значение F равное 74. Случайным образом выбираем клетку с индексами [4, 2]. Удаляем её из открытого списка, добавляем в закрытый список. Проверяем её соседей – добавляем в открытый список клетку с индексами [4, 3]. Смотри рисунок 13.

Предположим, что следующей клеткой с наименьшим значением F выбрана клетка ближе к той, которую проверяли перед этим – клетка с индексами [4, 3]. Удаляем её из открытого списка, добавляем в закрытый список. Обрабатываем её соседние клетки (рисунок 14).

Далее, выбираем клетку с индексами [4, 4], удаляем её из открытого списка, добавляем в закрытый список. Обрабатываем её соседние клетки – добавляем три клетки в открытый список (клетки с индексами [3, 4], [3, 5] и [5, 4]) (рисунок 15).

Следующая клетка с наименьшим значением F это клетка с индексами [3, 5]. Выбираем её, удаляем из открытого списка, добавляем в закрытый список. Обрабатываем её соседние клетки, при этом в открытый список добавляются клетки с индексами [2, 4], [3, 6], [2, 6] и целевая клетка с индексами [2, 5]. Смотри рисунок 16.

Целевая клетка находится в открытом списке, а это значит, что был найден путь от стартовой до финишной клетки. Теперь следуя указателям на родителей можно пройти от финишной клетки до стартовой клетки, а сохранённый путь в обратном направлении – путь от стартовой до целевой клетки, это и будет найденный кратчайший путь (рисунок 17).

Пошаговое представление метода:

1. Добавить стартовую клетку в открытый список (при этом её значения G, H и F равны 0).
2. Повторять следующие шаги:
   • Ищем в открытом списке клетку с наименьшим значением величины F, делаем её текущей.
   • Удаляем текущую клетку из открытого списка и помещаем в закрытый список.
   • Для каждой из соседних, к текущей клетке, клеток:
     • Если клетка непроходима или находится в закрытом списке, игнорируем её.
     • Если клетка не в открытом списке, то добавляем её в открытый список, при этом рассчитываем для неё значения G, H и F, и также устанавливаем ссылку родителя на текущую клетку.
     • Если клетка находится в открытом списке, то сравниваем её значение G со значением G таким, что если бы к ней пришли через текущую клетку. Если сохранённое в проверяемой клетке значение G больше нового, то меняем её значение G на новое, пересчитываем её значение F и изменяем указатель на родителя так, чтобы она указывала на текущую клетку.
   • Останавливаемся, если:
     • В открытый список добавили целевую клетку (в этом случае путь найден).
     • Открытый список пуст (в этом случае к целевой клетке пути не существует).
3. Сохраняем путь, двигаясь назад от целевой точки, проходя по указателям на родителей до тех пор, пока не дойдём до стартовой клетки.

Источник: перейти

На GitHub: перейти