Пошук шляху з точки А в точку Б - одна з найпоширеніших завдань при розробці ігор. Для вирішення цього завдання є безліч алгоритмів, але самим часто використовуваним є A * (A star). Йому і присвячений сьогоднішній пост.
- Створюється 2 списку вершин - очікують розгляду і вже розглянуті. У очікують додається точка старту, список розглянутих поки порожній.
- Для кожної точки розраховується F = G + H. G - відстань від старту до точки, H - приблизну відстань від точки до мети. Про розрахунок цієї величини я розповім пізніше. Так само кожна точка зберігає посилання на точку, з якої в неї прийшли.
- Зі списку точок на розгляд вибирається точка з найменшим F. Позначимо її X.
- Якщо X - мета, то ми знайшли маршрут.
- Переносимо X зі списку чекають на розгляд у список вже розглянутих.
- Для кожної з точок, сусідніх для X (позначимо цю сусідню точку Y), робимо наступне:
- Якщо Y вже знаходиться в розглянутих - пропускаємо її.
- Якщо Y ще немає в списку на очікування - додаємо її туди, запам'ятавши посилання на X і розрахувавши Y.G (це X.G + відстань від X до Y) і Y.H.
- Якщо ж Y в списку на розгляд - перевіряємо, якщо X.G + відстань від X до Y
- Якщо список точок на розгляд порожній, а до мети ми так і не дійшли - значить маршрут не існує.
Функція приблизної оцінки відстані до цілі.
Ця функція повинна виконувати кілька умов:
- Функція ніколи не переоцінює відстань до цілі.
- Для це функції відстані виконується нерівність трикутника. Поясню докладніше: Припустимо, що ми є три точки - A, B і C. Для шляхів A-B B-C і A-C має бути вірно наступне нерівність: A-B + B-C> = A-C.
Реалізація.
Я реалізував алгоритм для прямокутної карти, що складається з клітин.
Для початку створюємо клас точки:
Залишилося додати кілька службових функцій.
Перша з них - функція відстані від X до Y:
Відстань між сусідніми клітинами у мене завжди дорівнює 1.
Функція приблизної оцінки відстані до цілі:
Для оцінки відстані я використовую довжину шляху без перешкод.
Отримання списку сусідів для точки:
Отримання маршруту. Маршрут представлений у вигляді списку координат точок.
Саме для цього ми і зберігали посилання на точку, з якої прийшли.
Щоб переробити алгоритм на інший спосіб представлення точок (наприклад граф відстаней між містами), потрібно переробити отримання сусідів і розрахунок відстаней.
Ось, що в підсумку вийшло:
До речі квадратики вже вміють ходити і битися :-)
Функція приблизної оцінки відстані до цілі:
1
2
3
4private static int GetHeuristicPathLength (Point from, Point to)
return Math.Abs (from.X - to.X) + Math.Abs (from.Y - to.Y);
>
помилочка батенька. мабуть з геометрією зовсім зле. найменший шлях це шлях по прямій
private static int GetHeuristicPathLength (Point from, Point to)
var DeltaX = Math.Abs (from.X - to.X);
var DeltaY = Math.Abs (from.Y - to.Y);
var Dist = Math.sqrt (DeltaX * DeltaX + DeltaY * DeltaY);
а де вихідний код?