Алгоритм A* для новичков.

Автор: Патрик Лестер (Patrick Lester) (2 апреля 2004) Почта:

Перевод: Morpher (26 июля 2004) Почта: Morpher_KKnD@mail.ru

Данная статья переведена на Испанский и Французкий. Другие переводы приветствуются.

Алгоритм A* (произносится как "А-звездочка"), возможно, немного трудноват для новичков. И хотя в сети существует множество материалов, обьясняющих A*, большинство из них написаны для людей, которые уже понимают основы. Эта же статья действительно написана для новичков. 

Статья не пытается быть исчерпывающим материалом по данной теме. Вместо этого она описывает фундаментальные понятия и подготавливает вас к тому, чтобы прочитать все те материалы и понять о чем в них идет речь. Ссылки на некоторые из них прилагаются в конце статьи (под заголовком "Дальнейшее изучение").

Также эта статья не направлена на определенный язык программирования - вы сможете адаптировать ее к любому из них. Как вы, должно быть, и ожидали, я добавил ссылку на пример реализации в конце статьи. Архив примера содержит две версии: на C++ и на Blitz Basic. Он также содержит скомпилированную версию, если вы просто хотите увидеть A* в действии.

Но пора приступать к делу. Давайте начнем с самого начала...

Введение: Область Поиска

Давайте представим себе, что у нас есть кто-то, кто хочет попасть из точки А в точку B. Эти две точки разделены стеной. На иллюстрации ниже зеленый квадрат это стартовая точка A, красный квадрат - целевая точка B, а несколько синих квадратов - стена между ними.

   

[Рис. 1]

Первое, на что вы должны обратить внимание, то, что мы разделили нашу область поиска на сетку с квадратными ячейками. Упрощение области поиска это первый шаг в поиске пути. Этот метод упрощает нашу область поиска до простого двумерного массива. Каждый элемент масссива представляет одну из клеток сетки, а его значением будет проходимость этой клетки (проходима и непроходима). Для нахождения пути нам необходимо определить какие нам нужны клетки для перемещения из точки A в точку B. Как только путь будет найден, наш путник начнет двигаться с центра одной клетки на центр следующей до тех пор, пока не достигнет целевой клетки. 

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

Начало Поиска

Как только мы упростили нашу область поиска до некоторого числа вершин, нам нужно начать поиск для нахождения кратчайшего пути. Начнем с точки A, проверяя соседние клетки и двигаясь дальше до тех пор, пока не найдем целевую точку.

Начинаем поиск пути выполняя следующее:

1. Начинаем со стартовой точки A и добавляем ее в "открытый список" клеток, которые нужно обработать. Открытый список это что-то наподобие списка покупок. В данный момент есть только один элемент в списке, но позже мы добавим еще. Список содержит клетки, которые может быть находятся вдоль пути, который вы выберете, а может и нет. Проще говоря, это список клеток, которые нужно проверить.
2. Ищем доступные или проходимые клетки, граничащие со стартовой точкой, игнорируя клетки со стенами, водой или другой непроходимой областью. И также добавляем их в открытый список. Для каждой из этих клеток сохраняем точку A, как "родительскую клетку". Эта родительская клетка важна, когда мы будем прослеживать наш путь. Это будет описано намного позже.
3. Удаляем стартовую точку A с вашего открытого списка и добавляем ее в "закрытый список" клеток, которые вам больше не нужно проверять.

Дальше мы выберем одну из соседних клеток в открытом списке и практически повторим вышеописанный процесс . Но какую клетку мы выберем? Ту, у которой меньше стоимость F.

Оценка пути

Способом определения того, какую же клетку использовать, является следующие выражение:

F = G + H 

где

• G = стоимость передвижения из стартовой точки A к данной клетке, следуя найденному пути к этой клетке. 
• H = примерная стоимость передвижения от данной клетки до целевой, то есть точки B. Она обычно является эвристической функцией. Причина по которой она так называется в том, что это предположение. Мы действительно не узнаем длину пути, пока не найдем сам путь, потому что в процессе поиска нам может встретиться множество вещей (например, стены и вода). В этой статье вам предложили один способ вычислить H, но существует множество способов, которые можно найти в других статьях.

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

Как описано выше, G является стоимостью передвижения со стартовой клетки до текущей, используя найденный к ней путь. В этом примере мы присвоим стоимость 10 к горизонтальным и вертикальным передвижениям, а к диагональным - 14. Мы используем эти числа потому, что пройденное по диагонали расстояние примерно в 1,414 раз (корень с 2) больше стоимости передвижения по горизонтали или вертикали. Для простоты мы используем 10 и 14. Соотношение соблюдается и мы избегаем вычисления квадратных корней и десятичной дроби. Это не просто потому, что мы дураки и не любим математику. Использование целых чисел вроде этих, намного быстрее для компьютера. Как вы скоро узнаете, поиск пути может быть очень медленным если вы не используете упрощения наподобие этих. 

Так как мы вычисляем стоимость G вдоль пути к текущей точке, способ ее установить состоит в том, чтобы взять G родительской клетки и прибавить 10 или 14, в зависимости от диагонального или ортогонального (не диагонального) расположения текущей клетки относительно родительской клетки. Необходимость использования этого метода станет очевидной немного позже, когда мы отдалимся от стартовой точки более чем на одну клетку.

Стоимость H может быть вычислена множеством способов. Метод, который мы используем, называется методом Манхеттена (Manhattan method), где вы считаете общее количество клеток, необходимых для достижения целевой точки от текущей, по горизонтали и вертикали, игнорируя диагональные перемещения и любые препятствия, которые могут оказаться на пути. Затем мы умножаем общее количество полученных клеток на 10.

Читая это описание вы, должно быть, решили, что эвристика - просто приблизительное определение оставшегося расстояния между текущей клеткой и целью по прямой. Но это не так. Мы пытаемся установить оставшееся расстояние вдоль пути (который обычно идет не по прямой), но алгоритм требует от нас не переоценить это расстояние, иначе он может найти не верный путь. Использованный здесь метод гарантирует предоставить нам правильный путь. Хотите узнать про эвристику больше? Вы найдете выражения и дополнительные сведенья здесь.

Стоимость F вычисляется путем сложения стоимостей G и H. Результаты первого шага нашого поиска пути проиллюстрированы ниже. Значения F, G и H записаны в каждой клетке. Как видим по клетке справа от стартовой точки, F выводится в верхнем левом углу, G выводится в нижнем левом углу, а H выводится в нижнем правом углу.

 
  [Рис. 3] 

Давайте посмотрим на некоторые из этих клеток. В клетке с буквами G = 10. Это потому, что она находится на расстоянии в одну клетку от стартовой точки, при том по горизонтали. Также G = 10 у клеток прямо сверху, снизу и слева от стартовой точки. У диагональных клеток G = 14. 

Стоимость H посчитана с помощью вычисления Манхеттенского расстояния к красной целевой клетке, двигаясь только по горизонтали и вертикали, игнорируя все стены на пути. У клетки, прямо справа от стартовой, расстояние до цели 3 клетки. Используя этот метод видим, что H = 30. У клетки прямо над ней, расстояние уже 4 клетки (помните, что надо двигаться только по горизонтали и вертикали). И ее значение стоимости H будет равно 40. Вы, вероятно, можете догаться, как вычисляются стоимости H для других клеток. 

Стоимость F для каждой клетки вычисляется простым суммированием G и H.

Продолжаем поиск

4) Удаляем ее из открытого списка и добавляем в закрытый список.

Хорошо, давайте посмотрим, как это работает. С наших начальных 9 клеток, осталось 8 в открытом списке, а стартовая клетка была внесена в закрытый список. Клетка с наименьшей стоимостью F находится прямо справа от стартовой клетки, и ее стоимость F = 40. Поэтому мы выбираем эту клетку как нашу следующую клетку. Она выделена голубым цветом на этой иллюстрации.

   
[Рис. 4] 

1.  Другие юниты (уклонение от столкновений) Если вы присмотритесь внимательней к моему примеру реализации алгоритма, вы заметите, что он полностью игнорирует все остальные юниты на экране. Юниты спокойно проходят сквозь друг друга. В зависимости от игры, это может быть приемлимым, но может и не быть. Если вы хотите чтобы юниты обходили друг друга, то я предлагаю вам несколько методов. Можно обратбатывать юниты, которые не двигаються или находятся близко к юниту, для которого ищется путь, а остальные просто игнорировать. Если же вы хотите обрбатывать юниты, которые двигаются и находятся на расстоянии более чем в одну вершину, то вам нужно будет разработать метод для установления их положения в пространстве в любое время, чтобы они могли должным образом уклониться. Иначе в дальнейшем вы можете столкнуться со странными путями, где юниты двигаються по зигзагообразной траектории, пытаясь обьехать другие юниты, которых там давно нет. Вам также потребуется система определения столкновений, так как не важно насколько хорош ваш путь, со временем многие вещи могут измениться. Когда происходит столкновение, для юнита надо просчитать новый путь или, если это не лобовое столкновение, подождать пока другой юнит отойдет с дороги, перед тем, как двигаться дальше.

Вот некоторые ссылки, которые могут вам пригодиться:

• Steering Behavior for Autonomous Characters: по движению автономных устройств немного отходит от задачи поиска пути, но она может быть интегрирована с ним для более совершенного перемещения и определения столкновений.
• The Long and Short of Steering in Computer Games: Интересный обзор литературы по передвижению и поиску пути. Это pdf документ.
• Coordinated Unit Movement: Первая статья из двухсерийного цикла про формацию и сгруппированое передвижение юнитов от дизайнера Эпохи Империй (Age of Empires) Дейва Поттингера (Dave Pottinger).
  
• Implementing Coordinated Movement: Вторая статья из этого цикла.

2. Различная стоимость передвижения: В этой статье и в моей прилагающейся программе поверхность может быть только двух типов - проходимая и непроходимая. Но что, если у вас есть территория, которая проходимая, но имеет большую стоимость передвижения? Болота, возвышенности, лестницы в пещерах, и т.д. - это примеры поверхности, котрую можно пройти, но стоимость передвижения у нее выше, чем стоимость передвижения по ровной, открытой поверхности. Также стоимость передвижения по дорогам может быть немного ниже стоимости передвижения по другим видам поверхности.

Эта проблема легко решается путем добавления стоимости поверхности при вычислении стоимости G любой вершины. Просто добавьте дополнительную стоимость к таким вершинам. Алгоритм поиска пути A* написан для нахождения пути с наименьшей стоимостью и легко справится с такой задачей. В простом примере, который я описал, когда поверхность может быть или проходимой или нет, A* будет искать кратчайший, более прямолинейный путь. Но в случае с различной стоимостью поверхности, юнит может пойти более длинным путем - как, например, при движении по дороге через болото, а не движении напрямик по самому болоту.

Существует еще одно интересное решение, которое проффесионалы называют "influence mapping" (что-то вроде карты с областями влияния). Так же как и с различной стоимостью поверхности, вы можете создавать дополнительные системы и применять их для целей ИИ (искуственного интеллекта). Представьте, что у вас есть карта, на которой находятся толпы юнитов, охраняющих проезд через горный регион. Каждый раз, когда компьютер посылает свой юнит через этот проход, он уничтожается. Если вы захотите, то можете создать "карту влияний", которая будет "штрафовать" вершины, возле которых множество вражеских единиц. Это научит компьютер планировать более безопасные пути и поможет избежать глупых ситуаций, когда компьютер продолжит посылать юниты через более опасный район только потому, что он более короткий.

3. Обработка неизведанных территорий: Вы когда-нибудь играли в игры, в которых компьютер всегда знает точно какой путь выбрать, даже если карта еще не полностью исследована? В зависимости от игры, поиск пути это то, что может быть очень нереалистичным. К сожалению, это та проблема, которую не так-то просто решить.

Ответ заключается в создании массива "известнаяПроходимость" для каждого из игроков и компьютерных оппонентов ("каждый игрок" не значит "каждый юнит", это потребовало бы очень много памяти). Каждый такой массив должен содержать информацию про области, которые игрок уже исследовал, остальные же области должны оставаться непроходимыми до исследования. Используя такое решение, юниты будут попадать в тупики и искать неверный путь до тех пор, пока они не откроют всю карту. Как только карта будет исследована, поиск пути станет всегда находить верные пути.

4. Сглаженные пути: A* даст вам кратчайший, с наименьшей стоимостью путь, но он не даст вам визуально сглаженного пути. Давайте посмотрим на окончательный путь, просчитанный в примере (рис. 7). На этом пути первый шаг находится справа внизу от стартовой клетки. Не казался бы наш путь более плавным, если бы первый шаг находился прямо под стартовой клеткой?

Есть несколько способов решить эту проблему. В процессе поиска вы можете "штрафовать" вершины, где есть смена направления движения, увеличивая их стоимости G. Так же вы можете пройти по всему пути после его вычисления и выискивать вершины, в которых вы бы хотели изменить направление для более сглаженного пути. Для более обширного описания проблемы, проверьте , Toward More Realistic Pathfinding, бесплатную (но требующую регистрации) статью Марка Пинтера (Marco Pinter) на Gamasutra.com.

5. Неквадратные области поиска: В нашем примере мы используем простые плоские квадратные ячейки. Необязательно всегда выбирать такое решение. Вы можете использовать области с неправильной формой. Вспомните про игру Risk (Риск :-) и страны в ней. Вы можете захоть использовать такой сценарий поиска пути. Для того, чтобы это сделать вам необходимо создать таблицу для хранения информации о том, какие страны с какими граничат и стоимости G для передвижения от одной страны к другой. Вы также должны выбрать метод определения стоимости H. Все остальное остается таки же, как и в нашем примере. При добавлении элементов в открытый список, вместо просмотра соседних клеток просто просматривайте соседние страны в таблице.

Также вы можете создать систему вэйпоинтов для путей нафиксированной карте. Вэйпоинты представляют собой несколько связанных точек пути, например, на дороге или в тунелле подземелья. Как гейм-дизайнер вы можете указывать эти вэйпоинты вручную. Два вэйпоинта считаются соседними, если на линии между ними нет никаких препятствий. В случае с игрой Риск (Risk), вы сохраняете эту информацию о соседстве в какой-нибудь таблице и используете эту информацию при генерации элементов открытого списка. Затем вы сохраняеете присвоенные стоимости G (возможно, используя длины отрезков, соеденяющих вершины) и стоимости H (возможно, используя длины отрезков, соеденяющих вершины и цель). Все остальное выполняется как обычно.

6. Некоторые советы по увеличению скорости поиска: Как только вы разработаете свою собственную программу A*, или адаптируете ту, которую написал я, то обнаружите, что поиск пути использует львиную долю вашего процессорного времени, особенно если у вас огромное количесво юнитов и большая карта. Если вы прочитаете в сети различные материалы, то узнаете, что это распостраняется даже на программистов таких игр, как Starcraft или Age of Empires. Если вы заметили, что поиск пути стал медленным, то вот несколько советов о том, как ускорить этот процесс: 

• Используйте карты поменьше и небольшое количество юнитов.
• Никогда не ищите путь одновременно для нескольких юнитов. Вместо этого поставьте их в очередь и рассчитывайте за несколько игровых циклов. Если ваша игра работает на скорости, скажем, в 40 циклов за кадр, никто никогда этого не заметит. Но все заметят, если игра начнет работать очень медленно каждый раз, когда путь вычисляется одновременно для множества юнитов.
• Используйте для вашей карты как можно большие квадраты (или любую другую фигуру). Это уменьшит общее количество вершин просмотренных при поиске пути. Если вы очень амбитный человек, то можете использовать две или больше систем поиска пути, которые будут использоваться в разных ситуациях в зависимости от длины пути. Вот что делают проффесионалы: используют большие области для длинных путей, а затем переходят на более точный поиск, используя меньшие квадраты/области при приближении к цели. Если вы заинтересованы в таком подходе, прочтите мою статью Two-Tiered A* Pathfinding.
• Для длинных путей можно использовать предварительно просчитанные пути.
• Обрабатывайте вашу карту на наличие недоступных из других частей карты участков. Я называю эти участки "острова." В действительности они могут быть островами или любой другой поверхностью, которая отгорожена стенами или недоступна. Один из недостатков алгоритма A* состоит в том, для нахождения путей к таким участкам, он будет искать путь на всей карте, останавливаясь только когда каждый квадрат/вершина прошли через открытый и закрытый списки. Это может потратить очень много процессорного времени. Этого можно избежать если просчитывать какие области недостижими (с помощью flood-fill заливки или похожего метода), сохраняя эту информацию в любом массиве и проверяя ее каждый раз перед началом поиска.
• В запутанном, лабиринтоподобном окружении, стоит отметить вершины, которые не приводят никуда, кроме тупиков. Такие области можно указывать на вашей карте вручную или, если вы очень амбитны, разработать алгоритм, который будет опряделять такие области автоматически. Любой группе таких вершин можно присвоить уникальный идентификационный номер. Затем вы можете спокойно игнорировать все тупики при поиске пути, задумывая сь только о том, чтобы стартовая или челевая точки не попали в такую "тупиковую" область.

7. Реализация открытого списка: Это один из наиболее важных элементов в алгоритме A*. Каждый раз при обращении к открытому списку вам необходимо найти вершину с наименьшей стоимостью F. Существует несколько способов это сделать. Вы можете сохранять элементы пути когда потребуется и просто проматривать весь открытый список каждый раз, когда надо извлечь элемент с наименьшей стоимостью F. Это простой метод, но очень медленный для длинных путей. Он может быть улучшен использованием сортированного списка и тогда нуждно будет просто выбрать первый элемент списка - это и будет элемент с наименьшей стоимостью F. Когда я писал свою программу этот метод был первым, который я использовал.

Это будет быстро работать на маленьких картах, но это не оптимальное решение. Серьезные программисты A*, которые стремятся действительно к впечатляющей скорости, используют что-то, что называются "двоичными кучами" (binary heaps) и это то, что я использовал в своей программе. Это будет по крайней мере в 2-3 раза быстрее в большинстве случаев и намного быстрее (в 10 и больше раз) на длинных путях. Если вы заинтересовались, прочтите мою статью Using Binary Heaps in A* Pathfinding.

8. Алгоритм Дийкстры: В то время, как считается, что A* самый лучший алгоритм поиска (смотрите выше), сущетвует по крайней мере еще один алгоритм, который активно используется - алгоритм Дийкстры (Dijkstra's algorithm). Этот алгоритм точно такой же как и A*, только без эвристики (H всегда равна 0). Так как в нем нет эвристики, он ищет путь одновременно во все стороны. Перед тем, как найти путь, алгоритм исследует намного больше территории. Это делает его медленнее A*.

Так зачем его использовать? Иногда мы не знаем где находится наша цель. Например, у вас есть добывающий юнит, которому надо собрать каких-нибудь ресурсов. Он может знать, что на этой территории есть несколько областей с ресурсами, но он хочет добраться к ближайшим. Здесь использовать алгоритм Дийкстры будет более целесообразно, чем использовать A* потому, что мы не знаем, какие из ресурсов находятся ближе. Альтернатива есть только в повторном использовании A* для нахождения расстояния до каждого из ресурсов, а затем использовании этого пути. Существует множество таких ситуаций.

Дальнейшее изучение

Хорошо, теперь вы знаете основы и смысл некоторых углубленных решений. На этом этапе я советую заглянуть в мой исходный код. Архив содержит две версии: на C++ и на Blitz Basic. Обе версии содержат множество комментариев и должны быть довольно простыми в пониманииd.  Вот ссылка.

• Sample Code: A* Pathfinder (2D) Version 1.9

Если у вас нет возможности работать на C++ или в Blitz Basic, два небольших exe-файла находятся в папке с версией на C++. Версия на Blitz Basic может быть скомпилирована с помощью бесплатной демо-версии Blitz Basic 3D (не Blitz Plus) на оффициальном сайте Blitz Basic. Сетевая демонстрация Бена О'Нилла (Ben O'Neill) находится тут.

Вы также можете заинтересоваться некоторыми сайтами. После прочтения этой статьи они будут простыми для понимания.

• Amit’s A* Pages: Это очень обширная страничка Амита Патела (Amit Patel), но она может быть немного непонятной для тех, кто не читал эту статью. Но все же стоит глянуть. Советую прочитать личные рассуждения Амита про статью.
• http://www.policyalmanac.org/games/aStarTutorial_rus.htm