Поиск пути в компьютерных играх

FatCat_bot 8.11.2011 - 18:25

Люди, которые любят во всевозможные стратегические ролевые игры онлайн играть, да и вообще – в любые браузерные приложения, наверняка знакомы с таким компьютерным термином, как поиск пути. Этот термин, на английском языке звучащий как Pathfinding, используется в науках информатики и искусственного интеллекта в целом, и означает он поиск оптимального, самого короткого пути соединения двух реальных точек. Звучит понятно, однако как данный термин используется в игровом мире? Расскажем в этом материале.

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

Дело заключается в том, что стратегии в реальном времени зачастую характеризуются очень просторными территориями, ландшафт которых полностью открыт, поэтому нахождение оптимального пути не всегда является сложной задачей. Однако в тех случаях, когда по ландшафту перемещается уже не один персонаж, а сразу несколько юнитов одновременно, возникает потребность в куда более тяжелых и запутанных алгоритмах подсчета оптимального пути с целью избежать так называемых «пробок» на виртуальной карте. Это вам не в шарики и шарики играть онлайн, тут действительно думать и подсчитывать нужно!

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