Основы A*
Давайте познакомимся с терминами, которые используются при описании алгоритма A*.
Узел — Позиция на карте.
Открытый список — Список узлов в которые может переместиться игрок и которые являются смежными с закрытыми узлами.
Закрытый список — Спиок узлов, в которые может переместиться игрок и которые уже были пройдены им.
Чтобы понять, как эти термины применяются, взгляните на рис. 12.6.
Рис. 12.6. Терминология в алгоритме A*
На рис 12.6 изображены узлы, составляющие карту. Фактически, узлом является каждый квадрат карты. Я понимаю, что термин «узел» может звучать странно, но он подходит больше, чем «квадрат» или «клетка». Дело в том, что алгоритм A* может применяться и для тех карт, где форма блоков отличается от квадрата.
На карте как обычно отмечены начальная и конечная позиции. Помимо этого, начальная позиция обведена тонкой рамкой. Это показывает, что данный узел находится в закрытом списке. Поскольку начальная позиция всегда будет являться частью искомого пути, она автоматически включается в закрытый список пройденных узлов.
Узлы, соседствующие с единственным узлом из закрытого списка будут помещены в открытый список. В результате у вас будет один узел в закрытом списке и восемь узлов в открытом. Это показано на рис. 12.7.
Рис. 12.7. Добавление узлов в открытый список
На рис. 12.7 изображены восемь узлов входящих в открытый список и один узел, входящий в закрытый список. Узлы, входящие в открытый список очень просто определить по нарисованным в них стрелкам. Эти стрелки показывают направление перемещения из того закрытого узла, к которому относятся данные открытые узлы. Закрытый узел в этом случае называется родительским узлом каждого из открытых узлов.
