Реклама:

Алгоритм а* дает потрясающие результаты за относительно небольшое время, но... только если вы правильно подобрали функцию эвристической оценки. Чем лучше эта функция, тем точнее и быстрее найдется нужный путь. Более того, если для выбранной системы координат и представления игрового пространства вы используете оптимальную эвристическую функцию, найденный путь будет гарантированно кратчайшим из всех возможных. Управляя весовыми коэффициентами каждой конкретной точки карты, вы можете легко добавлять критерии поиска. Например, вы захотели поощрять искусственный интеллект исследовать еще некоторые территории. Просто добавьте к весовым коэффициентам неоткрытых точек определенный бонус, и тогда управляемый ИИ исследователь из всех кратчайших путей к нужной точке будет отдавать предпочтение тем, которые приводят к открытию новых земель. Точно так же вы можете дать задание шпиону уклоняться от вражеских патрулей или утлому суденышку опасаться быстрого течения на стрежне реки.

Совсем необязательно давать а* задание искать путь только в какую-то одну определенную точку. Вы можете задать целый набор точек. Тогда н (п) в каждой точке будет определяться как минимальная цена пути среди путей ко всем точкам назначения. Давайте взглянем на детализированный алгоритм а*.

//в — точка, из которой начинаем поиск s.g = О

//Вычисляем эвристическое расстояние до конечной точки

s.H = GoalDistEstimate( s )

s.f = s.g + s.H

s.parent = null

Поместить s в очередь Open

Пока список Open не пуст

Извлечь точку п из Open

Если п — финальная точка

Построить путь

//Алгоритм успешно отработал Выход

Для каждого наследника п* от п

newg = n.g + cost(n,n")

Если (п1 находится в Open или Closed)

и (n1.g <= newg)

Пропустить

n".parent = п п".д = newg

n'.H = GoalDistEstimate( п" )

n*.f = п'.д + n'.Н

Если п" находится в Closed

Удалить п' из Closed

Если п' еще не находится в Open

Поместить п" в Open

Поместить п в Closed

Выход // Путь не найден

Open — это все та же приоритетная очередь, хорошо знакомая вам по алгоритму Дейкстры. Здесь появился новый список — Closed. Он не обременен никакими дополнительными условиями — это просто список без всяких приоритетов. Поэтому вы можете реализовать его как с помощью TList, так и с помощью динамических массивов. Он предназначен для того, чтобы исключить повторную обработку точек, которые уже включались в путь на данном этапе поиска.

Потенциальные поля

У каждого из алгоритмов поиска путей, которые мы рассматривали, есть свои достоинства и два общих недостатка. В случае, если игровое поле представляет собой не лабиринт, а множество разрозненных препятствий, пусть и размещенных сколь угодно затейливо, алгоритмы будут работать неоправданно долго. Еще одна проблема: рассчитанные пути очень часто пролегают слишком близко к краям препятствий. Путь юнита по такому маршруту будет выглядеть неестественно. А иногда такое поведение противоречит логике игры.

Например, вражеский юнит обходит свое минное поле по периметру. Вы об этом минном поле, естественно, не знаете. Представьте картину: вражеский юнит бежит в атаку на ваше воинство, вдруг резко меняет направление, оббегает какой-то призрачный прямоугольник и бежит дальше. Есть повод задуматься! И самое главное — без дополнительных изменений алгоритмов путь придется рассчитывать после каждого хода, если ситуация на игровом поле постоянно меняется. А такое происходит сплошь и рядом.

В таких ситуациях хорошо себя зарекомендовали так называемые потенциальные поля. Каждой точке на карте присваивается свой весовой коэффициент — потенциал согласно какому-то условию. Пусть, например, чем ближе точка к цели поиска, тем выше у нее потенциал. Тогда у точки, из которой начинается поиск, потенциал будет самым низким. Запрограммируйте юнита все время двигаться из точек с меньшим потенциалом к точкам с большим — и вы увидите интересную картину. Точка старта будет как бы отталкивать юнита, а точка назначения, наоборот, притягивать. Мысленно поместите в точку старта мощный магнит северным концом, в точку назначения — еще более мощный магнит южным, а юнита представьте маленьким магнитиком, который отталкивается от первого магнита и притягивается ко второму.

Но на игровом поле пока нет никаких препятствий. Если мы поместим прямоугольное препятствие на пути юнита, он, повинуясь закону о разности потенциалов, проскользит вдоль одного из его краев и пойдет себе дальше. А если препятствие сделать в форме угла? Юнит в нем просто застрянет. Вот мы и подошли к самой интересной особенности потенциальных полей! Каждое препятствие— это тоже магнит, который отталкивает от себя юнита! Причем чем больше и опаснее препятствие, тем сильнее отталкивающая сила. Теперь юнит от точки старта до точки назначения будет двигаться как будто по фарватеру, между всеми возможными препятствиями и опасностями. С точки зрения игрока, путь, который выберет юнит, будет самым естественным. А ведь реализм — одна из главнейших характеристик любой игры.

Алгоритм потенциальных полей очень похож на волновой алгоритм, который мы рассмотрели выше. Вот только волны выпускаются не только из начальной точки, но и из всех препятствий. Реализовать этот алгоритм так же просто. Однако в целях оптимизации разделите все потенциальное поле карты на две части. Первая часть — поле, которое создают точки старта и назначения, ну а вторая — объединение всех полей препятствий. Дело в том, что при каждом новом поиске пути начальные и конечные точки меняются, а значит, меняются и их потенциальные поля. Ну а поля препятствий все время остаются неизменными. Перед каждым новым поиском просто сложите две этих части, и получите готовую потенциальную карту пути, по которому должен пойти юнит. Алгоритм потенциальных полей находит не всегда самый кратчайший путь, но уж точно самый красивый и естественный.

Р.Б. Остальные приемы работы с СЬ8сепе можно посмотреть в демо, поставляющихся с установочными файлами С1^>сепе.


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