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