prog:

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

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

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

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

Kozinaka:

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

Clamp:

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

Kozinaka:

Эм, нет?

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

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