| netlib.narod.ru | < Назад | Оглавление | Далее > |
Существует множество доступных алгоритмов поиска пути, но моим личным фаворитом является алгоритм с названием A*. Это великолепный алгоритм, позволяющий находить путь обхода препятствий и определять наилучший путь на изменяющемся ландшафте. Это означает, что данный метод не просто найдет путь из точки А в точку В, но и что найденный путь из точки А в точку В будет наилучшим.
Чтобы помочь вам, я написал программу, показывающую алгоритм А* в действии. Загрузите проект D3D_PathFinding и запустите его, чтобы увидеть работу алгоритма А*. Если все выполнено правильно, вы увидите окно, похожее на изображенное на рис. 12.5.
Рис. 12.5. Окно программы D3D_PathFinding
Запустите программу и щелкните по расположенной на панели команд кнопке Go. В результате будет запущен алгоритм поиска пути. Как видно на рис. 12.5 программа ищет путь из начальной точки в конечную и отображает решение в виде стрелок. Вы можете загружать различные ландшафты, находящиеся в сопроводительных файлах, и смотреть, как алгоритм справляется с ними. Самое лучшее, что алгоритм A* всегда находит лучший путь с учетом имеющегося времени и ресурсов.
Как работает программа D3D_PathFinding? Не беспокойтесь; на этот раз я не буду сразу переходить к описанию исходного кода. Вместо этого я сначала приведу теоретическое описание работы алгоритма A*.
Давайте познакомимся с терминами, которые используются при описании алгоритма A*.
Узел — Позиция на карте.
Открытый список — Список узлов в которые может переместиться игрок и которые являются смежными с закрытыми узлами.
Закрытый список — Спиок узлов, в которые может переместиться игрок и которые уже были пройдены им.
Чтобы понять, как эти термины применяются, взгляните на рис. 12.6.
Рис. 12.6. Терминология в алгоритме A*
На рис 12.6 изображены узлы, составляющие карту. Фактически, узлом является каждый квадрат карты. Я понимаю, что термин «узел» может звучать странно, но он подходит больше, чем «квадрат» или «клетка». Дело в том, что алгоритм A* может применяться и для тех карт, где форма блоков отличается от квадрата.
На карте как обычно отмечены начальная и конечная позиции. Помимо этого, начальная позиция обведена тонкой рамкой. Это показывает, что данный узел находится в закрытом списке. Поскольку начальная позиция всегда будет являться частью искомого пути, она автоматически включается в закрытый список пройденных узлов.
Узлы, соседствующие с единственным узлом из закрытого списка будут помещены в открытый список. В результате у вас будет один узел в закрытом списке и восемь узлов в открытом. Это показано на рис. 12.7.
Рис. 12.7. Добавление узлов в открытый список
На рис. 12.7 изображены восемь узлов входящих в открытый список и один узел, входящий в закрытый список. Узлы, входящие в открытый список очень просто определить по нарисованным в них стрелкам. Эти стрелки показывают направление перемещения из того закрытого узла, к которому относятся данные открытые узлы. Закрытый узел в этом случае называется родительским узлом каждого из открытых узлов.
Вот вы и узнали о терминологии, применяемой в алгоритме А*, но как использовать сам алгоритм? Первое, что делает алгоритм А* — это добавление начального узла в закрытый список. Это делается потому, что начальный узел всегда будет первым узлом полученного пути. Сделав это вы должны найти все узлы, которые являются смежными с начальным и в которые может переместиться игрок. Если смежный узел доступен, он добавляется в открытый список. Так как в самом начале нет никаких открытых узлов, перед началом работы алгоритма открытый список пуст.
Итак, вот этапы поиска:
На рис. 12.7 я выполнил эти два шага и теперь у меня один узел в закрытом списке и восемь узлов в открытом. Что дальше?
В мире А* узлы не равны между собой. Одни из них лучше подходят для создания пути, чем другие. Чтобы выяснить, какой узел является самым лучшим, необходимо каждому узлу в закрытом и открытом списках назначить его стоимость. Как только всем узлам назначена стоимость, достаточно простой сортировки, чтобы выяснить какой узел является самым дешевым. Для вычисления стоимости узлов в алгоритме А* необходимы следующие значения:
Базовой стоимостью узла называется стоимость передвижения через данный узел. В простейшем случае базовая стоимость всех доступных узлов одна и та же. Однако, если вы хотите усложнить игру, можно назначить различным узлам различную стоимость, в зависимости от их типа ландшафта. Взгляните, например, на следующий список узлов с их стоимостью:
|
Таблица 12.1. Базовая стоимость узлов | |
| Тип узла | Стоимость |
| Трава | 1 |
| Грязь | 2 |
| Песок | 3 |
| Скалы | 4 |
| Болото | 5 |
В таблице 12.1 перечислены пять типов узлов и их базовая стоимость. Назначив каждому типу узла собственную базовую стоимость вы сможете находить наилучший путь на карте. Чтобы не усложнять пример, я назначаю всем узлам карты одинаковую базовую стоимость. Вам же ничто не мешает назначать в реальной игре различные стоимости разным узлам.
Следующая стоимость позволяет отследить во сколько обойдется игроку возвращение из данного узла к начальному. Она необходима для того, чтобы вы знали насколько труден путь из начального узла до данного. Вычисляется эта стоимость очень просто — достаточно взять стоимость относительно начального узла для родительского узла и прибавить к ней базовую стоимость текущего узла. В результате вы получите общую стоимость текущего узла относительно начального.
Последний компонент стоимости — это стоимость достижения цели из данного узла. Она вычисляется путем сложения количества строк и столбцов на которые текущий узел отстоит от цели. Предположим, текущий узел расположен на один ряд ниже и на десять столбцов левее цели. Стоимость этого узла относительно цели будет 10 + 1 = 11. Правда, просто?
Как только все три упомянутых выше стоимости вычислены, вам надо собрать их воедино и получить общую стоимость узла. Это может звучать непонятно, так что взгляните на рис. 12.8, где показаны стоимости всех рассматриваемых в примере узлов из открытого списка.
Рис. 12.8. Стоимость узлов из открытого списка
На рис. 12.8 показаны узлы из открытого списка с их стоимостью. Из чего составляется стоимость каждого узла показано на рис. 12.9.
Рис. 12.9. Составляющие стоимости узла
Как видно на рис. 12.8 и рис. 12.9, общая стоимость узла показана в левом верхнем углу. В правом верхнем углу приводится базовая стоимость, в левом нижнем — стоимость относительно начального узла и в правом нижнем — стоимость относительно цели.
Вооружившись общей стоимостью каждого узла, очень просто найти наилучший узел, для добавления его в закрытый список. Отсортируйте узлы по значению общей стоимости и выберите тот из них у которого она меньше всего. На рис. 12.8 наименьшая общая стоимость у узла, расположенного справа от стартовой точки. Она равна 10 и других таких же дешевых узлов нет. Я даже обвел на рисунке этот узел рамкой, чтобы показать, что именно его следует выбрать.
После того, как узел с наименьшей общей стоимостью найден, добавьте его в закрытый список в качестве кандидата на участие в итоговом пути. Не забудьте удалить этот узел из открытого списка, чтобы он не был обработан снова. Итак, давайте подытожим пройденные шаги:
Если в открытом списке отсутствует конечный пункт маршрута, следует продолжать поиск пути добавив в открытый список те узлы, которые находятся вокруг узла только что добавленного в закрытый список. После этого вы снова найдете открытый узел с наименьшей стоимостью и добавите его в закрытый список. Эти действия будут повторяться до тех пор, пока конечный пункт маршрута не окажется в открытом списке.
Как только конечный пункт маршрута окажется в открытом списке, необходимо будет составить путь обратно к исходной точке. Для этого мы берем родителя открытого узла в котором расположен конечный пункт. Затем берем родителя родителя и так далее до тех пор, пока не вернемся к исходной позиции. В результате вы получите путь от конечного пункта до начального. Теперь вам достаточно инвертировать полученный путь, чтобы получить маршрут от исходной точки до цели. На рис. 12.10 показан путь, сформированный алгоритмом для рассматриваемого примера.
Рис. 12.10. Найденный путь
На рисунке вы можете заметить, что в сформированный путь попали несколько лишних узлов. Это вызвано тем, что несколько узлов имеют одинаковую общую стоимость. Вы не можете выбрать сразу два узла, и просто берется тот узел, который находится в списке первым. Это может привести к увеличению объема работы, но в конце путь будет скорректирован.
| netlib.narod.ru | < Назад | Оглавление | Далее > |