Приветствие


Проект WebToolGallery представляет собой галерею доступных инструментов для любого человека, который ведет свои блог в сети Интернет. Мы предоставляем, как интересные обзоры шаблонов для Blogger.com и Вордпресс, как и практические советы для любителей Интернет творчества.

среда, 9 июля 2014 г.

Развитие системы игрового дизайна и программирования

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

Поиск пути используется почти для всех жанров игр. Это и игры-бродилки, стратегии реального времени, пошаговые стратегии, action-шутеры, аркады и многие другие. Общая идея использования этих алгоритмов заключается в нахождении оптимального (минимального) пути из одной точки на игровой карте в другую, минуя препятствия.

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

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

Так и в рассматриваемом алгоритме: начиная от начального, пересматриваются все ячейки вокруг, причем:

- Если ячейка пересмотрена ранее, игнорируем ее,

- Если это препятствие, обозначим его как пересмотренную и ту, по которой невозможно пройти,

- Если ячейка ранее не пересматривалась, обозначим ее как пересмотренную и запишем для нее родительскую клетку.

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

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

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

Алгоритм Jump Point Search - это совершенствование алгоритма поиска A *. Был разработан в 2011 году. Он позволяет просматривать не все точки, которые стоят на пути, а проводить "прыжки" через пустые точки без просмотра их. Это позволяет в разы сократить количество итераций в цикле поиска.

Авторы и литературные источники:


Комментариев нет:

Отправить комментарий