В строках 2 и 3 из кода выше, мы создаем пустые открытый и замкнутый массивы. Для поиска пути нам необходима начальная точка и цель назначения, куда нужно идти. S представляет собой объект, который представляет начальный узел. Мы устанавливаем s.g в 0, поскольку начальный узел не имеет родителей, так что стоимость (g) для его достижения равно 0 (строка 4). Далее, мы находим эвристику h для начального узла. (Помните, что эвристика является оценочной стоимостью от текущего узла до цели.) Затем мы сохраняем значение f, которое является суммой s.g и s.h, в начальном узле (строка 6). Поскольку s не имеет родителей, мы устанавливаем s.родитель в ноль. Далее, мы помещаем узел s в открытый массив (строка 8). Узел s является теперь первым и лишь узлом в открытом массиве.
В строке 9 мы устанавливаем переменную признакПоиска в true. Пока она остается в true, мы будем выполнять поиск A*. Когда мы определили, что мы нашли путь, что пути не существует, или что мы ищем слишком долго, мы устанавливаем признакПоиска в false.
В строке 11 мы берем узел из приоритетной ветви. Затем мы проверяем, является ли этот узел целью. Если да, мы достигли цели; тогда мы прекращаем поиск и строим путь (строки 12-14). Если это не цель, мы раскрываем узел. Раскрытие узла означает, что мы посещаем каждого соседа узла. В строке 16 мы находим g соседнего узла, m, которую мы искали в данный момент. Затем мы проверяем, посещался ли когда-либо этот узел. Если он еще не посещался, то мы входим в часть алгоритма в строках 18-23. Мы устанавливаем значение g в m; это f его родителя, n. Далее мы вычисляем и сохраняем эвристику и f в m. Наконец, мы устанавливаем свойство родителя на предыдущий узел, n. Если этот узел был посещен прежде и теперь имеет более низкий g, то мы входим в часть алгоритма в строках 25-31.
В этом месте я хочу сказать несколько больше о переменной g. Когда узел посещается в первый раз, он назначает g, основываясь на пути, необходимом, чтобы добраться до этого узла (как мы уже рассматривали)
Русская версия