Comments 17
Достаточно интересная статься, надо будет как-нибудь применить подобный вариант поиска пути. Спасибо, за перевод.
Мне не удалось запустить в чистом виде метод потенциалов расчета пути на больших картах.
Метод неплохо работает на небольших пространствах, например в замкнутых зонах между горами.
Проход через перевалы этим методом приходится реализовывать хакерскими методами.
Фактически большая карта делится на зоны, где метод работает и нет локальных минимумов (либо они исправлены).
А переход из одной зоны в другую делается другими алгоритмами. Причем зоны надо размечать либо руками, либо придумывать алгоритм автоматического выделения зон с локальными минимумами. И в месте соединения зон ставить временные притягивающие потенциалы.
Мой вывод:
Метод хорош для ближнего взаимодействия, юнитов, гор и т.п. Особенно он удобен для движущихся объектов.
Метод плох для длинного планирования пути из зоны в зону.
Замечание:
Можно было бы испробовать метод потенциалов для планирования переходов из зоны в зону. Руки не дошли.
Метод неплохо работает на небольших пространствах, например в замкнутых зонах между горами.
Проход через перевалы этим методом приходится реализовывать хакерскими методами.
Фактически большая карта делится на зоны, где метод работает и нет локальных минимумов (либо они исправлены).
А переход из одной зоны в другую делается другими алгоритмами. Причем зоны надо размечать либо руками, либо придумывать алгоритм автоматического выделения зон с локальными минимумами. И в месте соединения зон ставить временные притягивающие потенциалы.
Мой вывод:
Метод хорош для ближнего взаимодействия, юнитов, гор и т.п. Особенно он удобен для движущихся объектов.
Метод плох для длинного планирования пути из зоны в зону.
Замечание:
Можно было бы испробовать метод потенциалов для планирования переходов из зоны в зону. Руки не дошли.
В старкрафте используют комбинацию метода потенциальных полей и А*. Вроде бы, выходит неплохо :) На самом деле всё упирается в задачи. Они могут сильно различаться. Может быть этот метод будет хорошо работать, скажем, для летательных аппаратов, где нет преград, кроме других врагов. Сложно сказать у кого как будет использован данный метод.
Окружать врагов, например, очень удобно по этому методу.
>>Метод плох для длинного планирования пути из зоны в зону.
Так он и не предназначен. Можно считать только 8 клеток вокруг, где поле сильнее — туда и идти. Нужен точный поиск пути — А* в руки. Однако, путь могут и перекрыть, а А* — дорогостоящий алгоритм. Представьте, что зерлинги в старкрафте понесутся рассчитывать путь по А* все. Штук 400 сразу.
Тут идёт комплексный подход. Считается один путь по А*, а передвижение считается уже через ПП для каждого юнита, но вот вся масса в целом идет вдоль проложенного одного пути. Тогда и 400 юнитов сразу не станут проблемой.
Окружать врагов, например, очень удобно по этому методу.
>>Метод плох для длинного планирования пути из зоны в зону.
Так он и не предназначен. Можно считать только 8 клеток вокруг, где поле сильнее — туда и идти. Нужен точный поиск пути — А* в руки. Однако, путь могут и перекрыть, а А* — дорогостоящий алгоритм. Представьте, что зерлинги в старкрафте понесутся рассчитывать путь по А* все. Штук 400 сразу.
Тут идёт комплексный подход. Считается один путь по А*, а передвижение считается уже через ПП для каждого юнита, но вот вся масса в целом идет вдоль проложенного одного пути. Тогда и 400 юнитов сразу не станут проблемой.
Утащил в фейсбуг, хорошая статья
Как будет работать данный метод навигации, если юнит находится в глубокой «выемке» в наших условных горах?
Никак, прямо перед заключением написано же…
Если не предпринимать никаких хаков — будет там торчать. Для этого выемки глубокие заливались почти что нулевыми значениями полей.
Можно использовать комбинацию из потенциального метода и обычных методов поиска пути, можно распространять поля с учетом препятствий. Ну а вообще да, недостаток метода.
Использовал похожий метод для ИИ в походовой стратегии (ну, прототипчике). Клетки помечались в плюс если юнит мог походить на клетку, в больший плюс — если мог достать с нее противника и в минус — если противник мог достать в ответ (соответственно если до клетки доставали несколько противников — на ней получался большой штраф). Получилось неплохо, в рамках одного хода действия компьютера были умеренно адекватными, артиллерия вообще вела себя как артиллерия, но гениальностью кремниевый болванчик не блистал. Метод определенно требует тонкой настройки.
Вот здесь очень хорошо показан принцип работы поиска путей визуально.
Но речь идет не совсем о поиске пути. Поиск пути в рамках данной статьи вообще не рассматривается. Для поиска отлично подходит А*. Легкий в реализации и достаточно шустрый. Но, как я и сказал выше, для поведения нескольких сотен юнитов слишком ресурсоёмкий.
Конечная задача одна — найти путь, выполняя некоторые условия, за минимально возможное время. И всегда есть множество нюансов.
В любом случае — задача очень интересная!
В любом случае — задача очень интересная!
Я о другом. А* позволит найти путь, да. Но вот поведение юнитов оно не позволит реализовать. Смотри то же окружение юнитами с максимально безопасного расстояния, например. Тоесть тут нельзя использовать что-то одно.
Использование этой техники должно подкрепляться, разумеется, классическим поиском пути.
Использование этой техники должно подкрепляться, разумеется, классическим поиском пути.
А как конкретно в рамках GameLoop происходит пересчет пути?
ну вот предположим мы стоим в клетке (x,y) и мы решили, что нам надо идти в (x+1,y). Как обрабатыавется когда скорость юнита больше чем одна клетка за фрэйм, а если меньше чем клетка? либо размер клетки обязательно должен быть минимально возможным перемещением и все перемещения должны быть кратны размеру сетки и скорости соответственно должны выбираться соответственно кратными? Фактические юниты всегда перемещаются с какойто своей конечной скоростью.
ну вот предположим мы стоим в клетке (x,y) и мы решили, что нам надо идти в (x+1,y). Как обрабатыавется когда скорость юнита больше чем одна клетка за фрэйм, а если меньше чем клетка? либо размер клетки обязательно должен быть минимально возможным перемещением и все перемещения должны быть кратны размеру сетки и скорости соответственно должны выбираться соответственно кратными? Фактические юниты всегда перемещаются с какойто своей конечной скоростью.
А почему бы ПП не скорректировать проходимым маршрутом? Тогда поиск пути не надо будет пересчитывать для каждого юнита.
Или изначально строить ПП вдоль поиска пути. Для статических карт это будет не очень затратно. И локальных минимумов можно будет избежать.
Ещё можно предусмотреть влияние вражеских юнитов только на клетках без препятствий.
Или изначально строить ПП вдоль поиска пути. Для статических карт это будет не очень затратно. И локальных минимумов можно будет избежать.
Ещё можно предусмотреть влияние вражеских юнитов только на клетках без препятствий.
Sign up to leave a comment.
Использование потенциальных полей в сценарии стратегии реального времени