Знаходження шляху на карті
Знаходження шляху на карті
Тема знаходження шляху на карті хвилює багатьох програмістів ігор (в основному початківців), але навіть бувалі програмісти роблять свої алгоритми не надто мобільними. Тут я описав деякі алгоритми знаходження шляху. Беручи їх за основу можна придумати багато досить просунутих алгоритмів. На жаль ідеального алгоритму не існує і тому заради використання того чи іншого потрібно жертвувати або продуктивністю або тим досить невеликим інтелектом який потрібен для нього.
В іграх досить часто застосовують маршрутний алгоритм (або його модифікації) в силу його простий реалізації і невеликої кількості обчислень. Але він дуже часто не страбативает в складній ігровій ситуації і персонаж починає смикатися з боку в бік тим самим дратуючи гравця (по своєму прикладу в грі StarCraft). Застосовуючи хвильової алгоритм можна домогтися більшого результату, але хвильової алгоритм для використання в іграх вимагає невеликого доопрацювання, адже він не може будувати трасу по діагоналі. Можна поєднати досконалість хвильового і маневреність маршрутного, розглядаючи 8-ми елементну околиця навколо фронту хвилі при побудові траси. Тільки ось обчислень тут поменше, адже номер фронту хвилі вже і є відстань до початкового елемента, значить можна просто вибрати найменший елемент з околиці і просунути трасу в його сторону. Але все ж яким би універсальним хвильової алгоритм ні, єдиний величезний недолік на обличчя - це необхідність великої кількості пам'яті для зберігання допоміжної карти для фронтів хвиль і досить довгий побудова шляху для кожного персонажа. Для менших витрат я особисто використовую вже прораховані карту фронтів хвиль для всіх персонажів, які йдуть в одну точку, тим самим зменшуючи час розрахунку траси для кожного з них.
Хвильовий алгоритм (Алгоритм Лі)
Хвильовий алгоритм є одним з найбільш унікальних алгоритмів трасування. Він дозволяє побудувати трасу (шлях) між двома елементами в будь-якому лабіринті.
З початкового елемента поширюється в 4-х напрямках хвиля (ріс1.). Елемент в який прийшла хвиля утворює фронт волни.На малюнках цифрами позначені номери фронтів хвилі.
Кожен елемент першого фронту хвилі є джерелом вторинної хвилі (рис 2.). Елементи другого фронту хвилі генерують хвилю третього фронту і т.д. Процес триває до тих пір поки не буде досягнутий кінцевий елемент.
На другому етапі будується сама траса. Її побудова здійснюється відповідно до наступних правил:- Рух при побудові траси здійснюється відповідно до обраних пріоритетами.
- При русі від кінцевого елемента до початкового номер фронту хвилі (шляхові координати) повинні зменшаться.
Пріоритети напрямку руху вибираються на стадії розробки. Залежно від того якими задаються ці пріоритети виходять різні траси, АЛЕ довжина траси в будь-якому випадку залишається однією і тією ж.
Переваги хвильового алгоритму в тому, що з його допомогою можна знайти трасу в будь-якому лабіринті і з будь-якою кількістю заборонених елементів (стін). Єдиним недоліком цього алгоритму є, то що при побудові траси потрібен великий обсяг пам'яті.
Приклад використання хвильового алгоритму:
Червоним кольором відзначені заборонені елементи. Сірим кольором траса після дії алгоритму.
А-Початкова точка, В-Кінцева.
Пріоритети руху вліво, вправо, ВГОРУ, ВНИЗ.
Побудова траси ведеться від початкової точки до кінцевої. Пріоритетні напрямки показані зеленими стрілками.
маршрутний алгоритм
Маршрутний алгоритм має два різновиди.- Заснований на обчисленні відстані між точками.
- Заснований на рекурентного співвідношення.
Маршрутний алгоритм отримав свою назву, тому що осухествляет одночасно і формування фронту і прокладання трасси.Істочніком хвилі на кожному кроці є кінцевий елемент ділянки траси прокладеної на попередніх кроках.
Маршрутний алгоритм заснований на обчисленні відстані між точками.
Робота алгоритму починається від початкового елемента. При цьому навколо початкового елемента розглядається 8-ми елементна околиця. Від кожного елемента околиць аж до кінцевого елемента оцінюється довжина шляху. При цьому відстань між точками вичіслется за формулою:
D = | X i -X B | + | Y i -Y B |
де (X i, Y i) - Координати точки околиці. (X В, Y В) - Координати кінцевого елемента.
Таким чином обчислюється вісім значень з яких вибирається мінімальне. Елемент від якого відстань виявилося мінімальним вибирається в якості елемента траси. Навколо нього знову розглядається 8-ми елементна околиця. Процес триває до тих пір поки не буде досягнутий кінцевий елемент. Якщо на шляху зустрічається перешкода у вигляді забороненого елемента, то обхід перешкоди здійснюється виходячи з інтуїції розробника. При цьому задаються напрямки обходу перешкоди.
Маршрутний алгоритм заснований на рекурентного співвідношення.
Маршрутний алгоритм можна побудувати на основі наступного рекурентного співвідношення:
y (x) = 2y (x + h) + y (x + 2h) + d
Де x, y (x) - абсциса і ордината елемента займаного трасою на даному етапі.
(X + h) - ордината елемента займаного трасою на попередньому кроці.
(X + 2h) - ордината елемента віддаленого від обчислюваного на 2 кроки.
h - величина зміни абцісс на кожному кроці.
d (delta) - це функція визначає вид траси. Якщо d = 0 то будується прямолінійна траса, якщо d = const то будується параболічна траса.
Ордината чергового елемента траси обчислюється по рекурентной формулою, а абсциса траси обчислюється за формулою:
Знак "+" або "-" в рекурентной формулою вибирається виходячи з того звідки починається побудова траси, з початкового елемента "+", і відповідно з кінцевого "-".
За цією формулою щоб обчислити 3-й елемент траси необхідно знати два попередніх. Першим елементом є вихідний елемент A (X A, Y A), тоді ордината другого елемента обчислюється за формулою:
Y (X) = Y (X A) + ((Y (X A) -Y (X B)) / (X A -X B)) * h
Якщо на шляху зустрінеться заборонений елемент його обхід здійснюється виходячи з інтуїції розробника.
Головним достоїнством маршрутного алгоритму є простота, а також можливість руху по діагоналі.