Алгоритм обхода препятствийDelphi , Графика и Игры , Создание игрАлгоритм обхода препятствий
Оформил: DeeCo Автор: Алексей Моисеев Предлагаемый алгоритм обхода препятствий - это, так называемый, обобщенный алгоритм Дейкстры. В англоязычной литературе он называется алгоритмом A*. Реализация алгоритма: скачать проект (191 К)
Алгоритм этот проще реализовать, чем описать: Start - начальная клеткаFinish - конечная клетка. Алгоритм итерационный 1 шаг: Помечаем Start как граничную точку. 2 шаг: Среди всех граничных точек находим Клетку1 - клетку с минимальной суммой оценки пройденного пути g и оценки оставшегося пути h. 3 шаг: Для Клетки 1 рассматриваем соседей. Если сосед имеет статус непосещенного, то мы обозначаеми его как граничную клетку, и указываем Клетку1 как предыдущую для него. Оценку g1 для соседа принимаем равной g+p, где p-стоимость прохождения по клетке сосед, а g - оценка пройденного пути для Клетки1 . Оценка h для любой клетки равна длине кратчайшего пути (по прямой от рассматриваемой клетки до клетки Finish) Рассматриваемую Клетку1 помечаем как отброшенную. 4 шаг: Если на предыдущем шаге один из соседей оказался равен клетке Finish, то путь найден. Если ни одного нового соседа не существует, то нет и пути. 5 шаг: Переход на шаг 2. Буду рад любым предложениям по оптимизации, так как меня, к сожалению, не устраивает быстродействие. Статья Алгоритм обхода препятствий раздела Графика и Игры Создание игр может быть полезна для разработчиков на delphi & pascal. Комментарии и вопросыМатериалы статей собраны из открытых источников, владелец сайта не претендует на авторство. Там где авторство установить не удалось, материал подаётся без имени автора. В случае если Вы считаете, что Ваши права нарушены, пожалуйста, свяжитесь с владельцем сайта. :: Главная :: Создание игр ::
|
||||
©KANSoftWare (разработка программного обеспечения, создание программ, создание интерактивных сайтов), 2007 |