Pull to refresh

Comments 31

А как же A*, в котором есть эвристика? Интересно бы было почитать про возможности нахождения пути с использованием GPU.
Когда я писал эту статью, я забыл упомянуть в заголовке, что я рассматриваю только взвешенные графы.
Разве волновой алгоритм не подходит для любого графа?
Волново́й алгори́тм — алгоритм, позволяющий найти минимальный путь в графе с рёбрами единичной длины.
Не вижу проблем его использовать для ребер разного веса.
в случае взвешенного графа асимптотика что поиска в глубину, что поиска в ширину начинает сильно отличаться от O(e + v) в худшую сторону, грубо говоря мы в каждую вершину вместо одного раза сможем попасть ~v^2 раз каждый раз релаксируя результат и пуская новую волну, что и говорит о его неприменимости для поиска кратчайших путей
Вроде, зависит от реализации?
зависит от теста, и в вашем примере граф невзвешенный, очевидно

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

Практическое применение

Волновой алгоритм — один из основных при автоматизированной трассировке (разводке) печатных плат. Также одно из характерных применений волнового алгоритма — поиск кратчайшего расстояния на карте в стратегических играх.
И да, как правильно заметили, то, что он ориентирован на ребра единичной длинны не мешает модифицировать его для прочих нужд.
В одном своём проекте я использую А* именно в взвешенном графе. Веса неотрицательные. Просто А* не считается базовым с точки зрения математики, потому что там самое важное — эвристическая функция оценки расстояния.
Почему бы для вашего псевдокода не использовать тег source?
<source lang="java">
    <!-- Code here -->
</source>
Спасибо за ваш совет, учту на будущее. К сожалению сейчас править слишком много.
Сделать читабельнее четыре блока кода ради того, чтобы многократно повысить качество статьи?
Простите, но сейчас, имхо, код выглядит как каша — без подсветки, с навязчивыми линиями слева и пропорциональным шрифтом.
Поправил, стало заметно лучше.
К сожалению, А* показывает не очень хорошую скорость. И, например, в стратегии, где надо пускать много юнитов по длинному пути (выбрали пачку из 100 юнитов и шлём на вражескую базу за речкой в другом конце карты) в обычном виде будет страшно глючить.

Я бы с удовольствием почитал об оптимизациях этих алгоритмов. Были мысли о кешировании результата (но как корректно применить кеш, что делать при динамически меняющейся карте) и (бить карту на блоки/использовать контрольные точки). Но всё-же хотелось бы почитать про готовые решения.
Интересно, а какой алгоритм на какой основе показывает лучший результат? А* с хорошей эвристикой, по-моему, лучший алгоритм для нахождения пути на клетчатом поле.
Имхо, тоже, но без оптимизации он слишком медлителен.
Был пример на Флеше. При более менее загруженной карте (а она всего лишь 60*60) — поиск пути для одного юнита — 200 мс:


Тут есть ещё одна дилемма для оптимизации — считать ли первый найденный маршрут самым коротким, или поискать более короткий?
Если соблюдено некое условие для эвристической функции, то алгоритм всегда находит минимальный путь (или один из минимальных). Условие звучит примерно так, что оценка не должна превышать минимально допустимый теоретический путь. Могу ошибаться.
Ну можно искать любой путь, а не самый короткий. Возможно, это будет быстрее, плюс велика вероятность таки нахождения самого короткого пути, но не факт.
К сожалению, А* показывает не очень хорошую скорость.
Базовый — не значит оптимальный или лучший. Хотя А* достаточно сбалансирован для большинства задач. Базовый — это основной или простейший, на котором легко показать основные задачи алгоритма в целом. ИМХО конечно.
Насколько я помню, этот алгоритм оптимизирует решения нескольких функций в многомерном пространстве (обычно больше 2). Он слишком далёк от реального поиска пути.
А если сделать одну функцию минимума и одну функцию оценки, и искать кратчайший путь по этим двум функциям? Транспортные задачи симплекс-метод решает на ура, самое длинное решение, которое я видел — 20 итераций. Хотя да, возможно, что составление матрицы потребует больше итераций, чем любой из приведенных алгоритмов.
Действительно, в этой статье алгоритмы поиска в графе описаны в больше мере с математической точки зрения, нежели с точки зрения гейм-дева.

В играх поиск пути обычно заканчивается на А* и компании ( IDA, D*, fringe search ) а дальше идут специфичные для представления и топологии карты оптимизации — иерархический поиск, мемоизация, прогрессивное улучшение, адаптивный поиск итп. Если же игра — интерактивная, то найденное решение требует дальнейшей обработки с учетом динамических коллизий, сглаживания и всего остального.

Кстате, стоит упомянуть, что поиск на графе даже в гейм-деве не ограничивается картами. Это так же ИИ, планирование и многое другое.
Кратчайшие пути не только в играх нужны. В связи есть целое направление по проектированию сетей связи с целью получить наиболее оптимальный вариант сети с заданной надёжностью.
Разумеется, но в данном случае автор в самом начале статьи сослался на гейм-дев.
Действительно, просмотрел. Просто у меня был конспект лекций СибГУТИ в электронном виде (набирал когда учился в odt), где вопросы построения сетей связи рассматриваются на уровне графов. Если интересует, могу поискать.
Sign up to leave a comment.

Articles