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




Скачать 0.64 Mb.
Название В настоящий момент в создании искусственного интеллекта (в первоначальном смысле этого слова, экспертные системы и шахматные программы сюда не относятся)
страница 1/4
Дата публикации 21.09.2014
Размер 0.64 Mb.
Тип Документы
literature-edu.ru > Лекции > Документы
  1   2   3   4

ВВЕДЕНИЕ



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

Алгоритм – это точно определённая инструкция, последовательно применяя которую к исходным данным, можно получить решение задачи. Он служит, как правило, для решения не одной конкретной задачи, а некоторого класса задач. Так, алгоритм сложения применим к любой паре натуральных чисел. В этом выражается его свойство массовости, то есть возможности применять многократно один и тот же алгоритм для любой задачи одного класса. Для разработки алгоритмов и программ используется  алгоритмизация – процесс систематического составления алгоритмов для решения поставленных прикладных задач. Алгоритмизация считается обязательным этапом в процессе разработки программ и решении задач на ЭВМ. Именно для прикладных алгоритмов и программ принципиально важны детерминированность, результативность и массовость, а также правильность результатов решения поставленных задач.

Алгоритм поиска пути является ярким примером искусственного интеллекта. Его поведение, решение поставленной задачи и вывод результата своей работы должно быть таким же точным как разум человека. Свою область применения он нашел в различных навигационных системах, как в спутниковых путём измерения расстояний от спутника до объекта от точек с известными координатами, так и наземных с помощью интернет ресурсов. Так же широко используется в компьютерных играх, здесь применяются различные алгоритмы в зависимости от сложности требований к алгоритму, факторам которых являются скорость обработки, точность поиска, множество вычислений за единицу времени и т.д.

1 ПОСТАНОВКА ЗАДАЧИ


  1. Цель работы


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

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

Данная работа является не только предметом рассмотрения алгоритмов, позволяющих найти более гибкие и оптимальные решения, но и рассматривает проблемы представления данных для «удобной» и как самый важный критерий, «быстрой» работы, какого либо алгоритма. Так же необходимо выявить наиболее оптимальный алгоритм, определить его недостатки, определить возможные варианты решения последних.

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

За основу будут взяты изученные в этой работе алгоритмы, широко используемые в представленной отрасли. Необходимо будет рассмотреть основные принципы работы, рассмотреть достоинства и недостатки, после сравнительного анализа определить максимально подходящий алгоритм.

Следующим этапом поставленной задачи является модификация выбранного алгоритма, таким образом, чтобы избавиться или минимизировать недостатки, и при этом не повлиять негативно на производительность методики в целом.
1.2 Основные понятия
В работе будут использованы такие понятия как, обходной путь, под этим выражением подразумевается путь, который каким либо образом обходит препятствия. Быстрый путь – первый найден обходной путь, но не являющийся наилучшим решениям. Кратчайший путь – наилучшее решение из найденных путей.

2 ОБЗОР И АНАЛИЗ СОВРЕМЕННОГО СОСТОЯНИЯ ПРОБЛЕМЫ
2.1 Анализ области применения
В последнее время с ростом компьютерных технологий, всё более широкое применение находит отрасль компьютерных игр. Ни одна игра не обходиться без применения искусственного интеллекта, который в свою очередь базируется на задачах поиска пути в пространстве или на плоскости. Наверное это самая большая проблема в разработке искусственного интеллекта в этой отрасли. Здесь стоит задача как можно быстрей (с точки зрения процессорного времени) обработать большое количество данных чтобы найти самый оптимальный путь.

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

Стратегии реального времени обычно содержат большие территории с открытым ландшафтом, в которых поиск пути обычно является простой задачей. Однако в большинстве случаев по карте перемещается не один юнит, а несколько, что создаёт потребность в различных и намного более сложных алгоритмах поиска пути для избежание пробок в узких областях игрового ландшафта. В стратегиях игровой уровень делится на тайлы (англ.tiles), которые действуют как узлы (англ. nodes) в алгоритме поиска пути.

В жанре 3D-шутеров используются намного более ограниченные пространства, которые не так легко разделить на узлы. Здесь взамен узлов используются так называемые вэйпоинты (англ. waypoints; дословно – русск.точки пути). Вэйпоинты – это нерегулярные и вручную установленные узлы, которые содержат информацию о том, к каким другим узлам возможно добраться от данного.
2.2 Обзор и анализ существующих методов и средств реализации
По своей сути алгоритм поиска пути ищет на графе, начиная с одной (стартовой) точки и исследуя смежные узлы до тех пор, пока не будет достигнут узел назначения (конечный узел). Кроме того, в алгоритмы поиска пути в большинстве случаев заложена также цель найти самый короткий путь. Некоторые методы поиска на графе, такие как поиск в ширину, могут найти путь, если дано достаточно времени. Другие методы, которые « исследуют» граф, могут достичь точки назначения намного скорее. Здесь можно привести аналогию с человеком, идущим через комнату. Человек может перед началом пути заранее исследовать все характеристики и препятствия в пространстве, вычислить оптимальный маршрут и только тогда начать непосредственное движение. В другом случае человек может сразу пойти в приблизительном или предполагаемом направлении цели и потом, уже во время пути, делать корректировки своего движения для избегания столкновений с препятствиями.

К самым известным и популярным алгоритмам поиска пути относятся такие алгоритмы:

  • алгоритм поиска A*;

  • алгоритм Дейкстры;

  • волновой алгоритм;

  • navmesh;

  • иерархические алгоритмы;

  • обход препятствий;

  • алгоритм «Разделяй и властвуй»;

  • алгоритм поворота Креша.


3 ОБЗОР АЛГОРИТМОВ ПОИСКА ПУТИ
3.1 Основные методы поиска пути

3.1.1 Обход препятствий

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

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

Типичной проблемой в поиске пути является обход препятствий. Наипростейшим подходом к проблеме является игнорирование препятствий до столкновения с ними. Такой алгоритм будет выглядеть примерно так:
Пока цель не достигнута

Выбрать направление для движения к цели

Если это направление свободно для движения

Двигаться туда

Иначе

Выбрать другое направление в

соответствии со стратегией обхода
Этот подход прост, так как он предъявляет совсем немного требований: все, что необходимо знать – это относительные положения объекта и его цели, и признак блокирования препятствием. Для многих игровых ситуаций этого достаточно.

Различные стратегии обхода препятствий включают в себя:

3.1.2 Перемещение в случайном направлении

Если препятствия маленькие и выпуклые, объект (показан зеленой точкой) может, вероятно, обойти их путем небольшого смещения в сторону до тех пор, пока не достигнет цели (показана красной точкой). Рисунок 3.1 показывает, как работает такая стратегия. Проблемы у этого метода возникают, если препятствия большие или вогнутые, как показано на рисунке 3.2 – объект может полностью застрять или как минимум потерять много времени, пока не будет найден обходной путь. Существует только один способ избежать этого: если проблему очень трудно преодолеть, то измените игру так, чтобы эта проблема никогда не возникала. То есть, убедитесь, что в игре никогда не будет вогнутых объектов.



Рисунок 3.1 – Обход путем смещения

Рисунок 3.2 – Потеря пути

3.1.3 Трассировка вокруг препятствия

Но существуют и другие методы обхода. Если препятствие большое, можно коснуться рукой препятствия и следовать контуру препятствия, пока она не обойдено. Рисунок 3.3 показывает, как хорошо этот метод работает с большими препятствиями. Проблема с этим методом состоит в принятии решения – когда же прекратить трассировку. Типичной эвристикой может быть: «Остановить трассировку при передвижении в направлении, которое было желаемым в начале трассировки». Это будет работать во многих случаях, однако рисунок 3.4 показывает, как можно постоянно кружить внутри препятствия не находя пути наружу.



Рисунок 3.3 – Трассировка вокруг препятствия



Рисунок 3.4 – Блуждающая трассировка
3.1.4 Надежная трассировка

Более надежная эвристика пришла из работ над мобильными роботами: «При блокировании, вычислить уравнение линии из текущей позиции к цели. Трассировать до тех пор, пока эта линия не пересечена снова. Прервать работу, если вы опять попали в начальную позицию». Этот метод гарантирует нахождение пути вокруг препятствия, если он есть, что показано на рисунке 3.5. (Если изначальная точка блокирования между вами и целью при пересечении линии, ни в коем случае не останавливайте трассировку, чтобы избежать дальнейшего зацикливания) Рисунок 3.6 показывает обратную сторону этого подхода: зачастую требуется гораздо больше времени на трассировку чем необходимо. Компромисс состоит в комбинации обоих подходов: всегда использовать эвристику попроще для остановки трассирования, но если зафиксировано зацикливание, переключаться на надежную эвристику.

Рисунок 3.5 – Надежная трассировка


Рисунок 3.6 – Обратная сторона надежной трассировки

3.2 Поиск пути на графе

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

В областях теории графов и обычного ИИ имеется несколько алгоритмов, которые могут решить проблему и сложных препятствий и взвешенных областей. В литературе, многие из этих алгоритмов представлены в терминах изменения состояний или прохода по узлам графа. Это зачастую используется для решения множества проблем, включая «пятнашки» и кубик Рубика, где состоянием является сочетание цифр или кубиков, и соседние состояния (или смежные узлы) посещаются путем перемещения цифр или поворота граней кубика. Применение этих алгоритмов к поиску пути в геометрическом пространстве требует простой адаптации: состояние или узел графа представляют объект, находящийся в определенной клетке, и передвижение в соседние клетки соответствует перемещению в соседние состояния или смежные узлы.

Рассматривая алгоритмы от простейших к более надежным, имеем:

3.2.1 Поиск в ширину

Начиная со стартового узла, этот алгоритм сначала определяет все непосредственно соседние узлы, затем все узлы в двух шагах, затем в трех, и так далее, пока цель не достигнута. Типичным является то, что для каждого узла его непроверенные соседи помещаются в список Open, который обычно является FIFO очередью. Алгоритм может работать так, как показано в приложении А. Рисунок 3.7 демонстрирует процесс поиска. Можно заметить, что он находит путь вокруг препятствий, и этот путь является кратчайшим, то есть одним из нескольких кратчайших в длину путей, если все шаги имеют одинаковую стоимость. Тут имеется множество простых проблем. Одна заключается в том, что поиск идет равномерно во всех направлениях, вместо того, чтобы быть направленным в сторону цели. Другая проблема в том, что не все шаги равны, по крайней мере, шаги по диагонали должны быть длиннее ортогональных.


Рисунок 3.7 – Процесс поиска в ширину
3.2.2 Двунаправленный поиск в ширину
Это улучшает простой поиск в ширину тем, что запускаются два одновременных поиска в ширину из стартового и конечного узлов и останавливается, когда узел из одного фронта поиска находит соседний узел из другого фронта. Как показано на рисунке 3.8, это может улучшить простой поиск в ширину (обычно в 2 раза), но все еще является очень неэффективным. Хитрости, наподобие этой, хорошо запомнить, так как они могут пригодиться в дальнейшем.



Рисунок. 3.8 – Двунаправленный поиск в ширину

3.2.3 Алгоритм Дийкстры
Е. Дийкстра разработал классический алгоритм для прохода по графам, грани которых имеют различный вес. На каждом шаге, он ищет необработанные узлы близкие к стартовому, затем просматривает соседей найденного узла, и устанавливает или обновляет их соответствующие расстояния от старта. Этот алгоритм имеет два преимущества по сравнению с поиском в ширину: он принимает во внимание стоимость или длину пути и обновляет узлы, если к ним найден лучший путь. Для реализации, список Open с очередью FIFO заменяется приоритетной очередью, где извлеченный узел имеет лучшее значение – здесь, это наименьшая стоимость пути от старта (см. прил. А). На рисунке 3.9 показана хорошая адаптация алгоритма к стоимости местности. Однако, он имеет слабость поиска в ширину, игнорируя направление к цели.



Рисунок 3.9 – Алгоритм Дийкстры
3.2.4 Поиск в глубину

Этот поиск противоположен поиску в ширину. Вместо посещения вначале всех соседей, а потом их наследников, он сначала посещает всех наследников, а только затем переключается на соседей. Для уверенности в том, что поиск закончится, необходимо предусмотреть остановку на определенной глубине. Можно использовать тот же самый код, что и в поиске в ширину, если добавить параметр для отслеживания глубины каждого узла и заменить Open с очереди FIFO на стек LIFO (last-in-first-out). На самом деле можно полностью избавиться от списка Open и вместо этого сделать поиск рекурсивной подпрограммой, что уменьшит расход памяти использованной под Open. Необходимо, чтобы каждая ячейка маркировалась как «посещенная» при продвижении в глубь и эта пометка снималась на обратном ходу, чтобы избежать генерации путей, которые посещают дважды одну и ту же ячейку. На рисунке 3.10 можно заметить, что этого недостаточно, алгоритм все равно может путаться вокруг себя и тратить время на бессмысленные пути. Для геометрического поиска пути можно сделать два дополнения. Первое будет заключаться в добавлении метки на каждую ячейку с длиной найденного к ней кратчайшего пути; алгоритм больше не посетит эту ячейку пока не будет иметь к ней путь с меньшей стоимостью. Другое заключается в выборе вначале соседей, которые ближе к цели. С этими двумя дополнениями, можно заметить, что поиск в глубину быстро найдет путь. Могут обрабатываться даже взвешенные пути, если сделать остановку по общей накопленной стоимости вместо общего расстояния.

Рисунок 3.10 – Поиск в глубину

3.2.5 Алгоритм последовательных приближений при поиске в глубину

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

3.2.6 Алгоритм «лучший-первый»

Это первый рассматриваемый эвристический поиск, который принимает во внимание знания о пространстве поиска для направления своих усилий. Он похож на алгоритм Дийкстры, за исключением того, что узлы в списке Open оцениваются по приблизительному оставшемуся расстоянию до цели. Эта оценка так же не требует наличия обновлений, в отличие от алгоритма Дийкстры. Рисунок 3.11 показывает работу алгоритма. Это самый быстрый из всех планирующих алгоритмов рассмотренных ранее, который направляется по прямой к цели. Он так же имеет и свои слабости. На рисунке 3.12, показано, что он не принимает во внимание накопленную стоимость пути, направляясь по прямой через зону с высокой стоимостью, а не обходя ее. И на можно увидеть, что найденный путь вокруг препятствия не прямой, а изгибается вокруг препятствия на манер алгоритма трассировки, рассмотренного ранее.


Рисунок 3.11 – Алгоритм «лучший-первый»

Рисунок 3.12 – Недостаток алгоритма
3.3 Алгоритм А*

Наилучшим алгоритмом для поиска оптимальных путей в различных пространствах является A* (читается как «А-звездочка»). Этот эвристический поиск сортирует все узлы по приближению наилучшего маршрута идущего через этот узел. Типичная формула эвристики выражается в виде:

f(n) = g(n) + h(n),
где f(n) –значение оценки, назначенное узлу n;

g(n) – наименьшая стоимость прибытия в узел n;

h(n) – эвристическое приближение стоимости пути к цели от узла n.
Таким образом, этот алгоритм сочетает в себе учет длины предыдущего пути из алгоритма Дийкстры с эвристикой из алгоритма «лучший-первый». Алгоритм хорошо отражен в приложении А. Так как некоторые узлы могут обрабатываться повторно (для поиска оптимальных путей к ним позднее) необходимо ввести новый список Closed для их отслеживания. A* имеет множество интересных свойств. Он гарантированно находит кратчайший путь, до тех пор пока эвристическое приближение h(n) является допустимым, то есть он никогда не превышает действительного оставшегося расстояния до цели. Этот алгоритм наилучшим образом использует эвристику: ни один другой алгоритм не раскроет меньшее число узлов, не учитывая узлов с одинаковой стоимостью. На рисунках 3.13, можно увидеть как A* справляется с ситуациями проблемными для других алгоритмов.

Рисунок 3.13 – Алгоритм А*

3.3.1 Гибкость А*

На практике A* оказывается очень гибким. Рассмотрим различные части алгоритма. Состоянием зачастую является ячейка или позиция, которую занимает объект. Но при необходимости, состоянием с таким же успехом может быть ориентация и скорость (например, при поиске пути для танка или любой другой машины – их радиус поворота становится хуже при большей скорости).

Соседние состояния могут изменяться в зависимости от игры и локальной ситуации. Смежные позиции могут быть исключены, потому что они непроходимы. Некоторые типы местности могут быть непроходимыми для некоторых объектов, но проходимыми для других; объекты, которые медленно разворачиваются, не могут перемещаться во все соседние клетки.

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

Приближение обычно равняется минимальному расстоянию между текущим узлом и целью умноженному на минимальную стоимость передвижения между узлами. Это гарантирует допустимость эвристики h(n). (На карте с квадратными клетками, где объекты могут занимать только точки на сетке, минимальным расстоянием будет не геометрическое расстояние, а минимальное число ортогональных и диагональных перемещений между двумя точками.)

Цель не обязательно должна быть единственной позицией, но может состоять из множества позиций. Тогда приближение должно равняться минимуму приближений ко всем возможным целям. Указание пределов по стоимости пути или по расстоянию, или по обоим признакам может быть легко реализовано. Из моего непосредственного опыта я знаю, что А* хорошо работает для большого числа типов путей в военных играх (wargames) и стратегиях.

3.3.2 Ограничения A*

Существуют ситуации, в которых A* не может работать хорошо по различным причинам. Требования работы в реальном масштабе времени для некоторых игр, плюс ограничения по памяти и процессорному времени в некоторых из них, создают проблемы для хорошей работы даже для А*. Большая карта может требовать тысячи ячеек в списках Open и Closed, для чего может оказаться недостаточно места. Даже если для них окажется достаточно памяти, алгоритмы для работы с этими списками могут оказаться неэффективными.

Качество работы алгоритма сильно зависит от качества эвристического приближения h(n). Если h близко к истинной стоимости оставшегося пути, то эффективность будет очень высокой; с другой стороны, если h будет слишком низким, то это отразится на эффективности в худшую сторону. На самом деле, алгоритм Дийкстры – это A* с h установленной в ноль для всех узлов – это конечно будет допустимым приближением и этот алгоритм найдет путь, но это будет очень медленно. На рисунке 3.14, можно увидеть что при поиске в зоне с повышенной стоимостью (затененная зона), фронт просмотренных узлов похож на фронт в алгоритме Дийкстры; на рисунке 3.15 при увеличении эвристики стал более сфокусированным.

Рисунок 3.14 – Поиск в зоне с повышенной стоимостью

Рисунок 3.15 – Поиск в зоне с повышенной стоимостью с увеличенной эвристикой
3.3.3 Иерархический поиск

Рассмотрим способы, как добиться от A* большей эффективности в рассматриваемых областях.

Возможно самой главной оптимизацией, которую только можно сделать, является реструктуризация проблемы в более простую. Макрооператоры – это последовательности шагов, которые принадлежат друг другу и могут быть объединены в один шаг, заставляя поиск делать большие шаги за один раз. Например, самолеты делают серию шагов для того, чтобы изменить свои положение и высоту. Общая последовательность может быть использована как одно изменение состояния, вместо множества маленьких отдельных шагов. В дополнение к сказанному, поиск и общие методы решения задач могут быть значительно упрощены, если они будут разбиты на подзадачи, индивидуальное решение каждой из которых довольно простое. В случае поиска пути, карта разбивается на большие непрерывные области, чья связность известна. Выбирается одна или две граничных ячейки, которые находятся между двумя смежными областями; затем поиск производится между смежными областями, в каждой из которых путь находится для граничных ячеек.

Например, в стратегической карте Европы, планировщик пути прокладывающий путь из Мадрида в Афины может с большой вероятностью потратить кучу времени на обработку итальянского «сапога». Используя страны в качестве областей, иерархический планировщик сначала определит, что путь должен следовать из Испании во Францию, затем в Италию, и из Югославии (если смотреть на старую карту) в Грецию; и затем путь через Италию должен вести от границей между Италией и Францией до границы между Италией и Югославией. В качестве другого примера можно привести путь из одной части здания в другое, который может быть разбит на пути между комнатами и коридорами и пути между дверьми в каждой комнате.

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

3.3.4 Оптимизация А*

Существует несколько способов изменить алгоритм поиска, чтобы получить хорошие результаты при использовании ограниченных ресурсов:

Лучевой поиск. Одним из способов борьбы с ограничением по памяти является наложение ограничений на количество узлов в списке Open; когда список полон и необходимо добавить новый узел, просто выбрасывается узел с наихудшим значением. Список Closed также может быть уничтожен, если каждая ячейка хранит в себе длину наилучшего пути и обратный указатель. Этот алгоритм не гарантирует оптимальности пути, так как узел ведущий к нему может быть выброшен, но все равно может позволить найти разумный путь.

Алгоритм последовательных приближений для A* (IDA*). Алгоритм последовательных приближений, использованный для IDDFS, как упоминалось ранее, может быть использован и для A*. Это полностью избавляет от необходимости хранить списки Open и Closed. Делается простой рекурсивный поиск, собирается наколенная стоимость пути g(n), и поиск прекращается при достижении значением f(n) = g(n) + h(n) заданных пределов. Начинать нужно с пределом остановки равным h(start), и в каждой последовательной итерации, устанавливать новый предел остановки равным минимальному значению f(n), которое превысило прежнюю границу. Аналогично для IDDFS среди методов полного перебора, IDA* – асимптотически оптимален в расходе времени и памяти среди эвристических методов.

Недопустимая эвристика h(n). Как обсуждалось выше, если эвристическое приближение оставшейся стоимости пути слишком мало, то A* может быть очень неэффективным. Но если приближение слишком высоко, то для найденного пути не гарантируется оптимальность. В играх в которых диапазон изменения стоимостей ландшафта широк – от болот до автострад – можно поэкспериментировать с различными промежуточными значениями, чтобы найти точный баланс между эффективностью поиска и качеством найденного пути.

Существуют и другие модификации A*, однако они не подтвердили свою полезность для поиска пути в геометрическом пространстве.

4 ПРОЕКТИРОВАНИЕ И РАЗРАБОТКА АЛГОРИТМА

4.1 Проектирование

Главной целью дипломной работы является проектирования и разработка алгоритма сложного поиска пути, с высокой скоростью расчета, с большим пространством и с разными уровнями проходимости. Ярким примером являются компьютерные игры жанра RTS, другие жанры в рамках этой работы нам неинтересны.

Определения:

  • старт - точка начала пути;

  • финиш - точка конца пути;

  • решение - точка (кроме старта и финиша), гарантированно входящая в путь, или ее отсутствие, если на пути нет препятствий;

  • карта проходимости - карта/массив, хранящий уровень проходимости участков игровой карты. В самом простом случае - карта, хранящая бинарный лабиринт;

  • опорная точка - центр объекта; точка местонахождения объекта.

  • левая / правая рука - "человек", двигающийся в лабиринте, держась за стену левой / правой рукой;

  • юнит – движущий игровой объект;

  • техника - живые или механические большие юниты.

После анализа желаемого поведения юнитов в игре были выведены требования к поиску путей:

  1. высокая скорость расчета: многотысячные армии; сотни солдат должны рассчитывать себе путь каждую секунду;

  2. большие пространства: большая игровая карта, преодолеваемая солдатом за большое время;

  3. движение в любом направлении, остановка в любом месте: отсутствие видимых ячеек карты, свободное движение солдат; cолдат может находиться в любом месте ячейки;

  4. погрешность: допустима погрешность в найденном пути, но она не должна быть значительной;

  5. прямые пути: рассчитанный путь представляет собой ломаную линию;

  6. солдат безразмерный: солдат занимает минимальный размер - 1 ячейку;

  7. поиск пути для техники: алгоритм, аналогичный поиску пути для солдат; техника, в отличие от солдата, имеет определенный размер;

  8. разные уровни проходимости: пехота может проходить сквозь пехоту и мелкую растительность; техника движется только сквозь мелкую растительность; амфибии рассчитывают путь, как по земле, так и по воде;

  9. достаточное расстояние до цели: расстояние до финиша, которое преодолевать необязательно. Рабочему, идущему строить здание, не нужно доходить до здания (до опорной точки, центра здания) расстояние равное радиусу здания;

  10. случаи невозможных путей: в случае невозможности рассчитать путь к финишу найти ближайшую доступную точку к финишу;

  11. один слой проходимости: юниты не могут двигаться один над другим (не считая летающих юнитов); если можно двигаться по мосту, значит нельзя под мостом;

  12. динамическая перестройка пространства: карта проходимости может существенно изменяться каждый такт игры.

Для юнитов, двигающихся только в 8 направлениях, занимающих всегда 1 ячейку и останавливающихся только посередине ячеек карты (см. рис. 4.1 и 4.2), поиск пути не является сложной задачей. В проекте было установлено требование №3, значительно усложнявшее алгоритм. Так же требования №1 и №2 не позволяют использовать тяжелые алгоритмы.


Рисунок 4.1 – Простой поиск пути

Рисунок 4.2 – Сложный поиск пути
4.1.1 Недостатки различных алгоритмов для данных требований

Волновой алгоритм и его модификации:

  • большое время расчета;

  • ограниченное количество направлений движения.

A*, алгоритм Дейкстры:

  • недостаточно быстрое время расчета;

  • большой объем памяти для хранения списков.

Navmesh:

  • низкая скорость расчета пути для большого числа юнитов разных размеров и огромной карты проходимости;

  • постоянно изменяющаяся карта проходимости требует регулярного пересчета графа.

Иерархические алгоритмы:

  • перерасчет графа при изменении карты проходимости.

Каждый из этих алгоритмов в зависимости от реализации нарушает тот или иной пункт из требований описанных выше. Волновой алгоритм медленный для огромной карты проходимости, а так же нарушает пункт требований №3. Из перечисленных алгоритмов A* лучше всего подходит для решения этой задачи. Алгоритмы с предрасчитанным графом не подходят в основном из-за пунктов №7 и №12.

Наилучшим алгоритмом, удовлетворяющим всем условиям, оказался обход препятствий по контуру. В большинстве случаев обход препятствий исследует значительно меньшее пространство, и при этом гарантированно находит путь, если он существует. Для такого алгоритма не важно как часто и интенсивно меняется карта проходимости. Так же не имеет значения размер юнита. Этот алгоритм не универсальный и имеет ряд ограничений, но для множества игр жанра RTS он подходит очень хорошо. Его можно использовать как сам по себе, так и в сочетании с другими алгоритмами поиска пути.

4.1.2 Общая идея. Алгоритм

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

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

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

 
4.1.3 Описания алгоритма поиска пути
Алгоритм выглядит следующим образом:

  1. задать точки старта и финиша, скорость движения юнита и его уровень проходимости, достаточное расстояние до финиша;

  2. если юнит заперт со всех сторон и не может двигаться ни в одном направлении, то нет ни одного решения; поиск окончен;

  3. если скорость движения юнита высокая, то делить ее пополам до тех пор, пока она не будет превышать установленный предел; это необходимо для того, чтобы, имея высокую скорость движения, юнит не перескакивал через небольшие препятствия;

  4. провести условный отрезок из старта в финиш; этот отрезок может быть самым коротким путем;

  5. трассировать луч по этому отрезку, проверяя через каждый шаг юнита, не наступил ли он на непроходимую область; если вступил в непроходимую зону, то точку входа в препятствие запомнить, и продолжить трассирование; так же запомнить точку выхода из препятствия; последнего выхода из препятствия может не быть, если финиш находится внутри него;

  6. запомнить все точки входов в препятствия и выходов из них; запомнить значения карты проходимости в точках выхода, а в эти ячейки записать индексы точек выхода;

  7. если точек входа нет, значит, на пути нет препятствий; путь между точками прямой; поиск окончен;

  8. в первой точке входа создать левую и правую руку; обнулить счетчик шагов;

  9. провести условные оси точки финиша: вертикаль и горизонталь;

  10. лучшим решением не считать никакое (ни одного кандидата на лучшее решение еще нет, поиск не начался);

  11. все руки двигаются по периметру своего препятствия на один шаг; левые руки двигаются против часовой стрелки, правые – по часовой;

  12. если какая-либо рука наступила на ось (см. пункт 9) или повернула, встретив препятствие спереди, то считать эту точку кандидатом на ближайшую к финишу точку; если этот кандидат находится на достаточном расстоянии к точке финиша, то дальнейших кандидатов игнорировать;

  13. если какая-либо рука повернула из-за того, что отпустила стену, то считать эту точку кандидатом на лучшее решение (см. рис. 4.3);


Рисунок 4.3 – Описания алгоритма

  1. если встретились две любые разные руки (левая с правой), уничтожить обе руки; если не осталось ни одной руки, то перейти к пункту 19;

  2. если какая-либо рука наступила на точку выхода, где еще никакая другая рука не была (точки выхода изначально имеют индекс, а после посещения рукой, точка выхода помечается специальным образом, запоминая, левая или правая рука туда пришла), то перейти к пункту 17; если рука пришла в точку выхода, где уже побывала другая рука, то, если тут побывала такая же рука, продолжить обход этой руки, иначе уничтожить руку (далее будет описано, зачем необходимо такое усложнение); если не осталось ни одной руки, то перейти к пункту 19;

  3. увеличить счетчик шагов; если счетчик шагов превысил допустимое количество, то перейти к пункту 20, иначе перейти к пункту 11;

  4. уничтожить руку; пометить точку выхода, куда пришла рука, специальным образом в зависимости от того, левая или правая рука туда пришла; если это последняя точка выхода, и далее нет точки входа – прекратить обход и перейти к пункту 18; еначе в следующей точке входа создать правую и левую руку и перейти к пункту 11;

  5. путь к финишу есть; отследить родительскую историю руки, которая пришла к последней точке выхода (родитель руки – рука, в результате обхода которой была создана данная рука); cреди всех кандидатов на лучшее решение этой руки и всех ее предков выбрать лучшее решение (для каждой руки достаточно хранить в памяти одного, лучшего кандидата); лучшим решением считается точка, наиболее далеко лежащая от точек старта и финиша; поиск окончен;

  6. пути к финишу нет. среди всех кандидатов на ближайшую точку к финишу выбрать лучшего – самого ближнего (это лучше делать по мере обнаружения новых кандидатов); поиск окончен;

  7. время на поиск пути вышло. Решением считать лучшего кандидата на ближайшую точку к финишу. Поиск окончен.

Всего  5 возможных исходов работы алгоритма:

  • точка старта заперта со всех сторон; решения нет;

  • препятствий нет, путь прямой;

  • путь к финишу есть; решение – точка, гарантированно входящая в путь; отрезок разбит на 2 отрезка. для каждого отрезка следует снова выполнить поиск пути, если это необходимо;

  • пути к финишу нет; решение – ближайшая к финишу доступная точка; для полученного отрезка нужно снова выполнить поиск пути;

  • время на поиск пути вышло; возможно, лучшее решение еще не найдено; лучшим решением объявляется ближайшая к финишу доступная точка среди всех проверенных; если необходимо, можно повторить поиск с большим временем поиска.

Поиск пути для техники аналогичный, учитывая дополнительно параметр размера.

4.2 Реализация

Существует две системы координат: игровая и путевая. Игровая - это система координат и размеров, принятая в игре. Путевая - система координат для карты проходимости. При инициализации карты проходимости следует указать границы игрового пространства и размер карты проходимости. Независимо от размера, карта проходимости будет накрывать полностью все указанное игровое пространство. Также нужно указать максимальное время поиска пути.

Важно, чтобы размеры мира были пропорциональны размерам массива. Для преобразования координат из одной системы в другую доступны специальные функции. После инициализации создается однобайтовый массив указанного размера. Доступ к нему можно получить напрямую, а можно заполнять его через функции. После окончания работы приложения, карту нужно выгрузить.

Вся техника представляется в форме квадратов. Расчет круглых форм был бы значительно дороже. Прямоугольные формы не подходят из-за того, что юнит может поворачиваться, а поворачивать вслед за ним прямоугольник невозможно.

Размер техники должен быть строго по размеру ячеек карты проходимости. Для преобразования свободного размера, в ближайший допустимый размер предоставлена специальная функция.

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

4.3 Тестирования

Для тестирования алгоритма и визуализации найденного пути была разработана программа (см. рис. 4.4). Она реализована на мультимедийной платформе Adobe Flash, с использованием скриптового языка ActionScript 3, для компиляции и редактирования кода программы был использован скриптовый редактор FlashDeveloper 3.0, для просмотра листинга программы смотреть приложения В . Выбор этого программного пакета основан на доступности, простоте использования и имеющем в полном объеме требуемого функционала для написания данного программного продукта, допустим для реализации графической части и интерфейса программы не требуются дополнительные ресурсы.



Рисунок 4.4 – Утилита для тестирования и визуализации работы алгоритма

4.3.1 Описания работы программы

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

Карта пути загружается из файла map.png и отображается в правой части программы. Там же показываются построенные пути (см. рис. 4.5).



Рисунок 4.5 – Правая часть в программы

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

В левой части программы отображена панель (см. рис. 4.6), для вывода результатов поиска пути. В ней показывается время затраченное на поиск, и координаты точек пути.



Рисунок 4.6 – Панель программы

4.3.2 Руководства использования программы

Для того что бы задать точки начала и конца пути необходимо кликнуть левой кнопкой мыши. Если необходимо задать новую начальную точку нужно нажать на кнопку «Очистить» (см. рис. 4.7). После нажатия кнопки очиститься правая часть программы если путь был до этого задан.



Рисунок 4.7 – Кнопка «Очистить»

4.3.3 Результаты тестирования

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

При тестировании было замерено затраченное время 10 результатов поиска пути (см. рис. 4.8), и вычислено средний показатель, 19 миллисекунд. Этот результат говорит о том, что выполнено главное требования поставленное алгоритму, скорость вычисления пути.



Рисунок 4.8 – Результаты затраченного времени на поиск пути

5 ЭКОНОМИЧЕСКОЕ ОБОСНОВАНИЯ СТОИМОСТИ ПРОГРАММНОГО ПРОДУКТА

Ценообразование
  1   2   3   4

Добавить документ в свой блог или на сайт

Похожие:

В настоящий момент в создании искусственного интеллекта (в первоначальном смысле этого слова, экспертные системы и шахматные программы сюда не относятся) icon Реферат в данном проекте произведена попытка автоматизировать процесс...
Полученное таким образом решение на данный момент не имеет аналогов в нашем университете по дисциплине «Системы искусственного интеллекта»....
В настоящий момент в создании искусственного интеллекта (в первоначальном смысле этого слова, экспертные системы и шахматные программы сюда не относятся) icon Обзор исследований в области искусственного интеллекта
Обзор исследований в области искусственного интеллекта глава представление знаний
В настоящий момент в создании искусственного интеллекта (в первоначальном смысле этого слова, экспертные системы и шахматные программы сюда не относятся) icon Существующее выражение «искусственный интеллект» появилась как дань...
Существующее выражение «искусственный интеллект» появилась как дань артефактам. Человек, преуспел в создании искусственного. Однако...
В настоящий момент в создании искусственного интеллекта (в первоначальном смысле этого слова, экспертные системы и шахматные программы сюда не относятся) icon Как вернуться к жизни
...
В настоящий момент в создании искусственного интеллекта (в первоначальном смысле этого слова, экспертные системы и шахматные программы сюда не относятся) icon «Целостный мир viii» 2014 Секция №1 «В царстве линий, формул и файлов»
Моделирование поведения искусственного интеллекта в редакторе уровней на примере двумерной игры
В настоящий момент в создании искусственного интеллекта (в первоначальном смысле этого слова, экспертные системы и шахматные программы сюда не относятся) icon Дитмар Эльяшевич Розенталь а как лучше сказать?
На вопрос, который поставлен в названии этой книги, вы, юные читатели, получите ответ, прочитав ее. Книга поможет вам повысить речевую...
В настоящий момент в создании искусственного интеллекта (в первоначальном смысле этого слова, экспертные системы и шахматные программы сюда не относятся) icon Рабочая программа дисциплины основы искусственного интеллекта
Программа составлена в соответствии с Государственным образовательным стандартом высшего профессионального образования по педагогическим...
В настоящий момент в создании искусственного интеллекта (в первоначальном смысле этого слова, экспертные системы и шахматные программы сюда не относятся) icon «сутра о нирване» толкование японского буддийского мастера нитирэна
Охватывает три жизни существа: [1]–[2] относятся к прежней жизни, [3]–[7] относятся к нынешней жизни, [8]–[10] относятся к «плодам»...
В настоящий момент в создании искусственного интеллекта (в первоначальном смысле этого слова, экспертные системы и шахматные программы сюда не относятся) icon Возникновение древнерусской литературы
Древняя Русь, в традиционном смысле этого слова, обнимающем страну и ее историю с X по XVII век, обладала великой культурой. Эта...
В настоящий момент в создании искусственного интеллекта (в первоначальном смысле этого слова, экспертные системы и шахматные программы сюда не относятся) icon Биография одного слова Тема
А задумывались ли вы, ребята, о происхождении, строении, значении слова Родина”? Сегодня я вам предлагаю познакомиться с биографией...
Литература


При копировании материала укажите ссылку © 2015
контакты
literature-edu.ru
Поиск на сайте

Главная страница  Литература  Доклады  Рефераты  Курсовая работа  Лекции