Алексей Моисеев
дата публикации 10-04-2000 00:00 Алгоритм обхода препятствий
Примечание:
Данный материал не является аналитическим, в нем не описываются особенности алгоритма, оценки его эффективности
и т.д.
Автором предоставлен проект реализующий этого алгоритм и краткое пояснение к конкретной реализации.
Елена Филиппова
Предлагаемый алгоритм обхода препятствий - это,
так называемый, обобщенный алгоритм Дейкстры. В англоязычной литературе
он называется алгоритмом A*.
- 1. Карта разбита на квадратные части, назовем их клетками.
- 2. Каждая клетка имеет несколько показателей:
- 1) стоимость прохождения по этой клетке,
- 2) предыдущая клетка - клетка из которой пришли в эту клетку,
- 3) статус клетки (непосещенная, граничная, отброшенная),
- 4) оценка пройденного пути,
- 5) оценка оставшегося пути.
- 3. Имеется две клетки - начальная и конечная.
- 4. Сосед клетки - клетка в которую можно попасть из рассматриваемой за 1 шаг.
Общий принцип: на каждой итерации из всех граничных точек выбирается
та, для которой сумма уже пройденного пути и пути до конца по прямой
является минимальной, и от нее осуществляется дальнейшее продвижение.
Алгоритм этот проще реализовать, чем описать:
Start - начальная клетка
Finish - конечная клетка.
Алгоритм итерационный
1 шаг: Помечаем Start как граничную точку.
2 шаг: Среди всех граничных точек находим Клетку1 - клетку с минимальной
суммой оценки пройденного пути g и оценки оставшегося пути h.
3 шаг: Для Клетки 1 рассматриваем соседей. Если сосед имеет статус
непосещенного, то мы обозначаеми его как граничную клетку, и указываем
Клетку1 как предыдущую для него. Оценку g1 для соседа принимаем равной
g+p, где p-стоимость прохождения по клетке сосед, а g - оценка
пройденного пути для Клетки1 . Оценка h для любой клетки равна длине
кратчайшего пути (по прямой от рассматриваемой клетки до клетки Finish)
Рассматриваемую Клетку1 помечаем как отброшенную.
4 шаг: Если на предыдущем шаге один из соседей оказался равен клетке
Finish, то путь найден. Если ни одного нового соседа не существует, то
нет и пути.
5 шаг: Переход на шаг 2.
Буду рад любым предложениям по оптимизации, так как меня, к сожалению,
не устраивает быстродействие.
К материалу прилагаются файлы:
[Задачи оптимизации] [Программирование игр.]
 Обсуждение материала [ 05-06-2009 03:35 ] 26 сообщений |
