Работа в Paradox Interactive

Kozinaka, беру и по результатам плейтестов удаляю какой-нибудь проход, ставлю туда стену, для баланса, например. В результате тебе приходится пересчитывать всю карту и задавать новые значения, а в нормальных играх (давай не будем далеко ходить за примером: SC2 или WC3, или вообще любая игра с редактором) этого делать не надо, только автоматически генерится новая карта проходимости.

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

Kozinaka:

Эм, нет?

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

Clamp:

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

Kozinaka:

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

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

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

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

prog:

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

prog:

Вот это прикольно, кстати! В толпе неизбежно нужно толкаться, а не пути искать, я тоже делал толчки у себя. А тут некоторая надежда организовать этот хаос именно на уровне столкновения пачек. Оффтоп: ретро про жидкости :)

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

Итак. Мой вариант поиска на RTS:
Между точками юзаем лучевой эвристический поиск пути. Он быстро, очень быстро находит все пути. Алгоритм дает разветвление на препятствиях. По оптимистичному сценарию, как вы помните, мы просто берем короткую "руку" и сохраняем.
Но нам нужен кратчайший путь. Мы сохраняем оба результата. Понятно, что на стадии сглаживания, создавая всего по 4 вариации (сгладить левый и правый рукав со следующим левым и правым) пути мы так или иначе найдем, какой рукав короче. Таким образом мы найдем и кратчайший путь. В результате мы получаем относительно быстрый алгоритм без необходимости запекания (немного жертвуем скоростью, но все равно опережаем астар). И это еще без оптимизаций.
Говорю про лучевой алгоритм не с потолка, это самое частое решение для RTS. И есть несколько способов сделать из него "кратчайший" поиск.

GeneralElConsul:

Ошибся, это был не поиск в глубину, там у путей были стоимости и все углублялось в зависимости от стоимости очередного отрезка пути. Естественно, при сколь-нибудь серьезных данных здесь поиск в глубину бы за 4 сек не управился.