Интеллектуальный поиск путей на графах. Обзор алгоритмов, применение в компьютерных играх Факультет ВМК Кафедра МО ЭВМ Нижегородский государственный университет им. Н. И. Лобачевского Национальный исследовательский университет Выполнили : Сударикова М. А. Филичев Т. А г.

Введение Алгоритм поиска пути на графе, начиная с некоторой стартовой вершины, исследует достижимые из нее узлы до тех пор, пока не будет найдена конечная вершина. Задача поиска путей на графе обычно возникает при необходимости составления оптимального маршрута, и может встречаться в экономике, робототехнике и компьютерных играх ( стратегии реального времени ). В практике компьютерных игр часто возникает необходимость проложить курс из одной в другую точки игрового поля с отмеченными на нем непроходимыми областями. Примером может стать движение бота к персонажу игрока. 2 Сударикова М. А. Филичев Т. А. Поиск путей на графах. Обзор алгоритмов.2

Основные понятия Путем называется последовательность вершин в графе G = (V, Е ), такая что каждое из ребер находится в наборе Е. Вес пути это сумма весов каждого ребра пути : Вес ( и, v) кратчайшего пути из вершины и в вершину v это минимум весов всех возможных путей из и в v. Кратчайшим путем называется любой путь, вес которого равен весу кратчайшего пути 3 Сударикова М. А. Филичев Т. А. Поиск путей на графах. Обзор алгоритмов.3

Дискретная модель На карту накладывается дискретная сетка Перемещение по карте - перемещение по клеткам сетки Математическая модель - ориентированный граф, вершины которого соответствуют клеткам, а рёбра возможностям перехода из одной клетки в другую. Каждому ребру можно назначить стоимость перехода - препятствие - свободная клетка 4 Сударикова М. А. Филичев Т. А. Поиск путей на графах. Обзор алгоритмов.4

Непрерывная модель Положение объектов на карте определяется их геометрической формой и взаимным расположением Вводится набор абстракций, например : точки видимости ( на рисунке ) выпуклые полигоны квадрантные деревья 5 Сударикова М. А. Филичев Т. А. Поиск путей на графах. Обзор алгоритмов.5

Обход препятствий 1.Пока цель не достигнута 2.Выбрать направление в сторону цели 3.Если сделать шаг невозможно ( встретили препятствие ) 4.Применить стратегию обхода Принцип работы алгоритма : Стратегии обхода : 1.Случайный выбор направления 2.Обход по контуру ( трассировка препятствия ) - путь поиска 6 Сударикова М. А. Филичев Т. А. Поиск путей на графах. Обзор алгоритмов.6

Обход препятствий 1.Простота реализации 2.Учет взаимного расположения стартовой и финишной точки на карте Достоинства : Недостатки : 1.При неверном выборе стратегии обхода препятствий результат может быть не получен 2.Алгоритм не применим на случай взвешенных областей - путь поиска 7 Сударикова М. А. Филичев Т. А. Поиск путей на графах. Обзор алгоритмов.7

Поиск в ширину 8 Поиск в ширину обход графа, который посещает все вершины, достижимые из данной исходной вершины. Порядок посещения вершин определяется расстоянием от исходной вершины до каждой вершины графа. Процедура поиска в ширину Procedure BFS(a) Q – очередь открытых вершин V(x) – вершины, смежные с x 1. посетить вершину a 2. a Q; 3. x Q 4. for y V(x) do 5. исследовать ребро (x,y) 6. if вершина y новая 7. then посетить вершину y 8. y Q Время работы процедуры BFS(a) есть O(m), где m - число ребер в компоненте связности, содержащей вершину. Максимальное число ребер, т. е. сложность Для графов с небольшим числом ребер предпочтительнее задание графа списками смежности Если веса ребер одинаковы, то поиск в ширину находит кратчайший путь Сударикова М. А. Филичев Т. А. Поиск путей на графах. Обзор алгоритмов.8

Поиск в ширину. Пример. 9 На каждом шаге алгоритма происходит обработка 1 активной вершины Путь длины L+1 не может быть найден раньше пути длины L Двунаправленный поиск в ширину Такой поиск улучшает простой поиск в ширину тем, что запускаются два одновременных поиска в ширину из стартового и конечного узлов и останавливается, когда узел из одного фронта поиска находит соседний узел из другого фронта. Сударикова М. А. Филичев Т. А. Поиск путей на графах. Обзор алгоритмов.9

Поиск в глубину 10 Поиск в глубину - обход графа, при этом на очередном шаге выбирается смежная с текущей еще не посещенная вершина, пока не будет достигнута вершина у которой нет смежных не посещенных вершин. Затем поиск возвращается к предыдущей вершине и продолжает идти вдоль еще не исследованных ребер, выходящих из этой вершины. Процедура поиска в глубину Procedure DFS(a) S – стек открытых вершин 1. посетить вершину a; a S; 2. While S!= 3. x = top(S) 4. if неисследованное ребро (x,y) 5. исследовать ребро (x,y) 6. if вершина y новая 7. then посетить вершину y; y S 8. Если нет неисследованных ребер x S; Время работы процедуры DFS(a) есть O(m), где m - число ребер в компоненте связности, содержащей вершину или, n – число вершин в графе. Путь, найденный поиском в глубину не обязательно является кратчайшим. При выборе очередной вершины можно учитывать оставшееся расстояние до цели. Сударикова М. А. Филичев Т. А. Поиск путей на графах. Обзор алгоритмов.10

Поиск в глубину. Пример. 11 На каждом шаге алгоритма происходит обработка 1 активной вершины Сударикова М. А. Филичев Т. А. Поиск путей на графах. Обзор алгоритмов.11

Алгоритм Дейкстры 12 Алгоритм Дейкстры находит все кратчайшие пути взвешенного графа с неотрицательными весами из исходной вершины до каждой вершины графа, последовательно наращивая множество вершин S, для которых известен кратчайший путь Алгоритм : Q – приоритетная очередь 1. x E d(x) = ; d(a) = 0; a Q 2. while Q 3. x = min(Q); // x Q выбираем элемент с минимальной меткой. 4. for y ϵ V(x) 5. if y – новая, d(y) = d(x)+w(x,y), y Q 6. else d(y) = min(d(y), d(x)+w(x,y)); В общем случае сложность алгоритма На каждом шаге для вершин, изъятых из очереди уже найден кратчайший путь. Примени для использования во взвешенных областях Игнорирует направление к цели Сударикова М. А. Филичев Т. А. Поиск путей на графах. Обзор алгоритмов.12

Алгоритм Дейкстры. Пример стартовой вершине проставляется метка = 0, остальным = Сударикова М. А. Филичев Т. А. Поиск путей на графах. Обзор алгоритмов.13

Алгоритм Дейкстры. Пример стартовой вершине проставляется метка = 0, остальным = 2.Обновляем метки в вершинах, смежных с «0» Сударикова М. А. Филичев Т. А. Поиск путей на графах. Обзор алгоритмов.13

Алгоритм Дейкстры. Пример стартовой вершине проставляется метка = 0, остальным = 2.Обновляем метки в вершинах, смежных с «0» 3.Выбираем вершину с минимальной меткой ( среди зеленых ). Обновляем метки для смежных вершин Сударикова М. А. Филичев Т. А. Поиск путей на графах. Обзор алгоритмов.13

Алгоритм Дейкстры. Пример стартовой вершине проставляется метка = 0, остальным = 2.Обновляем метки в вершинах, смежных с «0» 3.Выбираем вершину с минимальной меткой ( среди зеленых ). Обновляем метки для смежных вершин 4.Если есть еще зеленые, выполнить шаг 3. Сударикова М. А. Филичев Т. А. Поиск путей на графах. Обзор алгоритмов.13

Эвристические алгоритмы 14 Алгоритм « лучший - первый » Алгоритм использует знание о пространстве поиска ; Работает как алгоритм Дейкстры, но применяет другую тактику выбора вершины ; Всегда направляется к цели, но не учитывает накопленной стоимости пути. Алгоритм «A*» поиск оптимального пути сочетает достоинства метода « лучший - первый » и метода Дейкстры ; считается одним из лучших алгоритмов для обоих типов игровых пространств ; Сударикова М. А. Филичев Т. А. Поиск путей на графах. Обзор алгоритмов.14

Алгоритм А * 15 Сортировка узлов по приближению наилучшего маршрута : f(n) = g(n) + h(n) f(n) - значение оценки, назначенное узлу n g(n) - наименьшая стоимость достижения узла n из точки старта h(n) - эвристическое приближение стоимости пути к цели от узла n A* гарантированно находит кратчайший путь, до тех пор пока эвристическое приближение h(n) является допустимым, то есть он никогда не превышает действительного оставшегося расстояния до цели. Приближение обычно равняется минимальному расстоянию между текущим узлом и целью умноженному на минимальную стоимость передвижения между узлами. Это гарантирует допустимость эвристики h(n) Сударикова М. А. Филичев Т. А. Поиск путей на графах. Обзор алгоритмов.15

Алгоритм А * 16 В компьютерных играх за счет приближения стоимости пути можно учесть дополнительные ограничения при перемещении по карте : Цель не обязательно должна быть единственной позицией. Приближение тогда выбирается как минимум приближений ко всем возможным целям Изменение состояний в зависимости от локальной ситуации в игре. Для реализации поиска используются следующие основные структуры данных. 1) представление игровой области. 2) узел или состояние поиска ( координаты, скорость объекта, g(n), h(n), f(n), ссылка на родительский узел и т. д.) 3) Структуры хранения списков посещенных / непосещенных вершин Структура алгоритма аналогична алгоритму Дейкстры Ограничение : большие затраты памяти при большом числе вершин качество сильно зависит от качества приближения h(n) Сударикова М. А. Филичев Т. А. Поиск путей на графах. Обзор алгоритмов.16

Эксперименты (1) 17 Сударикова М. А. Филичев Т. А. Поиск путей на графах. Обзор алгоритмов.17 Поиск в ширину Серия требуемых экспериментов проведена на процессоре Intel серии Core 2 Duo с тактовой частотой 2.53 GHz Граф ориентированный Число ребер в графе = ¼ максимального числа ребер

Эксперименты (2) 18 Сударикова М. А. Филичев Т. А. Поиск путей на графах. Обзор алгоритмов.18 Поиск в глубину Серия требуемых экспериментов проведена на процессоре Intel серии Core 2 Duo с тактовой частотой 2.53 GHz Граф ориентированный Число ребер в графе = ¼ максимального числа ребер

Эксперименты (3) 19 Сударикова М. А. Филичев Т. А. Поиск путей на графах. Обзор алгоритмов.19 Алгоритм Дейкстры Серия требуемых экспериментов проведена на процессоре Intel серии Core 2 Duo с тактовой частотой 2.53 GHz Граф ориентированный Число ребер в графе = ¼ максимального числа ребер

Эксперименты (4) 20 Сударикова М. А. Филичев Т. А. Поиск путей на графах. Обзор алгоритмов.20 Сравнение алгоритмов Серия требуемых экспериментов проведена на процессоре Intel серии Core 2 Duo с тактовой частотой 2.53 GHz Граф ориентированный Число вершин в графе = 4000 Алгоритм Дейкстры Поиск в ширину Поиск в глубину

Список литературы 21 Сударикова М. А. Филичев Т. А. Поиск путей на графах. Обзор алгоритмов Лекции по курсу « Теория графов », Алексеев В. Е. 2. Лекции по курсу « Анализ и разработка алгоритмов », Таланов В. А. 3. Дж. Сик, Л. Ли, Э. Ламсдэйн, С 35 C++ Boost Graph Library. Библиотека программиста / Пер. с английского Сузи Р. СПб.: Питер, с : 4. Материалы курса « Параллельные численные методы », Козинов Е. А., Сиднев А. А. Кафедра математического обеспечения ЭВМ / Н. Новгород, 243 с 5. Лекции интернет - университета. / Intuit ( В. Е. Алексеев, В. А. Таланов, Графы и алгоритмы ) ( 6. Сайт библиотеки BOOST. / ( 7. Алгоритмы, методы, исходники. (

Сударикова М. А. Филичев Т. А. Поиск путей на графах. Обзор алгоритмов.22 Спасибо за внимание