Реклама:

Приоритетная очередь Open DijkstraSearch Опорные точки n, n*, s s.cost = 0

s.parent = null // s — точка начала поиска Занести s в Open Пока Open не пуст Извлечь точку п из Open

Если п — цель поиска, построить путь и выйти из алгоритма

Для каждой точки п', смежной с п,

newcost = п.cost + cost(n.n')

Если п" находится в Open и п'.cost <= newcost, прервать текущую итерацию и перейти к следующей

n'.parent = п

n'.cost = newcost

Если п" не содержится в Open, занести п" в Open

Путь не найден

Open — это приоритетная очередь, т.е. список вершин, который остается отсортированным по расстоянию вершин от начальной точки после любой операции. Его можно реализовать списком Tlist, и тогда несложно воспользоваться его свойством Sorted. Однако для некоторых задач удобнее представить приоритетную очередь в виде динамического массива опорных точек и при добавлении нового элемента следить за тем, чтобы порядок сортировки не нарушался. В некоторых средах и языках программирования есть отдельные классы, которые реализуют приоритетную очередь. Тогда вы можете воспользоваться ими. Функция Cost рассчитывает весовой коэффициент между точками п и п1. В простейшем случае это будет расстояние между двумя точками, ну а в сложном — можно учитывать такие вещи, как тип местности, время разворота юнита в нужном направлении, затраты энергии и много чего еще.

Гори-гори, моя звезда...

Звездой поисковых алгоритмов программисты между собой называют алгоритм со странным названием а*. На первый взгляд, он очень похож на алгоритм Дейкстры. А работает во много раз быстрее и эффективнее. Секрет — в особой эвристике определения качества найденного пути. Каждой точке пути алгоритм присваивает весовой коэффициент f (п), который можно определить так: f(n) = g(n) + H(n)

Здесь g(n) — это цена пути из начальной точки поиска в текущую. Цена пути определяется точно так же, как и в алгоритме Дейкстры. В простейшем случае это сумма евклидовых расстояний между всеми точками пути. Вы можете взять в расчет местность, по которой пролегает путь, расстояние до объектов, которых надо опасаться (врагов). Вторая часть суммы — н (п) — это примерная (эвристическая) цена пути из текущей точки в конечную. Как же определить эту цену, если и самого пути-то еще нет? В этом и заключается основная хитрость.

Представьте себе, что в дальнейшем путь будет обладать такими же характеристиками, как и раньше. Например, вы все время шли по гористой местности и приходилось один раз обходить лагерь врагов. Значит, вполне возможно, что и оставшаяся часть пути будет не менее гористой, да и еще один лагерь попадется. Это предположение может быть неверным, — например, сразу после текущей точки начнется ровное поле. Но представьте, что наше предположение верно. Статистика— замечательная штука. Из этого самого предположения рассчитайте кратчайший путь до конечной точки. Если карта игры у вас двухмерная, достаточно определить длину прямой, соединяющей текущую и конечную точки. Умножьте эту длину на среднюю "тяжесть" пути, и, вуаля, готова эвристическая цена оставшегося пути.


⇐ Предыдущая страница| |Следующая страница ⇒