Войти
Эквивалентные пути между A и B в 2D-среде Поиск пути или pathing - это построение компьютерным приложением кратчайшего маршрута между двумя точками. Это более практичный вариант решения лабиринтов. Эта область исследований в значительной степени основана на алгоритме Дейкстры для поиска кратчайшего пути на взвешенном графе.
Поиск пути тесно связан с проблемой кратчайшего пути, в пределах теория графов, в которой изучается, как определить путь, который лучше всего соответствует некоторым критериям (самый короткий, самый дешевый, самый быстрый и т. д.) между двумя точками в большой сети.
По своей сути, метод поиска пути выполняет поиск граф , начиная с одной вершины и исследуя соседние узлы до тех пор, пока не будет достигнут целевой узел, как правило, с намерением найти самый дешевый маршрут. Хотя методы поиска по графу, такие как поиск в ширину, найдут маршрут, если у них будет достаточно времени, другие методы, которые «исследуют» граф, будут стремиться достичь пункта назначения раньше. Аналогия: человек, идущий по комнате; вместо того, чтобы заранее исследовать все возможные маршруты, человек обычно идет в направлении пункта назначения и отклоняется от пути только для того, чтобы избежать препятствия, и делает отклонения как можно более незначительными.
Две основные проблемы поиска пути: (1) найти путь между двумя узлами в графе ; и (2) задача кратчайшего пути - найти оптимальный кратчайший путь. Базовые алгоритмы, такие как поиск в ширину и в глубину, решают первую проблему, исчерпывая все возможности; начиная с данного узла, они перебирают все возможные пути, пока не достигнут конечного узла. Эти алгоритмы выполняются за 
Более сложная проблема - найти оптимальный путь. Исчерпывающий подход в этом случае известен как алгоритм Беллмана – Форда, который дает временную сложность 
Вышеупомянутые алгоритмы являются одними из лучших общих алгоритмов, которые работают с графом без предварительной обработки. Однако в практических системах маршрутизации путешествий даже лучшие временные сложности могут быть достигнуты с помощью алгоритмов, которые могут предварительно обрабатывать график для достижения лучшей производительности. Одним из таких алгоритмов является сжатие иерархий.
Распространенным примером алгоритма поиска пути на основе графа является алгоритм Дейкстры. Этот алгоритм начинается с начального узла и «открытого набора» узлов-кандидатов. На каждом шаге исследуется узел в открытом множестве с наименьшим расстоянием от старта. Узел помечается как «закрытый», и все соседние с ним узлы добавляются в открытый набор, если они еще не были исследованы. Этот процесс повторяется до тех пор, пока не будет найден путь к месту назначения. Поскольку в первую очередь проверяются узлы с наименьшим расстоянием, при первом нахождении пункта назначения путь к нему будет кратчайшим.
Алгоритм Дейкстры не работает, если имеется отрицательный вес edge. В гипотетической ситуации, когда узлы A, B и C образуют связный неориентированный граф с ребрами AB = 3, AC = 4 и BC = −2, оптимальный путь от A до C стоит 1, а оптимальный путь от A до B стоит 2. Алгоритм Дейкстры, начиная с A, сначала исследует B, так как он является ближайшим. Он присвоит ему стоимость 3 и пометит его закрытым, что означает, что его стоимость никогда не будет переоценена. Следовательно, метод Дейкстры не может оценивать отрицательные веса ребер. Однако, поскольку для многих практических целей отрицательного веса ребра никогда не будет, алгоритм Дейкстры в значительной степени подходит для целей поиска пути.
A* - это вариант алгоритма Дейкстры, обычно используемый в играх. A * присваивает вес каждому открытому узлу, равному весу края этого узла плюс приблизительное расстояние между этим узлом и финишем. Это приблизительное расстояние определяется эвристикой и представляет собой минимально возможное расстояние между этим узлом и концом. Это позволяет исключить более длинные пути после нахождения исходного пути. Если между началом и концом есть путь длиной x, а минимальное расстояние между узлом и концом больше x, этот узел не нужно проверять.
A * использует эту эвристику для улучшения поведение относительно алгоритма Дейкстры. Когда эвристика дает нулевое значение, A * эквивалентен алгоритму Дейкстры. По мере того как эвристическая оценка увеличивается и приближается к истинному расстоянию, A * продолжает находить оптимальные пути, но работает быстрее (за счет проверки меньшего количества узлов). Когда значение эвристики точно соответствует истинному расстоянию, A * проверяет наименьшее количество узлов. (Однако, как правило, нецелесообразно писать эвристическую функцию, которая всегда вычисляет истинное расстояние, так как тот же результат сравнения часто можно получить с помощью более простых вычислений - например, используя Манхэттенское расстояние на Евклидово расстояние в двумерном пространстве.) По мере увеличения значения эвристики A * проверяет меньше узлов, но больше не гарантирует оптимальный путь. Во многих приложениях (таких как видеоигры) это приемлемо и даже желательно, чтобы алгоритм работал быстро.
Это довольно простой и понятный алгоритм поиска пути для тайловых карт. Для начала у вас есть карта, координаты начала и координаты пункта назначения. Карта будет выглядеть так: X- стены, S- начало, O- конец, а _- открытые пространства, числа по верхнему и правому краям - это номера столбцов и строк:
1 2 3 4 5 6 7 8 XXXXXXXXXXX _ _ _ XX _ X _ X 1 X _ X _ _ X _ _ _ X 2 XSXX _ _ _ X _ X 3 X _ X _ _ X _ _ _ X 4 X _ _ _ XX _ X _ X 5 X _ X _ _ X _ X _ X 6 X _ XX _ _ _ X _ X 7 X _ _ O _ X _ _ _ X 8 XXXXXXXXXX
Сначала создайте список координат, который мы будем использовать в качестве очереди. Очередь будет инициализирована одной координатой, конечной координатой. К каждой координате также будет прикреплена переменная счетчика (цель этого скоро станет очевидной). Таким образом, очередь начинается как ((3,8,0)).
Затем просмотрите все элементы в очереди, включая элементы, добавленные в конец в ходе алгоритма, и для каждого элемента выполните следующие действия:
Таким образом, после хода 1 список элементов следующий: ((3,8,0), (2,8,1), (4,8,1))
Теперь сопоставьте счетчики на карте, получив следующее:
1 2 3 4 5 6 7 8 XXXXXXXXXXX _ _ _ XX _ X _ X 1 X _ X _ _ X _ _ _ X 2 XSXX _ _ _ X _ X 3 X 6 X 6 _ X _ _ _ X 4 X 5 6 5 XX 6 X _ X 5 X 4 X 4 3 X 5 X _ X 6 X 3 XX 2 3 4 X _ X 7 X 2 1 0 1 X 5 6 _ X 8 XXXXXXXXXX
Теперь начните с S (7) и перейдите к соседняя ячейка с наименьшим номером (непроверенные ячейки нельзя переместить). Прослеживаемый путь: (1,3,7) ->(1,4,6) ->(1,5,5) ->(1,6,4) ->(1,7,3) ->( 1,8,2) ->(2,8,1) ->(3,8,0). В случае, если два числа одинаково малы (например, если S было в (2,5)), выберите случайное направление - длины одинаковы. Теперь алгоритм завершен.
Крис Кроуфорд в 1982 году описал, как он «потратил много времени», пытаясь решить проблему с поиском пути в Tanktics, в котором компьютер учитывал оказались в ловушке на суше в U-образных озерах. «После многих потраченных впустую усилий я нашел лучшее решение: удалить U-образные озера с карты», - сказал он.
Quadtrees можно использовать для иерархического поиска путей Идея была впервые описана индустрией видеоигр, у которой возникла потребность в планировании на больших картах с небольшим количеством процессорного времени. Концепция использования абстракции и эвристики старше и впервые упоминалась под названием ABSTRIPS (Abstraction-Based STRIPS ), которая использовалась для эффективного поиска в пространствах состояний логических игр. Похожая техника - это навигационные сетки (navmesh), которые используются для геометрического планирования в играх, и мультимодальное планирование транспортировки, которое используется в задачах коммивояжера с более чем одно транспортное средство.
Карта разделена на кластеры. На высокоуровневом слое планируется путь между кластерами. После того, как план был найден, планируется второй путь в кластере на нижнем уровне. Это означает, что планирование выполняется в два этапа: управляемый локальный поиск в исходном пространстве. Преимущество состоит в том, что количество узлов меньше, и алгоритм работает очень хорошо. Недостатком является то, что иерархический планировщик путей сложно реализовать.
A map имеет размер 3000x2000 пикселей. Планирование пути на основе пикселей заняло бы очень много времени. Даже эффективный алгоритм должен будет вычислить множество возможных графиков. Причина в том, что такая карта будет содержать в целом 6 миллионов пикселей, а возможности исследования геометрического пространства чрезвычайно велики. Первым шагом для иерархического планировщика путей является разделение карты на более мелкие суб-карты. Каждый кластер имеет размер 300x200 пикселей. Общее количество кластеров 10x10 = 100. Во вновь созданном графе количество узлов невелико, можно перемещаться между 100 кластерами, но не внутри подробной карты. Если действительный путь был найден в графе высокого уровня, следующим шагом будет планирование пути в каждом кластере. Подкарта имеет размер 300x200 пикселей, что может быть легко обработано обычным планировщиком путей A *.
Многоагентный поиск пути предназначен для поиска путей для несколько агентов из их текущих местоположений в их целевые местоположения, не сталкиваясь друг с другом, в то же время оптимизируя функцию стоимости, такую как сумма длин путей всех агентов. Это обобщение поиска пути. Многие многоагентные алгоритмы поиска пути являются обобщением A * или сводятся к другим хорошо изученным задачам, таким как целочисленное линейное программирование. Однако такие алгоритмы обычно неполны; другими словами, не доказано, что решение может быть получено за полиномиальное время. Другая категория алгоритмов жертвует оптимальностью ради производительности, используя известные шаблоны навигации (например, поток трафика) или топологию проблемного пространства.
