Те кто играли в бета-версию Starcraft 2 наверняка заметили, как изменился алгоритм поиска путей движения юнитов. Многое из сказанного в статье основано на личных оценках. Я не программировал ни BroodWar, ни StarCraft 2 и некоторые выводы будут основаны на моих догадках. Также не верьте на 100% моим словам, постарайтесь сделать собственные заключения. В статье будут как факты, так и домыслы.
Перевод статьи The Mechanics of Starcraft 2 Pathfinding
StarCraft 2 использует алгоритм нахождения путей под названием «flocking» или «swarm AI» (поведение роя, прим. пер.), который пытается скоординировать движение юнитов по типу перемещения косяка рыб или стаи птиц. Очень похоже, что StarCraft 2 использует продвинутый алгоритм, который находит минимальное количество опорных точек и позволяет юнитам независимо проложить гладкий маршрут для обхода препятствий или других юнитов.
С точки зрения достигнутого результата, Blizzard проделал огромную работу над алгоритмом. Конечно это закрытая область и о ней нет подробных сведений. Но факт, что 200 юнитов передвигаются по карте безукоризненно, говорит о том, что алгоритм работает эффективно. На такие технологии тратятся большие силы в игровом комьюнити, и поэтому Blizzard не мог обойти эту проблему стороной. Когда я начал играть в BroodWar, я проводил много времени, пытаясь понять как это работает.
Поиск путей в BroodWar работает немного по другому. На изометрической карте юнит может двигаться только в 8 направлениях и на работу алгоритма не следует тратить много процессорного времени. Поэтому алгоритм поиска маршрутов в этой ситуации может быть основан на алгоритме A* (A-Star — волновой алгоритм) и, глядя на перемещение юнитов, я думаю, это предположение очень близко к истине.
Применение алгоритма A-Star в broodWar
Что видит в этой ситуации игрок
Карта покрыта большим числом узлов, по типу черепицы. Попадая в узел, юнит знает куда двигаться дальше (каждому узлу сопоставлены возможные направления движения), и так далее пока не попадет в место назначения. Узлы через которые прошел юнит становятся опорными точками. Но StarCraft 2 позволяет избежать столкновений за счет обхода других юнитов по маршруту малого радиуса, а в BroodWar юниты соревнуются за узлы. Это главная причина того, почему Вы получаете более лучшее окружение в StarCraft 2, чем в BroodWar, но есть и обратный эффект: юниты разбегаются, когда двигаются навстречу друг другу.
Муталиски выбирают разные опорные точки, если их развернуть на 180 градусов
Попытка смоделировать алгоритм BroodWar, задав большое число ключевых точек
Различие в том, что в BroodWar юниты используют, согласно алгоритму A*, одни и те же ключевые точки, двигаясь шаг за шагом. А в StarCraft 2 для каждого юнита просчитывается отдельный маршрут и используется минимальное количество узлов.
В BroodWar защита от столкновений также более примитивна. Юнит избегает столкновений за счет того, что он останавливается и пропускает другого, или вычисляет новый маршрут движения. В BroodWar при разведке рабочим Вы часто можете увидеть ситуацию, когда один игрок останавливает разведчика своим юнитом, а другой пробует обойти преграду, или оба игрока пытаются задержать таким способом друг друга.
В StarCraft 2 юниты избегают столкновений и обходят препятствия за счет изменения маршрута. Логично предположить, что у каждого юнита есть датчик столкновений, который в нужный момент подаст сигнал обойти препятствие. Это также позволяет юнитам сливаться вместе или наоборот разделяться без вычисления полного нового пути или потери момента движения. В худшем случае, юниты могут проигнорировать радиус столкновения, обеспечивая тем самым более плавное движение и более высокую эффективность движения в общем.
OpenSteer: библиотека с открытым кодом для обхода препятствий
BroodWar'овские зерги решают, кто подбежит первым. А в StarCraft 2 зерги начинают разворачиваться заранее.
Большому числу фанов BroodWar не нравится новый алгоритм, и на то есть причина. Одна из самых эффективных тактик в начале игры — обход и окружение. Но, если юниты врага передвигаются близко друг к другу, то окружение не будет таким эффективным. Зерглинги наносят так много урона маринам, когда они не стоят кучей, потому что марины атакуют на расстоянии, а зерглинги нет. Если Вы уменьшите «площадь поверхности» Вашей армии (например, расположите ее в форме круга), то юниты будут получать куда меньше урона. Соответственно, чем больше размер армии, тем больше и эффект от такой тактики.
Flash vs Effort (OSL 3-ья финальная игра). Марины Flash'а расположены достаточно далеко друг от друга. Поэтому зерглинги, забежавшие с фланга, убили их. Это стоило победу Flash'у
Другой вопрос в том, что в идеале, количество усилий, потраченных на движение юнита должно прямо коррелировать с его эффективностью. Т.е. игроки, которые не контролируют своих юнитов, должны быть за это наказаны. Но похоже, что в Starcraft 2 алгоритм может управлять юнитами лучше, чем игрок, а это означает, что Вы получите обратный эффект от своих действий.
Полагаю, что «неправильное движение» юнита может срывать планы новичков, и для Blizzard нет ничего хуже, чем показать, что игра несовершенна. Я также считаю, что юниты должны разбегаться, когда ими небрежно управляют, и наоборот. Не следует заставлять людей «бороться с интерфейсом», чтобы создать баланс в игре.
От себя добавлю, что с точки зрения математики, Blizzard разработал очень хороший алгоритм. Еще бы они его опубликовали.
Замечание: статья была написана еще до оффициального выхода SC2
Перевод статьи The Mechanics of Starcraft 2 Pathfinding
Поиск маршрута
StarCraft 2 использует алгоритм нахождения путей под названием «flocking» или «swarm AI» (поведение роя, прим. пер.), который пытается скоординировать движение юнитов по типу перемещения косяка рыб или стаи птиц. Очень похоже, что StarCraft 2 использует продвинутый алгоритм, который находит минимальное количество опорных точек и позволяет юнитам независимо проложить гладкий маршрут для обхода препятствий или других юнитов.
С точки зрения достигнутого результата, Blizzard проделал огромную работу над алгоритмом. Конечно это закрытая область и о ней нет подробных сведений. Но факт, что 200 юнитов передвигаются по карте безукоризненно, говорит о том, что алгоритм работает эффективно. На такие технологии тратятся большие силы в игровом комьюнити, и поэтому Blizzard не мог обойти эту проблему стороной. Когда я начал играть в BroodWar, я проводил много времени, пытаясь понять как это работает.
Поиск путей в BroodWar работает немного по другому. На изометрической карте юнит может двигаться только в 8 направлениях и на работу алгоритма не следует тратить много процессорного времени. Поэтому алгоритм поиска маршрутов в этой ситуации может быть основан на алгоритме A* (A-Star — волновой алгоритм) и, глядя на перемещение юнитов, я думаю, это предположение очень близко к истине.
Применение алгоритма A-Star в broodWar
Что видит в этой ситуации игрок
Карта покрыта большим числом узлов, по типу черепицы. Попадая в узел, юнит знает куда двигаться дальше (каждому узлу сопоставлены возможные направления движения), и так далее пока не попадет в место назначения. Узлы через которые прошел юнит становятся опорными точками. Но StarCraft 2 позволяет избежать столкновений за счет обхода других юнитов по маршруту малого радиуса, а в BroodWar юниты соревнуются за узлы. Это главная причина того, почему Вы получаете более лучшее окружение в StarCraft 2, чем в BroodWar, но есть и обратный эффект: юниты разбегаются, когда двигаются навстречу друг другу.
Муталиски выбирают разные опорные точки, если их развернуть на 180 градусов
Попытка смоделировать алгоритм BroodWar, задав большое число ключевых точек
Различие в том, что в BroodWar юниты используют, согласно алгоритму A*, одни и те же ключевые точки, двигаясь шаг за шагом. А в StarCraft 2 для каждого юнита просчитывается отдельный маршрут и используется минимальное количество узлов.
Защита от столкновений
В BroodWar защита от столкновений также более примитивна. Юнит избегает столкновений за счет того, что он останавливается и пропускает другого, или вычисляет новый маршрут движения. В BroodWar при разведке рабочим Вы часто можете увидеть ситуацию, когда один игрок останавливает разведчика своим юнитом, а другой пробует обойти преграду, или оба игрока пытаются задержать таким способом друг друга.
В StarCraft 2 юниты избегают столкновений и обходят препятствия за счет изменения маршрута. Логично предположить, что у каждого юнита есть датчик столкновений, который в нужный момент подаст сигнал обойти препятствие. Это также позволяет юнитам сливаться вместе или наоборот разделяться без вычисления полного нового пути или потери момента движения. В худшем случае, юниты могут проигнорировать радиус столкновения, обеспечивая тем самым более плавное движение и более высокую эффективность движения в общем.
OpenSteer: библиотека с открытым кодом для обхода препятствий
BroodWar'овские зерги решают, кто подбежит первым. А в StarCraft 2 зерги начинают разворачиваться заранее.
Большому числу фанов BroodWar не нравится новый алгоритм, и на то есть причина. Одна из самых эффективных тактик в начале игры — обход и окружение. Но, если юниты врага передвигаются близко друг к другу, то окружение не будет таким эффективным. Зерглинги наносят так много урона маринам, когда они не стоят кучей, потому что марины атакуют на расстоянии, а зерглинги нет. Если Вы уменьшите «площадь поверхности» Вашей армии (например, расположите ее в форме круга), то юниты будут получать куда меньше урона. Соответственно, чем больше размер армии, тем больше и эффект от такой тактики.
Flash vs Effort (OSL 3-ья финальная игра). Марины Flash'а расположены достаточно далеко друг от друга. Поэтому зерглинги, забежавшие с фланга, убили их. Это стоило победу Flash'у
Выводы
Другой вопрос в том, что в идеале, количество усилий, потраченных на движение юнита должно прямо коррелировать с его эффективностью. Т.е. игроки, которые не контролируют своих юнитов, должны быть за это наказаны. Но похоже, что в Starcraft 2 алгоритм может управлять юнитами лучше, чем игрок, а это означает, что Вы получите обратный эффект от своих действий.
Полагаю, что «неправильное движение» юнита может срывать планы новичков, и для Blizzard нет ничего хуже, чем показать, что игра несовершенна. Я также считаю, что юниты должны разбегаться, когда ими небрежно управляют, и наоборот. Не следует заставлять людей «бороться с интерфейсом», чтобы создать баланс в игре.
От себя добавлю, что с точки зрения математики, Blizzard разработал очень хороший алгоритм. Еще бы они его опубликовали.
Замечание: статья была написана еще до оффициального выхода SC2
