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

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

• Карта разбита на квадратные части, назовем их клетками.
• Каждая клетка имеет несколько показателей:
  1. стоимость прохождения по этой клетке,
  2. предыдущая клетка - клетка из которой пришли в эту клетку,
  3. статус клетки (непосещенная, граничная, отброшенная),
  4. оценка пройденного пути,
  5. оценка оставшегося пути.
• Имеется две клетки - начальная и конечная.
• Сосед клетки - клетка в которую можно попасть из рассматриваемой за 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.