Статьи Королевства Дельфи

Алгоритм обхода препятствий.


Раздел Подземелье Магов Алексей Моисеев ,
дата публикации 10 апреля 2000 г.

Примечание:
Данный материал не является аналитическим, в нем не описываются особенности алгоритма, оценки его эффективности и т.д.
Автором предоставлен проект реализующий этого алгоритм и краткое пояснение к конкретной реализации.

Елена Филиппова

Предлагаемый алгоритм обхода препятствий - это, так называемый, обобщенный алгоритм Дейкстры. В англоязычной литературе он называется алгоритмом A*.

Реализация алгоритма: (191 К)

  • 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.

    Буду рад любым предложениям по оптимизации, так как меня, к сожалению, не устраивает быстродействие.



  • Содержание раздела