Комментарии 55
Отличная пища для размышлений, спасибо!
В старкрафте юниты не заезжают друг на друга, но ходят группками, при этом они расталкивают друг другжку.
Должен заметить, что всё же в старкрафте есть редкие случаи, когда юнитам разрешается проходить сквозь друг друга, см. mineral walk.
расталкивать научились только во второй части, в первой части вроде только строители могли расталкивать
если Вы попытаетесь перевести 10-12 драгунов через рампу одним кликом, то картина будет примерно та же, что и в начале статьи
И через минут 5ть вы обнаружите, что половина так и не дошла :)
Гуны это был особый скил
Гуны это был особый скил
В старкрафте это приемлемо и допустимо.
1) Это игра про микроконтроль. Подавляющее большинство GML вытаскивают катки через микро.
2) Блокирование проходов юнитами часть игры. В том числе и карты создаются так, чтобы это блокирование было возможно.
1) Это игра про микроконтроль. Подавляющее большинство GML вытаскивают катки через микро.
2) Блокирование проходов юнитами часть игры. В том числе и карты создаются так, чтобы это блокирование было возможно.
Спасибо за статью, было неожиданно узнать, что задача поиска маршрута не такая тривиальная, как я о ней привык думать с позиции игрока. Могу ли я у вас спросить, знакомы ли вы с пасфайндингом старкрафт2, если да, то можете ли как-то прокомментировать его сходства и различия с вашим методом?
Там steering behaviour.
Это набор техник поведенческих, часть из которых сильно похожа на то о чем я рассказываю в статье.
Наверно нет смысла пересказывать здесь краткое содержание, термин легко гуглится.
Но вообще можно найти годную статью и перевести. Я подумаю.
Стоит учитывать, что старкрафт 2 с точки зрения перемещения юнитов не совсем честное 3Д. Там двумерная сеткая работает. Это решение идеально подходит для старика, но его нельзя назвать универсальным.
Это набор техник поведенческих, часть из которых сильно похожа на то о чем я рассказываю в статье.
Наверно нет смысла пересказывать здесь краткое содержание, термин легко гуглится.
Но вообще можно найти годную статью и перевести. Я подумаю.
Стоит учитывать, что старкрафт 2 с точки зрения перемещения юнитов не совсем честное 3Д. Там двумерная сеткая работает. Это решение идеально подходит для старика, но его нельзя назвать универсальным.
Всё-таки старкрафт это стратегия, а не соревнование в точности кликов, поэтому во втором старкрафте такое поведение сочли багом и исправили.
В первом старкрафте это было допустимо, но по совершенно другой причине — первый старкрафт создавался в то время, когда возможность обвести "рамочкой" несколько юнитов и отдать им общий приказ уже считалась чем-то крутым.
Вы матчи GML смотрели хоть разок? 90% победы это не лажать в билд-ордере и микрить. Оддна из самых микрозависимых игр. Через идеальное макро с плохим микро на уровне GML не побеждает никто. Ошибки в макро гасят через идеальное микро постоянно.
Смотрел я эти матчи, смотрел. В частности, много раз видел ситуацию, когда юниты отправлялись на другую базу через две рампы "вслепую" (по миникарте). И ведь как-то доходили!
Там микроконтролем считается нечто более умное, чем перевод драгунов через рампу по-одному. Более того, именно благодаря тому что каждому юниту в отдельности большую часть времени индивидуальная "нянька" не требуется — эти самые чудеса микроконтроля и становятся возможны.
Приходит в голову ещё 4-ый вариант: попросить стоячий юнит освободить дорогу. Передать ему прямую, с которой было бы неплохо уйти, и если он может — уходит и после проезда первым юнитом определённой точки возвращается назад.
Много частных случаев, и большой риск что будет как в Red Alert 2 с застревающими юнитами при движении большой толпой, когда непонятно кто кого и куда должен пропускать.
Идея про «долженг пропускать» начинает очень сильно обрастать костылями, если юнитов больше двух.
Идея про «долженг пропускать» начинает очень сильно обрастать костылями, если юнитов больше двух.
Стоячие юниты — должны пропускать. Идущие — должны идти как шли.
Что значит «стоячий должен пропускать»?
Отодвигаться в сторону?
Игроки терпеть не могут, когда снначала очень аккуратно расставляют линию обороны, чуть ли не пиксель перфектно выставляя каждый юнит, а потом проезжает подкрепление из тыла и оборона разъезжается во все стороны покидая идеально выставленные позиции,
В итоге игрок либо не может рулить ситуацией на фронте, потому что восстанавливает оборону, либо оставляет оборону в раздрае, потому что занят на фронте.
Итог один: фрустрация.
Только не надо предлагать вариант: юнит пропустивший потом возвращается на позицию.
Во первых никакого пиксель перфектного возврата у нас не будет, реализовать идеальное занятие указанной позиции для колесной техники тоже нетривиальная задача.
Во вторых во время возврата юниты которые возвращаются позиции тоже будут конфликтовать друг с другом.
Отодвигаться в сторону?
Игроки терпеть не могут, когда снначала очень аккуратно расставляют линию обороны, чуть ли не пиксель перфектно выставляя каждый юнит, а потом проезжает подкрепление из тыла и оборона разъезжается во все стороны покидая идеально выставленные позиции,
В итоге игрок либо не может рулить ситуацией на фронте, потому что восстанавливает оборону, либо оставляет оборону в раздрае, потому что занят на фронте.
Итог один: фрустрация.
Только не надо предлагать вариант: юнит пропустивший потом возвращается на позицию.
Во первых никакого пиксель перфектного возврата у нас не будет, реализовать идеальное занятие указанной позиции для колесной техники тоже нетривиальная задача.
Во вторых во время возврата юниты которые возвращаются позиции тоже будут конфликтовать друг с другом.
Игроки терпеть не могут, когда снначала очень аккуратно расставляют линию обороны, чуть ли не пиксель перфектно выставляя каждый юнит, а потом проезжает подкрепление из тыла и оборона разъезжается во все стороны покидая идеально выставленные позиции,
Ну так есть же команда "Держать позицию", она же "Hold". Разумеется, юнит который удерживает позицию никого пропускать не должен.
И что тогда должно происходить?
Ничего, юнит должен останавливаться. Не зря в большей части комментов приводят в пример SC2 — pathfinding там близок к идеальному. И там именно так: юнит на hold не пропустит, без — пропустит.
В старкрафте патчфайндинг действительно близко к идеалу.
Это в целом самая близкая к идеалу РТС. За счет изначального очень хорошего качества и последующей многолетней полировке.
Но есть нюанс. Решения используемые в старкрафте не универсальны.
Если мы уходим в сторону(причем куда идти не так важно), начинаются нюансы.
P.S.
Ну и кстати в старкрафте юнит не останавливается, а пытается найти альтернативный маршрут. Да и костыль в виде минералвока никто не отменял(хотя костыль это или намеренно реализованная фишка — не возьмусь утверждать).
Это в целом самая близкая к идеалу РТС. За счет изначального очень хорошего качества и последующей многолетней полировке.
Но есть нюанс. Решения используемые в старкрафте не универсальны.
Если мы уходим в сторону(причем куда идти не так важно), начинаются нюансы.
P.S.
Ну и кстати в старкрафте юнит не останавливается, а пытается найти альтернативный маршрут. Да и костыль в виде минералвока никто не отменял(хотя костыль это или намеренно реализованная фишка — не возьмусь утверждать).
Это зависит от того, могут ли юниты поворачиваться на месте. Если да — проблемы нет. Если нет — тогда да, это крайне нетривиально.
конечно условия задачи не принято обсуждать, но можете пояснить почему отдельным юнитам нельзя пропускать другие в ожидании?
Третий случай: — по-моему довольно частНый, чтобы ставить запрет на ожидание для всех локаций.
Третий случай: — по-моему довольно частНый, чтобы ставить запрет на ожидание для всех локаций.
Как решать кто кого должен ждать?
Как быть в ситуации когда встречаются два юнита принадлежащих разным сторонам? Допустимо ли, чтобы юнит одной стороны мог как-то влиять на движение юнита с другой стороны?
В данном случае условие задачи: сделать максимлаьно адеватное движение юнитов.
Соответственно то о чем вы говорите не противоречит постановке задачи.
Вопрос в том как это сделать и как учексть все нюансы?
Потому что утрированно решение можно свести к: «юнит должен находить обходной путь когда нет возможности проехать напрямую и должен договариваться с другими юнитами для установки приоритета движения».
Вот только это решение реализовать совершенно непонятно как.
Как быть в ситуации когда встречаются два юнита принадлежащих разным сторонам? Допустимо ли, чтобы юнит одной стороны мог как-то влиять на движение юнита с другой стороны?
В данном случае условие задачи: сделать максимлаьно адеватное движение юнитов.
Соответственно то о чем вы говорите не противоречит постановке задачи.
Вопрос в том как это сделать и как учексть все нюансы?
Потому что утрированно решение можно свести к: «юнит должен находить обходной путь когда нет возможности проехать напрямую и должен договариваться с другими юнитами для установки приоритета движения».
Вот только это решение реализовать совершенно непонятно как.
В данном случае условие задачи: сделать максимлаьно адеватное движение юнитов.
Ну так максимально адекватное движение-то у вас и не получилось...
Верно. Я и не говорил что получилось, я говорил что стояла такая задача.
Предложение «надо пропускать» не противоречит задаче, но и само по себе решения не дает.
Надо пропускать? Окей. Как?
Предложение «надо пропускать» не противоречит задаче, но и само по себе решения не дает.
Надо пропускать? Окей. Как?
ну кто должен пропускать думаю вопрос чисто технический, если столкновение не конфликт противодействующих сторон.
как вариант помеха справа или тот кто позже оказывается в точке пересечения.
по жизни такие ситуации чаще решаются ожиданием чем пересчетом маршрута.
Р. S. далее не по теме статьи… Для игры тоже может оказаться полезным создать сложности игроку-стратегу, который перемещает юниты без учета специфики локации.
как вариант помеха справа или тот кто позже оказывается в точке пересечения.
по жизни такие ситуации чаще решаются ожиданием чем пересчетом маршрута.
Р. S. далее не по теме статьи… Для игры тоже может оказаться полезным создать сложности игроку-стратегу, который перемещает юниты без учета специфики локации.
вчегда смешило, когда выделяешь много юнитов, командуешь ехать вперед, и кто-то обязательно поедет назад «обогнуть Землю, чтобы зайти с тыла» (с).
Проблема хождения юнитов остро стоит в генералах 2003-го года. Как они там любят стоять и тупить друг на друга, если колонка из техники встретилась с каким-нибудь строителем.
Практически у всех стратегий так или иначе есть проблемы с маневрированием юнитов.
Генералы так вообще одна из первых полноценно 3Д РТС, так что не удивительно что там есть проблемы.
Генералы так вообще одна из первых полноценно 3Д РТС, так что не удивительно что там есть проблемы.
Этот баг встречается и в реале: сколько лет живу напротив воинской части, самой реалистичной моделью движения является тот самый мёртвый упор, только там соответствующий звуковой фон.
А что по поводу микроконтроля юнитов в данном случае? Вариант WC3 был плохо реализован?
>> Каждое динамическое препятствие (юнит) записывает в сетку в своём положении окружность с меняющимся значением от 1 до 0…
А вы пробовали записывать не окружность, а «визуальную проекцию» объекта?
Выглядит так, что вычислений у вас и так достаточно, но можно было бы приблизить физ.движок к его графическому отображению.
А вы пробовали записывать не окружность, а «визуальную проекцию» объекта?
Выглядит так, что вычислений у вас и так достаточно, но можно было бы приблизить физ.движок к его графическому отображению.
Для поля потенциалов это не имеет смысла. Даже наоборот скорее вредно, потому что по сфере мы так или иначе можем «соскользнуть» влево или вправо. А на сложной форме можем уткнуться в плоскость и… чего делать? Усложнять алгоритм, чтобы выйти из этой ситуации? А зачем, если мы можем просто окружность сделать и избежать этой проблемы, без каких-либо потерь.
А вот где усложнение формы имеет смысл — это для алгоритма отталкивания. Апроксимация формы юнита несколькими сферами. Это не так сильно влияет на усложние математики отталкивания, зато значительно улучшает ситуацию с расталкиванием юнитами друг друга. Правда в рамках данной реализации я этого не делал в силу того, что большинство юнитов весьма близки к квадратам. Но такая модификация имеет право на обдумывание и существование.
А вот где усложнение формы имеет смысл — это для алгоритма отталкивания. Апроксимация формы юнита несколькими сферами. Это не так сильно влияет на усложние математики отталкивания, зато значительно улучшает ситуацию с расталкиванием юнитами друг друга. Правда в рамках данной реализации я этого не делал в силу того, что большинство юнитов весьма близки к квадратам. Но такая модификация имеет право на обдумывание и существование.
1. >> Для поля потенциалов это не имеет смысла.
2. >> А вот где усложнение формы имеет смысл — это для алгоритма отталкивания.
Ещё как имеет смысл — перекрытие юнитов в «спокойной» обстановке режет глаз.
Но основное — А почему бы эти алгоритмы не совместить?
1. Потенциалы:
Конструируете поле максимальной интенсивности по периметру объекта. Потом, по тем же правилам что и для окружности, рассчитываем потенциал поля (можно закэшировать пред-рассчёты для разных углов поворота).
2. Отталкивание:
В качестве отталкивания выбираем вектор, идущий в сторону максимального ослабления поля потенциалов.
2. >> А вот где усложнение формы имеет смысл — это для алгоритма отталкивания.
Ещё как имеет смысл — перекрытие юнитов в «спокойной» обстановке режет глаз.
Но основное — А почему бы эти алгоритмы не совместить?
1. Потенциалы:
Конструируете поле максимальной интенсивности по периметру объекта. Потом, по тем же правилам что и для окружности, рассчитываем потенциал поля (можно закэшировать пред-рассчёты для разных углов поворота).
2. Отталкивание:
В качестве отталкивания выбираем вектор, идущий в сторону максимального ослабления поля потенциалов.
Поле потенциалов никак не спасает от перекрытия в спокойно обстановке. Оно нужно только для выбора траектории объезда. Ничего лучше простого круга там не работает.
Если юниты въехали друг в друга, тут не форма поля сыграла. Поле заведомо больше юнита, изменение формы тут не поможет.
Считать вектор с вычислением где максимальное ослабление поля будет очень дорого.
Текущий алгоритм это всего четыре расчета:
трейс вперед.
трейсы в сторону если первый трейс уперся кудато.
расчет расстояния между сферами
Это вся нагрузка на алгоритм описанный в статье.
А теперь попробуйте добавить сюда свои правки.
Если юниты въехали друг в друга, тут не форма поля сыграла. Поле заведомо больше юнита, изменение формы тут не поможет.
Считать вектор с вычислением где максимальное ослабление поля будет очень дорого.
Текущий алгоритм это всего четыре расчета:
трейс вперед.
трейсы в сторону если первый трейс уперся кудато.
расчет расстояния между сферами
Это вся нагрузка на алгоритм описанный в статье.
А теперь попробуйте добавить сюда свои правки.
>> А теперь попробуйте добавить сюда свои правки.
Добавляем поле потенциалов в «цену» одного шага алгоритма нахождения пути (тут надо подумать как добавлять — локально для движущихся объектов, менее локально для стоящих).
Считаем как выбраться.
Добавляем поле потенциалов в «цену» одного шага алгоритма нахождения пути (тут надо подумать как добавлять — локально для движущихся объектов, менее локально для стоящих).
Считаем как выбраться.
Как считаем то?
Дайте последовательность шагов по расчету.
Дайте последовательность шагов по расчету.
>> Добавляем поле потенциалов в «цену» одного шага алгоритма нахождения пути (тут надо подумать как добавлять — локально для движущихся объектов, менее локально для стоящих).
>> Считаем как выбраться (т.е. производим поиск пути до конечной точки с учётом взвешенных стоимостей прохода)
> Дайте последовательность шагов по расчету.
Не понял что ещё вам нужно уточнить. Расписать алгоритм поиска пути в графе — думаю вы лучше меня их знаете (как минимум знания свежее).
>> Считаем как выбраться (т.е. производим поиск пути до конечной точки с учётом взвешенных стоимостей прохода)
> Дайте последовательность шагов по расчету.
Не понял что ещё вам нужно уточнить. Расписать алгоритм поиска пути в графе — думаю вы лучше меня их знаете (как минимум знания свежее).
То есть вы предлагаете динамически постоянно пересчитывать путь? Ну это точно не вариант.
Это дорого, толпу юнитов более менее адекватно мы не сможем просчитывать. Да и профит не очевиден — т.к. постоянно будет маршрут менятся, что приведет к метанию юнитов в толпе.
Это дорого, толпу юнитов более менее адекватно мы не сможем просчитывать. Да и профит не очевиден — т.к. постоянно будет маршрут менятся, что приведет к метанию юнитов в толпе.
>> То есть вы предлагаете динамически постоянно пересчитывать путь?
В целом да.
Изначальный профит был в не наезжании юнитов друг-на друга углами.
>> Это дорого
Можно не весь путь, а сделать performance- эвристику. И при первичном проссчитывании пути ставть «контрольные точки». А при необходимости перерассчитать путь — перерассчитывать её только до ближайшей контрольной точки.
>> Да и профит не очевиден — т.к. постоянно будет маршрут менятся, что приведет к метанию юнитов в толпе.
Изначальный профит очевиден — не наезжать «неквадратным» объектам друг-на друга.
По вашему же замечанию со сменой путь — ИМХО наоборот. Чем раньше вы обнаружите что путь неплохо бы пересчитать — тем меньше вы потеряете (разумеется граничные случаи, когда тупики самосоздаются — возможны, ну с ними вероятно надо будет побороться).
В целом да.
Изначальный профит был в не наезжании юнитов друг-на друга углами.
>> Это дорого
Можно не весь путь, а сделать performance- эвристику. И при первичном проссчитывании пути ставть «контрольные точки». А при необходимости перерассчитать путь — перерассчитывать её только до ближайшей контрольной точки.
>> Да и профит не очевиден — т.к. постоянно будет маршрут менятся, что приведет к метанию юнитов в толпе.
Изначальный профит очевиден — не наезжать «неквадратным» объектам друг-на друга.
По вашему же замечанию со сменой путь — ИМХО наоборот. Чем раньше вы обнаружите что путь неплохо бы пересчитать — тем меньше вы потеряете (разумеется граничные случаи, когда тупики самосоздаются — возможны, ну с ними вероятно надо будет побороться).
Так у нас создание тупиков — это основной кейс который мы обрабатываем.
Всё остальное разруливается поиском пути.
Всё остальное разруливается поиском пути.
>> разумеется граничные случаи, когда тупики самосоздаются — возможны, ну с ними вероятно надо будет побороться.
Хм разве не очевидно, что имелось в виду, что есть конфигурация, где при разрешении тупика «самосоздаётся» другой тупик. И так циклически \ часто (как с livelock в многопоточном программировании).
Вроде бы у вас в статье нет доказательств, что ваш метод от такого уберегает. Разрешили тупик, а он (в той же конфигурации) снова создался.
ПС
Хотя по-видимому вытянутые объекты ещё долго не научатся хорошо обрабатывать, см следующий коммент, так что даже если потратится на реализацию «отталкивания по всему контуру» — кардинально это не спасёт.
Хм разве не очевидно, что имелось в виду, что есть конфигурация, где при разрешении тупика «самосоздаётся» другой тупик. И так циклически \ часто (как с livelock в многопоточном программировании).
Вроде бы у вас в статье нет доказательств, что ваш метод от такого уберегает. Разрешили тупик, а он (в той же конфигурации) снова создался.
ПС
Хотя по-видимому вытянутые объекты ещё долго не научатся хорошо обрабатывать, см следующий коммент, так что даже если потратится на реализацию «отталкивания по всему контуру» — кардинально это не спасёт.
Вообще я там нашёл ещё одну проблему с «некруглыми» юнитами.
Насколько я понимаю все алгоритмы поиска путей на плоскости (графе некоторого специального частного представления) на такие крайне плохо заточены.
И если для«круглых» ~> «квадратных» квадратных ~> круглых юнитов эта проблема разрешима без замедления и без усложнения рассчётов (но с раздуванием памяти), то для прямоугольных юнитов я пока не вижу как её решать без кратного усложнения алгоритма.
В общем пока получается: или делайте квадратных юнитов или ваши игроки будут «визуально страдать».
Насколько я понимаю все алгоритмы поиска путей на плоскости (графе некоторого специального частного представления) на такие крайне плохо заточены.
И если для
В общем пока получается: или делайте квадратных юнитов или ваши игроки будут «визуально страдать».
Сделайте то же самое для GPU, цены не будет
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Реализация маневрирования юнитов в играх (избегание столкновений)