Программирование стратегических игр с DirectX 9.0

         

Основы A*


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

Узел — Позиция на карте.

Открытый список — Список узлов в которые может переместиться игрок и которые являются смежными с закрытыми узлами.

Закрытый список — Спиок узлов, в которые может переместиться игрок и которые уже были пройдены им.

Чтобы понять, как эти термины применяются, взгляните на рис. 12.6.


Рис. 12.6. Терминология в алгоритме A*

На рис 12.6 изображены узлы, составляющие карту. Фактически, узлом является каждый квадрат карты. Я понимаю, что термин «узел» может звучать странно, но он подходит больше, чем «квадрат» или «клетка». Дело в том, что алгоритм A* может применяться и для тех карт, где форма блоков отличается от квадрата.

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

Узлы, соседствующие с единственным узлом из закрытого списка будут помещены в открытый список. В результате у вас будет один узел в закрытом списке и восемь узлов в открытом. Это показано на рис. 12.7.


Рис. 12.7. Добавление узлов в открытый список

На рис. 12.7 изображены восемь узлов входящих в открытый список и один узел, входящий в закрытый список. Узлы, входящие в открытый список очень просто определить по нарисованным в них стрелкам. Эти стрелки показывают направление перемещения из того закрытого узла, к которому относятся данные открытые узлы. Закрытый узел в этом случае называется родительским узлом каждого из открытых узлов.



Содержание раздела