у клітку у відкритий список;
Повторюємо наступне:
Шукаємо у відкритому списку клітку з найменшою вартістю F. Робимо її поточної кліткою;
Розміщуємо її в закритий список видаляємо з відкритого;
Для кожної з сусідніх 8-ми клітин:
Якщо клітина непрохідна або вона знаходиться в закритому списку, ігноруємо її. В іншому випадку робимо наступне:
Якщо клітина ще не у відкритому списку, то додаємо її туди. Робимо поточну клітку батьківської для цієї клітини. Розраховуємо вартості F, G і H клітини (пояснення в прикладі);
Якщо клітина вже у відкритому списку, то перевіряємо, чи не дешевше буде шлях в неї через цю клітку. Для порівняння використовуємо вартість G. Більш низька вартість G вказує на те, що шлях буде дешевше. Якщо це так, то міняємо батька клітини на поточну клітку і перераховуємо для неї вартості G і F.
Зупиняємося якщо:
Додали цільову клітку у відкритий список, в цьому випадку шлях знайдений;
Відкритий список порожній і ми не дійшли до цільової клітини. У цьому випадку шлях відсутня;
Зберігаємо шлях. Рухаючись назад від цільової точки, проходячи від кожної точки до її батькові до тих пір, поки не дійдемо до стартової точки. Це і буде шуканий шлях.
ПРИКЛАД
Ініціалізація. Є дві точки, зелена - стартова, червона - кінцева, синя - стіна (непрохідні клітини). Сама область пошуку розділена на сітку з квадратними клітинами, спрощуючи таким чином її до квадратного масиву. Для знаходження шляху необхідно визначити, які клітини потрібно пройти для переміщення з стартовою клітини в кінцеву.
Крок №1. Починаючи зі стартовою клітини, поміщаємо її в «відкритий список» клітин, які необхідно опрацювати. Шукаємо доступні клітини, які межують з поточною, ігноруючи непрохідні клітини. Додаємо знайдені клітини у відкритий список, вказуючи як батька поточну клітку. Видаляємо стартову клітку з відкритого списку, і переносимо на «закритий список».
Темно-зелений квадрат в центрі - стартова точка, виділена блакитним кольором для відображення того, що вона знаходиться в закритому списку, інші клітини зараз знаходяться в білому списку, і мають вказівку на свого батька.
Крок №2. Необхідно вибрати одну з кліток відкритого списку для подальшої обробки, в якості такої вибирається клітина з найменшою вартістю. Вартість шляху Fрассчітивается як сума Gі H. F=G + H, де G-вартість пересування від стартової точки A до даній клітині, по знайденому шляху. H - приблизна вартість пересування від даної клітини до цільової (точці B). Вартість Hрассчітивается за допомогою евристичної (прогнозуючої) функції.
Як описано вище - Gето вартість пересування зі стартовою клітини, до поточної. У цьому прикладі вартість вертикальних і горизонтальних пересування дорівнює 10, а діагональних - 14. Отже, G розраховується як вартість шляху до тієї т?? ЧКЕ, в якій ми зараз знаходимося, плюс 10 у разі горизонтального розташування поточної клітини, щодо батьківської, або 14 у разі діагонального її розташування.
Вартість H можна обчислити безліччю різних способів, найпростішим є метод Манхеттена. Метод Манхеттена полягає в розрахунку шляху загальної кількості клітин до кінцевої по горизонталі і вертикалі, ігноруючи діагональні переміщення і перешкоди. Потім отримане кількість клітин множиться на вартість переміщення по одній клітці - в даному випадку 10.
На следующе малюнку - в кожній клітині відкритого списку записані значення F, Gі H. F- в лівому верхньому кутку, G - в лівому нижньому і H- в правому нижньому. У ортогональних клітин G дорівнює 10, у діагональних - 14.
Відстань H прораховано за допомогою методу Манхеттена, з малюнка видно, що клітина праворуч від стартової без урахування перешкод знаходиться за 3 клітини до кінцевої і має відстань 30. (3 * 10=30). Клітка зверху - 5клеток і відстань 50.
Крок № 3. Для продовження пошуку вибираємо клітку з найменшою вартістю F з усіх клітин, що знаходяться у відкритому списку. Видаляємо її з відкритого списку і додаємо в закритий.
Перевіряємо всі сусідні клітини, ті що знаходяться в закритому списку, а також непрохідні пропускаємо. Решта додаємо у відкритий список, якщо вони там ще не знаходяться, як батька у них буде поточна обрана клітка.
Перераховуємо шляху до сусіднім клітинам, що вже знаходяться у відкритому списку, якщо шлях через поточну клітку менше, то встановлюємо цій клітці батьком поточну, і перераховуємо путьF і G.
