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

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

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

Kozinaka:

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

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

Clamp:

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

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