|
|
Алгоритм поиска пути(А*)
Поиск пути
Каждый программист, когда-нибудь задумывается, а как
сделать, чтобы монстры тупо не бились в стенку, а умели обходить ее,
при этом по самому быстрому пути. Для этого существует целый ряд
алгоритмов, но я вам расскажу только об одном, о самом распространенном
А*(а стар). Суть этого алгоритма заключается в следующем: рис.1 есть
точка А и точка Б, нужно добраться из т. А до т. Б. Самый быстрый путь
указан стрелочками. Так разберемся поподробнее. Поле разбито на
квадраты. Квадрат должен быть размером с самый маленький объект,
который может представлять из себя препятствие. Центр квадрата принято
называть вершиной. У каждого перемещения ест цена, т.е. прямо идти
быстрее чем по диагонали. Цена если идти прямо будет 10, а если по
диагонали то 14(1.414 корень из 2).
Ну что ж давайте перейдем к
практике. Поиск пути начинается перебором соседних клеток А, перебор
идет до тех пор пока не достигнет конечной цели. Все соседние клетки в
данный момент находятся в открытом списке(в открытый список заносятся
точки которые необходимо проверить). Далее мы выбираем одну из соседних
клеток и производим следующее:
1. Проверяем граничащие клетки с
родительской(с начала пути родительской клеткой является т. А), если
они являются препятствием пропускаем их).
2. Добавляем родительскую клетку в закрытый список).
Оценка:
T = стоимость передвижения из стартовой точки к данной клетке
I = примерная стоимость передвижения от данной клетки до целевой.
Стоимость G вычисляется по формуле
G = T+I
T вычисляется путем прибавления к T родительской точки 10 или 14 в зависимости от по диагонали или прямо мы идем.
I
же вычисляется путем подсчета вертикальных и горизонтальных клеток от
начальной точки до конечной и это число умножается на 10. рис2.
Вот алгоритм вычисления пути:
1) Добавляем стартовую точку в открытый список
2) Проверяем следующее:
a) Ищем в открытом списке клетку с наименьшей стоимостью G
b) Помещаем ее в закрытый список и удаляем из открытого
c) Для каждой из соседних клеток(их 8)
• Если клетка не проходима или находится в закрытом списке, игнорируем ее
• Если клетка еще не в открытом списке, то добавляем ее туда
•
Если клетка уже в открытом списке, то проверяем ее дешевизну(дешевил ли
будет путь через эту клетку).Для используем стоимость T, более низкая
стоимость T указывает на более дешевый путь. Если это так то меняем
родительскую клетку на текущую и пересчитываем для нее стоимость T и G.
Если вы сортируете открытый список по стоимости G, то придется
перестроить весь список заново.
d) Останавливаемся если:
• Добавили в открытый список целевую клетку, т.е. путь найден
• Или открытый список пуст и целевая точка не достигнута, т.е. путь не найден.
3) Сохраняем путь. Двигаемся от целевой точки до стартовой через родительские – это и будет наш путь.
Ну, вот в принципе и все. Надеюсь, я помог вам этой статьей.
Другие материалы по теме
|
Категория: Игрострой | Добавил: SilentHill (08/04/08)
|
| Просмотров: 1096
|
Добавлять комментарии могут только зарегистрированные пользователи. [ Регистрация | Вход ]
© 2006-2024 "P-GameStudio".
Сайт оптимизирован под любое разрешение.
Используются технологии uCoz
|
|
|
|
