Содержание

1 Введение 1

1.1 Оцифрованые карты 1

1.1.1 Растровые данные 2

1.1.1.1 Растр класса местности 2

1.1.1.2 Растр от высоты 2

1.1.2 Геометрические данные 3

1.1.2.1 Векторы путей 3

1.1.2.2 Препятствия 3

1.2 Поставка задачи 3

1.3 Цель 4

1.4 Обзор работы 4

2 Обзор методов поиска пути 5

2.1 Методы пересечения линий 5

2.2 Методы на взвешенном графе 5

2.3 Другие методы 6

3 Построение графа 7

3.1 Упрощение задачи 7

3.1.1 Ограничение пространства поиска 7

3.1.1.1 Ограничение области поиска 7

3.1.1.2 Разделение пространства на ячейки 8

3.1.1.3 Ограничение перемещений на гранях 9

3.1.2 Введение в функцию стоимости 10

3.1.2.1 Местность 11

3.1.2.2 Дороги 12

3.1.2.3 Наклоны 13

3.1.2.4 Препятствия 14

3.1.2.5 Враги 15

3.1.2.6 Пределы ошибок 15

3.2 Эффективное представление графа 18

3.2.1 Неявное представление графа 18

3.2.2 Вычисление функции стоимости 19

3.2.2.1 Местность 19

3.2.2.2 Дороги 20

3.2.2.3 Наклоны 20

3.2.2.4 Препятствия 20

3.2.2.5 Враги 20

3.2.3 Размер памяти 21

3.2.4 Пример реализации 22

4 Алгоритмы поиска 24

4.1 Обзор методов 24

4.1.1 Полный перебор 24

4.1.2 Релаксационные методы 25

4.1.3 Линейное программирование 25

4.1.4 Моделирование обжига 25

4.2 Алгоритм 26

4.2.1 Дийкстры алгоритм 27

4.2.2 A* эвристическое уточнение 28

4.2.3 Реконструкция пути 30

4.2.4 Уход от направленного смещения 30

4.2.5 Память и время 31

4.2.6 Простейшая реализация 32

4.3 Прогрессивная аппроксимация 36

5 Примеры 38

5.1 Уход от препятствий 38

5.2 Уход от врагов 39

5.3 Движение по дорогам 40

5.4 Область поиска A* 41

5.5 Прогрессивная аппроксимация 42

5.6 Разное 43

6 Заключение 44

6.1 Общие заключения 44

6.2 Поле для будущей работы 44

6.2.1 Динамические сцены 44

6.2.2 Увеличение числа граней 45

6.2.3 Быстрые пути определения видимости 45

6.2.4 Приблизительные пути, использующие не-оптимальную эвристику A* 45

6.2.5 Другие методы поиска на графе 46

7 Библиография 47

1