Недавно добавленные исходники

•  DeLiKaTeS Tetris (Тетрис)  3 877

•  TDictionary Custom Sort  5 982

•  Fast Watermark Sources  5 771

•  3D Designer  8 587

•  Sik Screen Capture  6 114

•  Patch Maker  6 541

•  Айболит (remote control)  6 535

•  ListBox Drag & Drop  5 400

•  Доска для игры Реверси  95 229

•  Графические эффекты  6 749

•  Рисование по маске  5 910

•  Перетаскивание изображений  4 924

•  Canvas Drawing  5 299

•  Рисование Луны  5 028

•  Поворот изображения  4 570

•  Рисование стержней  3 243

•  Paint on Shape  2 484

•  Генератор кроссвордов  3 367

•  Головоломка Paletto  2 681

•  Теорема Монжа об окружностях  3 450

•  Пазл Numbrix  2 279

•  Заборы и коммивояжеры  2 965

•  Игра HIP  1 929

•  Игра Go (Го)  1 845

•  Симулятор лифта  2 180

•  Программа укладки плитки  1 912

•  Генератор лабиринта  2 350

•  Проверка числового ввода  2 038

•  HEX View  2 358

•  Физический маятник  1 990

 
скрыть

  Форум  

Delphi FAQ - Часто задаваемые вопросы

| Базы данных | Графика и Игры | Интернет и Сети | Компоненты и Классы | Мультимедиа |
| ОС и Железо | Программа и Интерфейс | Рабочий стол | Синтаксис | Технологии | Файловая система |



Delphi Sources

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



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

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

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




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

Генетический Алгоритм

Алгоритм Дейкстры

Алгоритм Беллмана-Форда




Copyright © 2004-2025 "Delphi Sources" by BrokenByte Software. Delphi World FAQ

Группа ВКонтакте