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

Автор: Алексей Моисеев

Предлагаемый алгоритм обхода препятствий - это, так называемый, обобщенный алгоритм Дейкстры. В англоязычной литературе он называется алгоритмом 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.

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

Недавно добавленные исходники
• DeLiKaTeS Tetris (Тетрис) 4 134 • TDictionary Custom Sort 6 207 • Fast Watermark Sources 6 006 • 3D Designer 8 898 • Sik Screen Capture 6 342 • Patch Maker 6 761 • Айболит (remote control) 6 745 • ListBox Drag & Drop 5 617 • Доска для игры Реверси 96 137 • Графические эффекты 6 961 • Рисование по маске 6 230 • Перетаскивание изображений 5 133 • Canvas Drawing 5 502 • Рисование Луны 5 204 • Поворот изображения 4 753 • Рисование стержней 3 362 • Paint on Shape 2 609 • Генератор кроссвордов 3 503 • Головоломка Paletto 2 795 • Теорема Монжа об окружностях 3 603 • Пазл Numbrix 2 365 • Заборы и коммивояжеры 3 046 • Игра HIP 1 999 • Игра Go (Го) 1 923 • Симулятор лифта 2 281 • Программа укладки плитки 1 983 • Генератор лабиринта 2 439 • Проверка числового ввода 2 120 • HEX View 2 455 • Физический маятник 2 076

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

Похожие по теме исходники