Обход препятствий Перемещение в случайном направлении Трассировка вокруг препятствия Надежная трассировка Поиск пути на графе Поиск в ширину Двунаправленный поиск в ширину Алгоритм Дийкстры Поиск в глубину Алгоритм последовательных приближений при поиске в глубину Алгоритм "лучший-первый" Алгоритм А* Гибкость Ограничения Иерархический поиск Реализация в играх Оптимизация Непрерывное игровое пространство Обход препятствий Хотя поиск пути не тривиальная задача, существует несколько хороших, надежных алгоритмов, которые заслуживают большей известности в сообществе разработчиков. Некоторые алгоритмы поиска пути не очень эффективны, но их изучение позволяет постепенно вводить концепции. Так можно понять, как решаются различные проблемы. Типичной проблемой в поиске пути является обход препятствий. Наипростейшим подходом к проблеме является игнорирование препятствий до столкновения с ними. Такой алгоритм будет выглядеть примерно так: Пока не цель не достигнута Выбрать направление для движения к цели Если это направление свободно для движения Двигаться туда Иначе Выбрать другое направление в соответсвии со стратегией обхода Этот подход прост, так как он предъявляет совсем немного требований: все, что необходимо знать - это относительные положения объекта и его цели, и признак блокирования препятствием. Для многих игровых ситуаций этого достаточно. Различные стратегии обхода препятсвий включают в себя: Перемещение в случайном направлении. Если препятствия маленькие и выпуклые, объект (показан зеленой точкой) может, вероятно, обойти их путем небольшого смещения в сторону до тех пор, пока не достигнет цели (показана красной точкой). Рисунок 1А показывает, как работает такая стратегия. Проблемы у этого метода возникают, если препятствия большие или вогнутые, как показано на рисунке 1Б - объект может полностью застрять или как минимум потерять много времени, пока не будет найден обходной путь. Существует только один способ избежать этого: если проблему очень трудно преодолеть, то измените игру так, чтобы эта проблема никогда не возникала. То есть, убедитесь, что в игре никогда не будет вогнутых объектов Трассировка вокруг препятствия. К счастью, существуют другие методы обхода. Если препятствие большое, можно коснуться рукой препятствия и следовать контуру препятствия, пока она не обойдено. Рисунок 2А показывает, как хорошо этот метод работает с большими препятствиями. Проблема с этим методом состоит в принятии решения - когда же прекратить трассировку. Типичной эвристикой может быть: "Остановить трассировку при передвижении в направлении, которое было желаемым в начале трассировки". Это будет работать во многих случаях, однако рисунок 2Б показывает, как можно постоянно кружить внутри препятствия не находя пути наружу. Надежная трассировка. Более надежная эвристика пришла из работ над мобильными роботами: "При блокировании, вычислить уравнение линии из текущей позиции к цели. Трассировать до тех пор, пока эта линия не пересечена снова. Прервать работу, если вы опять попали в начальную позицию". Этот метод гарантирует нахождение пути вокруг препятствия, если он есть, что показано на рисунке 3А. (Если изначальная точка блокирования между вами и целью при пересечении линии, ни в коем случае не останавливайте трассировку, чтобы избежать дальнейшего зацикливания) Рисунок 3Б показывает обратную сторону этого подхода: зачастую требуется гораздо больше времени на трассировку чем необходимо. Компромисс состоит в комбинации обоих подходов: всегда использовать эвристику попроще для остановки трассирования, но если зафиксировано зацикливание, переключаться на надежную эвристику. Поиск пути на графе Хотя техники обхода препятствий рассмотренные выше часто могут проделать допустимую или даже адекватную работу, существуют ситуации, в которых единственно разумный подход это планирование всего пути перед началом перемещений. В дополнение, эти методы не могут решить проблему взвешенных областей, которая состоит не столько в обходе препятствий, сколько в поиске пути с наименьшей стоимостью среди других вариантов, где стоимость местности может изменяться. К счастью, в областях теории графов и обычного ИИ имеется несколько алгоритмов, которые могут решить проблему и сложных препятствий и взвешенных областей. В литературе, многие из этих алгоритмов представлены в терминах изменения состояний или прохода по узлам графа. Это зачастую используется для решения множества проблем, включая "пятнашки" и кубик Рубика, где состоянием является сочетание цифр или кубиков, и соседние состояния (или смежные узлы) посещаются путем перемещения цифр или поворота граней кубика. Применение этих алгоритмов к поиску пути в геометрическом пространстве требует простой адаптации: состояние или узел графа представляют объект, находящийся в определенной клетке, и передвижение в соседние клетки соответствует перемещению в соседние состояния или смежные узлы. Рассматривая алгоритмы от простейших к более надежным, имеем: Поиск в ширину. Начиная со стартового узла, этот алгоритм сначала определяет все непосредственно соседние узлы, затем все узлы в двух шагах, затем в трех, и так далее, пока цель не достигнута. Типичным является то, что для каждого узла его непроверенные соседи помещаются в список Open, который обычно является FIFO очередью. Алгоритм может работать так, как показано в Листинге 1. Рисунок 4 демонстрирует процесс поиска. Можно заметить, что он находит путь вокруг препятствий, и этот путь является кратчайшим, то есть одним из нескольких кратчайших в длину путей, если все шаги имеют одинаковую стоимость. Тут имеется множество простых проблем. Одна заключается в том, что поиск идет равномерно во всех направлениях, вместо того, чтобы быть направленным в сторону цели. Другая проблема в том, что не все шаги равны, по крайней мере, шаги по диагонали должны быть длиннее ортогональных. Двунаправленный поиск в ширину. Это улучшает простой поиск в ширину тем, что запускаются два одновременных поиска в ширину из стартового и конечного узлов и останавливается, когда узел из одного фронта поиска находит соседний узел из другого фронта. Как показано на рисунке 5, это может улучшить простой поиск в ширину (обычно в 2 раза), но все еще является очень неэффективным. Хитрости, наподобие этой, хорошо запомнить, так как они могут пригодиться в дальнейшем. Алгоритм Дийкстры. Е. Дийкстра разработал классический алгоритм для прохода по графам, грани которых имеют различный вес. На каждом шаге, он ищет необработанные узлы близкие к стартовому, затем просматривает соседей найденного узла, и устанавливает или обновляет их соответствующие расстояния от старта. Этот алгоритм имеет два преимущества по сравнению с поиском в ширину: он принимает во внимание стоимость или длину пути и обновляет узлы, если к ним найден лучший путь. Для реализации, список Open с очередью FIFO заменяется приоритетной очередью, где извлеченный узел имеет лучшее значение - здесь, это наименьшая стоимость пути от старта. (См. листинг 2.) На рисунке 6 показана хорошая адаптация алгоритма к стоимости местности. Однако, он имеет слабость поиска в ширину, игнорируя направление к цели. Поиск в глубину. Этот поиск противоположен поиску в ширину. Вместо посещения вначале всех соседей, а потом их наследников, он сначала посещает всех наследников, а только затем переключается на соседей. Для уверенности в том, что поиск закончится, необходимо предусмотреть остановку на определенной глубине. Можно использовать тот же самый код, что и в поиске в ширину, если добавить параметр для отслеживания глубины каждого узла и заменить Open с очереди FIFO на стек LIFO (last-in-first-out). На самом деле можно полностью избавиться от списка Open и вместо этого сделать поиск рекурсивной подпрограммой, что уменьшит расход памяти использованной под Open. Необходимо, чтобы каждая ячейка маркировалась как "посещенная" при продвижении в глубь и эта пометка снималась на обратном ходу, чтобы избежать генерации путей, которые посещают дважды одну и ту же ячейку. На рисунке 7 можно заметить, что этого недостаточно, алгоритм все равно может путаться вокруг себя и тратить время на бессмысленные пути. Для геометрического поиска пути можно сделать два дополнения. Первое будет заключаться в добавлении метки на каждую ячейку с длиной найденного к ней кратчайшего пути; алгоритм больше не посетит эту ячейку пока не будет иметь к ней путь с меньшей стоимостью. Другое заключается в выборе вначале соседей, которые ближе к цели. С этими двумя дополнениями, можно заметить, что поиск в глубину быстро найдет путь. Могут обрабатываться даже взвешенные пути, если сделать остановку по общей накопленной стоимости вместо общего расстояния. Алгоритм последовательных приближений при поиске в глубину (IDDFS). В действительности в алгоритме поиска в глубину существует еще одна проблема - выбор правильной глубины остановки. Если она будет слишком маленькой, то путь не будет найден; если слишком большой, то потенциально можно потратить много времени впустую, исследуя слишком глубоко, или найти путь с очень высокой стоимостью. Эти проблемы решаются итеративным углублением - техника, при которой выполняется поиск в глубину с увеличивающейся глубиной до тех пор, пока путь не будет найден. При поиске пути мы можем не начинать с глубины равной единице, а сразу начать с глубины равной расстоянию по прямой от старта к цели. Этот поиск является асимптотически оптимальным среди всех переборных алгоритмов по времени и памяти. Алгоритм 'лучший-первый'. Это первый рассматриваемый эвристический поиск, который принимает во внимание знания о пространстве поиска для направления своих усилий. Он похож на алгоритм Дийкстры, за исключением того, что узлы в списке Open оцениваются по приблизительному оставшемуся расстоянию до цели. Эта оценка так же не требует наличия обновлений, в отличие от алгоритма Дийкстры. Рисунок 8 показывает работу алгоритма. Это самый быстрый из всех планирующих алгоритмов рассмотренных ранее, который направляется по прямой к цели. Он так же имеет и свои слабости. На рисунке 8А, показано, что он не принимает во внимание накопленную стоимость пути, направляясь по прямой через зону с высокой стоимостью, а не обходя ее. И на рисунке 8Б можно увидеть, что найденный путь вокруг препятствия не прямой, а изгибается вокруг препятствия на манер алгоритма трассировки, рассмотренного ранее. Вперед  >>>  1  2   8  Комментарии к статье  8 8  Обсудить в чате