Поиск путей в сложных полигонах для динамических систем реального времени. Работа Порошина И.А., 544 гр. Научный руководитель Уфнаровский В.В. Рецензент, доцент кафедры информатики, к.ф.-м.н.Соловьёв И.П. Математико-механический факультет СПбГУ, 2007г.

Постановка задачи поиска пути для систем виртуальной реальности Симуляторы, системы визуализации, игры СРВ с высокой частотой обновления Интеллектуальные агенты с возможностью передвижения Задача поиска пути в R 3 NP-трудна Ограничение свободы перемещения навигационными поверхностями

Поиск путей в сложных полигонах C free = cl ( U {Loc i } \ U {Obst j }) –Loc i (помещения) и Obst j (препятствия) – многоугольники с конечным числом вершин –Все помещения попарно дизъюнктны, все препятствия попарно дизъюнктны –Каждое препятствие полностью содержится в некотором помещении –Границей является семейство ломаных (стены) –Никакие две стены не имеют общих точек, кроме пар стен, инцидентных одной и той же вершине Loc 1 Loc 2 Obst 2 Obst 1

Граф видимостей и его использование при поиске кратчайших путей Построение статической части графа видимостей Достроение динамической части графа А*, эвристика – евклидово расстояние до конца пути

Недостатки базового алгоритма Сложный процесс достроения графа (в среднем сложнее поиска пути в графе) Ловушки для евклидовой эвристики Избыточность поиска всего пути Распределение вычислений во времени

Метод обзоров View(A) – множество вершин графа видимостей, видимых из А View(A i )View(A i+1 ) Средняя вычислительная сложность О(|A i A i+1 |*ρ 2 ) при смене направления, в большинстве случаев О(1) при сохранении направления

Метод зонирования пространства Основная цель – улучшение используемой эвристики Известные методы декомпозиции не подходят Метод трапецийМетод квадратов Требуемое разбиение

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

Кусочное построение путей Границы между зонами – двери Двери – последовательность промежуточных целей Увеличение длины пути на суммарную длину пересекаемых дверей Выбор промежуточной цели на основании «графа видимостей» для множества дверей

Оптимизация базового алгоритма Метод обзоров Метод зон Достроение графа Ловушки для эвристики Избыточность поиска всего пути Распределение вычислений во времени

Результаты работы Проанализированы существующие методы поиска путей в системах виртуальной реальности Выявлены основные недостатки используемого подхода Предложено два способа оптимизации Проведено доказательство корректности новых методов, даны оценки потери точности и вычислительной сложности. Новый метод реализован в рамках реально действующей системы для навигации персонажей в игре, разрабатываемой компанией «Мадиа» по заказу компании «Новый Диск»