Работа в Paradox Interactive

Clamp:

Чем подкреплен авторитет, если не секрет?

darkowlom, тремя с половиной годами на должностях гейм-дизайнера/дизайнера уровней в паре крупных компаний.

Clamp:

Обоснуй пожалуйста! Я как автор одной-единственной, но стратегии (клона первого Starcraft'а) имею противоположный опыт. Я вообще использовал примитивный поиск в ширину, т.к. он никогда не искал в большой зоне, он был нужен только для поиска внутри мелких квадратов карты и для обхода динамических препятствий. Большие пути собирались из заранее рассчитанных. Только так я мог считать пути сразу для большого количества юнитов вне зависимости от расстояние на которое им нужно было переместиться. Проблемой может быть только динамически изменяющийся ландшафт карты, которого в моём случае не было.

Kozinaka:

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

Разумеется, я говорю о более-менее крупных проектах, которые делает команда и которые имеют бюджет в целом.

Clamp, никаких роутов и вейпоинтов. Делишь большую карту на крупные квадраты и рассчитываешь кратчайшие пути между центрами этих квадратов. Пути от каждого квадрата к каждому. Теперь когда тебе нужно найти путь из точки А в точку Б, то ты узнаешь в каком квадрате А, в каком квадрате Б. Путь между этими квадратами у тебя уже рассчитан заранее. Осталось просчитать коротенькие пути до центров этих квадратов и сгладить полученный конгломерат, чтобы естественно смотрелось. Дёшево и сердито. Зависимость времени расчета от длины пути - константа! Пофигу куда искать - в соседний тайл или в противоположный конец карты. Астар, не астар, любой честный проход по сетке не может иметь константную сложность.

Ну вот генерация карты проходимости это предварительный расчет путей это одно и то же считай. У меня это считалось вообще при загрузке уровня.

Kozinaka:

Эм, нет?

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

Clamp:

Давай так: такого не делали в той стратегии, с которой ты работал. И делали в стратегии с которой работал я. Излишние обощения зло.

Kozinaka:

Такое не делают в полноценных RTS. Роут движения КАЖДОГО юнита правильно создавать в тот момент, когда он получает приказ.

Вставлю и я свои пять копеек - у меня тоже был опыт в использовании различных алгоритмов поиска пути в RTS. самую первую я вобще писал на delphi 7 с ручной отрисовкой спрайтов winapi функциями в канвас окна, это было ужасно, но работало на удивление шустро даже с учетом использования модифицированного поиска в ширину для нахождения пути по всей карте. В качестве одной из попыток оптимизации я пытался реализовать описанную Kozinaka идею - разбить карту на большие ячейки и искать пути по ним, а потом досчитывать недостающее. Запоролся этот подход когда я столкнулся с тем, что большая ячейка не всегда гарантированно проходима насквозь - может случиться так, что из центра большой ячейки до цели можно добраться за пару шагов, но юнит находится за стеной, проходящей через пол карты и обход к центру затронет множество других ячеек. Еще хуже это работает в динамически изменяемом окружении - маршрут и так приходится постоянно корректировать, а тут еще и добавляется необходимость постоянно пересчитывать связи между большими ячейками.

В итоге в тот раз я реализовал другие способы "оптимизации" - общее вычисление маршрута для группы юнитов при отдаче приказа вместо индивидуального плюс кеширование недавних вычисленных маршрутов и приоритет на поиск маршрута вдоль них, если они ведут в подходящем направлении.

С тех пор времени прошло изрядно и я попробовал множество разных способов, в том числе построение геолокационной карты, состоящей из участков гарантированной однородной проходимости с последующим поиском пути по ней. Тоже не идеальный способ - дороговато выходит пересчитывать триангуляцию при движении юнитов, а не только при строительстве и разрушении стационарных объектов вроде зданий, а без этого приходится изощряться чтобы корректно обработать невозможность проходить через движущиеся объекты, особенно когда дело доходит до большого кол-ва движущихся объектов в одном месте - приходится посылать лесом поиск пути и полностью отдавать контроль над движением другим системам. Последнее что я обдумывал в этой сфере было посвящено тому, не выйдет ли такие ситуации разрулить с помощью алгоритмов симуляции жидкостей. Даже запилил себе небольшую демку, в которой трактор легко расталкивал небольшую групку пехоты, застревал в средней, а большая толпа пехоты выносила его на руках на противоположный конец карты (концепции атаки в демке не было, только движение).