RTS алгоритмы реальных игр

← →
Artem_usb © (2006-03-01 22:44) [0]

Друзья програмеры, на форуме много раз подымалась тема «Поиск кратчайшего пути» и в нете много ресурсов на эту тему. Некоторые говорят что волновой алгоритм самый точный, другой самый быстрый и т.д. И ещё вагон и маленькая тележка способов.
Стратегий в реальном времени, большое кол-во и как я вижу у програмеров нет такой проблемы. К примеру Age of Empires 2-3 или ещё какие ни будь 3D RTS, достаточно быстро юниты находят кротчайший путь вне зависимости от дальности и кол-во юнитов.
Мне нравится волновой метод, 99% точность, но не знаю будет ли он хорош в RTS если
1) Кол-во юнитов более 1000.
2) Просчитанный путь может быть прегражден, другими юнитами или объектами.
3) Пока идет просчет пути, в какую сторону двигаться юниту?
И очень интересно увидеть собственными глазами примеры из
РЕАЛЬНЫХ игр. Или если не сам код, хотя бы, расписанный способ который применен.
Спасибо.

← →
Da Stranger © (2006-03-03 10:50) [1]

Во-первых, советую прочитать в инете все статьи со словом pathfinding. Много интересного есть на dtf.ru, gamasutra.com.
Во-вторых, задача нахождения пути (а за одно определение и предотвращение столкновений) очень специфичная в плане особенности карт. Тут нужно знать, насколько часто будут встречаться препятствия. Если не часто или все они мелкие, то можно строить путь по прямой и обходить все препятствия по дороге. Если часто и препятствия крупнее (типа реки, горы), по нужно строить путь сначала по большой карте, а потом по каждому мелкому участку уточнять путь в тот момент, когда юнит зайдёт на него. Если есть угроза возникновения проблемы "забитого прохода", то создавать специальные теги на картах, а програма должна мониторить состояние каждого прохода и управлять юнитами на них по отдельному алгоритму.

Нужно знать, есть ли деление карты на клетки, насколько резко юнит может затормозить и т.п.

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

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

RTS алгоритмы реальных игр Найти похожие ветки